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 was developed by Chris Lattner and is distributed under
   6 // the University of Illinois Open Source 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 <cassert>
  19 #include <utility>
  20
  21 namespace llvm {
  22
  23 template<typename T>
  24 struct DenseMapKeyInfo {
  25   //static inline T getEmptyKey();
  26   //static inline T getTombstoneKey();
  27   //static unsigned getHashValue(const T &Val);
  28   //static bool isPod()
  29 };
  30
  31 // Provide DenseMapKeyInfo for all pointers.
  32 template<typename T>
  33 struct DenseMapKeyInfo<T*> {
  34   static inline T* getEmptyKey() { return (T*)-1; }
  35   static inline T* getTombstoneKey() { return (T*)-2; }
  36   static unsigned getHashValue(const T *PtrVal) {
  37     return (unsigned)((uintptr_t)PtrVal >> 4) ^
  38            (unsigned)((uintptr_t)PtrVal >> 9);
  39   }
  40   static bool isPod() { return true; }
  41 };
  42
  43 template<typename KeyT, typename ValueT,
  44          typename KeyInfoT = DenseMapKeyInfo<KeyT> >
  45 class DenseMapIterator;
  46 template<typename KeyT, typename ValueT,
  47          typename KeyInfoT = DenseMapKeyInfo<KeyT> >
  48 class DenseMapConstIterator;
  49
  50 template<typename KeyT, typename ValueT,
  51          typename KeyInfoT = DenseMapKeyInfo<KeyT> >
  52 class DenseMap {
  53   typedef std::pair<KeyT, ValueT> BucketT;
  54   unsigned NumBuckets;
  55   BucketT *Buckets;
  56
  57   unsigned NumEntries;
  58   unsigned NumTombstones;
  59   DenseMap(const DenseMap &); // not implemented.
  60 public:
  61   explicit DenseMap(unsigned NumInitBuckets = 64) {
  62     init(NumInitBuckets);
  63   }
  64   ~DenseMap() {
  65     const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
  66     for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) {
  67       if (P->first != EmptyKey && P->first != TombstoneKey)
  68         P->second.~ValueT();
  69       P->first.~KeyT();
  70     }
  71     delete[] (char*)Buckets;
  72   }
  73
  74   typedef DenseMapIterator<KeyT, ValueT, KeyInfoT> iterator;
  75   typedef DenseMapConstIterator<KeyT, ValueT, KeyInfoT> const_iterator;
  76   inline iterator begin() {
  77      return iterator(Buckets, Buckets+NumBuckets);
  78   }
  79   inline iterator end() {
  80     return iterator(Buckets+NumBuckets, Buckets+NumBuckets);
  81   }
  82   inline const_iterator begin() const {
  83     return const_iterator(Buckets, Buckets+NumBuckets);
  84   }
  85   inline const_iterator end() const {
  86     return const_iterator(Buckets+NumBuckets, Buckets+NumBuckets);
  87   }
  88
  89   bool empty() const { return NumEntries == 0; }
  90   unsigned size() const { return NumEntries; }
  91
  92   void clear() {
  93     const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
  94     for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) {
  95       if (P->first != EmptyKey && P->first != TombstoneKey) {
  96         P->first = EmptyKey;
  97         P->second.~ValueT();
  98         --NumEntries;
  99       }
 100     }
 101     assert(NumEntries == 0 && "Node count imbalance!");
 102     NumTombstones = 0;
 103   }
 104
 105   /// count - Return true if the specified key is in the map.
 106   bool count(const KeyT &Val) const {
 107     BucketT *TheBucket;
 108     return LookupBucketFor(Val, TheBucket);
 109   }
 110
 111   iterator find(const KeyT &Val) {
 112     BucketT *TheBucket;
 113     if (LookupBucketFor(Val, TheBucket))
 114       return iterator(TheBucket, Buckets+NumBuckets);
 115     return end();
 116   }
 117   const_iterator find(const KeyT &Val) const {
 118     BucketT *TheBucket;
 119     if (LookupBucketFor(Val, TheBucket))
 120       return const_iterator(TheBucket, Buckets+NumBuckets);
 121     return end();
 122   }
 123
 124   bool insert(const std::pair<KeyT, ValueT> &KV) {
 125     BucketT *TheBucket;
 126     if (LookupBucketFor(KV.first, TheBucket))
 127       return false; // Already in map.
 128
 129     // Otherwise, insert the new element.
 130     InsertIntoBucket(KV.first, KV.second, TheBucket);
 131     return true;
 132   }
 133
 134   bool erase(const KeyT &Val) {
 135     BucketT *TheBucket;
 136     if (!LookupBucketFor(Val, TheBucket))
 137       return false; // not in map.
 138
 139     TheBucket->second.~ValueT();
 140     TheBucket->first = getTombstoneKey();
 141     --NumEntries;
 142     ++NumTombstones;
 143     return true;
 144   }
 145   bool erase(iterator I) {
 146     BucketT *TheBucket = &*I;
 147     TheBucket->second.~ValueT();
 148     TheBucket->first = getTombstoneKey();
 149     --NumEntries;
 150     ++NumTombstones;
 151     return true;
 152   }
 153
 154   ValueT &operator[](const KeyT &Key) {
 155     BucketT *TheBucket;
 156     if (LookupBucketFor(Key, TheBucket))
 157       return TheBucket->second;
 158
 159     return InsertIntoBucket(Key, ValueT(), TheBucket)->second;
 160   }
 161
 162 private:
 163   BucketT *InsertIntoBucket(const KeyT &Key, const ValueT &Value,
 164                             BucketT *TheBucket) {
 165     // If the load of the hash table is more than 3/4, or if fewer than 1/8 of
 166     // the buckets are empty (meaning that many are filled with tombstones),
 167     // grow the table.
 168     //
 169     // The later case is tricky.  For example, if we had one empty bucket with
 170     // tons of tombstones, failing lookups (e.g. for insertion) would have to
 171     // probe almost the entire table until it found the empty bucket.  If the
 172     // table completely filled with tombstones, no lookup would ever succeed,
 173     // causing infinite loops in lookup.
 174     if (NumEntries*4 >= NumBuckets*3 ||
 175         NumBuckets-(NumEntries+NumTombstones) < NumBuckets/8) {
 176       this->grow();
 177       LookupBucketFor(Key, TheBucket);
 178     }
 179     ++NumEntries;
 180
 181     // If we are writing over a tombstone, remember this.
 182     if (TheBucket->first != getEmptyKey())
 183       --NumTombstones;
 184
 185     TheBucket->first = Key;
 186     new (&TheBucket->second) ValueT(Value);
 187     return TheBucket;
 188   }
 189
 190   static unsigned getHashValue(const KeyT &Val) {
 191     return KeyInfoT::getHashValue(Val);
 192   }
 193   static const KeyT getEmptyKey() {
 194     return KeyInfoT::getEmptyKey();
 195   }
 196   static const KeyT getTombstoneKey() {
 197     return KeyInfoT::getTombstoneKey();
 198   }
 199
 200   /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in
 201   /// FoundBucket.  If the bucket contains the key and a value, this returns
 202   /// true, otherwise it returns a bucket with an empty marker or tombstone and
 203   /// returns false.
 204   bool LookupBucketFor(const KeyT &Val, BucketT *&FoundBucket) const {
 205     unsigned BucketNo = getHashValue(Val);
 206     unsigned ProbeAmt = 1;
 207     BucketT *BucketsPtr = Buckets;
 208
 209     // FoundTombstone - Keep track of whether we find a tombstone while probing.
 210     BucketT *FoundTombstone = 0;
 211     const KeyT EmptyKey = getEmptyKey();
 212     const KeyT TombstoneKey = getTombstoneKey();
 213     assert(Val != EmptyKey && Val != TombstoneKey &&
 214            "Empty/Tombstone value shouldn't be inserted into map!");
 215
 216     while (1) {
 217       BucketT *ThisBucket = BucketsPtr + (BucketNo & (NumBuckets-1));
 218       // Found Val's bucket?  If so, return it.
 219       if (ThisBucket->first == Val) {
 220         FoundBucket = ThisBucket;
 221         return true;
 222       }
 223
 224       // If we found an empty bucket, the key doesn't exist in the set.
 225       // Insert it and return the default value.
 226       if (ThisBucket->first == EmptyKey) {
 227         // If we've already seen a tombstone while probing, fill it in instead
 228         // of the empty bucket we eventually probed to.
 229         if (FoundTombstone) ThisBucket = FoundTombstone;
 230         FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket;
 231         return false;
 232       }
 233
 234       // If this is a tombstone, remember it.  If Val ends up not in the map, we
 235       // prefer to return it than something that would require more probing.
 236       if (ThisBucket->first == TombstoneKey && !FoundTombstone)
 237         FoundTombstone = ThisBucket;  // Remember the first tombstone found.
 238
 239       // Otherwise, it's a hash collision or a tombstone, continue quadratic
 240       // probing.
 241       BucketNo += ProbeAmt++;
 242     }
 243   }
 244
 245   void init(unsigned InitBuckets) {
 246     NumEntries = 0;
 247     NumTombstones = 0;
 248     NumBuckets = InitBuckets;
 249     assert(InitBuckets && (InitBuckets & InitBuckets-1) == 0 &&
 250            "# initial buckets must be a power of two!");
 251     Buckets = (BucketT*)new char[sizeof(BucketT)*InitBuckets];
 252     // Initialize all the keys to EmptyKey.
 253     const KeyT EmptyKey = getEmptyKey();
 254     for (unsigned i = 0; i != InitBuckets; ++i)
 255       new (&Buckets[i].first) KeyT(EmptyKey);
 256   }
 257
 258   void grow() {
 259     unsigned OldNumBuckets = NumBuckets;
 260     BucketT *OldBuckets = Buckets;
 261
 262     // Double the number of buckets.
 263     NumBuckets <<= 1;
 264     NumTombstones = 0;
 265     Buckets = (BucketT*)new char[sizeof(BucketT)*NumBuckets];
 266
 267     // Initialize all the keys to EmptyKey.
 268     const KeyT EmptyKey = getEmptyKey();
 269     for (unsigned i = 0, e = NumBuckets; i != e; ++i)
 270       new (&Buckets[i].first) KeyT(EmptyKey);
 271
 272     // Insert all the old elements.
 273     const KeyT TombstoneKey = getTombstoneKey();
 274     for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) {
 275       if (B->first != EmptyKey && B->first != TombstoneKey) {
 276         // Insert the key/value into the new table.
 277         BucketT *DestBucket;
 278         bool FoundVal = LookupBucketFor(B->first, DestBucket);
 279         FoundVal = FoundVal; // silence warning.
 280         assert(!FoundVal && "Key already in new map?");
 281         DestBucket->first = B->first;
 282         new (&DestBucket->second) ValueT(B->second);
 283
 284         // Free the value.
 285         B->second.~ValueT();
 286       }
 287       B->first.~KeyT();
 288     }
 289
 290     // Free the old table.
 291     delete[] (char*)OldBuckets;
 292   }
 293 };
 294
 295 template<typename KeyT, typename ValueT, typename KeyInfoT>
 296 class DenseMapIterator {
 297   typedef std::pair<KeyT, ValueT> BucketT;
 298 protected:
 299   const BucketT *Ptr, *End;
 300 public:
 301   DenseMapIterator(const BucketT *Pos, const BucketT *E) : Ptr(Pos), End(E) {
 302     AdvancePastEmptyBuckets();
 303   }
 304
 305   std::pair<KeyT, ValueT> &operator*() const {
 306     return *const_cast<BucketT*>(Ptr);
 307   }
 308   std::pair<KeyT, ValueT> *operator->() const {
 309     return const_cast<BucketT*>(Ptr);
 310   }
 311
 312   bool operator==(const DenseMapIterator &RHS) const {
 313     return Ptr == RHS.Ptr;
 314   }
 315   bool operator!=(const DenseMapIterator &RHS) const {
 316     return Ptr != RHS.Ptr;
 317   }
 318
 319   inline DenseMapIterator& operator++() {          // Preincrement
 320     ++Ptr;
 321     AdvancePastEmptyBuckets();
 322     return *this;
 323   }
 324   DenseMapIterator operator++(int) {        // Postincrement
 325     DenseMapIterator tmp = *this; ++*this; return tmp;
 326   }
 327
 328 private:
 329   void AdvancePastEmptyBuckets() {
 330     const KeyT Empty = KeyInfoT::getEmptyKey();
 331     const KeyT Tombstone = KeyInfoT::getTombstoneKey();
 332
 333     while (Ptr != End && (Ptr->first == Empty || Ptr->first == Tombstone))
 334       ++Ptr;
 335   }
 336 };
 337
 338 template<typename KeyT, typename ValueT, typename KeyInfoT>
 339 class DenseMapConstIterator : public DenseMapIterator<KeyT, ValueT, KeyInfoT> {
 340 public:
 341   DenseMapConstIterator(const std::pair<KeyT, ValueT> *Pos,
 342                         const std::pair<KeyT, ValueT> *E)
 343     : DenseMapIterator<KeyT, ValueT, KeyInfoT>(Pos, E) {
 344   }
 345   const std::pair<KeyT, ValueT> &operator*() const {
 346     return *this->Ptr;
 347   }
 348   const std::pair<KeyT, ValueT> *operator->() const {
 349     return this->Ptr;
 350   }
 351 };
 352
 353 } // end namespace llvm
 354
 355 #endif