+template<typename T>
+struct DenseMapInfo {
+ //static inline T getEmptyKey();
+ //static inline T getTombstoneKey();
+ //static unsigned getHashValue(const T &Val);
+ //static bool isEqual(const T &LHS, const T &RHS);
+ //static bool isPod()
+};
+
+// Provide DenseMapInfo for all pointers.
+template<typename T>
+struct DenseMapInfo<T*> {
+ static inline T* getEmptyKey() { return reinterpret_cast<T*>(-1); }
+ static inline T* getTombstoneKey() { return reinterpret_cast<T*>(-2); }
+ static unsigned getHashValue(const T *PtrVal) {
+ return (unsigned((uintptr_t)PtrVal) >> 4) ^
+ (unsigned((uintptr_t)PtrVal) >> 9);
+ }
+ static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; }
+ static bool isPod() { return true; }
+};
+
+// Provide DenseMapInfo for unsigned ints.
+template<> struct DenseMapInfo<unsigned> {
+ static inline unsigned getEmptyKey() { return ~0; }
+ static inline unsigned getTombstoneKey() { return ~0 - 1; }
+ static unsigned getHashValue(const unsigned& Val) { return Val * 37; }
+ static bool isPod() { return true; }
+ static bool isEqual(const unsigned& LHS, const unsigned& RHS) {
+ return LHS == RHS;
+ }
+};
+
+// Provide DenseMapInfo for unsigned longs.
+template<> struct DenseMapInfo<unsigned long> {
+ static inline unsigned long getEmptyKey() { return ~0L; }
+ static inline unsigned long getTombstoneKey() { return ~0L - 1L; }
+ static unsigned getHashValue(const unsigned long& Val) {
+ return (unsigned)(Val * 37L);
+ }
+ static bool isPod() { return true; }
+ static bool isEqual(const unsigned long& LHS, const unsigned long& RHS) {
+ return LHS == RHS;
+ }
+};
+
+// Provide DenseMapInfo for all pairs whose members have info.
+template<typename T, typename U>
+struct DenseMapInfo<std::pair<T, U> > {
+ typedef std::pair<T, U> Pair;
+ typedef DenseMapInfo<T> FirstInfo;
+ typedef DenseMapInfo<U> SecondInfo;
+
+ static inline Pair getEmptyKey() {
+ return std::make_pair(FirstInfo::getEmptyKey(),
+ SecondInfo::getEmptyKey());
+ }
+ static inline Pair getTombstoneKey() {
+ return std::make_pair(FirstInfo::getTombstoneKey(),
+ SecondInfo::getEmptyKey());
+ }
+ static unsigned getHashValue(const Pair& PairVal) {
+ uint64_t key = (uint64_t)FirstInfo::getHashValue(PairVal.first) << 32
+ | (uint64_t)SecondInfo::getHashValue(PairVal.second);
+ key += ~(key << 32);
+ key ^= (key >> 22);
+ key += ~(key << 13);
+ key ^= (key >> 8);
+ key += (key << 3);
+ key ^= (key >> 15);
+ key += ~(key << 27);
+ key ^= (key >> 31);
+ return (unsigned)key;
+ }
+ static bool isEqual(const Pair& LHS, const Pair& RHS) { return LHS == RHS; }
+ static bool isPod() { return FirstInfo::isPod() && SecondInfo::isPod(); }
+};
+
+template<typename KeyT, typename ValueT,
+ typename KeyInfoT = DenseMapInfo<KeyT>,
+ typename ValueInfoT = DenseMapInfo<ValueT> >
+class DenseMapIterator;
+template<typename KeyT, typename ValueT,
+ typename KeyInfoT = DenseMapInfo<KeyT>,
+ typename ValueInfoT = DenseMapInfo<ValueT> >
+class DenseMapConstIterator;
+
+template<typename KeyT, typename ValueT,
+ typename KeyInfoT = DenseMapInfo<KeyT>,
+ typename ValueInfoT = DenseMapInfo<ValueT> >
+class DenseMap {
+ typedef std::pair<KeyT, ValueT> BucketT;
+ unsigned NumBuckets;
+ BucketT *Buckets;
+
+ unsigned NumEntries;
+ unsigned NumTombstones;
+public:
+ typedef KeyT key_type;
+ typedef ValueT mapped_type;
+ typedef BucketT value_type;
+
+ DenseMap(const DenseMap& other) {
+ NumBuckets = 0;
+ CopyFrom(other);
+ }
+
+ explicit DenseMap(unsigned NumInitBuckets = 64) {
+ init(NumInitBuckets);
+ }
+
+ ~DenseMap() {
+ const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
+ for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) {
+ if (!KeyInfoT::isEqual(P->first, EmptyKey) &&
+ !KeyInfoT::isEqual(P->first, TombstoneKey))
+ P->second.~ValueT();
+ P->first.~KeyT();
+ }
+ operator delete(Buckets);
+ }
+
+ typedef DenseMapIterator<KeyT, ValueT, KeyInfoT> iterator;
+ typedef DenseMapConstIterator<KeyT, ValueT, KeyInfoT> const_iterator;
+ inline iterator begin() {
+ return iterator(Buckets, Buckets+NumBuckets);
+ }
+ inline iterator end() {
+ return iterator(Buckets+NumBuckets, Buckets+NumBuckets);
+ }
+ inline const_iterator begin() const {
+ return const_iterator(Buckets, Buckets+NumBuckets);
+ }
+ inline const_iterator end() const {
+ return const_iterator(Buckets+NumBuckets, Buckets+NumBuckets);
+ }
+
+ bool empty() const { return NumEntries == 0; }
+ unsigned size() const { return NumEntries; }
+
+ /// Grow the densemap so that it has at least Size buckets. Does not shrink
+ void resize(size_t Size) { grow(Size); }
+
+ void clear() {
+ // If the capacity of the array is huge, and the # elements used is small,
+ // shrink the array.
+ if (NumEntries * 4 < NumBuckets && NumBuckets > 64) {
+ shrink_and_clear();
+ return;
+ }
+
+ const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
+ for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) {
+ if (!KeyInfoT::isEqual(P->first, EmptyKey)) {
+ if (!KeyInfoT::isEqual(P->first, TombstoneKey)) {
+ P->second.~ValueT();
+ --NumEntries;
+ }
+ P->first = EmptyKey;
+ }