1894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===- llvm/ADT/DenseMap.h - Dense probed hash table ------------*- C++ -*-===// 2894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 3894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The LLVM Compiler Infrastructure 4894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 5894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file is distributed under the University of Illinois Open Source 6894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// License. See LICENSE.TXT for details. 7894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 8894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 9894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 10894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file defines the DenseMap class. 11894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 12894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 13894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 14894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#ifndef LLVM_ADT_DENSEMAP_H 15894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#define LLVM_ADT_DENSEMAP_H 16894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 17894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/MathExtras.h" 18894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/PointerLikeTypeTraits.h" 19894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/type_traits.h" 20894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/DenseMapInfo.h" 2119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include <algorithm> 22894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include <iterator> 23894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include <new> 24894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include <utility> 25894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include <cassert> 26894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include <cstddef> 27894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include <cstring> 28894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 29894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumannamespace llvm { 30894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 31894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate<typename KeyT, typename ValueT, 32894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typename KeyInfoT = DenseMapInfo<KeyT>, 33894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typename ValueInfoT = DenseMapInfo<ValueT>, bool IsConst = false> 34894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass DenseMapIterator; 35894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 36894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate<typename KeyT, typename ValueT, 37894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typename KeyInfoT = DenseMapInfo<KeyT>, 38894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typename ValueInfoT = DenseMapInfo<ValueT> > 39894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass DenseMap { 40894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef std::pair<KeyT, ValueT> BucketT; 41894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned NumBuckets; 42894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BucketT *Buckets; 43894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 44894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned NumEntries; 45894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned NumTombstones; 46894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanpublic: 47894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef KeyT key_type; 48894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef ValueT mapped_type; 49894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef BucketT value_type; 50894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 51894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DenseMap(const DenseMap &other) { 52894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NumBuckets = 0; 53894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman CopyFrom(other); 54894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 55894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 5619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman explicit DenseMap(unsigned NumInitBuckets = 0) { 57894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman init(NumInitBuckets); 58894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 59894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 60894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman template<typename InputIt> 61894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DenseMap(const InputIt &I, const InputIt &E) { 6219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman init(NextPowerOf2(std::distance(I, E))); 63894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman insert(I, E); 64894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 65894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 66894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ~DenseMap() { 67894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 68894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { 69894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!KeyInfoT::isEqual(P->first, EmptyKey) && 70894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman !KeyInfoT::isEqual(P->first, TombstoneKey)) 71894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman P->second.~ValueT(); 72894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman P->first.~KeyT(); 73894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 74894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#ifndef NDEBUG 7519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (NumBuckets) 7619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman memset((void*)Buckets, 0x5a, sizeof(BucketT)*NumBuckets); 77894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#endif 78894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman operator delete(Buckets); 79894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 80894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 81894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef DenseMapIterator<KeyT, ValueT, KeyInfoT> iterator; 82894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef DenseMapIterator<KeyT, ValueT, 83894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman KeyInfoT, ValueInfoT, true> const_iterator; 84894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline iterator begin() { 85894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // When the map is empty, avoid the overhead of AdvancePastEmptyBuckets(). 86894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return empty() ? end() : iterator(Buckets, Buckets+NumBuckets); 87894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 88894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline iterator end() { 89894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return iterator(Buckets+NumBuckets, Buckets+NumBuckets); 90894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 91894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline const_iterator begin() const { 92894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return empty() ? end() : const_iterator(Buckets, Buckets+NumBuckets); 93894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 94894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline const_iterator end() const { 95894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return const_iterator(Buckets+NumBuckets, Buckets+NumBuckets); 96894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 97894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 98894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool empty() const { return NumEntries == 0; } 99894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned size() const { return NumEntries; } 100894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 101894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// Grow the densemap so that it has at least Size buckets. Does not shrink 10219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void resize(size_t Size) { 10319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Size > NumBuckets) 10419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman grow(Size); 10519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 106894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 107894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void clear() { 108894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (NumEntries == 0 && NumTombstones == 0) return; 109894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 110894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If the capacity of the array is huge, and the # elements used is small, 111894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // shrink the array. 112894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (NumEntries * 4 < NumBuckets && NumBuckets > 64) { 113894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman shrink_and_clear(); 114894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return; 115894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 116894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 117894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 118894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { 119894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!KeyInfoT::isEqual(P->first, EmptyKey)) { 120894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!KeyInfoT::isEqual(P->first, TombstoneKey)) { 121894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman P->second.~ValueT(); 122894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman --NumEntries; 123894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 124894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman P->first = EmptyKey; 125894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 126894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 127894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(NumEntries == 0 && "Node count imbalance!"); 128894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NumTombstones = 0; 129894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 130894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 131894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// count - Return true if the specified key is in the map. 132894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool count(const KeyT &Val) const { 133894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BucketT *TheBucket; 134894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return LookupBucketFor(Val, TheBucket); 135894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 136894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 137894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman iterator find(const KeyT &Val) { 138894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BucketT *TheBucket; 139894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (LookupBucketFor(Val, TheBucket)) 140894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return iterator(TheBucket, Buckets+NumBuckets); 141894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return end(); 142894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 143894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const_iterator find(const KeyT &Val) const { 144894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BucketT *TheBucket; 145894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (LookupBucketFor(Val, TheBucket)) 146894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return const_iterator(TheBucket, Buckets+NumBuckets); 147894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return end(); 148894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 149894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 150894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// lookup - Return the entry for the specified key, or a default 151894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// constructed value if no such entry exists. 152894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ValueT lookup(const KeyT &Val) const { 153894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BucketT *TheBucket; 154894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (LookupBucketFor(Val, TheBucket)) 155894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return TheBucket->second; 156894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return ValueT(); 157894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 158894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 159894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Inserts key,value pair into the map if the key isn't already in the map. 160894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If the key is already in the map, it returns false and doesn't update the 161894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // value. 162894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { 163894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BucketT *TheBucket; 164894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (LookupBucketFor(KV.first, TheBucket)) 165894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return std::make_pair(iterator(TheBucket, Buckets+NumBuckets), 166894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman false); // Already in map. 167894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 168894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Otherwise, insert the new element. 169894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TheBucket = InsertIntoBucket(KV.first, KV.second, TheBucket); 170894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return std::make_pair(iterator(TheBucket, Buckets+NumBuckets), 171894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman true); 172894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 173894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 174894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// insert - Range insertion of pairs. 175894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman template<typename InputIt> 176894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void insert(InputIt I, InputIt E) { 177894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (; I != E; ++I) 178894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman insert(*I); 179894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 180894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 181894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 182894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool erase(const KeyT &Val) { 183894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BucketT *TheBucket; 184894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!LookupBucketFor(Val, TheBucket)) 185894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; // not in map. 186894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 187894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TheBucket->second.~ValueT(); 188894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TheBucket->first = getTombstoneKey(); 189894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman --NumEntries; 190894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++NumTombstones; 191894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 192894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 19319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void erase(iterator I) { 194894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BucketT *TheBucket = &*I; 195894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TheBucket->second.~ValueT(); 196894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TheBucket->first = getTombstoneKey(); 197894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman --NumEntries; 198894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++NumTombstones; 199894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 200894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 201894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void swap(DenseMap& RHS) { 202894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::swap(NumBuckets, RHS.NumBuckets); 203894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::swap(Buckets, RHS.Buckets); 204894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::swap(NumEntries, RHS.NumEntries); 205894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::swap(NumTombstones, RHS.NumTombstones); 206894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 207894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 208894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman value_type& FindAndConstruct(const KeyT &Key) { 209894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BucketT *TheBucket; 210894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (LookupBucketFor(Key, TheBucket)) 211894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return *TheBucket; 212894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 213894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return *InsertIntoBucket(Key, ValueT(), TheBucket); 214894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 215894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 216894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ValueT &operator[](const KeyT &Key) { 217894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return FindAndConstruct(Key).second; 218894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 219894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 220894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DenseMap& operator=(const DenseMap& other) { 221894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman CopyFrom(other); 222894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return *this; 223894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 224894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 225894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// isPointerIntoBucketsArray - Return true if the specified pointer points 226894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// somewhere into the DenseMap's array of buckets (i.e. either to a key or 227894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// value in the DenseMap). 228894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isPointerIntoBucketsArray(const void *Ptr) const { 229894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Ptr >= Buckets && Ptr < Buckets+NumBuckets; 230894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 231894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 232894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets 233894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// array. In conjunction with the previous method, this can be used to 234894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// determine whether an insertion caused the DenseMap to reallocate. 235894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const void *getPointerIntoBucketsArray() const { return Buckets; } 236894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 237894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanprivate: 238894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void CopyFrom(const DenseMap& other) { 239894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (NumBuckets != 0 && 240894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman (!isPodLike<KeyInfoT>::value || !isPodLike<ValueInfoT>::value)) { 241894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 242894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { 243894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!KeyInfoT::isEqual(P->first, EmptyKey) && 244894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman !KeyInfoT::isEqual(P->first, TombstoneKey)) 245894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman P->second.~ValueT(); 246894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman P->first.~KeyT(); 247894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 248894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 249894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 250894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NumEntries = other.NumEntries; 251894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NumTombstones = other.NumTombstones; 252894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 253894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (NumBuckets) { 254894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#ifndef NDEBUG 25519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman memset((void*)Buckets, 0x5a, sizeof(BucketT)*NumBuckets); 256894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#endif 257894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman operator delete(Buckets); 258894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 25919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 26019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NumBuckets = other.NumBuckets; 26119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 26219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (NumBuckets == 0) { 26319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Buckets = 0; 26419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 26519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 26619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 26719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT) * NumBuckets)); 268894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 269894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isPodLike<KeyInfoT>::value && isPodLike<ValueInfoT>::value) 27019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman memcpy(Buckets, other.Buckets, NumBuckets * sizeof(BucketT)); 271894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else 27219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (size_t i = 0; i < NumBuckets; ++i) { 273894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman new (&Buckets[i].first) KeyT(other.Buckets[i].first); 274894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!KeyInfoT::isEqual(Buckets[i].first, getEmptyKey()) && 275894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman !KeyInfoT::isEqual(Buckets[i].first, getTombstoneKey())) 276894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman new (&Buckets[i].second) ValueT(other.Buckets[i].second); 277894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 278894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 279894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 280894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BucketT *InsertIntoBucket(const KeyT &Key, const ValueT &Value, 281894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BucketT *TheBucket) { 282894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If the load of the hash table is more than 3/4, or if fewer than 1/8 of 283894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // the buckets are empty (meaning that many are filled with tombstones), 284894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // grow the table. 285894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // 286894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // The later case is tricky. For example, if we had one empty bucket with 287894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // tons of tombstones, failing lookups (e.g. for insertion) would have to 288894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // probe almost the entire table until it found the empty bucket. If the 289894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // table completely filled with tombstones, no lookup would ever succeed, 290894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // causing infinite loops in lookup. 291894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++NumEntries; 29219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (NumEntries*4 >= NumBuckets*3) { 293894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman this->grow(NumBuckets * 2); 294894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LookupBucketFor(Key, TheBucket); 295894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 29619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (NumBuckets-(NumEntries+NumTombstones) < NumBuckets/8) { 29719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman this->grow(NumBuckets); 29819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LookupBucketFor(Key, TheBucket); 29919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 300894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 301894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If we are writing over a tombstone, remember this. 302894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!KeyInfoT::isEqual(TheBucket->first, getEmptyKey())) 303894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman --NumTombstones; 304894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 305894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TheBucket->first = Key; 306894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman new (&TheBucket->second) ValueT(Value); 307894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return TheBucket; 308894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 309894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 310894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static unsigned getHashValue(const KeyT &Val) { 311894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return KeyInfoT::getHashValue(Val); 312894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 313894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static const KeyT getEmptyKey() { 314894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return KeyInfoT::getEmptyKey(); 315894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 316894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static const KeyT getTombstoneKey() { 317894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return KeyInfoT::getTombstoneKey(); 318894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 319894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 320894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in 321894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// FoundBucket. If the bucket contains the key and a value, this returns 322894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// true, otherwise it returns a bucket with an empty marker or tombstone and 323894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// returns false. 324894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool LookupBucketFor(const KeyT &Val, BucketT *&FoundBucket) const { 325894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned BucketNo = getHashValue(Val); 326894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned ProbeAmt = 1; 327894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BucketT *BucketsPtr = Buckets; 328894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 32919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (NumBuckets == 0) { 33019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman FoundBucket = 0; 33119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 33219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 33319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 334894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // FoundTombstone - Keep track of whether we find a tombstone while probing. 335894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BucketT *FoundTombstone = 0; 336894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const KeyT EmptyKey = getEmptyKey(); 337894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const KeyT TombstoneKey = getTombstoneKey(); 338894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(!KeyInfoT::isEqual(Val, EmptyKey) && 339894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman !KeyInfoT::isEqual(Val, TombstoneKey) && 340894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "Empty/Tombstone value shouldn't be inserted into map!"); 341894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 342894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (1) { 343894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BucketT *ThisBucket = BucketsPtr + (BucketNo & (NumBuckets-1)); 344894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Found Val's bucket? If so, return it. 345894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (KeyInfoT::isEqual(ThisBucket->first, Val)) { 346894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman FoundBucket = ThisBucket; 347894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 348894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 349894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 350894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If we found an empty bucket, the key doesn't exist in the set. 351894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Insert it and return the default value. 352894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (KeyInfoT::isEqual(ThisBucket->first, EmptyKey)) { 353894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If we've already seen a tombstone while probing, fill it in instead 354894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // of the empty bucket we eventually probed to. 355894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (FoundTombstone) ThisBucket = FoundTombstone; 356894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket; 357894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 358894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 359894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 360894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If this is a tombstone, remember it. If Val ends up not in the map, we 361894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // prefer to return it than something that would require more probing. 362894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (KeyInfoT::isEqual(ThisBucket->first, TombstoneKey) && !FoundTombstone) 363894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman FoundTombstone = ThisBucket; // Remember the first tombstone found. 364894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 365894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Otherwise, it's a hash collision or a tombstone, continue quadratic 366894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // probing. 367894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BucketNo += ProbeAmt++; 368894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 369894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 370894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 371894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void init(unsigned InitBuckets) { 372894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NumEntries = 0; 373894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NumTombstones = 0; 374894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NumBuckets = InitBuckets; 37519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 37619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (InitBuckets == 0) { 37719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Buckets = 0; 37819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 37919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 38019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 381894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(InitBuckets && (InitBuckets & (InitBuckets-1)) == 0 && 382894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "# initial buckets must be a power of two!"); 383894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*InitBuckets)); 384894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Initialize all the keys to EmptyKey. 385894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const KeyT EmptyKey = getEmptyKey(); 386894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0; i != InitBuckets; ++i) 387894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman new (&Buckets[i].first) KeyT(EmptyKey); 388894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 389894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 390894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void grow(unsigned AtLeast) { 391894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned OldNumBuckets = NumBuckets; 392894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BucketT *OldBuckets = Buckets; 393894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 39419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (NumBuckets < 64) 39519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NumBuckets = 64; 39619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 397894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Double the number of buckets. 398894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (NumBuckets < AtLeast) 399894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NumBuckets <<= 1; 400894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NumTombstones = 0; 401894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*NumBuckets)); 402894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 403894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Initialize all the keys to EmptyKey. 404894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const KeyT EmptyKey = getEmptyKey(); 405894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = NumBuckets; i != e; ++i) 406894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman new (&Buckets[i].first) KeyT(EmptyKey); 407894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 408894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Insert all the old elements. 409894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const KeyT TombstoneKey = getTombstoneKey(); 410894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) { 411894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!KeyInfoT::isEqual(B->first, EmptyKey) && 412894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman !KeyInfoT::isEqual(B->first, TombstoneKey)) { 413894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Insert the key/value into the new table. 414894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BucketT *DestBucket; 415894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool FoundVal = LookupBucketFor(B->first, DestBucket); 41619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman (void)FoundVal; // silence warning. 417894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(!FoundVal && "Key already in new map?"); 418894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DestBucket->first = B->first; 419894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman new (&DestBucket->second) ValueT(B->second); 420894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 421894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Free the value. 422894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman B->second.~ValueT(); 423894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 424894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman B->first.~KeyT(); 425894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 426894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 427894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#ifndef NDEBUG 42819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (OldNumBuckets) 42919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman memset((void*)OldBuckets, 0x5a, sizeof(BucketT)*OldNumBuckets); 430894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#endif 431894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Free the old table. 432894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman operator delete(OldBuckets); 433894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 434894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 435894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void shrink_and_clear() { 436894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned OldNumBuckets = NumBuckets; 437894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BucketT *OldBuckets = Buckets; 438894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 439894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Reduce the number of buckets. 440894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NumBuckets = NumEntries > 32 ? 1 << (Log2_32_Ceil(NumEntries) + 1) 441894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman : 64; 442894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NumTombstones = 0; 443894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*NumBuckets)); 444894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 445894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Initialize all the keys to EmptyKey. 446894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const KeyT EmptyKey = getEmptyKey(); 447894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = NumBuckets; i != e; ++i) 448894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman new (&Buckets[i].first) KeyT(EmptyKey); 449894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 450894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Free the old buckets. 451894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const KeyT TombstoneKey = getTombstoneKey(); 452894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) { 453894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!KeyInfoT::isEqual(B->first, EmptyKey) && 454894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman !KeyInfoT::isEqual(B->first, TombstoneKey)) { 455894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Free the value. 456894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman B->second.~ValueT(); 457894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 458894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman B->first.~KeyT(); 459894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 460894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 461894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#ifndef NDEBUG 46219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman memset((void*)OldBuckets, 0x5a, sizeof(BucketT)*OldNumBuckets); 463894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#endif 464894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Free the old table. 465894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman operator delete(OldBuckets); 466894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 467894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NumEntries = 0; 468894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 46919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 47019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanpublic: 47119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Return the approximate size (in bytes) of the actual map. 47219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// This is just the raw memory used by DenseMap. 47319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// If entries are pointers to objects, the size of the referenced objects 47419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// are not included. 47519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman size_t getMemorySize() const { 47619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return NumBuckets * sizeof(BucketT); 47719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 478894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman}; 479894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 480894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantemplate<typename KeyT, typename ValueT, 481894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typename KeyInfoT, typename ValueInfoT, bool IsConst> 482894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass DenseMapIterator { 483894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef std::pair<KeyT, ValueT> Bucket; 484894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef DenseMapIterator<KeyT, ValueT, 485894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman KeyInfoT, ValueInfoT, true> ConstIterator; 486894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, ValueInfoT, true>; 487894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanpublic: 488894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef ptrdiff_t difference_type; 489894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef typename conditional<IsConst, const Bucket, Bucket>::type value_type; 490894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef value_type *pointer; 491894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef value_type &reference; 492894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef std::forward_iterator_tag iterator_category; 493894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanprivate: 494894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman pointer Ptr, End; 495894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanpublic: 496894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DenseMapIterator() : Ptr(0), End(0) {} 497894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 498894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DenseMapIterator(pointer Pos, pointer E) : Ptr(Pos), End(E) { 499894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AdvancePastEmptyBuckets(); 500894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 501894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 502894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If IsConst is true this is a converting constructor from iterator to 503894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // const_iterator and the default copy constructor is used. 504894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Otherwise this is a copy constructor for iterator. 505894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DenseMapIterator(const DenseMapIterator<KeyT, ValueT, 506894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman KeyInfoT, ValueInfoT, false>& I) 507894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman : Ptr(I.Ptr), End(I.End) {} 508894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 509894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman reference operator*() const { 510894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return *Ptr; 511894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 512894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman pointer operator->() const { 513894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Ptr; 514894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 515894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 516894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool operator==(const ConstIterator &RHS) const { 517894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Ptr == RHS.operator->(); 518894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 519894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool operator!=(const ConstIterator &RHS) const { 520894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Ptr != RHS.operator->(); 521894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 522894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 523894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman inline DenseMapIterator& operator++() { // Preincrement 524894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++Ptr; 525894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AdvancePastEmptyBuckets(); 526894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return *this; 527894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 528894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DenseMapIterator operator++(int) { // Postincrement 529894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DenseMapIterator tmp = *this; ++*this; return tmp; 530894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 531894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 532894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanprivate: 533894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void AdvancePastEmptyBuckets() { 534894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const KeyT Empty = KeyInfoT::getEmptyKey(); 535894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const KeyT Tombstone = KeyInfoT::getTombstoneKey(); 536894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 537894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (Ptr != End && 538894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman (KeyInfoT::isEqual(Ptr->first, Empty) || 539894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman KeyInfoT::isEqual(Ptr->first, Tombstone))) 540894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++Ptr; 541894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 542894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman}; 54319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 54419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumantemplate<typename KeyT, typename ValueT, typename KeyInfoT, typename ValueInfoT> 54519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanstatic inline size_t 54619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumancapacity_in_bytes(const DenseMap<KeyT, ValueT, KeyInfoT, ValueInfoT> &X) { 54719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return X.getMemorySize(); 54819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 549894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 550894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} // end namespace llvm 551894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 552894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#endif 553