sparsehash/internal/hashtable-common.h

filter: Statementstmt 0.0% 0 / 45 Branchbran 0.0% 0 / 8 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 0.0% 0 / 53 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« sparsehash/internal/densehashtable.h ↑ Summary sparsehash/internal/libc_allocator_with_realloc.h »
1 // Copyright (c) 2010, 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 //
32 // Provides classes shared by both sparse and dense hashtable.
33 //
34 // sh_hashtable_settings has parameters for growing and shrinking
35 // a hashtable. It also packages zero-size functor (ie. hasher).
36 //
37 // Other functions and classes provide common code for serializing
38 // and deserializing hashtables to a stream (such as a FILE*).
39  
40 #ifndef UTIL_GTL_HASHTABLE_COMMON_H_
41 #define UTIL_GTL_HASHTABLE_COMMON_H_
42  
43 #include <sparsehash/internal/sparseconfig.h>
44 #include <assert.h>
45 #include <stdio.h>
46 #include <stddef.h> // for size_t
47 #include <iosfwd>
48 #include <stdexcept> // For length_error
49  
50 _START_GOOGLE_NAMESPACE_
51  
52 template <bool> struct SparsehashCompileAssert { };
53 #define SPARSEHASH_COMPILE_ASSERT(expr, msg) \
54 typedef SparsehashCompileAssert<(bool(expr))> msg[bool(expr) ? 1 : -1]
55  
56 namespace sparsehash_internal {
57  
58 // Adaptor methods for reading/writing data from an INPUT or OUPTUT
59 // variable passed to serialize() or unserialize(). For now we
60 // have implemented INPUT/OUTPUT for FILE*, istream*/ostream* (note
61 // they are pointers, unlike typical use), or else a pointer to
62 // something that supports a Read()/Write() method.
63 //
64 // For technical reasons, we implement read_data/write_data in two
65 // stages. The actual work is done in *_data_internal, which takes
66 // the stream argument twice: once as a template type, and once with
67 // normal type information. (We only use the second version.) We do
68 // this because of how C++ picks what function overload to use. If we
69 // implemented this the naive way:
70 // bool read_data(istream* is, const void* data, size_t length);
71 // template<typename T> read_data(T* fp, const void* data, size_t length);
72 // C++ would prefer the second version for every stream type except
73 // istream. However, we want C++ to prefer the first version for
74 // streams that are *subclasses* of istream, such as istringstream.
75 // This is not possible given the way template types are resolved. So
76 // we split the stream argument in two, one of which is templated and
77 // one of which is not. The specialized functions (like the istream
78 // version above) ignore the template arg and use the second, 'type'
79 // arg, getting subclass matching as normal. The 'catch-all'
80 // functions (the second version above) use the template arg to deduce
81 // the type, and use a second, void* arg to achieve the desired
82 // 'catch-all' semantics.
83  
84 // ----- low-level I/O for FILE* ----
85  
86 template<typename Ignored>
87 inline bool read_data_internal(Ignored*, FILE* fp,
88 void* data, size_t length) {
89 return fread(data, length, 1, fp) == 1;
90 }
91  
92 template<typename Ignored>
93 inline bool write_data_internal(Ignored*, FILE* fp,
94 const void* data, size_t length) {
95 return fwrite(data, length, 1, fp) == 1;
96 }
97  
98 // ----- low-level I/O for iostream ----
99  
100 // We want the caller to be responsible for #including <iostream>, not
101 // us, because iostream is a big header! According to the standard,
102 // it's only legal to delay the instantiation the way we want to if
103 // the istream/ostream is a template type. So we jump through hoops.
104 template<typename ISTREAM>
105 inline bool read_data_internal_for_istream(ISTREAM* fp,
106 void* data, size_t length) {
107 return fp->read(reinterpret_cast<char*>(data), length).good();
108 }
109 template<typename Ignored>
110 inline bool read_data_internal(Ignored*, std::istream* fp,
111 void* data, size_t length) {
112 return read_data_internal_for_istream(fp, data, length);
113 }
114  
115 template<typename OSTREAM>
116 inline bool write_data_internal_for_ostream(OSTREAM* fp,
117 const void* data, size_t length) {
118 return fp->write(reinterpret_cast<const char*>(data), length).good();
119 }
120 template<typename Ignored>
121 inline bool write_data_internal(Ignored*, std::ostream* fp,
122 const void* data, size_t length) {
123 return write_data_internal_for_ostream(fp, data, length);
124 }
125  
126 // ----- low-level I/O for custom streams ----
127  
128 // The INPUT type needs to support a Read() method that takes a
129 // buffer and a length and returns the number of bytes read.
130 template <typename INPUT>
131 inline bool read_data_internal(INPUT* fp, void*,
132 void* data, size_t length) {
133 return static_cast<size_t>(fp->Read(data, length)) == length;
134 }
135  
136 // The OUTPUT type needs to support a Write() operation that takes
137 // a buffer and a length and returns the number of bytes written.
138 template <typename OUTPUT>
139 inline bool write_data_internal(OUTPUT* fp, void*,
140 const void* data, size_t length) {
141 return static_cast<size_t>(fp->Write(data, length)) == length;
142 }
143  
144 // ----- low-level I/O: the public API ----
145  
146 template <typename INPUT>
147 inline bool read_data(INPUT* fp, void* data, size_t length) {
148 return read_data_internal(fp, fp, data, length);
149 }
150  
151 template <typename OUTPUT>
152 inline bool write_data(OUTPUT* fp, const void* data, size_t length) {
153 return write_data_internal(fp, fp, data, length);
154 }
155  
156 // Uses read_data() and write_data() to read/write an integer.
157 // length is the number of bytes to read/write (which may differ
158 // from sizeof(IntType), allowing us to save on a 32-bit system
159 // and load on a 64-bit system). Excess bytes are taken to be 0.
160 // INPUT and OUTPUT must match legal inputs to read/write_data (above).
161 template <typename INPUT, typename IntType>
162 bool read_bigendian_number(INPUT* fp, IntType* value, size_t length) {
163 *value = 0;
164 unsigned char byte;
165 // We require IntType to be unsigned or else the shifting gets all screwy.
166 SPARSEHASH_COMPILE_ASSERT(static_cast<IntType>(-1) > static_cast<IntType>(0),
167 serializing_int_requires_an_unsigned_type);
168 for (size_t i = 0; i < length; ++i) {
169 if (!read_data(fp, &byte, sizeof(byte))) return false;
170 *value |= static_cast<IntType>(byte) << ((length - 1 - i) * 8);
171 }
172 return true;
173 }
174  
175 template <typename OUTPUT, typename IntType>
176 bool write_bigendian_number(OUTPUT* fp, IntType value, size_t length) {
177 unsigned char byte;
178 // We require IntType to be unsigned or else the shifting gets all screwy.
179 SPARSEHASH_COMPILE_ASSERT(static_cast<IntType>(-1) > static_cast<IntType>(0),
180 serializing_int_requires_an_unsigned_type);
181 for (size_t i = 0; i < length; ++i) {
182 byte = (sizeof(value) <= length-1 - i)
183 ? 0 : static_cast<unsigned char>((value >> ((length-1 - i) * 8)) & 255);
184 if (!write_data(fp, &byte, sizeof(byte))) return false;
185 }
186 return true;
187 }
188  
189 // If your keys and values are simple enough, you can pass this
190 // serializer to serialize()/unserialize(). "Simple enough" means
191 // value_type is a POD type that contains no pointers. Note,
192 // however, we don't try to normalize endianness.
193 // This is the type used for NopointerSerializer.
194 template <typename value_type> struct pod_serializer {
195 template <typename INPUT>
196 bool operator()(INPUT* fp, value_type* value) const {
197 return read_data(fp, value, sizeof(*value));
198 }
199  
200 template <typename OUTPUT>
201 bool operator()(OUTPUT* fp, const value_type& value) const {
202 return write_data(fp, &value, sizeof(value));
203 }
204 };
205  
206  
207 // Settings contains parameters for growing and shrinking the table.
208 // It also packages zero-size functor (ie. hasher).
209 //
210 // It does some munging of the hash value in cases where we think
211 // (fear) the original hash function might not be very good. In
212 // particular, the default hash of pointers is the identity hash,
213 // so probably all the low bits are 0. We identify when we think
214 // we're hashing a pointer, and chop off the low bits. Note this
215 // isn't perfect: even when the key is a pointer, we can't tell
216 // for sure that the hash is the identity hash. If it's not, this
217 // is needless work (and possibly, though not likely, harmful).
218  
219 template<typename Key, typename HashFunc,
220 typename SizeType, int HT_MIN_BUCKETS>
221 class sh_hashtable_settings : public HashFunc {
222 public:
223 typedef Key key_type;
224 typedef HashFunc hasher;
225 typedef SizeType size_type;
226  
227 public:
228 0 sh_hashtable_settings(const hasher& hf,
229 const float ht_occupancy_flt,
230 const float ht_empty_flt)
231 : hasher(hf),
232 0 enlarge_threshold_(0),
233 0 shrink_threshold_(0),
234 0 consider_shrink_(false),
235 0 use_empty_(false),
236 0 use_deleted_(false),
237 0 num_ht_copies_(0) {
238 0 set_enlarge_factor(ht_occupancy_flt);
239 0 set_shrink_factor(ht_empty_flt);
240 0 }
241  
242 size_type hash(const key_type& v) const {
243 // We munge the hash value when we don't trust hasher::operator().
244 return hash_munger<Key>::MungedHash(hasher::operator()(v));
245 }
246  
247 0 float enlarge_factor() const {
248 0 return enlarge_factor_;
249 }
250 0 void set_enlarge_factor(float f) {
251 0 enlarge_factor_ = f;
252 0 }
253 float shrink_factor() const {
254 return shrink_factor_;
255 }
256 0 void set_shrink_factor(float f) {
257 0 shrink_factor_ = f;
258 0 }
259  
260 size_type enlarge_threshold() const {
261 return enlarge_threshold_;
262 }
263 0 void set_enlarge_threshold(size_type t) {
264 0 enlarge_threshold_ = t;
265 0 }
266 size_type shrink_threshold() const {
267 return shrink_threshold_;
268 }
269 0 void set_shrink_threshold(size_type t) {
270 0 shrink_threshold_ = t;
271 0 }
272  
273 0 size_type enlarge_size(size_type x) const {
274 0 return static_cast<size_type>(x * enlarge_factor_);
275 }
276 0 size_type shrink_size(size_type x) const {
277 0 return static_cast<size_type>(x * shrink_factor_);
278 }
279  
280 bool consider_shrink() const {
281 return consider_shrink_;
282 }
283 0 void set_consider_shrink(bool t) {
284 0 consider_shrink_ = t;
285 0 }
286  
287 bool use_empty() const {
288 return use_empty_;
289 }
290 void set_use_empty(bool t) {
291 use_empty_ = t;
292 }
293  
294 bool use_deleted() const {
295 return use_deleted_;
296 }
297 void set_use_deleted(bool t) {
298 use_deleted_ = t;
299 }
300  
301 size_type num_ht_copies() const {
302 return static_cast<size_type>(num_ht_copies_);
303 }
304 void inc_num_ht_copies() {
305 ++num_ht_copies_;
306 }
307  
308 // Reset the enlarge and shrink thresholds
309 0 void reset_thresholds(size_type num_buckets) {
310 0 set_enlarge_threshold(enlarge_size(num_buckets));
311 0 set_shrink_threshold(shrink_size(num_buckets));
312 // whatever caused us to reset already considered
313 0 set_consider_shrink(false);
314 0 }
315  
316 // Caller is resposible for calling reset_threshold right after
317 // set_resizing_parameters.
318 void set_resizing_parameters(float shrink, float grow) {
319 assert(shrink >= 0.0);
320 assert(grow <= 1.0);
321 if (shrink > grow/2.0f)
322 shrink = grow / 2.0f; // otherwise we thrash hashtable size
323 set_shrink_factor(shrink);
324 set_enlarge_factor(grow);
325 }
326  
327 // This is the smallest size a hashtable can be without being too crowded
328 // If you like, you can give a min #buckets as well as a min #elts
329 0 size_type min_buckets(size_type num_elts, size_type min_buckets_wanted) {
330 0 float enlarge = enlarge_factor();
331 0 size_type sz = HT_MIN_BUCKETS; // min buckets allowed
332 0 ▶ while ( sz < min_buckets_wanted ||
Branch: 1 branch
BranchTrueFalseTotal
while ( sz < min_buckets_wanted || 0 0 0
333 0 ▶ num_elts >= static_cast<size_type>(sz * enlarge) ) {
Branch: 1 branch
BranchTrueFalseTotal
num_elts >= static_cast<size_type>(sz * enlarge) ) { 0 0 0
334 // This just prevents overflowing size_type, since sz can exceed
335 // max_size() here.
336 0 ▶ if (static_cast<size_type>(sz * 2) < sz) {
Branch: 1 branch
BranchTrueFalseTotal
if (static_cast<size_type>(sz * 2) < sz) { 0 0 0
337 0 ▶ throw std::length_error("resize overflow"); // protect against overflow
Branch: 1 branch
BranchTrueFalseTotal
throw std::length_error("resize overflow"); // protect against overflow 0 0 0
338 }
339 0 sz *= 2;
340 }
341 0 return sz;
342 }
343  
344 private:
345 template<class HashKey> class hash_munger {
346 public:
347 static size_t MungedHash(size_t hash) {
348 return hash;
349 }
350 };
351 // This matches when the hashtable key is a pointer.
352 template<class HashKey> class hash_munger<HashKey*> {
353 public:
354 static size_t MungedHash(size_t hash) {
355 // TODO(csilvers): consider rotating instead:
356 // static const int shift = (sizeof(void *) == 4) ? 2 : 3;
357 // return (hash << (sizeof(hash) * 8) - shift)) | (hash >> shift);
358 // This matters if we ever change sparse/dense_hash_* to compare
359 // hashes before comparing actual values. It's speedy on x86.
360 return hash / sizeof(void*); // get rid of known-0 bits
361 }
362 };
363  
364 size_type enlarge_threshold_; // table.size() * enlarge_factor
365 size_type shrink_threshold_; // table.size() * shrink_factor
366 float enlarge_factor_; // how full before resize
367 float shrink_factor_; // how empty before resize
368 // consider_shrink=true if we should try to shrink before next insert
369 bool consider_shrink_;
370 bool use_empty_; // used only by densehashtable, not sparsehashtable
371 bool use_deleted_; // false until delkey has been set
372 // num_ht_copies is a counter incremented every Copy/Move
373 unsigned int num_ht_copies_;
374 };
375  
376 } // namespace sparsehash_internal
377  
378 #undef SPARSEHASH_COMPILE_ASSERT
379 _END_GOOGLE_NAMESPACE_
380  
381 #endif // UTIL_GTL_HASHTABLE_COMMON_H_
« sparsehash/internal/densehashtable.h ↑ Summary sparsehash/internal/libc_allocator_with_realloc.h »