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) const {
 112     BucketT *TheBucket;
 113     if (LookupBucketFor(Val, TheBucket))
 114       return iterator(TheBucket, Buckets+NumBuckets);
 115     return end();
 116   }
 117
 118   bool insert(const std::pair<KeyT, ValueT> &KV) {
 119     BucketT *TheBucket;
 120     if (LookupBucketFor(KV.first, TheBucket))
 121       return false; // Already in map.
 122
 123     // Otherwise, insert the new element.
 124     InsertIntoBucket(KV.first, KV.second, TheBucket);
 125     return true;
 126   }
 127
 128   bool erase(const KeyT &Val) {
 129     BucketT *TheBucket;
 130     if (!LookupBucketFor(Val, TheBucket))
 131       return false; // not in map.
 132
 133     TheBucket->second.~ValueT();
 134     TheBucket->first = getTombstoneKey();
 135     --NumEntries;
 136     ++NumTombstones;
 137     return true;
 138   }
 139   bool erase(iterator I) {
 140     BucketT *TheBucket = &*I;
 141     TheBucket->second.~ValueT();
 142     TheBucket->first = getTombstoneKey();
 143     --NumEntries;
 144     ++NumTombstones;
 145     return true;
 146   }
 147
 148   ValueT &operator[](const KeyT &Key) {
 149     BucketT *TheBucket;
 150     if (LookupBucketFor(Key, TheBucket))
 151       return TheBucket->second;
 152
 153     return InsertIntoBucket(Key, ValueT(), TheBucket)->second;
 154   }
 155
 156 private:
 157   BucketT *InsertIntoBucket(const KeyT &Key, const ValueT &Value,
 158                             BucketT *TheBucket) {
 159     // If the load of the hash table is more than 3/4, or if fewer than 1/8 of
 160     // the buckets are empty (meaning that many are filled with tombstones),
 161     // grow the table.
 162     //
 163     // The later case is tricky.  For example, if we had one empty bucket with
 164     // tons of tombstones, failing lookups (e.g. for insertion) would have to
 165     // probe almost the entire table until it found the empty bucket.  If the
 166     // table completely filled with tombstones, no lookup would ever succeed,
 167     // causing infinite loops in lookup.
 168     if (NumEntries*4 >= NumBuckets*3 ||
 169         NumBuckets-(NumEntries+NumTombstones) < NumBuckets/8) {
 170       this->grow();
 171       LookupBucketFor(Key, TheBucket);
 172     }
 173     ++NumEntries;
 174
 175     // If we are writing over a tombstone, remember this.
 176     if (TheBucket->first != getEmptyKey())
 177       --NumTombstones;
 178
 179     TheBucket->first = Key;
 180     new (&TheBucket->second) ValueT(Value);
 181     return TheBucket;
 182   }
 183
 184   static unsigned getHashValue(const KeyT &Val) {
 185     return KeyInfoT::getHashValue(Val);
 186   }
 187   static const KeyT getEmptyKey() {
 188     return KeyInfoT::getEmptyKey();
 189   }
 190   static const KeyT getTombstoneKey() {
 191     return KeyInfoT::getTombstoneKey();
 192   }
 193
 194   /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in
 195   /// FoundBucket.  If the bucket contains the key and a value, this returns
 196   /// true, otherwise it returns a bucket with an empty marker or tombstone and
 197   /// returns false.
 198   bool LookupBucketFor(const KeyT &Val, BucketT *&FoundBucket) const {
 199     unsigned BucketNo = getHashValue(Val);
 200     unsigned ProbeAmt = 1;
 201     BucketT *BucketsPtr = Buckets;
 202
 203     // FoundTombstone - Keep track of whether we find a tombstone while probing.
 204     BucketT *FoundTombstone = 0;
 205     const KeyT EmptyKey = getEmptyKey();
 206     const KeyT TombstoneKey = getTombstoneKey();
 207     assert(Val != EmptyKey && Val != TombstoneKey &&
 208            "Empty/Tombstone value shouldn't be inserted into map!");
 209
 210     while (1) {
 211       BucketT *ThisBucket = BucketsPtr + (BucketNo & (NumBuckets-1));
 212       // Found Val's bucket?  If so, return it.
 213       if (ThisBucket->first == Val) {
 214         FoundBucket = ThisBucket;
 215         return true;
 216       }
 217
 218       // If we found an empty bucket, the key doesn't exist in the set.
 219       // Insert it and return the default value.
 220       if (ThisBucket->first == EmptyKey) {
 221         // If we've already seen a tombstone while probing, fill it in instead
 222         // of the empty bucket we eventually probed to.
 223         if (FoundTombstone) ThisBucket = FoundTombstone;
 224         FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket;
 225         return false;
 226       }
 227
 228       // If this is a tombstone, remember it.  If Val ends up not in the map, we
 229       // prefer to return it than something that would require more probing.
 230       if (ThisBucket->first == TombstoneKey && !FoundTombstone)
 231         FoundTombstone = ThisBucket;  // Remember the first tombstone found.
 232
 233       // Otherwise, it's a hash collision or a tombstone, continue quadratic
 234       // probing.
 235       BucketNo += ProbeAmt++;
 236     }
 237   }
 238
 239   void init(unsigned InitBuckets) {
 240     NumEntries = 0;
 241     NumTombstones = 0;
 242     NumBuckets = InitBuckets;
 243     assert(InitBuckets && (InitBuckets & InitBuckets-1) == 0 &&
 244            "# initial buckets must be a power of two!");
 245     Buckets = (BucketT*)new char[sizeof(BucketT)*InitBuckets];
 246     // Initialize all the keys to EmptyKey.
 247     const KeyT EmptyKey = getEmptyKey();
 248     for (unsigned i = 0; i != InitBuckets; ++i)
 249       new (&Buckets[i].first) KeyT(EmptyKey);
 250   }
 251
 252   void grow() {
 253     unsigned OldNumBuckets = NumBuckets;
 254     BucketT *OldBuckets = Buckets;
 255
 256     // Double the number of buckets.
 257     NumBuckets <<= 1;
 258     NumTombstones = 0;
 259     Buckets = (BucketT*)new char[sizeof(BucketT)*NumBuckets];
 260
 261     // Initialize all the keys to EmptyKey.
 262     const KeyT EmptyKey = getEmptyKey();
 263     for (unsigned i = 0, e = NumBuckets; i != e; ++i)
 264       new (&Buckets[i].first) KeyT(EmptyKey);
 265
 266     // Insert all the old elements.
 267     const KeyT TombstoneKey = getTombstoneKey();
 268     for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) {
 269       if (B->first != EmptyKey && B->first != TombstoneKey) {
 270         // Insert the key/value into the new table.
 271         BucketT *DestBucket;
 272         bool FoundVal = LookupBucketFor(B->first, DestBucket);
 273         FoundVal = FoundVal; // silence warning.
 274         assert(!FoundVal && "Key already in new map?");
 275         DestBucket->first = B->first;
 276         new (&DestBucket->second) ValueT(B->second);
 277
 278         // Free the value.
 279         B->second.~ValueT();
 280       }
 281       B->first.~KeyT();
 282     }
 283
 284     // Free the old table.
 285     delete[] (char*)OldBuckets;
 286   }
 287 };
 288
 289 template<typename KeyT, typename ValueT, typename KeyInfoT>
 290 class DenseMapIterator {
 291   typedef std::pair<KeyT, ValueT> BucketT;
 292 protected:
 293   const BucketT *Ptr, *End;
 294 public:
 295   DenseMapIterator(const BucketT *Pos, const BucketT *E) : Ptr(Pos), End(E) {
 296     AdvancePastEmptyBuckets();
 297   }
 298
 299   std::pair<KeyT, ValueT> &operator*() const {
 300     return *const_cast<BucketT*>(Ptr);
 301   }
 302   std::pair<KeyT, ValueT> *operator->() const {
 303     return const_cast<BucketT*>(Ptr);
 304   }
 305
 306   bool operator==(const DenseMapIterator &RHS) const {
 307     return Ptr == RHS.Ptr;
 308   }
 309   bool operator!=(const DenseMapIterator &RHS) const {
 310     return Ptr != RHS.Ptr;
 311   }
 312
 313   inline DenseMapIterator& operator++() {          // Preincrement
 314     ++Ptr;
 315     AdvancePastEmptyBuckets();
 316     return *this;
 317   }
 318   DenseMapIterator operator++(int) {        // Postincrement
 319     DenseMapIterator tmp = *this; ++*this; return tmp;
 320   }
 321
 322 private:
 323   void AdvancePastEmptyBuckets() {
 324     const KeyT Empty = KeyInfoT::getEmptyKey();
 325     const KeyT Tombstone = KeyInfoT::getTombstoneKey();
 326
 327     while (Ptr != End && (Ptr->first == Empty || Ptr->first == Tombstone))
 328       ++Ptr;
 329   }
 330 };
 331
 332 template<typename KeyT, typename ValueT, typename KeyInfoT>
 333 class DenseMapConstIterator : public DenseMapIterator<KeyT, ValueT, KeyInfoT> {
 334 public:
 335   DenseMapConstIterator(const std::pair<KeyT, ValueT> *Pos,
 336                         const std::pair<KeyT, ValueT> *E)
 337     : DenseMapIterator<KeyT, ValueT>(Pos, E) {
 338   }
 339   const std::pair<KeyT, ValueT> &operator*() const {
 340     return *this->Ptr;
 341   }
 342   const std::pair<KeyT, ValueT> *operator->() const {
 343     return this->Ptr;
 344   }
 345 };
 346
 347 } // end namespace llvm
 348
 349 #endif