include/llvm/ADT/DenseMap.h

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