Sierra Toolkit Version of the Day
hashtable-common.h
00001 // Copyright (c) 2005, Google Inc.
00002 // All rights reserved.
00003 //
00004 // Redistribution and use in source and binary forms, with or without
00005 // modification, are permitted provided that the following conditions are
00006 // met:
00007 //
00008 //     * Redistributions of source code must retain the above copyright
00009 // notice, this list of conditions and the following disclaimer.
00010 //     * Redistributions in binary form must reproduce the above
00011 // copyright notice, this list of conditions and the following disclaimer
00012 // in the documentation and/or other materials provided with the
00013 // distribution.
00014 //     * Neither the name of Google Inc. nor the names of its
00015 // contributors may be used to endorse or promote products derived from
00016 // this software without specific prior written permission.
00017 //
00018 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
00019 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
00020 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
00021 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
00022 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
00023 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
00024 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
00025 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
00026 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00027 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
00028 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00029 
00030 // ---
00031 // Author: Giao Nguyen
00032 
00033 #ifndef UTIL_GTL_HASHTABLE_COMMON_H_
00034 #define UTIL_GTL_HASHTABLE_COMMON_H_
00035 
00036 #include <assert.h>
00037 
00038 // Settings contains parameters for growing and shrinking the table.
00039 // It also packages zero-size functor (ie. hasher).
00040 
00041 template<typename Key, typename HashFunc,
00042          typename SizeType, int HT_MIN_BUCKETS>
00043 class sh_hashtable_settings : public HashFunc {
00044  public:
00045   typedef Key key_type;
00046   typedef HashFunc hasher;
00047   typedef SizeType size_type;
00048 
00049  public:
00050   sh_hashtable_settings(const hasher& hf,
00051                         const float ht_occupancy_flt,
00052                         const float ht_empty_flt)
00053       : hasher(hf),
00054         enlarge_threshold_(0),
00055         shrink_threshold_(0),
00056         consider_shrink_(false),
00057         use_empty_(false),
00058         use_deleted_(false),
00059         num_ht_copies_(0) {
00060     set_enlarge_factor(ht_occupancy_flt);
00061     set_shrink_factor(ht_empty_flt);
00062   }
00063 
00064   size_type hash(const key_type& v) const {
00065     return hasher::operator()(v);
00066   }
00067 
00068   float enlarge_factor() const {
00069     return enlarge_factor_;
00070   }
00071   void set_enlarge_factor(float f) {
00072     enlarge_factor_ = f;
00073   }
00074   float shrink_factor() const {
00075     return shrink_factor_;
00076   }
00077   void set_shrink_factor(float f) {
00078     shrink_factor_ = f;
00079   }
00080 
00081   size_type enlarge_threshold() const {
00082     return enlarge_threshold_;
00083   }
00084   void set_enlarge_threshold(size_type t) {
00085     enlarge_threshold_ = t;
00086   }
00087   size_type shrink_threshold() const {
00088     return shrink_threshold_;
00089   }
00090   void set_shrink_threshold(size_type t) {
00091     shrink_threshold_ = t;
00092   }
00093 
00094   size_type enlarge_size(size_type x) const {
00095     return static_cast<size_type>(x * enlarge_factor_);
00096   }
00097   size_type shrink_size(size_type x) const {
00098     return static_cast<size_type>(x * shrink_factor_);
00099   }
00100 
00101   bool consider_shrink() const {
00102     return consider_shrink_;
00103   }
00104   void set_consider_shrink(bool t) {
00105     consider_shrink_ = t;
00106   }
00107 
00108   bool use_empty() const {
00109     return use_empty_;
00110   }
00111   void set_use_empty(bool t) {
00112     use_empty_ = t;
00113   }
00114 
00115   bool use_deleted() const {
00116     return use_deleted_;
00117   }
00118   void set_use_deleted(bool t) {
00119     use_deleted_ = t;
00120   }
00121 
00122   size_type num_ht_copies() const {
00123     return static_cast<size_type>(num_ht_copies_);
00124   }
00125   void inc_num_ht_copies() {
00126     ++num_ht_copies_;
00127   }
00128 
00129   // Reset the enlarge and shrink thresholds
00130   void reset_thresholds(size_type num_buckets) {
00131     set_enlarge_threshold(enlarge_size(num_buckets));
00132     set_shrink_threshold(shrink_size(num_buckets));
00133     // whatever caused us to reset already considered
00134     set_consider_shrink(false);
00135   }
00136 
00137   // Caller is resposible for calling reset_threshold right after
00138   // set_resizing_parameters.
00139   void set_resizing_parameters(float shrink, float grow) {
00140     assert(shrink >= 0.0);
00141     assert(grow <= 1.0);
00142     if (shrink > grow/2.0f)
00143       shrink = grow / 2.0f;     // otherwise we thrash hashtable size
00144     set_shrink_factor(shrink);
00145     set_enlarge_factor(grow);
00146   }
00147 
00148   // This is the smallest size a hashtable can be without being too crowded
00149   // If you like, you can give a min #buckets as well as a min #elts
00150   size_type min_buckets(size_type num_elts, size_type min_buckets_wanted) {
00151     float enlarge = enlarge_factor();
00152     size_type sz = HT_MIN_BUCKETS;             // min buckets allowed
00153     while ( sz < min_buckets_wanted ||
00154             num_elts >= static_cast<size_type>(sz * enlarge) ) {
00155       // This just prevents overflowing size_type, since sz can exceed
00156       // max_size() here.
00157       if (static_cast<size_type>(sz * 2) < sz) {
00158         throw std::length_error("resize overflow");  // protect against overflow
00159       }
00160       sz *= 2;
00161     }
00162     return sz;
00163   }
00164 
00165  private:
00166   size_type enlarge_threshold_;  // table.size() * enlarge_factor
00167   size_type shrink_threshold_;   // table.size() * shrink_factor
00168   float enlarge_factor_;         // how full before resize
00169   float shrink_factor_;          // how empty before resize
00170   // consider_shrink=true if we should try to shrink before next insert
00171   bool consider_shrink_;
00172   bool use_empty_;    // used only by densehashtable, not sparsehashtable
00173   bool use_deleted_;  // false until delkey has been set
00174   // num_ht_copies is a counter incremented every Copy/Move
00175   unsigned int num_ht_copies_;
00176 };
00177 
00178 #endif  // UTIL_GTL_HASHTABLE_COMMON_H_
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines