« 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
| |||||||||||
| 333 | 0 | ▶ | num_elts >= static_cast<size_type>(sz * enlarge) ) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 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
| |||||||||||
| 337 | 0 | ▶ | throw std::length_error("resize overflow"); // protect against overflow | ||||||||
|
Branch: 1 branch
| |||||||||||
| 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_ | ||||||||||