Sierra Toolkit  Version of the Day
hashtable-common.h
1 // Copyright (c) 2005, Google Inc.
2 // All rights reserved.
3 //
4 // Redistribution and use in source and binary forms, with or without
5 // modification, are permitted provided that the following conditions are
6 // met:
7 //
8 // * Redistributions of source code must retain the above copyright
9 // notice, this list of conditions and the following disclaimer.
10 // * Redistributions in binary form must reproduce the above
11 // copyright notice, this list of conditions and the following disclaimer
12 // in the documentation and/or other materials provided with the
13 // distribution.
14 // * Neither the name of Google Inc. nor the names of its
15 // contributors may be used to endorse or promote products derived from
16 // this software without specific prior written permission.
17 //
18 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 
30 // ---
31 // Author: Giao Nguyen
32 
33 #ifndef UTIL_GTL_HASHTABLE_COMMON_H_
34 #define UTIL_GTL_HASHTABLE_COMMON_H_
35 
36 #include <assert.h>
37 
38 // Settings contains parameters for growing and shrinking the table.
39 // It also packages zero-size functor (ie. hasher).
40 
41 template<typename Key, typename HashFunc,
42  typename SizeType, int HT_MIN_BUCKETS>
43 class sh_hashtable_settings : public HashFunc {
44  public:
45  typedef Key key_type;
46  typedef HashFunc hasher;
47  typedef SizeType size_type;
48 
49  public:
50  sh_hashtable_settings(const hasher& hf,
51  const float ht_occupancy_flt,
52  const float ht_empty_flt)
53  : hasher(hf),
54  enlarge_threshold_(0),
55  shrink_threshold_(0),
56  consider_shrink_(false),
57  use_empty_(false),
58  use_deleted_(false),
59  num_ht_copies_(0) {
60  set_enlarge_factor(ht_occupancy_flt);
61  set_shrink_factor(ht_empty_flt);
62  }
63 
64  size_type hash(const key_type& v) const {
65  return hasher::operator()(v);
66  }
67 
68  float enlarge_factor() const {
69  return enlarge_factor_;
70  }
71  void set_enlarge_factor(float f) {
72  enlarge_factor_ = f;
73  }
74  float shrink_factor() const {
75  return shrink_factor_;
76  }
77  void set_shrink_factor(float f) {
78  shrink_factor_ = f;
79  }
80 
81  size_type enlarge_threshold() const {
82  return enlarge_threshold_;
83  }
84  void set_enlarge_threshold(size_type t) {
85  enlarge_threshold_ = t;
86  }
87  size_type shrink_threshold() const {
88  return shrink_threshold_;
89  }
90  void set_shrink_threshold(size_type t) {
91  shrink_threshold_ = t;
92  }
93 
94  size_type enlarge_size(size_type x) const {
95  return static_cast<size_type>(x * enlarge_factor_);
96  }
97  size_type shrink_size(size_type x) const {
98  return static_cast<size_type>(x * shrink_factor_);
99  }
100 
101  bool consider_shrink() const {
102  return consider_shrink_;
103  }
104  void set_consider_shrink(bool t) {
105  consider_shrink_ = t;
106  }
107 
108  bool use_empty() const {
109  return use_empty_;
110  }
111  void set_use_empty(bool t) {
112  use_empty_ = t;
113  }
114 
115  bool use_deleted() const {
116  return use_deleted_;
117  }
118  void set_use_deleted(bool t) {
119  use_deleted_ = t;
120  }
121 
122  size_type num_ht_copies() const {
123  return static_cast<size_type>(num_ht_copies_);
124  }
125  void inc_num_ht_copies() {
126  ++num_ht_copies_;
127  }
128 
129  // Reset the enlarge and shrink thresholds
130  void reset_thresholds(size_type num_buckets) {
131  set_enlarge_threshold(enlarge_size(num_buckets));
132  set_shrink_threshold(shrink_size(num_buckets));
133  // whatever caused us to reset already considered
134  set_consider_shrink(false);
135  }
136 
137  // Caller is resposible for calling reset_threshold right after
138  // set_resizing_parameters.
139  void set_resizing_parameters(float shrink, float grow) {
140  assert(shrink >= 0.0);
141  assert(grow <= 1.0);
142  if (shrink > grow/2.0f)
143  shrink = grow / 2.0f; // otherwise we thrash hashtable size
144  set_shrink_factor(shrink);
145  set_enlarge_factor(grow);
146  }
147 
148  // This is the smallest size a hashtable can be without being too crowded
149  // If you like, you can give a min #buckets as well as a min #elts
150  size_type min_buckets(size_type num_elts, size_type min_buckets_wanted) {
151  float enlarge = enlarge_factor();
152  size_type sz = HT_MIN_BUCKETS; // min buckets allowed
153  while ( sz < min_buckets_wanted ||
154  num_elts >= static_cast<size_type>(sz * enlarge) ) {
155  // This just prevents overflowing size_type, since sz can exceed
156  // max_size() here.
157  if (static_cast<size_type>(sz * 2) < sz) {
158  throw std::length_error("resize overflow"); // protect against overflow
159  }
160  sz *= 2;
161  }
162  return sz;
163  }
164 
165  private:
166  size_type enlarge_threshold_; // table.size() * enlarge_factor
167  size_type shrink_threshold_; // table.size() * shrink_factor
168  float enlarge_factor_; // how full before resize
169  float shrink_factor_; // how empty before resize
170  // consider_shrink=true if we should try to shrink before next insert
171  bool consider_shrink_;
172  bool use_empty_; // used only by densehashtable, not sparsehashtable
173  bool use_deleted_; // false until delkey has been set
174  // num_ht_copies is a counter incremented every Copy/Move
175  unsigned int num_ht_copies_;
176 };
177 
178 #endif // UTIL_GTL_HASHTABLE_COMMON_H_