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