+template<typename KeyT, typename ValueT,
+ typename KeyInfoT = DenseMapInfo<KeyT>,
+ bool IsConst = false>
+class DenseMapIterator;
+
+template<typename DerivedT,
+ typename KeyT, typename ValueT, typename KeyInfoT>
+class DenseMapBase {
+protected:
+ typedef std::pair<KeyT, ValueT> BucketT;
+
+public:
+ typedef KeyT key_type;
+ typedef ValueT mapped_type;
+ typedef BucketT value_type;
+
+ typedef DenseMapIterator<KeyT, ValueT, KeyInfoT> iterator;
+ typedef DenseMapIterator<KeyT, ValueT,
+ KeyInfoT, true> const_iterator;
+ inline iterator begin() {
+ // When the map is empty, avoid the overhead of AdvancePastEmptyBuckets().
+ return empty() ? end() : iterator(getBuckets(), getBucketsEnd());
+ }
+ inline iterator end() {
+ return iterator(getBucketsEnd(), getBucketsEnd(), true);
+ }
+ inline const_iterator begin() const {
+ return empty() ? end() : const_iterator(getBuckets(), getBucketsEnd());
+ }
+ inline const_iterator end() const {
+ return const_iterator(getBucketsEnd(), getBucketsEnd(), true);
+ }
+
+ bool empty() const { return getNumEntries() == 0; }
+ unsigned size() const { return getNumEntries(); }
+
+ /// Grow the densemap so that it has at least Size buckets. Does not shrink
+ void resize(size_t Size) {
+ if (Size > getNumBuckets())
+ grow(Size);
+ }
+
+ void clear() {
+ if (getNumEntries() == 0 && getNumTombstones() == 0) return;
+
+ // If the capacity of the array is huge, and the # elements used is small,
+ // shrink the array.
+ if (getNumEntries() * 4 < getNumBuckets() && getNumBuckets() > 64) {
+ shrink_and_clear();
+ return;
+ }
+
+ const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
+ for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) {
+ if (!KeyInfoT::isEqual(P->first, EmptyKey)) {
+ if (!KeyInfoT::isEqual(P->first, TombstoneKey)) {
+ P->second.~ValueT();
+ decrementNumEntries();
+ }
+ P->first = EmptyKey;
+ }
+ }
+ assert(getNumEntries() == 0 && "Node count imbalance!");
+ setNumTombstones(0);
+ }
+
+ /// count - Return true if the specified key is in the map.
+ bool count(const KeyT &Val) const {
+ const BucketT *TheBucket;
+ return LookupBucketFor(Val, TheBucket);
+ }
+
+ iterator find(const KeyT &Val) {
+ BucketT *TheBucket;
+ if (LookupBucketFor(Val, TheBucket))
+ return iterator(TheBucket, getBucketsEnd(), true);
+ return end();
+ }
+ const_iterator find(const KeyT &Val) const {
+ const BucketT *TheBucket;
+ if (LookupBucketFor(Val, TheBucket))
+ return const_iterator(TheBucket, getBucketsEnd(), true);
+ return end();
+ }
+
+ /// Alternate version of find() which allows a different, and possibly
+ /// less expensive, key type.
+ /// The DenseMapInfo is responsible for supplying methods
+ /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key
+ /// type used.
+ template<class LookupKeyT>
+ iterator find_as(const LookupKeyT &Val) {
+ BucketT *TheBucket;
+ if (LookupBucketFor(Val, TheBucket))
+ return iterator(TheBucket, getBucketsEnd(), true);
+ return end();
+ }
+ template<class LookupKeyT>
+ const_iterator find_as(const LookupKeyT &Val) const {
+ const BucketT *TheBucket;
+ if (LookupBucketFor(Val, TheBucket))
+ return const_iterator(TheBucket, getBucketsEnd(), true);
+ return end();
+ }
+
+ /// lookup - Return the entry for the specified key, or a default
+ /// constructed value if no such entry exists.
+ ValueT lookup(const KeyT &Val) const {
+ const BucketT *TheBucket;
+ if (LookupBucketFor(Val, TheBucket))
+ return TheBucket->second;
+ return ValueT();
+ }
+
+ // Inserts key,value pair into the map if the key isn't already in the map.
+ // If the key is already in the map, it returns false and doesn't update the
+ // value.
+ std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
+ BucketT *TheBucket;
+ if (LookupBucketFor(KV.first, TheBucket))
+ return std::make_pair(iterator(TheBucket, getBucketsEnd(), true),
+ false); // Already in map.
+
+ // Otherwise, insert the new element.
+ TheBucket = InsertIntoBucket(KV.first, KV.second, TheBucket);
+ return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), true);
+ }
+
+ /// insert - Range insertion of pairs.
+ template<typename InputIt>
+ void insert(InputIt I, InputIt E) {
+ for (; I != E; ++I)
+ insert(*I);
+ }
+
+
+ bool erase(const KeyT &Val) {
+ BucketT *TheBucket;
+ if (!LookupBucketFor(Val, TheBucket))
+ return false; // not in map.
+
+ TheBucket->second.~ValueT();
+ TheBucket->first = getTombstoneKey();
+ decrementNumEntries();
+ incrementNumTombstones();
+ return true;
+ }
+ void erase(iterator I) {
+ BucketT *TheBucket = &*I;
+ TheBucket->second.~ValueT();
+ TheBucket->first = getTombstoneKey();
+ decrementNumEntries();
+ incrementNumTombstones();
+ }
+
+ value_type& FindAndConstruct(const KeyT &Key) {
+ BucketT *TheBucket;
+ if (LookupBucketFor(Key, TheBucket))
+ return *TheBucket;
+
+ return *InsertIntoBucket(Key, ValueT(), TheBucket);
+ }
+
+ ValueT &operator[](const KeyT &Key) {
+ return FindAndConstruct(Key).second;
+ }
+
+#if LLVM_USE_RVALUE_REFERENCES
+ value_type& FindAndConstruct(KeyT &&Key) {
+ BucketT *TheBucket;
+ if (LookupBucketFor(Key, TheBucket))
+ return *TheBucket;
+
+ return *InsertIntoBucket(Key, ValueT(), TheBucket);
+ }
+
+ ValueT &operator[](KeyT &&Key) {
+ return FindAndConstruct(Key).second;
+ }
+#endif
+
+ /// isPointerIntoBucketsArray - Return true if the specified pointer points
+ /// somewhere into the DenseMap's array of buckets (i.e. either to a key or
+ /// value in the DenseMap).
+ bool isPointerIntoBucketsArray(const void *Ptr) const {
+ return Ptr >= getBuckets() && Ptr < getBucketsEnd();
+ }
+
+ /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets
+ /// array. In conjunction with the previous method, this can be used to
+ /// determine whether an insertion caused the DenseMap to reallocate.
+ const void *getPointerIntoBucketsArray() const { return getBuckets(); }
+
+protected:
+ DenseMapBase() {}
+
+ void destroyAll() {
+ if (getNumBuckets() == 0) // Nothing to do.
+ return;
+
+ const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
+ for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) {
+ if (!KeyInfoT::isEqual(P->first, EmptyKey) &&
+ !KeyInfoT::isEqual(P->first, TombstoneKey))
+ P->second.~ValueT();
+ P->first.~KeyT();
+ }
+
+#ifndef NDEBUG
+ memset((void*)getBuckets(), 0x5a, sizeof(BucketT)*getNumBuckets());
+#endif
+ }
+
+ void initEmpty() {
+ setNumEntries(0);
+ setNumTombstones(0);
+
+ assert((getNumBuckets() & (getNumBuckets()-1)) == 0 &&
+ "# initial buckets must be a power of two!");
+ const KeyT EmptyKey = getEmptyKey();
+ for (BucketT *B = getBuckets(), *E = getBucketsEnd(); B != E; ++B)
+ new (&B->first) KeyT(EmptyKey);
+ }
+
+ void moveFromOldBuckets(BucketT *OldBucketsBegin, BucketT *OldBucketsEnd) {
+ initEmpty();
+
+ // Insert all the old elements.
+ const KeyT EmptyKey = getEmptyKey();
+ const KeyT TombstoneKey = getTombstoneKey();
+ for (BucketT *B = OldBucketsBegin, *E = OldBucketsEnd; B != E; ++B) {
+ if (!KeyInfoT::isEqual(B->first, EmptyKey) &&
+ !KeyInfoT::isEqual(B->first, TombstoneKey)) {
+ // Insert the key/value into the new table.
+ BucketT *DestBucket;
+ bool FoundVal = LookupBucketFor(B->first, DestBucket);
+ (void)FoundVal; // silence warning.
+ assert(!FoundVal && "Key already in new map?");
+ DestBucket->first = llvm_move(B->first);
+ new (&DestBucket->second) ValueT(llvm_move(B->second));
+ incrementNumEntries();
+
+ // Free the value.
+ B->second.~ValueT();
+ }
+ B->first.~KeyT();
+ }
+
+#ifndef NDEBUG
+ if (OldBucketsBegin != OldBucketsEnd)
+ memset((void*)OldBucketsBegin, 0x5a,
+ sizeof(BucketT) * (OldBucketsEnd - OldBucketsBegin));
+#endif
+ }
+
+ template <typename OtherBaseT>
+ void copyFrom(const DenseMapBase<OtherBaseT, KeyT, ValueT, KeyInfoT>& other) {
+ assert(getNumBuckets() == other.getNumBuckets());
+
+ setNumEntries(other.getNumEntries());
+ setNumTombstones(other.getNumTombstones());
+
+ if (isPodLike<KeyT>::value && isPodLike<ValueT>::value)
+ memcpy(getBuckets(), other.getBuckets(),
+ getNumBuckets() * sizeof(BucketT));
+ else
+ for (size_t i = 0; i < getNumBuckets(); ++i) {
+ new (&getBuckets()[i].first) KeyT(other.getBuckets()[i].first);
+ if (!KeyInfoT::isEqual(getBuckets()[i].first, getEmptyKey()) &&
+ !KeyInfoT::isEqual(getBuckets()[i].first, getTombstoneKey()))
+ new (&getBuckets()[i].second) ValueT(other.getBuckets()[i].second);
+ }
+ }
+
+ void swap(DenseMapBase& RHS) {
+ std::swap(getNumEntries(), RHS.getNumEntries());
+ std::swap(getNumTombstones(), RHS.getNumTombstones());
+ }
+
+ static unsigned getHashValue(const KeyT &Val) {
+ return KeyInfoT::getHashValue(Val);
+ }
+ template<typename LookupKeyT>
+ static unsigned getHashValue(const LookupKeyT &Val) {
+ return KeyInfoT::getHashValue(Val);
+ }
+ static const KeyT getEmptyKey() {
+ return KeyInfoT::getEmptyKey();
+ }
+ static const KeyT getTombstoneKey() {
+ return KeyInfoT::getTombstoneKey();
+ }
+
+private:
+ unsigned getNumEntries() const {
+ return static_cast<const DerivedT *>(this)->getNumEntries();
+ }
+ void setNumEntries(unsigned Num) {
+ static_cast<DerivedT *>(this)->setNumEntries(Num);
+ }
+ void incrementNumEntries() {
+ setNumEntries(getNumEntries() + 1);
+ }
+ void decrementNumEntries() {
+ setNumEntries(getNumEntries() - 1);
+ }
+ unsigned getNumTombstones() const {
+ return static_cast<const DerivedT *>(this)->getNumTombstones();
+ }
+ void setNumTombstones(unsigned Num) {
+ static_cast<DerivedT *>(this)->setNumTombstones(Num);
+ }
+ void incrementNumTombstones() {
+ setNumTombstones(getNumTombstones() + 1);
+ }
+ void decrementNumTombstones() {
+ setNumTombstones(getNumTombstones() - 1);
+ }
+ const BucketT *getBuckets() const {
+ return static_cast<const DerivedT *>(this)->getBuckets();
+ }
+ BucketT *getBuckets() {
+ return static_cast<DerivedT *>(this)->getBuckets();
+ }
+ unsigned getNumBuckets() const {
+ return static_cast<const DerivedT *>(this)->getNumBuckets();
+ }
+ BucketT *getBucketsEnd() {
+ return getBuckets() + getNumBuckets();
+ }
+ const BucketT *getBucketsEnd() const {
+ return getBuckets() + getNumBuckets();
+ }
+
+ void grow(unsigned AtLeast) {
+ static_cast<DerivedT *>(this)->grow(AtLeast);
+ }
+
+ void shrink_and_clear() {
+ static_cast<DerivedT *>(this)->shrink_and_clear();
+ }
+
+
+ BucketT *InsertIntoBucket(const KeyT &Key, const ValueT &Value,
+ BucketT *TheBucket) {
+ TheBucket = InsertIntoBucketImpl(Key, TheBucket);
+
+ TheBucket->first = Key;
+ new (&TheBucket->second) ValueT(Value);
+ return TheBucket;
+ }
+
+#if LLVM_USE_RVALUE_REFERENCES
+ BucketT *InsertIntoBucket(const KeyT &Key, ValueT &&Value,
+ BucketT *TheBucket) {
+ TheBucket = InsertIntoBucketImpl(Key, TheBucket);
+
+ TheBucket->first = Key;
+ new (&TheBucket->second) ValueT(std::move(Value));
+ return TheBucket;
+ }
+
+ BucketT *InsertIntoBucket(KeyT &&Key, ValueT &&Value, BucketT *TheBucket) {
+ TheBucket = InsertIntoBucketImpl(Key, TheBucket);
+
+ TheBucket->first = std::move(Key);
+ new (&TheBucket->second) ValueT(std::move(Value));
+ return TheBucket;
+ }
+#endif
+
+ BucketT *InsertIntoBucketImpl(const KeyT &Key, BucketT *TheBucket) {
+ // If the load of the hash table is more than 3/4, or if fewer than 1/8 of
+ // the buckets are empty (meaning that many are filled with tombstones),
+ // grow the table.
+ //
+ // The later case is tricky. For example, if we had one empty bucket with
+ // tons of tombstones, failing lookups (e.g. for insertion) would have to
+ // probe almost the entire table until it found the empty bucket. If the
+ // table completely filled with tombstones, no lookup would ever succeed,
+ // causing infinite loops in lookup.
+ unsigned NewNumEntries = getNumEntries() + 1;
+ unsigned NumBuckets = getNumBuckets();
+ if (NewNumEntries*4 >= NumBuckets*3) {
+ this->grow(NumBuckets * 2);
+ LookupBucketFor(Key, TheBucket);
+ NumBuckets = getNumBuckets();
+ }
+ if (NumBuckets-(NewNumEntries+getNumTombstones()) <= NumBuckets/8) {
+ this->grow(NumBuckets);
+ LookupBucketFor(Key, TheBucket);
+ }
+
+ // Only update the state after we've grown our bucket space appropriately
+ // so that when growing buckets we have self-consistent entry count.
+ incrementNumEntries();
+
+ // If we are writing over a tombstone, remember this.
+ if (!KeyInfoT::isEqual(TheBucket->first, getEmptyKey()))
+ decrementNumTombstones();
+
+ return TheBucket;
+ }
+
+ /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in
+ /// FoundBucket. If the bucket contains the key and a value, this returns
+ /// true, otherwise it returns a bucket with an empty marker or tombstone and
+ /// returns false.
+ template<typename LookupKeyT>
+ bool LookupBucketFor(const LookupKeyT &Val,
+ const BucketT *&FoundBucket) const {
+ const BucketT *BucketsPtr = getBuckets();
+ const unsigned NumBuckets = getNumBuckets();
+
+ if (NumBuckets == 0) {
+ FoundBucket = 0;
+ return false;
+ }
+
+ // FoundTombstone - Keep track of whether we find a tombstone while probing.
+ const BucketT *FoundTombstone = 0;
+ const KeyT EmptyKey = getEmptyKey();
+ const KeyT TombstoneKey = getTombstoneKey();
+ assert(!KeyInfoT::isEqual(Val, EmptyKey) &&
+ !KeyInfoT::isEqual(Val, TombstoneKey) &&
+ "Empty/Tombstone value shouldn't be inserted into map!");
+
+ unsigned BucketNo = getHashValue(Val) & (NumBuckets-1);
+ unsigned ProbeAmt = 1;
+ while (1) {
+ const BucketT *ThisBucket = BucketsPtr + BucketNo;
+ // Found Val's bucket? If so, return it.
+ if (KeyInfoT::isEqual(Val, ThisBucket->first)) {
+ FoundBucket = ThisBucket;
+ return true;
+ }
+
+ // If we found an empty bucket, the key doesn't exist in the set.
+ // Insert it and return the default value.
+ if (KeyInfoT::isEqual(ThisBucket->first, EmptyKey)) {
+ // If we've already seen a tombstone while probing, fill it in instead
+ // of the empty bucket we eventually probed to.
+ if (FoundTombstone) ThisBucket = FoundTombstone;
+ FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket;
+ return false;
+ }
+
+ // If this is a tombstone, remember it. If Val ends up not in the map, we
+ // prefer to return it than something that would require more probing.
+ if (KeyInfoT::isEqual(ThisBucket->first, TombstoneKey) && !FoundTombstone)
+ FoundTombstone = ThisBucket; // Remember the first tombstone found.
+
+ // Otherwise, it's a hash collision or a tombstone, continue quadratic
+ // probing.
+ BucketNo += ProbeAmt++;
+ BucketNo &= (NumBuckets-1);
+ }
+ }
+
+ template <typename LookupKeyT>
+ bool LookupBucketFor(const LookupKeyT &Val, BucketT *&FoundBucket) {
+ const BucketT *ConstFoundBucket;
+ bool Result = const_cast<const DenseMapBase *>(this)
+ ->LookupBucketFor(Val, ConstFoundBucket);
+ FoundBucket = const_cast<BucketT *>(ConstFoundBucket);
+ return Result;
+ }
+
+public:
+ /// Return the approximate size (in bytes) of the actual map.
+ /// This is just the raw memory used by DenseMap.
+ /// If entries are pointers to objects, the size of the referenced objects
+ /// are not included.
+ size_t getMemorySize() const {
+ return getNumBuckets() * sizeof(BucketT);
+ }
+};
+
+template<typename KeyT, typename ValueT,
+ typename KeyInfoT = DenseMapInfo<KeyT> >
+class DenseMap
+ : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT>,
+ KeyT, ValueT, KeyInfoT> {
+ // Lift some types from the dependent base class into this class for
+ // simplicity of referring to them.
+ typedef DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT> BaseT;
+ typedef typename BaseT::BucketT BucketT;
+ friend class DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT>;
+
+ BucketT *Buckets;
+ unsigned NumEntries;
+ unsigned NumTombstones;
+ unsigned NumBuckets;