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