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