DenseMap.h revision 6a363782fe4ecba4f0a72c2edf03596004470c4a
143dee220252ef0b42c5f8a3bb1eca97f84f2565fArgyrios Kyrtzidis//===- llvm/ADT/DenseMap.h - Dense probed hash table ------------*- C++ -*-===// 243dee220252ef0b42c5f8a3bb1eca97f84f2565fArgyrios Kyrtzidis// 343dee220252ef0b42c5f8a3bb1eca97f84f2565fArgyrios Kyrtzidis// The LLVM Compiler Infrastructure 443dee220252ef0b42c5f8a3bb1eca97f84f2565fArgyrios Kyrtzidis// 543dee220252ef0b42c5f8a3bb1eca97f84f2565fArgyrios Kyrtzidis// This file is distributed under the University of Illinois Open Source 643dee220252ef0b42c5f8a3bb1eca97f84f2565fArgyrios Kyrtzidis// License. See LICENSE.TXT for details. 743dee220252ef0b42c5f8a3bb1eca97f84f2565fArgyrios Kyrtzidis// 843dee220252ef0b42c5f8a3bb1eca97f84f2565fArgyrios Kyrtzidis//===----------------------------------------------------------------------===// 943dee220252ef0b42c5f8a3bb1eca97f84f2565fArgyrios Kyrtzidis// 1043dee220252ef0b42c5f8a3bb1eca97f84f2565fArgyrios Kyrtzidis// This file defines the DenseMap class. 1143dee220252ef0b42c5f8a3bb1eca97f84f2565fArgyrios Kyrtzidis// 1243dee220252ef0b42c5f8a3bb1eca97f84f2565fArgyrios Kyrtzidis//===----------------------------------------------------------------------===// 1343dee220252ef0b42c5f8a3bb1eca97f84f2565fArgyrios Kyrtzidis 1443dee220252ef0b42c5f8a3bb1eca97f84f2565fArgyrios Kyrtzidis#ifndef LLVM_ADT_DENSEMAP_H 1543dee220252ef0b42c5f8a3bb1eca97f84f2565fArgyrios Kyrtzidis#define LLVM_ADT_DENSEMAP_H 16ca804539d908d3a0e8c72a0df5f1f571d29490bbTed Kremenek 17769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis#include "llvm/Support/MathExtras.h" 18769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis#include "llvm/Support/PointerLikeTypeTraits.h" 199fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis#include "llvm/Support/type_traits.h" 2043dee220252ef0b42c5f8a3bb1eca97f84f2565fArgyrios Kyrtzidis#include "llvm/ADT/DenseMapInfo.h" 2143dee220252ef0b42c5f8a3bb1eca97f84f2565fArgyrios Kyrtzidis#include <iterator> 2243dee220252ef0b42c5f8a3bb1eca97f84f2565fArgyrios Kyrtzidis#include <new> 2343dee220252ef0b42c5f8a3bb1eca97f84f2565fArgyrios Kyrtzidis#include <utility> 24d655ab28fdf7c940d3f79f8f287954d7f76e0977Argyrios Kyrtzidis#include <cassert> 25d655ab28fdf7c940d3f79f8f287954d7f76e0977Argyrios Kyrtzidis#include <cstring> 26d655ab28fdf7c940d3f79f8f287954d7f76e0977Argyrios Kyrtzidis 27d655ab28fdf7c940d3f79f8f287954d7f76e0977Argyrios Kyrtzidisnamespace llvm { 28d655ab28fdf7c940d3f79f8f287954d7f76e0977Argyrios Kyrtzidis 29d655ab28fdf7c940d3f79f8f287954d7f76e0977Argyrios Kyrtzidistemplate<typename KeyT, typename ValueT, 30d655ab28fdf7c940d3f79f8f287954d7f76e0977Argyrios Kyrtzidis typename KeyInfoT = DenseMapInfo<KeyT>, 31d655ab28fdf7c940d3f79f8f287954d7f76e0977Argyrios Kyrtzidis typename ValueInfoT = DenseMapInfo<ValueT>, bool IsConst = false> 32d655ab28fdf7c940d3f79f8f287954d7f76e0977Argyrios Kyrtzidisclass DenseMapIterator; 33d655ab28fdf7c940d3f79f8f287954d7f76e0977Argyrios Kyrtzidis 34d655ab28fdf7c940d3f79f8f287954d7f76e0977Argyrios Kyrtzidistemplate<typename KeyT, typename ValueT, 35d655ab28fdf7c940d3f79f8f287954d7f76e0977Argyrios Kyrtzidis typename KeyInfoT = DenseMapInfo<KeyT>, 36d655ab28fdf7c940d3f79f8f287954d7f76e0977Argyrios Kyrtzidis typename ValueInfoT = DenseMapInfo<ValueT> > 37d655ab28fdf7c940d3f79f8f287954d7f76e0977Argyrios Kyrtzidisclass DenseMap { 38d655ab28fdf7c940d3f79f8f287954d7f76e0977Argyrios Kyrtzidis typedef std::pair<KeyT, ValueT> BucketT; 39d655ab28fdf7c940d3f79f8f287954d7f76e0977Argyrios Kyrtzidis unsigned NumBuckets; 40deb6447d0029bdb122397fafb5fa2a4e76f2e555Argyrios Kyrtzidis BucketT *Buckets; 41deb6447d0029bdb122397fafb5fa2a4e76f2e555Argyrios Kyrtzidis 42deb6447d0029bdb122397fafb5fa2a4e76f2e555Argyrios Kyrtzidis unsigned NumEntries; 43deb6447d0029bdb122397fafb5fa2a4e76f2e555Argyrios Kyrtzidis unsigned NumTombstones; 44deb6447d0029bdb122397fafb5fa2a4e76f2e555Argyrios Kyrtzidispublic: 45deb6447d0029bdb122397fafb5fa2a4e76f2e555Argyrios Kyrtzidis typedef KeyT key_type; 46deb6447d0029bdb122397fafb5fa2a4e76f2e555Argyrios Kyrtzidis typedef ValueT mapped_type; 47deb6447d0029bdb122397fafb5fa2a4e76f2e555Argyrios Kyrtzidis typedef BucketT value_type; 48deb6447d0029bdb122397fafb5fa2a4e76f2e555Argyrios Kyrtzidis 49deb6447d0029bdb122397fafb5fa2a4e76f2e555Argyrios Kyrtzidis DenseMap(const DenseMap &other) { 50769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis NumBuckets = 0; 51769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis CopyFrom(other); 52769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis } 53769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 549fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis explicit DenseMap(unsigned NumInitBuckets = 64) { 559fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis init(NumInitBuckets); 569fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis } 579fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis 589fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis template<typename InputIt> 599fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis DenseMap(const InputIt &I, const InputIt &E) { 609fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis init(64); 619fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis insert(I, E); 629fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis } 639fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis 649fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis ~DenseMap() { 659fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 669fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { 679fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis if (!KeyInfoT::isEqual(P->first, EmptyKey) && 689fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis !KeyInfoT::isEqual(P->first, TombstoneKey)) 69769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis P->second.~ValueT(); 709fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis P->first.~KeyT(); 719fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis } 729fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis#ifndef NDEBUG 739fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis memset(Buckets, 0x5a, sizeof(BucketT)*NumBuckets); 749fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis#endif 75769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis operator delete(Buckets); 76769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis } 779fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis 789fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis typedef DenseMapIterator<KeyT, ValueT, KeyInfoT> iterator; 799fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis typedef DenseMapIterator<KeyT, ValueT, 809fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis KeyInfoT, ValueInfoT, true> const_iterator; 819fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis inline iterator begin() { 829fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis return iterator(Buckets, Buckets+NumBuckets); 83769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis } 84769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis inline iterator end() { 85769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis return iterator(Buckets+NumBuckets, Buckets+NumBuckets); 86769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis } 87769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis inline const_iterator begin() const { 88769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis return const_iterator(Buckets, Buckets+NumBuckets); 89769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis } 90769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis inline const_iterator end() const { 91769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis return const_iterator(Buckets+NumBuckets, Buckets+NumBuckets); 92c2e0db82139c70c0eac9d5c165b6bf3250af5bedArgyrios Kyrtzidis } 93c2e0db82139c70c0eac9d5c165b6bf3250af5bedArgyrios Kyrtzidis 94cd50e136ad7dc721822f5e6350769a37c216612dArgyrios Kyrtzidis bool empty() const { return NumEntries == 0; } 95769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis unsigned size() const { return NumEntries; } 96e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis 97e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis /// Grow the densemap so that it has at least Size buckets. Does not shrink 98e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis void resize(size_t Size) { grow(Size); } 99769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 100769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis void clear() { 101769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis if (NumEntries == 0 && NumTombstones == 0) return; 102769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 103cd50e136ad7dc721822f5e6350769a37c216612dArgyrios Kyrtzidis // If the capacity of the array is huge, and the # elements used is small, 104cd50e136ad7dc721822f5e6350769a37c216612dArgyrios Kyrtzidis // shrink the array. 105769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis if (NumEntries * 4 < NumBuckets && NumBuckets > 64) { 106e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis shrink_and_clear(); 107769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis return; 108769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis } 109769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 110769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 111cd50e136ad7dc721822f5e6350769a37c216612dArgyrios Kyrtzidis for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { 112769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis if (!KeyInfoT::isEqual(P->first, EmptyKey)) { 113769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis if (!KeyInfoT::isEqual(P->first, TombstoneKey)) { 114769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis P->second.~ValueT(); 115769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis --NumEntries; 116769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis } 117769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis P->first = EmptyKey; 118769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis } 119769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis } 120769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis assert(NumEntries == 0 && "Node count imbalance!"); 1219fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis NumTombstones = 0; 1229fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis } 1239fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis 124769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis /// count - Return true if the specified key is in the map. 125769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis bool count(const KeyT &Val) const { 1265f9e272e632e951b1efe824cd16acb4d96077930Chris Lattner BucketT *TheBucket; 127769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis return LookupBucketFor(Val, TheBucket); 128769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis } 129769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 130769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis iterator find(const KeyT &Val) { 131769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis BucketT *TheBucket; 132e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis if (LookupBucketFor(Val, TheBucket)) 133e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis return iterator(TheBucket, Buckets+NumBuckets); 134e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis return end(); 135769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis } 136769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis const_iterator find(const KeyT &Val) const { 137769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis BucketT *TheBucket; 138769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis if (LookupBucketFor(Val, TheBucket)) 139769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis return const_iterator(TheBucket, Buckets+NumBuckets); 140769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis return end(); 141769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis } 142769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 143769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis /// lookup - Return the entry for the specified key, or a default 144769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis /// constructed value if no such entry exists. 145769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis ValueT lookup(const KeyT &Val) const { 146769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis BucketT *TheBucket; 147769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis if (LookupBucketFor(Val, TheBucket)) 148769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis return TheBucket->second; 149769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis return ValueT(); 150769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis } 151769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 152769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis // Inserts key,value pair into the map if the key isn't already in the map. 153cd50e136ad7dc721822f5e6350769a37c216612dArgyrios Kyrtzidis // If the key is already in the map, it returns false and doesn't update the 154769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis // value. 155769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { 156769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis BucketT *TheBucket; 157769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis if (LookupBucketFor(KV.first, TheBucket)) 158c2e0db82139c70c0eac9d5c165b6bf3250af5bedArgyrios Kyrtzidis return std::make_pair(iterator(TheBucket, Buckets+NumBuckets), 159769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis false); // Already in map. 160769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 161769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis // Otherwise, insert the new element. 162769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis TheBucket = InsertIntoBucket(KV.first, KV.second, TheBucket); 163769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis return std::make_pair(iterator(TheBucket, Buckets+NumBuckets), 164769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis true); 165769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis } 166769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 167769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis /// insert - Range insertion of pairs. 168769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis template<typename InputIt> 169e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis void insert(InputIt I, InputIt E) { 170e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis for (; I != E; ++I) 171e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis insert(*I); 172769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis } 173769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 174769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 175769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis bool erase(const KeyT &Val) { 176769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis BucketT *TheBucket; 177769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis if (!LookupBucketFor(Val, TheBucket)) 178769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis return false; // not in map. 179769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 180769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis TheBucket->second.~ValueT(); 181769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis TheBucket->first = getTombstoneKey(); 182769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis --NumEntries; 183769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis ++NumTombstones; 184769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis return true; 185769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis } 186769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis bool erase(iterator I) { 187769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis BucketT *TheBucket = &*I; 188769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis TheBucket->second.~ValueT(); 189769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis TheBucket->first = getTombstoneKey(); 190cd50e136ad7dc721822f5e6350769a37c216612dArgyrios Kyrtzidis --NumEntries; 191769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis ++NumTombstones; 192769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis return true; 1933f8212787d9bd620930817177fbba5f32659377fArgyrios Kyrtzidis } 1943f8212787d9bd620930817177fbba5f32659377fArgyrios Kyrtzidis 1953f8212787d9bd620930817177fbba5f32659377fArgyrios Kyrtzidis value_type& FindAndConstruct(const KeyT &Key) { 1963f8212787d9bd620930817177fbba5f32659377fArgyrios Kyrtzidis BucketT *TheBucket; 197c2e0db82139c70c0eac9d5c165b6bf3250af5bedArgyrios Kyrtzidis if (LookupBucketFor(Key, TheBucket)) 198769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis return *TheBucket; 199769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 200769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis return *InsertIntoBucket(Key, ValueT(), TheBucket); 201769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis } 202769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 203769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis ValueT &operator[](const KeyT &Key) { 204769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis return FindAndConstruct(Key).second; 205769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis } 206769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 207769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis DenseMap& operator=(const DenseMap& other) { 208769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis CopyFrom(other); 209e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis return *this; 210e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis } 211e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis 212769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis /// isPointerIntoBucketsArray - Return true if the specified pointer points 2139c0d6891b3ec4b0d20b8a295946c0dc5426d147cArgyrios Kyrtzidis /// somewhere into the DenseMap's array of buckets (i.e. either to a key or 2149c0d6891b3ec4b0d20b8a295946c0dc5426d147cArgyrios Kyrtzidis /// value in the DenseMap). 215769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis bool isPointerIntoBucketsArray(const void *Ptr) const { 216769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis return Ptr >= Buckets && Ptr < Buckets+NumBuckets; 217769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis } 218769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 219769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets 2209c0d6891b3ec4b0d20b8a295946c0dc5426d147cArgyrios Kyrtzidis /// array. In conjunction with the previous method, this can be used to 221769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis /// determine whether an insertion caused the DenseMap to reallocate. 222769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis const void *getPointerIntoBucketsArray() const { return Buckets; } 223769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 2249fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidisprivate: 2259fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis void CopyFrom(const DenseMap& other) { 226769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis if (NumBuckets != 0 && 227769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis (!isPodLike<KeyInfoT>::value || !isPodLike<ValueInfoT>::value)) { 228cd50e136ad7dc721822f5e6350769a37c216612dArgyrios Kyrtzidis const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 229769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { 2309c0d6891b3ec4b0d20b8a295946c0dc5426d147cArgyrios Kyrtzidis if (!KeyInfoT::isEqual(P->first, EmptyKey) && 2319c0d6891b3ec4b0d20b8a295946c0dc5426d147cArgyrios Kyrtzidis !KeyInfoT::isEqual(P->first, TombstoneKey)) 232c2e0db82139c70c0eac9d5c165b6bf3250af5bedArgyrios Kyrtzidis P->second.~ValueT(); 2339fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis P->first.~KeyT(); 2349fb9474c5b267400d4abfbff63c8b39f378235d4Argyrios Kyrtzidis } 235312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis } 236312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis 237312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis NumEntries = other.NumEntries; 238312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis NumTombstones = other.NumTombstones; 239312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis 240312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis if (NumBuckets) { 241312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis#ifndef NDEBUG 242312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis memset(Buckets, 0x5a, sizeof(BucketT)*NumBuckets); 243312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis#endif 244312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis operator delete(Buckets); 245312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis } 246312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT) * 247312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis other.NumBuckets)); 248312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis 249312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis if (isPodLike<KeyInfoT>::value && isPodLike<ValueInfoT>::value) 250312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis memcpy(Buckets, other.Buckets, other.NumBuckets * sizeof(BucketT)); 251312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis else 252312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis for (size_t i = 0; i < other.NumBuckets; ++i) { 253312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis new (&Buckets[i].first) KeyT(other.Buckets[i].first); 254312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis if (!KeyInfoT::isEqual(Buckets[i].first, getEmptyKey()) && 255312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis !KeyInfoT::isEqual(Buckets[i].first, getTombstoneKey())) 256312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis new (&Buckets[i].second) ValueT(other.Buckets[i].second); 257312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis } 258312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis NumBuckets = other.NumBuckets; 259312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis } 260312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis 261312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis BucketT *InsertIntoBucket(const KeyT &Key, const ValueT &Value, 262312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis BucketT *TheBucket) { 263312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis // If the load of the hash table is more than 3/4, or if fewer than 1/8 of 264312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis // the buckets are empty (meaning that many are filled with tombstones), 265312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis // grow the table. 266312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis // 267312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis // The later case is tricky. For example, if we had one empty bucket with 268312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis // tons of tombstones, failing lookups (e.g. for insertion) would have to 26930726c6baee1417307236e854f1474fdb3cedb98Argyrios Kyrtzidis // probe almost the entire table until it found the empty bucket. If the 27030726c6baee1417307236e854f1474fdb3cedb98Argyrios Kyrtzidis // table completely filled with tombstones, no lookup would ever succeed, 27130726c6baee1417307236e854f1474fdb3cedb98Argyrios Kyrtzidis // causing infinite loops in lookup. 27230726c6baee1417307236e854f1474fdb3cedb98Argyrios Kyrtzidis ++NumEntries; 27330726c6baee1417307236e854f1474fdb3cedb98Argyrios Kyrtzidis if (NumEntries*4 >= NumBuckets*3 || 27430726c6baee1417307236e854f1474fdb3cedb98Argyrios Kyrtzidis NumBuckets-(NumEntries+NumTombstones) < NumBuckets/8) { 27530726c6baee1417307236e854f1474fdb3cedb98Argyrios Kyrtzidis this->grow(NumBuckets * 2); 276af5800a1e287990bb547e052f257adeeae5ab476Argyrios Kyrtzidis LookupBucketFor(Key, TheBucket); 277af5800a1e287990bb547e052f257adeeae5ab476Argyrios Kyrtzidis } 278af5800a1e287990bb547e052f257adeeae5ab476Argyrios Kyrtzidis 279af5800a1e287990bb547e052f257adeeae5ab476Argyrios Kyrtzidis // If we are writing over a tombstone, remember this. 280af5800a1e287990bb547e052f257adeeae5ab476Argyrios Kyrtzidis if (!KeyInfoT::isEqual(TheBucket->first, getEmptyKey())) 281af5800a1e287990bb547e052f257adeeae5ab476Argyrios Kyrtzidis --NumTombstones; 282af5800a1e287990bb547e052f257adeeae5ab476Argyrios Kyrtzidis 283af5800a1e287990bb547e052f257adeeae5ab476Argyrios Kyrtzidis TheBucket->first = Key; 284af5800a1e287990bb547e052f257adeeae5ab476Argyrios Kyrtzidis new (&TheBucket->second) ValueT(Value); 285af5800a1e287990bb547e052f257adeeae5ab476Argyrios Kyrtzidis return TheBucket; 286cc05d511b26ac6dc80fcbcc78ac305d2755aa0b9Argyrios Kyrtzidis } 287cc05d511b26ac6dc80fcbcc78ac305d2755aa0b9Argyrios Kyrtzidis 288cc05d511b26ac6dc80fcbcc78ac305d2755aa0b9Argyrios Kyrtzidis static unsigned getHashValue(const KeyT &Val) { 289cc05d511b26ac6dc80fcbcc78ac305d2755aa0b9Argyrios Kyrtzidis return KeyInfoT::getHashValue(Val); 290cc05d511b26ac6dc80fcbcc78ac305d2755aa0b9Argyrios Kyrtzidis } 291cc05d511b26ac6dc80fcbcc78ac305d2755aa0b9Argyrios Kyrtzidis static const KeyT getEmptyKey() { 292cc05d511b26ac6dc80fcbcc78ac305d2755aa0b9Argyrios Kyrtzidis return KeyInfoT::getEmptyKey(); 293cc05d511b26ac6dc80fcbcc78ac305d2755aa0b9Argyrios Kyrtzidis } 294cc05d511b26ac6dc80fcbcc78ac305d2755aa0b9Argyrios Kyrtzidis static const KeyT getTombstoneKey() { 295cc05d511b26ac6dc80fcbcc78ac305d2755aa0b9Argyrios Kyrtzidis return KeyInfoT::getTombstoneKey(); 296183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis } 297183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis 298183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in 299183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis /// FoundBucket. If the bucket contains the key and a value, this returns 300183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis /// true, otherwise it returns a bucket with an empty marker or tombstone and 301183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis /// returns false. 302183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis bool LookupBucketFor(const KeyT &Val, BucketT *&FoundBucket) const { 303183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis unsigned BucketNo = getHashValue(Val); 304183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis unsigned ProbeAmt = 1; 305183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis BucketT *BucketsPtr = Buckets; 306183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis 307183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis // FoundTombstone - Keep track of whether we find a tombstone while probing. 308183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis BucketT *FoundTombstone = 0; 309183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis const KeyT EmptyKey = getEmptyKey(); 310183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis const KeyT TombstoneKey = getTombstoneKey(); 311183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis assert(!KeyInfoT::isEqual(Val, EmptyKey) && 312183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis !KeyInfoT::isEqual(Val, TombstoneKey) && 313183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis "Empty/Tombstone value shouldn't be inserted into map!"); 314183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis 315183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis while (1) { 316183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis BucketT *ThisBucket = BucketsPtr + (BucketNo & (NumBuckets-1)); 317183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis // Found Val's bucket? If so, return it. 318183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis if (KeyInfoT::isEqual(ThisBucket->first, Val)) { 319183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis FoundBucket = ThisBucket; 320183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis return true; 321183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis } 322183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis 323183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis // If we found an empty bucket, the key doesn't exist in the set. 324183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis // Insert it and return the default value. 325183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis if (KeyInfoT::isEqual(ThisBucket->first, EmptyKey)) { 326183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis // If we've already seen a tombstone while probing, fill it in instead 327183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis // of the empty bucket we eventually probed to. 328183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis if (FoundTombstone) ThisBucket = FoundTombstone; 329183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket; 330183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis return false; 331183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis } 332183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis 333183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis // If this is a tombstone, remember it. If Val ends up not in the map, we 334183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis // prefer to return it than something that would require more probing. 335183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis if (KeyInfoT::isEqual(ThisBucket->first, TombstoneKey) && !FoundTombstone) 336183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis FoundTombstone = ThisBucket; // Remember the first tombstone found. 337183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis 338183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis // Otherwise, it's a hash collision or a tombstone, continue quadratic 339183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis // probing. 340183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis BucketNo += ProbeAmt++; 341183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis } 342183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis } 343183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis 344183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis void init(unsigned InitBuckets) { 345183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis NumEntries = 0; 346183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis NumTombstones = 0; 347183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis NumBuckets = InitBuckets; 348183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis assert(InitBuckets && (InitBuckets & (InitBuckets-1)) == 0 && 34935bdbf40624beba3fc00cb72ab444659939c1a6bTed Kremenek "# initial buckets must be a power of two!"); 350183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*InitBuckets)); 351183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis // Initialize all the keys to EmptyKey. 352183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis const KeyT EmptyKey = getEmptyKey(); 353183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis for (unsigned i = 0; i != InitBuckets; ++i) 354183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis new (&Buckets[i].first) KeyT(EmptyKey); 355183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis } 356183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis 35735bdbf40624beba3fc00cb72ab444659939c1a6bTed Kremenek void grow(unsigned AtLeast) { 358183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis unsigned OldNumBuckets = NumBuckets; 359183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis BucketT *OldBuckets = Buckets; 360183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis 361183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis // Double the number of buckets. 362312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis while (NumBuckets <= AtLeast) 363312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis NumBuckets <<= 1; 364312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis NumTombstones = 0; 365312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*NumBuckets)); 366312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis 367312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis // Initialize all the keys to EmptyKey. 368312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis const KeyT EmptyKey = getEmptyKey(); 369312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis for (unsigned i = 0, e = NumBuckets; i != e; ++i) 370312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis new (&Buckets[i].first) KeyT(EmptyKey); 371312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis 372312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis // Insert all the old elements. 373312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis const KeyT TombstoneKey = getTombstoneKey(); 374312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) { 375312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis if (!KeyInfoT::isEqual(B->first, EmptyKey) && 376e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis !KeyInfoT::isEqual(B->first, TombstoneKey)) { 377e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis // Insert the key/value into the new table. 378e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis BucketT *DestBucket; 379e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis bool FoundVal = LookupBucketFor(B->first, DestBucket); 380e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis FoundVal = FoundVal; // silence warning. 381e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis assert(!FoundVal && "Key already in new map?"); 382e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis DestBucket->first = B->first; 383e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis new (&DestBucket->second) ValueT(B->second); 384e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis 385e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis // Free the value. 386e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis B->second.~ValueT(); 387e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis } 388e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis B->first.~KeyT(); 389e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis } 390e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis 391e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis#ifndef NDEBUG 392e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis memset(OldBuckets, 0x5a, sizeof(BucketT)*OldNumBuckets); 393e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis#endif 394e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis // Free the old table. 395e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis operator delete(OldBuckets); 396e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis } 397e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis 398e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis void shrink_and_clear() { 399e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis unsigned OldNumBuckets = NumBuckets; 400e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis BucketT *OldBuckets = Buckets; 401e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis 402e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis // Reduce the number of buckets. 403e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis NumBuckets = NumEntries > 32 ? 1 << (Log2_32_Ceil(NumEntries) + 1) 404e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis : 64; 405e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis NumTombstones = 0; 406e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*NumBuckets)); 407e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis 408e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis // Initialize all the keys to EmptyKey. 409e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis const KeyT EmptyKey = getEmptyKey(); 410e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis for (unsigned i = 0, e = NumBuckets; i != e; ++i) 411e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis new (&Buckets[i].first) KeyT(EmptyKey); 412e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis 413e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis // Free the old buckets. 414e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis const KeyT TombstoneKey = getTombstoneKey(); 415e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) { 416e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis if (!KeyInfoT::isEqual(B->first, EmptyKey) && 417e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis !KeyInfoT::isEqual(B->first, TombstoneKey)) { 418e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis // Free the value. 419e1bfb7ae0dd0762c88e1fd94746e973c37f2e04eArgyrios Kyrtzidis B->second.~ValueT(); 4209be6e7ce5788e50c62d40c59b0bbc2ea423683f7Ted Kremenek } 4219be6e7ce5788e50c62d40c59b0bbc2ea423683f7Ted Kremenek B->first.~KeyT(); 4229be6e7ce5788e50c62d40c59b0bbc2ea423683f7Ted Kremenek } 4239be6e7ce5788e50c62d40c59b0bbc2ea423683f7Ted Kremenek 4249be6e7ce5788e50c62d40c59b0bbc2ea423683f7Ted Kremenek#ifndef NDEBUG 4259be6e7ce5788e50c62d40c59b0bbc2ea423683f7Ted Kremenek memset(OldBuckets, 0x5a, sizeof(BucketT)*OldNumBuckets); 4269be6e7ce5788e50c62d40c59b0bbc2ea423683f7Ted Kremenek#endif 4279be6e7ce5788e50c62d40c59b0bbc2ea423683f7Ted Kremenek // Free the old table. 4289be6e7ce5788e50c62d40c59b0bbc2ea423683f7Ted Kremenek operator delete(OldBuckets); 429769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 430769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis NumEntries = 0; 431769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis } 432769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis}; 433769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 434769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidistemplate<typename KeyT, typename ValueT, 435769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis typename KeyInfoT, typename ValueInfoT, bool IsConst> 436769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidisclass DenseMapIterator { 437769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis typedef std::pair<KeyT, ValueT> Bucket; 438769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis typedef DenseMapIterator<KeyT, ValueT, 439769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis KeyInfoT, ValueInfoT, true> ConstIterator; 440769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, ValueInfoT, true>; 441769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidispublic: 442769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis typedef ptrdiff_t difference_type; 443769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis typedef typename conditional<IsConst, const Bucket, Bucket>::type value_type; 444769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis typedef value_type *pointer; 445769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis typedef value_type &reference; 446769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis typedef std::forward_iterator_tag iterator_category; 447769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidisprivate: 448769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis pointer Ptr, End; 449769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidispublic: 450769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis DenseMapIterator() : Ptr(0), End(0) {} 451769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 452769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis DenseMapIterator(pointer Pos, pointer E) : Ptr(Pos), End(E) { 453769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis AdvancePastEmptyBuckets(); 454769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis } 455769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 456769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis // If IsConst is true this is a converting constructor from iterator to 457769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis // const_iterator and the default copy constructor is used. 458769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis // Otherwise this is a copy constructor for iterator. 459769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis DenseMapIterator(const DenseMapIterator<KeyT, ValueT, 460769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis KeyInfoT, ValueInfoT, false>& I) 461769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis : Ptr(I.Ptr), End(I.End) {} 462769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis 463769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis reference operator*() const { 464769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis return *Ptr; 465769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis } 466769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis pointer operator->() const { 467769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis return Ptr; 468769ce3e93ad35bd9ac28e4d8b8f035ae4fd9a5b5Argyrios Kyrtzidis } 469312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis 470312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis bool operator==(const ConstIterator &RHS) const { 471312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis return Ptr == RHS.operator->(); 472312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis } 47330726c6baee1417307236e854f1474fdb3cedb98Argyrios Kyrtzidis bool operator!=(const ConstIterator &RHS) const { 47430726c6baee1417307236e854f1474fdb3cedb98Argyrios Kyrtzidis return Ptr != RHS.operator->(); 47530726c6baee1417307236e854f1474fdb3cedb98Argyrios Kyrtzidis } 47630726c6baee1417307236e854f1474fdb3cedb98Argyrios Kyrtzidis 477af5800a1e287990bb547e052f257adeeae5ab476Argyrios Kyrtzidis inline DenseMapIterator& operator++() { // Preincrement 478af5800a1e287990bb547e052f257adeeae5ab476Argyrios Kyrtzidis ++Ptr; 479af5800a1e287990bb547e052f257adeeae5ab476Argyrios Kyrtzidis AdvancePastEmptyBuckets(); 480af5800a1e287990bb547e052f257adeeae5ab476Argyrios Kyrtzidis return *this; 481cc05d511b26ac6dc80fcbcc78ac305d2755aa0b9Argyrios Kyrtzidis } 482cc05d511b26ac6dc80fcbcc78ac305d2755aa0b9Argyrios Kyrtzidis DenseMapIterator operator++(int) { // Postincrement 483cc05d511b26ac6dc80fcbcc78ac305d2755aa0b9Argyrios Kyrtzidis DenseMapIterator tmp = *this; ++*this; return tmp; 484cc05d511b26ac6dc80fcbcc78ac305d2755aa0b9Argyrios Kyrtzidis } 485cc05d511b26ac6dc80fcbcc78ac305d2755aa0b9Argyrios Kyrtzidis 486183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidisprivate: 487183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis void AdvancePastEmptyBuckets() { 488183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis const KeyT Empty = KeyInfoT::getEmptyKey(); 489183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis const KeyT Tombstone = KeyInfoT::getTombstoneKey(); 490183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis 491183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis while (Ptr != End && 492183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis (KeyInfoT::isEqual(Ptr->first, Empty) || 493183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis KeyInfoT::isEqual(Ptr->first, Tombstone))) 494183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis ++Ptr; 495183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis } 496183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis}; 497183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis 498183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis} // end namespace llvm 499183ff98f425d470c2a0276880aaf43496c9dad14Argyrios Kyrtzidis 500312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis#endif 501312dbec867f6b8d6b86fd562c53352cd4db27468Argyrios Kyrtzidis