+// Provide DenseMapValueInfo for all pointers.
+template<typename T>
+struct DenseMapValueInfo<T*> {
+ static bool isPod() { return true; }
+};
+
+template<typename KeyT, typename ValueT,
+ typename KeyInfoT = DenseMapKeyInfo<KeyT>,
+ typename ValueInfoT = DenseMapValueInfo<ValueT> >
+class DenseMapIterator;
+template<typename KeyT, typename ValueT,
+ typename KeyInfoT = DenseMapKeyInfo<KeyT>,
+ typename ValueInfoT = DenseMapValueInfo<ValueT> >
+class DenseMapConstIterator;
+
+template<typename KeyT, typename ValueT,
+ typename KeyInfoT = DenseMapKeyInfo<KeyT>,
+ typename ValueInfoT = DenseMapValueInfo<ValueT> >
+class DenseMap {
+ typedef std::pair<KeyT, ValueT> BucketT;
+ unsigned NumBuckets;
+ BucketT *Buckets;
+
+ unsigned NumEntries;
+ unsigned NumTombstones;
+public:
+ 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 (P->first != EmptyKey && P->first != TombstoneKey)
+ P->second.~ValueT();
+ P->first.~KeyT();
+ }
+ delete[] reinterpret_cast<char*>(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; }
+
+ 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 (P->first != EmptyKey) {
+ if (P->first != TombstoneKey) {
+ P->second.~ValueT();
+ --NumEntries;
+ }
+ P->first = EmptyKey;
+ }
+ }
+ assert(NumEntries == 0 && "Node count imbalance!");
+ NumTombstones = 0;
+ }