DenseMap.h revision b6bbe6320b4a60b7399eea08426aec834701d514
1//===- llvm/ADT/DenseMap.h - Dense probed hash table ------------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines the DenseMap class. 11// 12//===----------------------------------------------------------------------===// 13 14#ifndef LLVM_ADT_DENSEMAP_H 15#define LLVM_ADT_DENSEMAP_H 16 17#include "llvm/Support/DataTypes.h" 18#include "llvm/Support/MathExtras.h" 19#include <cassert> 20#include <utility> 21 22namespace llvm { 23 24template<typename T> 25struct DenseMapInfo { 26 //static inline T getEmptyKey(); 27 //static inline T getTombstoneKey(); 28 //static unsigned getHashValue(const T &Val); 29 //static bool isEqual(const T &LHS, const T &RHS); 30 //static bool isPod() 31}; 32 33// Provide DenseMapInfo for all pointers. 34template<typename T> 35struct DenseMapInfo<T*> { 36 static inline T* getEmptyKey() { return reinterpret_cast<T*>(-1); } 37 static inline T* getTombstoneKey() { return reinterpret_cast<T*>(-2); } 38 static unsigned getHashValue(const T *PtrVal) { 39 return (unsigned((uintptr_t)PtrVal) >> 4) ^ 40 (unsigned((uintptr_t)PtrVal) >> 9); 41 } 42 static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; } 43 static bool isPod() { return true; } 44}; 45 46// Provide DenseMapInfo for unsigned ints. 47template<> struct DenseMapInfo<uint32_t> { 48 static inline uint32_t getEmptyKey() { return ~0; } 49 static inline uint32_t getTombstoneKey() { return ~0 - 1; } 50 static unsigned getHashValue(const uint32_t& Val) { return Val * 37; } 51 static bool isPod() { return true; } 52 static bool isEqual(const uint32_t& LHS, const uint32_t& RHS) { 53 return LHS == RHS; 54 } 55}; 56 57// Provide DenseMapInfo for all pairs whose members have info. 58template<typename T, typename U> 59struct DenseMapInfo<std::pair<T, U> > { 60 typedef std::pair<T, U> Pair; 61 typedef DenseMapInfo<T> FirstInfo; 62 typedef DenseMapInfo<U> SecondInfo; 63 64 static inline Pair getEmptyKey() { 65 return std::make_pair(FirstInfo::getEmptyKey(), 66 SecondInfo::getEmptyKey()); 67 } 68 static inline Pair getTombstoneKey() { 69 return std::make_pair(FirstInfo::getTombstoneKey(), 70 SecondInfo::getEmptyKey()); 71 } 72 static unsigned getHashValue(const Pair& PairVal) { 73 uint64_t key = (uint64_t)FirstInfo::getHashValue(PairVal.first) << 32 74 | (uint64_t)SecondInfo::getHashValue(PairVal.second); 75 key += ~(key << 32); 76 key ^= (key >> 22); 77 key += ~(key << 13); 78 key ^= (key >> 8); 79 key += (key << 3); 80 key ^= (key >> 15); 81 key += ~(key << 27); 82 key ^= (key >> 31); 83 return (unsigned)key; 84 } 85 static bool isEqual(const Pair& LHS, const Pair& RHS) { return LHS == RHS; } 86 static bool isPod() { return FirstInfo::isPod() && SecondInfo::isPod(); } 87}; 88 89template<typename KeyT, typename ValueT, 90 typename KeyInfoT = DenseMapInfo<KeyT>, 91 typename ValueInfoT = DenseMapInfo<ValueT> > 92class DenseMapIterator; 93template<typename KeyT, typename ValueT, 94 typename KeyInfoT = DenseMapInfo<KeyT>, 95 typename ValueInfoT = DenseMapInfo<ValueT> > 96class DenseMapConstIterator; 97 98template<typename KeyT, typename ValueT, 99 typename KeyInfoT = DenseMapInfo<KeyT>, 100 typename ValueInfoT = DenseMapInfo<ValueT> > 101class DenseMap { 102 typedef std::pair<KeyT, ValueT> BucketT; 103 unsigned NumBuckets; 104 BucketT *Buckets; 105 106 unsigned NumEntries; 107 unsigned NumTombstones; 108public: 109 typedef KeyT key_type; 110 typedef ValueT mapped_type; 111 typedef BucketT value_type; 112 113 DenseMap(const DenseMap& other) { 114 NumBuckets = 0; 115 CopyFrom(other); 116 } 117 118 explicit DenseMap(unsigned NumInitBuckets = 64) { 119 init(NumInitBuckets); 120 } 121 122 ~DenseMap() { 123 const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 124 for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { 125 if (!KeyInfoT::isEqual(P->first, EmptyKey) && 126 !KeyInfoT::isEqual(P->first, TombstoneKey)) 127 P->second.~ValueT(); 128 P->first.~KeyT(); 129 } 130 operator delete(Buckets); 131 } 132 133 typedef DenseMapIterator<KeyT, ValueT, KeyInfoT> iterator; 134 typedef DenseMapConstIterator<KeyT, ValueT, KeyInfoT> const_iterator; 135 inline iterator begin() { 136 return iterator(Buckets, Buckets+NumBuckets); 137 } 138 inline iterator end() { 139 return iterator(Buckets+NumBuckets, Buckets+NumBuckets); 140 } 141 inline const_iterator begin() const { 142 return const_iterator(Buckets, Buckets+NumBuckets); 143 } 144 inline const_iterator end() const { 145 return const_iterator(Buckets+NumBuckets, Buckets+NumBuckets); 146 } 147 148 bool empty() const { return NumEntries == 0; } 149 unsigned size() const { return NumEntries; } 150 151 /// Grow the densemap so that it has at least Size buckets. Does not shrink 152 void resize(size_t Size) { grow(Size); } 153 154 void clear() { 155 // If the capacity of the array is huge, and the # elements used is small, 156 // shrink the array. 157 if (NumEntries * 4 < NumBuckets && NumBuckets > 64) { 158 shrink_and_clear(); 159 return; 160 } 161 162 const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 163 for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { 164 if (!KeyInfoT::isEqual(P->first, EmptyKey)) { 165 if (!KeyInfoT::isEqual(P->first, TombstoneKey)) { 166 P->second.~ValueT(); 167 --NumEntries; 168 } 169 P->first = EmptyKey; 170 } 171 } 172 assert(NumEntries == 0 && "Node count imbalance!"); 173 NumTombstones = 0; 174 } 175 176 /// count - Return true if the specified key is in the map. 177 bool count(const KeyT &Val) const { 178 BucketT *TheBucket; 179 return LookupBucketFor(Val, TheBucket); 180 } 181 182 iterator find(const KeyT &Val) { 183 BucketT *TheBucket; 184 if (LookupBucketFor(Val, TheBucket)) 185 return iterator(TheBucket, Buckets+NumBuckets); 186 return end(); 187 } 188 const_iterator find(const KeyT &Val) const { 189 BucketT *TheBucket; 190 if (LookupBucketFor(Val, TheBucket)) 191 return const_iterator(TheBucket, Buckets+NumBuckets); 192 return end(); 193 } 194 195 /// lookup - Return the entry for the specified key, or a default 196 /// constructed value if no such entry exists. 197 ValueT lookup(const KeyT &Val) const { 198 BucketT *TheBucket; 199 if (LookupBucketFor(Val, TheBucket)) 200 return TheBucket->second; 201 return ValueT(); 202 } 203 204 std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { 205 BucketT *TheBucket; 206 if (LookupBucketFor(KV.first, TheBucket)) 207 return std::make_pair(iterator(TheBucket, Buckets+NumBuckets), 208 false); // Already in map. 209 210 // Otherwise, insert the new element. 211 TheBucket = InsertIntoBucket(KV.first, KV.second, TheBucket); 212 return std::make_pair(iterator(TheBucket, Buckets+NumBuckets), 213 true); 214 } 215 216 /// insert - Range insertion of pairs. 217 template<typename InputIt> 218 void insert(InputIt I, InputIt E) { 219 for (; I != E; ++I) 220 insert(*I); 221 } 222 223 224 bool erase(const KeyT &Val) { 225 BucketT *TheBucket; 226 if (!LookupBucketFor(Val, TheBucket)) 227 return false; // not in map. 228 229 TheBucket->second.~ValueT(); 230 TheBucket->first = getTombstoneKey(); 231 --NumEntries; 232 ++NumTombstones; 233 return true; 234 } 235 bool erase(iterator I) { 236 BucketT *TheBucket = &*I; 237 TheBucket->second.~ValueT(); 238 TheBucket->first = getTombstoneKey(); 239 --NumEntries; 240 ++NumTombstones; 241 return true; 242 } 243 244 value_type& FindAndConstruct(const KeyT &Key) { 245 BucketT *TheBucket; 246 if (LookupBucketFor(Key, TheBucket)) 247 return *TheBucket; 248 249 return *InsertIntoBucket(Key, ValueT(), TheBucket); 250 } 251 252 ValueT &operator[](const KeyT &Key) { 253 return FindAndConstruct(Key).second; 254 } 255 256 DenseMap& operator=(const DenseMap& other) { 257 CopyFrom(other); 258 return *this; 259 } 260 261private: 262 void CopyFrom(const DenseMap& other) { 263 if (NumBuckets != 0 && (!KeyInfoT::isPod() || !ValueInfoT::isPod())) { 264 const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 265 for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { 266 if (!KeyInfoT::isEqual(P->first, EmptyKey) && 267 !KeyInfoT::isEqual(P->first, TombstoneKey)) 268 P->second.~ValueT(); 269 P->first.~KeyT(); 270 } 271 } 272 273 NumEntries = other.NumEntries; 274 NumTombstones = other.NumTombstones; 275 276 if (NumBuckets) 277 operator delete(Buckets); 278 Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT) * 279 other.NumBuckets)); 280 281 if (KeyInfoT::isPod() && ValueInfoT::isPod()) 282 memcpy(Buckets, other.Buckets, other.NumBuckets * sizeof(BucketT)); 283 else 284 for (size_t i = 0; i < other.NumBuckets; ++i) { 285 new (&Buckets[i].first) KeyT(other.Buckets[i].first); 286 if (!KeyInfoT::isEqual(Buckets[i].first, getEmptyKey()) && 287 !KeyInfoT::isEqual(Buckets[i].first, getTombstoneKey())) 288 new (&Buckets[i].second) ValueT(other.Buckets[i].second); 289 } 290 NumBuckets = other.NumBuckets; 291 } 292 293 BucketT *InsertIntoBucket(const KeyT &Key, const ValueT &Value, 294 BucketT *TheBucket) { 295 // If the load of the hash table is more than 3/4, or if fewer than 1/8 of 296 // the buckets are empty (meaning that many are filled with tombstones), 297 // grow the table. 298 // 299 // The later case is tricky. For example, if we had one empty bucket with 300 // tons of tombstones, failing lookups (e.g. for insertion) would have to 301 // probe almost the entire table until it found the empty bucket. If the 302 // table completely filled with tombstones, no lookup would ever succeed, 303 // causing infinite loops in lookup. 304 if (NumEntries*4 >= NumBuckets*3 || 305 NumBuckets-(NumEntries+NumTombstones) < NumBuckets/8) { 306 this->grow(NumBuckets * 2); 307 LookupBucketFor(Key, TheBucket); 308 } 309 ++NumEntries; 310 311 // If we are writing over a tombstone, remember this. 312 if (!KeyInfoT::isEqual(TheBucket->first, getEmptyKey())) 313 --NumTombstones; 314 315 TheBucket->first = Key; 316 new (&TheBucket->second) ValueT(Value); 317 return TheBucket; 318 } 319 320 static unsigned getHashValue(const KeyT &Val) { 321 return KeyInfoT::getHashValue(Val); 322 } 323 static const KeyT getEmptyKey() { 324 return KeyInfoT::getEmptyKey(); 325 } 326 static const KeyT getTombstoneKey() { 327 return KeyInfoT::getTombstoneKey(); 328 } 329 330 /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in 331 /// FoundBucket. If the bucket contains the key and a value, this returns 332 /// true, otherwise it returns a bucket with an empty marker or tombstone and 333 /// returns false. 334 bool LookupBucketFor(const KeyT &Val, BucketT *&FoundBucket) const { 335 unsigned BucketNo = getHashValue(Val); 336 unsigned ProbeAmt = 1; 337 BucketT *BucketsPtr = Buckets; 338 339 // FoundTombstone - Keep track of whether we find a tombstone while probing. 340 BucketT *FoundTombstone = 0; 341 const KeyT EmptyKey = getEmptyKey(); 342 const KeyT TombstoneKey = getTombstoneKey(); 343 assert(!KeyInfoT::isEqual(Val, EmptyKey) && 344 !KeyInfoT::isEqual(Val, TombstoneKey) && 345 "Empty/Tombstone value shouldn't be inserted into map!"); 346 347 while (1) { 348 BucketT *ThisBucket = BucketsPtr + (BucketNo & (NumBuckets-1)); 349 // Found Val's bucket? If so, return it. 350 if (KeyInfoT::isEqual(ThisBucket->first, Val)) { 351 FoundBucket = ThisBucket; 352 return true; 353 } 354 355 // If we found an empty bucket, the key doesn't exist in the set. 356 // Insert it and return the default value. 357 if (KeyInfoT::isEqual(ThisBucket->first, EmptyKey)) { 358 // If we've already seen a tombstone while probing, fill it in instead 359 // of the empty bucket we eventually probed to. 360 if (FoundTombstone) ThisBucket = FoundTombstone; 361 FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket; 362 return false; 363 } 364 365 // If this is a tombstone, remember it. If Val ends up not in the map, we 366 // prefer to return it than something that would require more probing. 367 if (KeyInfoT::isEqual(ThisBucket->first, TombstoneKey) && !FoundTombstone) 368 FoundTombstone = ThisBucket; // Remember the first tombstone found. 369 370 // Otherwise, it's a hash collision or a tombstone, continue quadratic 371 // probing. 372 BucketNo += ProbeAmt++; 373 } 374 } 375 376 void init(unsigned InitBuckets) { 377 NumEntries = 0; 378 NumTombstones = 0; 379 NumBuckets = InitBuckets; 380 assert(InitBuckets && (InitBuckets & (InitBuckets-1)) == 0 && 381 "# initial buckets must be a power of two!"); 382 Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*InitBuckets)); 383 // Initialize all the keys to EmptyKey. 384 const KeyT EmptyKey = getEmptyKey(); 385 for (unsigned i = 0; i != InitBuckets; ++i) 386 new (&Buckets[i].first) KeyT(EmptyKey); 387 } 388 389 void grow(unsigned AtLeast) { 390 unsigned OldNumBuckets = NumBuckets; 391 BucketT *OldBuckets = Buckets; 392 393 // Double the number of buckets. 394 while (NumBuckets <= AtLeast) 395 NumBuckets <<= 1; 396 NumTombstones = 0; 397 Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*NumBuckets)); 398 399 // Initialize all the keys to EmptyKey. 400 const KeyT EmptyKey = getEmptyKey(); 401 for (unsigned i = 0, e = NumBuckets; i != e; ++i) 402 new (&Buckets[i].first) KeyT(EmptyKey); 403 404 // Insert all the old elements. 405 const KeyT TombstoneKey = getTombstoneKey(); 406 for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) { 407 if (!KeyInfoT::isEqual(B->first, EmptyKey) && 408 !KeyInfoT::isEqual(B->first, TombstoneKey)) { 409 // Insert the key/value into the new table. 410 BucketT *DestBucket; 411 bool FoundVal = LookupBucketFor(B->first, DestBucket); 412 FoundVal = FoundVal; // silence warning. 413 assert(!FoundVal && "Key already in new map?"); 414 DestBucket->first = B->first; 415 new (&DestBucket->second) ValueT(B->second); 416 417 // Free the value. 418 B->second.~ValueT(); 419 } 420 B->first.~KeyT(); 421 } 422 423 // Free the old table. 424 operator delete(OldBuckets); 425 } 426 427 void shrink_and_clear() { 428 unsigned OldNumBuckets = NumBuckets; 429 BucketT *OldBuckets = Buckets; 430 431 // Reduce the number of buckets. 432 NumBuckets = NumEntries > 32 ? 1 << (Log2_32_Ceil(NumEntries) + 1) 433 : 64; 434 NumTombstones = 0; 435 Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*NumBuckets)); 436 437 // Initialize all the keys to EmptyKey. 438 const KeyT EmptyKey = getEmptyKey(); 439 for (unsigned i = 0, e = NumBuckets; i != e; ++i) 440 new (&Buckets[i].first) KeyT(EmptyKey); 441 442 // Free the old buckets. 443 const KeyT TombstoneKey = getTombstoneKey(); 444 for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) { 445 if (!KeyInfoT::isEqual(B->first, EmptyKey) && 446 !KeyInfoT::isEqual(B->first, TombstoneKey)) { 447 // Free the value. 448 B->second.~ValueT(); 449 } 450 B->first.~KeyT(); 451 } 452 453 // Free the old table. 454 operator delete(OldBuckets); 455 456 NumEntries = 0; 457 } 458}; 459 460template<typename KeyT, typename ValueT, typename KeyInfoT, typename ValueInfoT> 461class DenseMapIterator { 462 typedef std::pair<KeyT, ValueT> BucketT; 463protected: 464 const BucketT *Ptr, *End; 465public: 466 DenseMapIterator(void) : Ptr(0), End(0) {} 467 468 DenseMapIterator(const BucketT *Pos, const BucketT *E) : Ptr(Pos), End(E) { 469 AdvancePastEmptyBuckets(); 470 } 471 472 std::pair<KeyT, ValueT> &operator*() const { 473 return *const_cast<BucketT*>(Ptr); 474 } 475 std::pair<KeyT, ValueT> *operator->() const { 476 return const_cast<BucketT*>(Ptr); 477 } 478 479 bool operator==(const DenseMapIterator &RHS) const { 480 return Ptr == RHS.Ptr; 481 } 482 bool operator!=(const DenseMapIterator &RHS) const { 483 return Ptr != RHS.Ptr; 484 } 485 486 inline DenseMapIterator& operator++() { // Preincrement 487 ++Ptr; 488 AdvancePastEmptyBuckets(); 489 return *this; 490 } 491 DenseMapIterator operator++(int) { // Postincrement 492 DenseMapIterator tmp = *this; ++*this; return tmp; 493 } 494 495private: 496 void AdvancePastEmptyBuckets() { 497 const KeyT Empty = KeyInfoT::getEmptyKey(); 498 const KeyT Tombstone = KeyInfoT::getTombstoneKey(); 499 500 while (Ptr != End && 501 (KeyInfoT::isEqual(Ptr->first, Empty) || 502 KeyInfoT::isEqual(Ptr->first, Tombstone))) 503 ++Ptr; 504 } 505}; 506 507template<typename KeyT, typename ValueT, typename KeyInfoT, typename ValueInfoT> 508class DenseMapConstIterator : public DenseMapIterator<KeyT, ValueT, KeyInfoT> { 509public: 510 DenseMapConstIterator(void) : DenseMapIterator<KeyT, ValueT, KeyInfoT>() {} 511 DenseMapConstIterator(const std::pair<KeyT, ValueT> *Pos, 512 const std::pair<KeyT, ValueT> *E) 513 : DenseMapIterator<KeyT, ValueT, KeyInfoT>(Pos, E) { 514 } 515 const std::pair<KeyT, ValueT> &operator*() const { 516 return *this->Ptr; 517 } 518 const std::pair<KeyT, ValueT> *operator->() const { 519 return this->Ptr; 520 } 521}; 522 523} // end namespace llvm 524 525#endif 526