LLVM API Documentation

DenseMap.h

Go to the documentation of this file.
00001 //===- llvm/ADT/DenseMap.h - Dense probed hash table ------------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines the DenseMap class.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #ifndef LLVM_ADT_DENSEMAP_H
00015 #define LLVM_ADT_DENSEMAP_H
00016 
00017 #include "llvm/Support/PointerLikeTypeTraits.h"
00018 #include "llvm/Support/MathExtras.h"
00019 #include "llvm/ADT/DenseMapInfo.h"
00020 #include <cassert>
00021 #include <cstring>
00022 #include <utility>
00023 #include <new>
00024 
00025 namespace llvm {
00026 
00027 template<typename KeyT, typename ValueT,
00028          typename KeyInfoT = DenseMapInfo<KeyT>,
00029          typename ValueInfoT = DenseMapInfo<ValueT> >
00030 class DenseMapIterator;
00031 template<typename KeyT, typename ValueT,
00032          typename KeyInfoT = DenseMapInfo<KeyT>,
00033          typename ValueInfoT = DenseMapInfo<ValueT> >
00034 class DenseMapConstIterator;
00035 
00036 template<typename KeyT, typename ValueT,
00037          typename KeyInfoT = DenseMapInfo<KeyT>,
00038          typename ValueInfoT = DenseMapInfo<ValueT> >
00039 class DenseMap {
00040   typedef std::pair<KeyT, ValueT> BucketT;
00041   unsigned NumBuckets;
00042   BucketT *Buckets;
00043 
00044   unsigned NumEntries;
00045   unsigned NumTombstones;
00046 public:
00047   typedef KeyT key_type;
00048   typedef ValueT mapped_type;
00049   typedef BucketT value_type;
00050 
00051   DenseMap(const DenseMap& other) {
00052     NumBuckets = 0;
00053     CopyFrom(other);
00054   }
00055 
00056   explicit DenseMap(unsigned NumInitBuckets = 64) {
00057     init(NumInitBuckets);
00058   }
00059 
00060   ~DenseMap() {
00061     const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
00062     for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) {
00063       if (!KeyInfoT::isEqual(P->first, EmptyKey) &&
00064           !KeyInfoT::isEqual(P->first, TombstoneKey))
00065         P->second.~ValueT();
00066       P->first.~KeyT();
00067     }
00068 #ifndef NDEBUG
00069     memset(Buckets, 0x5a, sizeof(BucketT)*NumBuckets);
00070 #endif
00071     operator delete(Buckets);
00072   }
00073 
00074   typedef DenseMapIterator<KeyT, ValueT, KeyInfoT> iterator;
00075   typedef DenseMapConstIterator<KeyT, ValueT, KeyInfoT> const_iterator;
00076   inline iterator begin() {
00077      return iterator(Buckets, Buckets+NumBuckets);
00078   }
00079   inline iterator end() {
00080     return iterator(Buckets+NumBuckets, Buckets+NumBuckets);
00081   }
00082   inline const_iterator begin() const {
00083     return const_iterator(Buckets, Buckets+NumBuckets);
00084   }
00085   inline const_iterator end() const {
00086     return const_iterator(Buckets+NumBuckets, Buckets+NumBuckets);
00087   }
00088 
00089   bool empty() const { return NumEntries == 0; }
00090   unsigned size() const { return NumEntries; }
00091 
00092   /// Grow the densemap so that it has at least Size buckets. Does not shrink
00093   void resize(size_t Size) { grow(Size); }
00094 
00095   void clear() {
00096     // If the capacity of the array is huge, and the # elements used is small,
00097     // shrink the array.
00098     if (NumEntries * 4 < NumBuckets && NumBuckets > 64) {
00099       shrink_and_clear();
00100       return;
00101     }
00102 
00103     const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
00104     for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) {
00105       if (!KeyInfoT::isEqual(P->first, EmptyKey)) {
00106         if (!KeyInfoT::isEqual(P->first, TombstoneKey)) {
00107           P->second.~ValueT();
00108           --NumEntries;
00109         }
00110         P->first = EmptyKey;
00111       }
00112     }
00113     assert(NumEntries == 0 && "Node count imbalance!");
00114     NumTombstones = 0;
00115   }
00116 
00117   /// count - Return true if the specified key is in the map.
00118   bool count(const KeyT &Val) const {
00119     BucketT *TheBucket;
00120     return LookupBucketFor(Val, TheBucket);
00121   }
00122 
00123   iterator find(const KeyT &Val) {
00124     BucketT *TheBucket;
00125     if (LookupBucketFor(Val, TheBucket))
00126       return iterator(TheBucket, Buckets+NumBuckets);
00127     return end();
00128   }
00129   const_iterator find(const KeyT &Val) const {
00130     BucketT *TheBucket;
00131     if (LookupBucketFor(Val, TheBucket))
00132       return const_iterator(TheBucket, Buckets+NumBuckets);
00133     return end();
00134   }
00135 
00136   /// lookup - Return the entry for the specified key, or a default
00137   /// constructed value if no such entry exists.
00138   ValueT lookup(const KeyT &Val) const {
00139     BucketT *TheBucket;
00140     if (LookupBucketFor(Val, TheBucket))
00141       return TheBucket->second;
00142     return ValueT();
00143   }
00144 
00145   std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
00146     BucketT *TheBucket;
00147     if (LookupBucketFor(KV.first, TheBucket))
00148       return std::make_pair(iterator(TheBucket, Buckets+NumBuckets),
00149                             false); // Already in map.
00150 
00151     // Otherwise, insert the new element.
00152     TheBucket = InsertIntoBucket(KV.first, KV.second, TheBucket);
00153     return std::make_pair(iterator(TheBucket, Buckets+NumBuckets),
00154                           true);
00155   }
00156 
00157   /// insert - Range insertion of pairs.
00158   template<typename InputIt>
00159   void insert(InputIt I, InputIt E) {
00160     for (; I != E; ++I)
00161       insert(*I);
00162   }
00163 
00164 
00165   bool erase(const KeyT &Val) {
00166     BucketT *TheBucket;
00167     if (!LookupBucketFor(Val, TheBucket))
00168       return false; // not in map.
00169 
00170     TheBucket->second.~ValueT();
00171     TheBucket->first = getTombstoneKey();
00172     --NumEntries;
00173     ++NumTombstones;
00174     return true;
00175   }
00176   bool erase(iterator I) {
00177     BucketT *TheBucket = &*I;
00178     TheBucket->second.~ValueT();
00179     TheBucket->first = getTombstoneKey();
00180     --NumEntries;
00181     ++NumTombstones;
00182     return true;
00183   }
00184 
00185   value_type& FindAndConstruct(const KeyT &Key) {
00186     BucketT *TheBucket;
00187     if (LookupBucketFor(Key, TheBucket))
00188       return *TheBucket;
00189 
00190     return *InsertIntoBucket(Key, ValueT(), TheBucket);
00191   }
00192 
00193   ValueT &operator[](const KeyT &Key) {
00194     return FindAndConstruct(Key).second;
00195   }
00196 
00197   DenseMap& operator=(const DenseMap& other) {
00198     CopyFrom(other);
00199     return *this;
00200   }
00201 
00202   /// isPointerIntoBucketsArray - Return true if the specified pointer points
00203   /// somewhere into the DenseMap's array of buckets (i.e. either to a key or
00204   /// value in the DenseMap).
00205   bool isPointerIntoBucketsArray(const void *Ptr) const {
00206     return Ptr >= Buckets && Ptr < Buckets+NumBuckets;
00207   }
00208 
00209   /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets
00210   /// array.  In conjunction with the previous method, this can be used to
00211   /// determine whether an insertion caused the DenseMap to reallocate.
00212   const void *getPointerIntoBucketsArray() const { return Buckets; }
00213 
00214 private:
00215   void CopyFrom(const DenseMap& other) {
00216     if (NumBuckets != 0 && (!KeyInfoT::isPod() || !ValueInfoT::isPod())) {
00217       const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
00218       for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) {
00219         if (!KeyInfoT::isEqual(P->first, EmptyKey) &&
00220             !KeyInfoT::isEqual(P->first, TombstoneKey))
00221           P->second.~ValueT();
00222         P->first.~KeyT();
00223       }
00224     }
00225 
00226     NumEntries = other.NumEntries;
00227     NumTombstones = other.NumTombstones;
00228 
00229     if (NumBuckets) {
00230 #ifndef NDEBUG
00231       memset(Buckets, 0x5a, sizeof(BucketT)*NumBuckets);
00232 #endif
00233       operator delete(Buckets);
00234     }
00235     Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT) *
00236                                                  other.NumBuckets));
00237 
00238     if (KeyInfoT::isPod() && ValueInfoT::isPod())
00239       memcpy(Buckets, other.Buckets, other.NumBuckets * sizeof(BucketT));
00240     else
00241       for (size_t i = 0; i < other.NumBuckets; ++i) {
00242         new (&Buckets[i].first) KeyT(other.Buckets[i].first);
00243         if (!KeyInfoT::isEqual(Buckets[i].first, getEmptyKey()) &&
00244             !KeyInfoT::isEqual(Buckets[i].first, getTombstoneKey()))
00245           new (&Buckets[i].second) ValueT(other.Buckets[i].second);
00246       }
00247     NumBuckets = other.NumBuckets;
00248   }
00249 
00250   BucketT *InsertIntoBucket(const KeyT &Key, const ValueT &Value,
00251                             BucketT *TheBucket) {
00252     // If the load of the hash table is more than 3/4, or if fewer than 1/8 of
00253     // the buckets are empty (meaning that many are filled with tombstones),
00254     // grow the table.
00255     //
00256     // The later case is tricky.  For example, if we had one empty bucket with
00257     // tons of tombstones, failing lookups (e.g. for insertion) would have to
00258     // probe almost the entire table until it found the empty bucket.  If the
00259     // table completely filled with tombstones, no lookup would ever succeed,
00260     // causing infinite loops in lookup.
00261     ++NumEntries;
00262     if (NumEntries*4 >= NumBuckets*3 ||
00263         NumBuckets-(NumEntries+NumTombstones) < NumBuckets/8) {
00264       this->grow(NumBuckets * 2);
00265       LookupBucketFor(Key, TheBucket);
00266     }
00267 
00268     // If we are writing over a tombstone, remember this.
00269     if (!KeyInfoT::isEqual(TheBucket->first, getEmptyKey()))
00270       --NumTombstones;
00271 
00272     TheBucket->first = Key;
00273     new (&TheBucket->second) ValueT(Value);
00274     return TheBucket;
00275   }
00276 
00277   static unsigned getHashValue(const KeyT &Val) {
00278     return KeyInfoT::getHashValue(Val);
00279   }
00280   static const KeyT getEmptyKey() {
00281     return KeyInfoT::getEmptyKey();
00282   }
00283   static const KeyT getTombstoneKey() {
00284     return KeyInfoT::getTombstoneKey();
00285   }
00286 
00287   /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in
00288   /// FoundBucket.  If the bucket contains the key and a value, this returns
00289   /// true, otherwise it returns a bucket with an empty marker or tombstone and
00290   /// returns false.
00291   bool LookupBucketFor(const KeyT &Val, BucketT *&FoundBucket) const {
00292     unsigned BucketNo = getHashValue(Val);
00293     unsigned ProbeAmt = 1;
00294     BucketT *BucketsPtr = Buckets;
00295 
00296     // FoundTombstone - Keep track of whether we find a tombstone while probing.
00297     BucketT *FoundTombstone = 0;
00298     const KeyT EmptyKey = getEmptyKey();
00299     const KeyT TombstoneKey = getTombstoneKey();
00300     assert(!KeyInfoT::isEqual(Val, EmptyKey) &&
00301            !KeyInfoT::isEqual(Val, TombstoneKey) &&
00302            "Empty/Tombstone value shouldn't be inserted into map!");
00303 
00304     while (1) {
00305       BucketT *ThisBucket = BucketsPtr + (BucketNo & (NumBuckets-1));
00306       // Found Val's bucket?  If so, return it.
00307       if (KeyInfoT::isEqual(ThisBucket->first, Val)) {
00308         FoundBucket = ThisBucket;
00309         return true;
00310       }
00311 
00312       // If we found an empty bucket, the key doesn't exist in the set.
00313       // Insert it and return the default value.
00314       if (KeyInfoT::isEqual(ThisBucket->first, EmptyKey)) {
00315         // If we've already seen a tombstone while probing, fill it in instead
00316         // of the empty bucket we eventually probed to.
00317         if (FoundTombstone) ThisBucket = FoundTombstone;
00318         FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket;
00319         return false;
00320       }
00321 
00322       // If this is a tombstone, remember it.  If Val ends up not in the map, we
00323       // prefer to return it than something that would require more probing.
00324       if (KeyInfoT::isEqual(ThisBucket->first, TombstoneKey) && !FoundTombstone)
00325         FoundTombstone = ThisBucket;  // Remember the first tombstone found.
00326 
00327       // Otherwise, it's a hash collision or a tombstone, continue quadratic
00328       // probing.
00329       BucketNo += ProbeAmt++;
00330     }
00331   }
00332 
00333   void init(unsigned InitBuckets) {
00334     NumEntries = 0;
00335     NumTombstones = 0;
00336     NumBuckets = InitBuckets;
00337     assert(InitBuckets && (InitBuckets & (InitBuckets-1)) == 0 &&
00338            "# initial buckets must be a power of two!");
00339     Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*InitBuckets));
00340     // Initialize all the keys to EmptyKey.
00341     const KeyT EmptyKey = getEmptyKey();
00342     for (unsigned i = 0; i != InitBuckets; ++i)
00343       new (&Buckets[i].first) KeyT(EmptyKey);
00344   }
00345 
00346   void grow(unsigned AtLeast) {
00347     unsigned OldNumBuckets = NumBuckets;
00348     BucketT *OldBuckets = Buckets;
00349 
00350     // Double the number of buckets.
00351     while (NumBuckets <= AtLeast)
00352       NumBuckets <<= 1;
00353     NumTombstones = 0;
00354     Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*NumBuckets));
00355 
00356     // Initialize all the keys to EmptyKey.
00357     const KeyT EmptyKey = getEmptyKey();
00358     for (unsigned i = 0, e = NumBuckets; i != e; ++i)
00359       new (&Buckets[i].first) KeyT(EmptyKey);
00360 
00361     // Insert all the old elements.
00362     const KeyT TombstoneKey = getTombstoneKey();
00363     for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) {
00364       if (!KeyInfoT::isEqual(B->first, EmptyKey) &&
00365           !KeyInfoT::isEqual(B->first, TombstoneKey)) {
00366         // Insert the key/value into the new table.
00367         BucketT *DestBucket;
00368         bool FoundVal = LookupBucketFor(B->first, DestBucket);
00369         FoundVal = FoundVal; // silence warning.
00370         assert(!FoundVal && "Key already in new map?");
00371         DestBucket->first = B->first;
00372         new (&DestBucket->second) ValueT(B->second);
00373 
00374         // Free the value.
00375         B->second.~ValueT();
00376       }
00377       B->first.~KeyT();
00378     }
00379 
00380 #ifndef NDEBUG
00381     memset(OldBuckets, 0x5a, sizeof(BucketT)*OldNumBuckets);
00382 #endif
00383     // Free the old table.
00384     operator delete(OldBuckets);
00385   }
00386 
00387   void shrink_and_clear() {
00388     unsigned OldNumBuckets = NumBuckets;
00389     BucketT *OldBuckets = Buckets;
00390 
00391     // Reduce the number of buckets.
00392     NumBuckets = NumEntries > 32 ? 1 << (Log2_32_Ceil(NumEntries) + 1)
00393                                  : 64;
00394     NumTombstones = 0;
00395     Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*NumBuckets));
00396 
00397     // Initialize all the keys to EmptyKey.
00398     const KeyT EmptyKey = getEmptyKey();
00399     for (unsigned i = 0, e = NumBuckets; i != e; ++i)
00400       new (&Buckets[i].first) KeyT(EmptyKey);
00401 
00402     // Free the old buckets.
00403     const KeyT TombstoneKey = getTombstoneKey();
00404     for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) {
00405       if (!KeyInfoT::isEqual(B->first, EmptyKey) &&
00406           !KeyInfoT::isEqual(B->first, TombstoneKey)) {
00407         // Free the value.
00408         B->second.~ValueT();
00409       }
00410       B->first.~KeyT();
00411     }
00412 
00413 #ifndef NDEBUG
00414     memset(OldBuckets, 0x5a, sizeof(BucketT)*OldNumBuckets);
00415 #endif
00416     // Free the old table.
00417     operator delete(OldBuckets);
00418 
00419     NumEntries = 0;
00420   }
00421 };
00422 
00423 template<typename KeyT, typename ValueT, typename KeyInfoT, typename ValueInfoT>
00424 class DenseMapIterator {
00425   typedef std::pair<KeyT, ValueT> BucketT;
00426 protected:
00427   const BucketT *Ptr, *End;
00428 public:
00429   DenseMapIterator() : Ptr(0), End(0) {}
00430 
00431   DenseMapIterator(const BucketT *Pos, const BucketT *E) : Ptr(Pos), End(E) {
00432     AdvancePastEmptyBuckets();
00433   }
00434 
00435   std::pair<KeyT, ValueT> &operator*() const {
00436     return *const_cast<BucketT*>(Ptr);
00437   }
00438   std::pair<KeyT, ValueT> *operator->() const {
00439     return const_cast<BucketT*>(Ptr);
00440   }
00441 
00442   bool operator==(const DenseMapIterator &RHS) const {
00443     return Ptr == RHS.Ptr;
00444   }
00445   bool operator!=(const DenseMapIterator &RHS) const {
00446     return Ptr != RHS.Ptr;
00447   }
00448 
00449   inline DenseMapIterator& operator++() {          // Preincrement
00450     ++Ptr;
00451     AdvancePastEmptyBuckets();
00452     return *this;
00453   }
00454   DenseMapIterator operator++(int) {        // Postincrement
00455     DenseMapIterator tmp = *this; ++*this; return tmp;
00456   }
00457 
00458 private:
00459   void AdvancePastEmptyBuckets() {
00460     const KeyT Empty = KeyInfoT::getEmptyKey();
00461     const KeyT Tombstone = KeyInfoT::getTombstoneKey();
00462 
00463     while (Ptr != End &&
00464            (KeyInfoT::isEqual(Ptr->first, Empty) ||
00465             KeyInfoT::isEqual(Ptr->first, Tombstone)))
00466       ++Ptr;
00467   }
00468 };
00469 
00470 template<typename KeyT, typename ValueT, typename KeyInfoT, typename ValueInfoT>
00471 class DenseMapConstIterator : public DenseMapIterator<KeyT, ValueT, KeyInfoT> {
00472 public:
00473   DenseMapConstIterator() : DenseMapIterator<KeyT, ValueT, KeyInfoT>() {}
00474   DenseMapConstIterator(const std::pair<KeyT, ValueT> *Pos,
00475                         const std::pair<KeyT, ValueT> *E)
00476     : DenseMapIterator<KeyT, ValueT, KeyInfoT>(Pos, E) {
00477   }
00478   const std::pair<KeyT, ValueT> &operator*() const {
00479     return *this->Ptr;
00480   }
00481   const std::pair<KeyT, ValueT> *operator->() const {
00482     return this->Ptr;
00483   }
00484 };
00485 
00486 } // end namespace llvm
00487 
00488 #endif