1193323Sed//===- llvm/ADT/DenseMap.h - Dense probed hash table ------------*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file defines the DenseMap class. 11193323Sed// 12193323Sed//===----------------------------------------------------------------------===// 13193323Sed 14193323Sed#ifndef LLVM_ADT_DENSEMAP_H 15193323Sed#define LLVM_ADT_DENSEMAP_H 16193323Sed 17252723Sdim#include "llvm/ADT/DenseMapInfo.h" 18252723Sdim#include "llvm/Support/AlignOf.h" 19245431Sdim#include "llvm/Support/Compiler.h" 20199481Srdivacky#include "llvm/Support/MathExtras.h" 21193323Sed#include "llvm/Support/PointerLikeTypeTraits.h" 22199481Srdivacky#include "llvm/Support/type_traits.h" 23218893Sdim#include <algorithm> 24193323Sed#include <cassert> 25245431Sdim#include <climits> 26210299Sed#include <cstddef> 27198090Srdivacky#include <cstring> 28252723Sdim#include <iterator> 29252723Sdim#include <new> 30252723Sdim#include <utility> 31193323Sed 32193323Sednamespace llvm { 33193323Sed 34193323Sedtemplate<typename KeyT, typename ValueT, 35193323Sed typename KeyInfoT = DenseMapInfo<KeyT>, 36235633Sdim bool IsConst = false> 37193323Sedclass DenseMapIterator; 38193323Sed 39245431Sdimtemplate<typename DerivedT, 40245431Sdim typename KeyT, typename ValueT, typename KeyInfoT> 41245431Sdimclass DenseMapBase { 42245431Sdimprotected: 43193323Sed typedef std::pair<KeyT, ValueT> BucketT; 44193323Sed 45193323Sedpublic: 46193323Sed typedef KeyT key_type; 47193323Sed typedef ValueT mapped_type; 48193323Sed typedef BucketT value_type; 49193323Sed 50193323Sed typedef DenseMapIterator<KeyT, ValueT, KeyInfoT> iterator; 51199481Srdivacky typedef DenseMapIterator<KeyT, ValueT, 52235633Sdim KeyInfoT, true> const_iterator; 53193323Sed inline iterator begin() { 54208599Srdivacky // When the map is empty, avoid the overhead of AdvancePastEmptyBuckets(). 55245431Sdim return empty() ? end() : iterator(getBuckets(), getBucketsEnd()); 56193323Sed } 57193323Sed inline iterator end() { 58245431Sdim return iterator(getBucketsEnd(), getBucketsEnd(), true); 59193323Sed } 60193323Sed inline const_iterator begin() const { 61245431Sdim return empty() ? end() : const_iterator(getBuckets(), getBucketsEnd()); 62193323Sed } 63193323Sed inline const_iterator end() const { 64245431Sdim return const_iterator(getBucketsEnd(), getBucketsEnd(), true); 65193323Sed } 66193323Sed 67263509Sdim bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const { 68263509Sdim return getNumEntries() == 0; 69263509Sdim } 70245431Sdim unsigned size() const { return getNumEntries(); } 71193323Sed 72193323Sed /// Grow the densemap so that it has at least Size buckets. Does not shrink 73221345Sdim void resize(size_t Size) { 74245431Sdim if (Size > getNumBuckets()) 75221345Sdim grow(Size); 76221345Sdim } 77193323Sed 78193323Sed void clear() { 79245431Sdim if (getNumEntries() == 0 && getNumTombstones() == 0) return; 80252723Sdim 81193323Sed // If the capacity of the array is huge, and the # elements used is small, 82193323Sed // shrink the array. 83245431Sdim if (getNumEntries() * 4 < getNumBuckets() && getNumBuckets() > 64) { 84193323Sed shrink_and_clear(); 85193323Sed return; 86193323Sed } 87193323Sed 88193323Sed const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 89245431Sdim for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) { 90193323Sed if (!KeyInfoT::isEqual(P->first, EmptyKey)) { 91193323Sed if (!KeyInfoT::isEqual(P->first, TombstoneKey)) { 92193323Sed P->second.~ValueT(); 93245431Sdim decrementNumEntries(); 94193323Sed } 95193323Sed P->first = EmptyKey; 96193323Sed } 97193323Sed } 98245431Sdim assert(getNumEntries() == 0 && "Node count imbalance!"); 99245431Sdim setNumTombstones(0); 100193323Sed } 101193323Sed 102193323Sed /// count - Return true if the specified key is in the map. 103193323Sed bool count(const KeyT &Val) const { 104245431Sdim const BucketT *TheBucket; 105193323Sed return LookupBucketFor(Val, TheBucket); 106193323Sed } 107193323Sed 108193323Sed iterator find(const KeyT &Val) { 109193323Sed BucketT *TheBucket; 110193323Sed if (LookupBucketFor(Val, TheBucket)) 111245431Sdim return iterator(TheBucket, getBucketsEnd(), true); 112193323Sed return end(); 113193323Sed } 114193323Sed const_iterator find(const KeyT &Val) const { 115245431Sdim const BucketT *TheBucket; 116193323Sed if (LookupBucketFor(Val, TheBucket)) 117245431Sdim return const_iterator(TheBucket, getBucketsEnd(), true); 118193323Sed return end(); 119193323Sed } 120193323Sed 121235633Sdim /// Alternate version of find() which allows a different, and possibly 122235633Sdim /// less expensive, key type. 123235633Sdim /// The DenseMapInfo is responsible for supplying methods 124235633Sdim /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key 125235633Sdim /// type used. 126235633Sdim template<class LookupKeyT> 127235633Sdim iterator find_as(const LookupKeyT &Val) { 128235633Sdim BucketT *TheBucket; 129235633Sdim if (LookupBucketFor(Val, TheBucket)) 130245431Sdim return iterator(TheBucket, getBucketsEnd(), true); 131235633Sdim return end(); 132235633Sdim } 133235633Sdim template<class LookupKeyT> 134235633Sdim const_iterator find_as(const LookupKeyT &Val) const { 135245431Sdim const BucketT *TheBucket; 136235633Sdim if (LookupBucketFor(Val, TheBucket)) 137245431Sdim return const_iterator(TheBucket, getBucketsEnd(), true); 138235633Sdim return end(); 139235633Sdim } 140235633Sdim 141193323Sed /// lookup - Return the entry for the specified key, or a default 142193323Sed /// constructed value if no such entry exists. 143193323Sed ValueT lookup(const KeyT &Val) const { 144245431Sdim const BucketT *TheBucket; 145193323Sed if (LookupBucketFor(Val, TheBucket)) 146193323Sed return TheBucket->second; 147193323Sed return ValueT(); 148193323Sed } 149193323Sed 150198090Srdivacky // Inserts key,value pair into the map if the key isn't already in the map. 151198090Srdivacky // If the key is already in the map, it returns false and doesn't update the 152198090Srdivacky // value. 153193323Sed std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { 154193323Sed BucketT *TheBucket; 155193323Sed if (LookupBucketFor(KV.first, TheBucket)) 156245431Sdim return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), 157193323Sed false); // Already in map. 158193323Sed 159193323Sed // Otherwise, insert the new element. 160193323Sed TheBucket = InsertIntoBucket(KV.first, KV.second, TheBucket); 161245431Sdim return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), true); 162193323Sed } 163193323Sed 164252723Sdim#if LLVM_HAS_RVALUE_REFERENCES 165252723Sdim // Inserts key,value pair into the map if the key isn't already in the map. 166252723Sdim // If the key is already in the map, it returns false and doesn't update the 167252723Sdim // value. 168252723Sdim std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) { 169252723Sdim BucketT *TheBucket; 170252723Sdim if (LookupBucketFor(KV.first, TheBucket)) 171252723Sdim return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), 172252723Sdim false); // Already in map. 173252723Sdim 174252723Sdim // Otherwise, insert the new element. 175252723Sdim TheBucket = InsertIntoBucket(std::move(KV.first), 176252723Sdim std::move(KV.second), 177252723Sdim TheBucket); 178252723Sdim return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), true); 179252723Sdim } 180252723Sdim#endif 181252723Sdim 182193323Sed /// insert - Range insertion of pairs. 183193323Sed template<typename InputIt> 184193323Sed void insert(InputIt I, InputIt E) { 185193323Sed for (; I != E; ++I) 186193323Sed insert(*I); 187193323Sed } 188193323Sed 189193323Sed 190193323Sed bool erase(const KeyT &Val) { 191193323Sed BucketT *TheBucket; 192193323Sed if (!LookupBucketFor(Val, TheBucket)) 193193323Sed return false; // not in map. 194193323Sed 195193323Sed TheBucket->second.~ValueT(); 196193323Sed TheBucket->first = getTombstoneKey(); 197245431Sdim decrementNumEntries(); 198245431Sdim incrementNumTombstones(); 199193323Sed return true; 200193323Sed } 201212904Sdim void erase(iterator I) { 202193323Sed BucketT *TheBucket = &*I; 203193323Sed TheBucket->second.~ValueT(); 204193323Sed TheBucket->first = getTombstoneKey(); 205245431Sdim decrementNumEntries(); 206245431Sdim incrementNumTombstones(); 207193323Sed } 208193323Sed 209193323Sed value_type& FindAndConstruct(const KeyT &Key) { 210193323Sed BucketT *TheBucket; 211193323Sed if (LookupBucketFor(Key, TheBucket)) 212193323Sed return *TheBucket; 213193323Sed 214193323Sed return *InsertIntoBucket(Key, ValueT(), TheBucket); 215193323Sed } 216193323Sed 217193323Sed ValueT &operator[](const KeyT &Key) { 218193323Sed return FindAndConstruct(Key).second; 219193323Sed } 220193323Sed 221252723Sdim#if LLVM_HAS_RVALUE_REFERENCES 222245431Sdim value_type& FindAndConstruct(KeyT &&Key) { 223245431Sdim BucketT *TheBucket; 224245431Sdim if (LookupBucketFor(Key, TheBucket)) 225245431Sdim return *TheBucket; 226245431Sdim 227263509Sdim return *InsertIntoBucket(std::move(Key), ValueT(), TheBucket); 228193323Sed } 229193323Sed 230245431Sdim ValueT &operator[](KeyT &&Key) { 231263509Sdim return FindAndConstruct(std::move(Key)).second; 232245431Sdim } 233245431Sdim#endif 234245431Sdim 235193323Sed /// isPointerIntoBucketsArray - Return true if the specified pointer points 236193323Sed /// somewhere into the DenseMap's array of buckets (i.e. either to a key or 237193323Sed /// value in the DenseMap). 238193323Sed bool isPointerIntoBucketsArray(const void *Ptr) const { 239245431Sdim return Ptr >= getBuckets() && Ptr < getBucketsEnd(); 240193323Sed } 241193323Sed 242193323Sed /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets 243193323Sed /// array. In conjunction with the previous method, this can be used to 244193323Sed /// determine whether an insertion caused the DenseMap to reallocate. 245245431Sdim const void *getPointerIntoBucketsArray() const { return getBuckets(); } 246193323Sed 247245431Sdimprotected: 248245431Sdim DenseMapBase() {} 249245431Sdim 250245431Sdim void destroyAll() { 251245431Sdim if (getNumBuckets() == 0) // Nothing to do. 252245431Sdim return; 253245431Sdim 254245431Sdim const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 255245431Sdim for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) { 256245431Sdim if (!KeyInfoT::isEqual(P->first, EmptyKey) && 257245431Sdim !KeyInfoT::isEqual(P->first, TombstoneKey)) 258245431Sdim P->second.~ValueT(); 259245431Sdim P->first.~KeyT(); 260193323Sed } 261193323Sed 262198090Srdivacky#ifndef NDEBUG 263245431Sdim memset((void*)getBuckets(), 0x5a, sizeof(BucketT)*getNumBuckets()); 264198090Srdivacky#endif 265245431Sdim } 266193323Sed 267245431Sdim void initEmpty() { 268245431Sdim setNumEntries(0); 269245431Sdim setNumTombstones(0); 270221345Sdim 271245431Sdim assert((getNumBuckets() & (getNumBuckets()-1)) == 0 && 272245431Sdim "# initial buckets must be a power of two!"); 273245431Sdim const KeyT EmptyKey = getEmptyKey(); 274245431Sdim for (BucketT *B = getBuckets(), *E = getBucketsEnd(); B != E; ++B) 275245431Sdim new (&B->first) KeyT(EmptyKey); 276245431Sdim } 277245431Sdim 278245431Sdim void moveFromOldBuckets(BucketT *OldBucketsBegin, BucketT *OldBucketsEnd) { 279245431Sdim initEmpty(); 280245431Sdim 281245431Sdim // Insert all the old elements. 282245431Sdim const KeyT EmptyKey = getEmptyKey(); 283245431Sdim const KeyT TombstoneKey = getTombstoneKey(); 284245431Sdim for (BucketT *B = OldBucketsBegin, *E = OldBucketsEnd; B != E; ++B) { 285245431Sdim if (!KeyInfoT::isEqual(B->first, EmptyKey) && 286245431Sdim !KeyInfoT::isEqual(B->first, TombstoneKey)) { 287245431Sdim // Insert the key/value into the new table. 288245431Sdim BucketT *DestBucket; 289245431Sdim bool FoundVal = LookupBucketFor(B->first, DestBucket); 290245431Sdim (void)FoundVal; // silence warning. 291245431Sdim assert(!FoundVal && "Key already in new map?"); 292245431Sdim DestBucket->first = llvm_move(B->first); 293245431Sdim new (&DestBucket->second) ValueT(llvm_move(B->second)); 294245431Sdim incrementNumEntries(); 295245431Sdim 296245431Sdim // Free the value. 297245431Sdim B->second.~ValueT(); 298245431Sdim } 299245431Sdim B->first.~KeyT(); 300221345Sdim } 301221345Sdim 302245431Sdim#ifndef NDEBUG 303245431Sdim if (OldBucketsBegin != OldBucketsEnd) 304245431Sdim memset((void*)OldBucketsBegin, 0x5a, 305245431Sdim sizeof(BucketT) * (OldBucketsEnd - OldBucketsBegin)); 306245431Sdim#endif 307245431Sdim } 308221345Sdim 309245431Sdim template <typename OtherBaseT> 310245431Sdim void copyFrom(const DenseMapBase<OtherBaseT, KeyT, ValueT, KeyInfoT>& other) { 311245431Sdim assert(getNumBuckets() == other.getNumBuckets()); 312245431Sdim 313245431Sdim setNumEntries(other.getNumEntries()); 314245431Sdim setNumTombstones(other.getNumTombstones()); 315245431Sdim 316235633Sdim if (isPodLike<KeyT>::value && isPodLike<ValueT>::value) 317245431Sdim memcpy(getBuckets(), other.getBuckets(), 318245431Sdim getNumBuckets() * sizeof(BucketT)); 319193323Sed else 320245431Sdim for (size_t i = 0; i < getNumBuckets(); ++i) { 321245431Sdim new (&getBuckets()[i].first) KeyT(other.getBuckets()[i].first); 322245431Sdim if (!KeyInfoT::isEqual(getBuckets()[i].first, getEmptyKey()) && 323245431Sdim !KeyInfoT::isEqual(getBuckets()[i].first, getTombstoneKey())) 324245431Sdim new (&getBuckets()[i].second) ValueT(other.getBuckets()[i].second); 325193323Sed } 326193323Sed } 327193323Sed 328245431Sdim void swap(DenseMapBase& RHS) { 329245431Sdim std::swap(getNumEntries(), RHS.getNumEntries()); 330245431Sdim std::swap(getNumTombstones(), RHS.getNumTombstones()); 331245431Sdim } 332245431Sdim 333245431Sdim static unsigned getHashValue(const KeyT &Val) { 334245431Sdim return KeyInfoT::getHashValue(Val); 335245431Sdim } 336245431Sdim template<typename LookupKeyT> 337245431Sdim static unsigned getHashValue(const LookupKeyT &Val) { 338245431Sdim return KeyInfoT::getHashValue(Val); 339245431Sdim } 340245431Sdim static const KeyT getEmptyKey() { 341245431Sdim return KeyInfoT::getEmptyKey(); 342245431Sdim } 343245431Sdim static const KeyT getTombstoneKey() { 344245431Sdim return KeyInfoT::getTombstoneKey(); 345245431Sdim } 346245431Sdim 347245431Sdimprivate: 348245431Sdim unsigned getNumEntries() const { 349245431Sdim return static_cast<const DerivedT *>(this)->getNumEntries(); 350245431Sdim } 351245431Sdim void setNumEntries(unsigned Num) { 352245431Sdim static_cast<DerivedT *>(this)->setNumEntries(Num); 353245431Sdim } 354245431Sdim void incrementNumEntries() { 355245431Sdim setNumEntries(getNumEntries() + 1); 356245431Sdim } 357245431Sdim void decrementNumEntries() { 358245431Sdim setNumEntries(getNumEntries() - 1); 359245431Sdim } 360245431Sdim unsigned getNumTombstones() const { 361245431Sdim return static_cast<const DerivedT *>(this)->getNumTombstones(); 362245431Sdim } 363245431Sdim void setNumTombstones(unsigned Num) { 364245431Sdim static_cast<DerivedT *>(this)->setNumTombstones(Num); 365245431Sdim } 366245431Sdim void incrementNumTombstones() { 367245431Sdim setNumTombstones(getNumTombstones() + 1); 368245431Sdim } 369245431Sdim void decrementNumTombstones() { 370245431Sdim setNumTombstones(getNumTombstones() - 1); 371245431Sdim } 372245431Sdim const BucketT *getBuckets() const { 373245431Sdim return static_cast<const DerivedT *>(this)->getBuckets(); 374245431Sdim } 375245431Sdim BucketT *getBuckets() { 376245431Sdim return static_cast<DerivedT *>(this)->getBuckets(); 377245431Sdim } 378245431Sdim unsigned getNumBuckets() const { 379245431Sdim return static_cast<const DerivedT *>(this)->getNumBuckets(); 380245431Sdim } 381245431Sdim BucketT *getBucketsEnd() { 382245431Sdim return getBuckets() + getNumBuckets(); 383245431Sdim } 384245431Sdim const BucketT *getBucketsEnd() const { 385245431Sdim return getBuckets() + getNumBuckets(); 386245431Sdim } 387245431Sdim 388245431Sdim void grow(unsigned AtLeast) { 389245431Sdim static_cast<DerivedT *>(this)->grow(AtLeast); 390245431Sdim } 391245431Sdim 392245431Sdim void shrink_and_clear() { 393245431Sdim static_cast<DerivedT *>(this)->shrink_and_clear(); 394245431Sdim } 395245431Sdim 396245431Sdim 397193323Sed BucketT *InsertIntoBucket(const KeyT &Key, const ValueT &Value, 398193323Sed BucketT *TheBucket) { 399245431Sdim TheBucket = InsertIntoBucketImpl(Key, TheBucket); 400245431Sdim 401245431Sdim TheBucket->first = Key; 402245431Sdim new (&TheBucket->second) ValueT(Value); 403245431Sdim return TheBucket; 404245431Sdim } 405245431Sdim 406252723Sdim#if LLVM_HAS_RVALUE_REFERENCES 407245431Sdim BucketT *InsertIntoBucket(const KeyT &Key, ValueT &&Value, 408245431Sdim BucketT *TheBucket) { 409245431Sdim TheBucket = InsertIntoBucketImpl(Key, TheBucket); 410245431Sdim 411245431Sdim TheBucket->first = Key; 412245431Sdim new (&TheBucket->second) ValueT(std::move(Value)); 413245431Sdim return TheBucket; 414245431Sdim } 415245431Sdim 416245431Sdim BucketT *InsertIntoBucket(KeyT &&Key, ValueT &&Value, BucketT *TheBucket) { 417245431Sdim TheBucket = InsertIntoBucketImpl(Key, TheBucket); 418245431Sdim 419245431Sdim TheBucket->first = std::move(Key); 420245431Sdim new (&TheBucket->second) ValueT(std::move(Value)); 421245431Sdim return TheBucket; 422245431Sdim } 423245431Sdim#endif 424245431Sdim 425245431Sdim BucketT *InsertIntoBucketImpl(const KeyT &Key, BucketT *TheBucket) { 426193323Sed // If the load of the hash table is more than 3/4, or if fewer than 1/8 of 427193323Sed // the buckets are empty (meaning that many are filled with tombstones), 428193323Sed // grow the table. 429193323Sed // 430193323Sed // The later case is tricky. For example, if we had one empty bucket with 431193323Sed // tons of tombstones, failing lookups (e.g. for insertion) would have to 432193323Sed // probe almost the entire table until it found the empty bucket. If the 433193323Sed // table completely filled with tombstones, no lookup would ever succeed, 434193323Sed // causing infinite loops in lookup. 435245431Sdim unsigned NewNumEntries = getNumEntries() + 1; 436245431Sdim unsigned NumBuckets = getNumBuckets(); 437245431Sdim if (NewNumEntries*4 >= NumBuckets*3) { 438193323Sed this->grow(NumBuckets * 2); 439193323Sed LookupBucketFor(Key, TheBucket); 440245431Sdim NumBuckets = getNumBuckets(); 441263509Sdim } else if (NumBuckets-(NewNumEntries+getNumTombstones()) <= NumBuckets/8) { 442263509Sdim this->grow(NumBuckets); 443221345Sdim LookupBucketFor(Key, TheBucket); 444221345Sdim } 445245431Sdim assert(TheBucket); 446193323Sed 447245431Sdim // Only update the state after we've grown our bucket space appropriately 448245431Sdim // so that when growing buckets we have self-consistent entry count. 449245431Sdim incrementNumEntries(); 450245431Sdim 451193323Sed // If we are writing over a tombstone, remember this. 452252723Sdim const KeyT EmptyKey = getEmptyKey(); 453252723Sdim if (!KeyInfoT::isEqual(TheBucket->first, EmptyKey)) 454245431Sdim decrementNumTombstones(); 455193323Sed 456193323Sed return TheBucket; 457193323Sed } 458193323Sed 459193323Sed /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in 460193323Sed /// FoundBucket. If the bucket contains the key and a value, this returns 461193323Sed /// true, otherwise it returns a bucket with an empty marker or tombstone and 462193323Sed /// returns false. 463235633Sdim template<typename LookupKeyT> 464245431Sdim bool LookupBucketFor(const LookupKeyT &Val, 465245431Sdim const BucketT *&FoundBucket) const { 466245431Sdim const BucketT *BucketsPtr = getBuckets(); 467245431Sdim const unsigned NumBuckets = getNumBuckets(); 468193323Sed 469221345Sdim if (NumBuckets == 0) { 470221345Sdim FoundBucket = 0; 471221345Sdim return false; 472221345Sdim } 473221345Sdim 474193323Sed // FoundTombstone - Keep track of whether we find a tombstone while probing. 475245431Sdim const BucketT *FoundTombstone = 0; 476193323Sed const KeyT EmptyKey = getEmptyKey(); 477193323Sed const KeyT TombstoneKey = getTombstoneKey(); 478193323Sed assert(!KeyInfoT::isEqual(Val, EmptyKey) && 479193323Sed !KeyInfoT::isEqual(Val, TombstoneKey) && 480193323Sed "Empty/Tombstone value shouldn't be inserted into map!"); 481193323Sed 482245431Sdim unsigned BucketNo = getHashValue(Val) & (NumBuckets-1); 483245431Sdim unsigned ProbeAmt = 1; 484193323Sed while (1) { 485245431Sdim const BucketT *ThisBucket = BucketsPtr + BucketNo; 486193323Sed // Found Val's bucket? If so, return it. 487235633Sdim if (KeyInfoT::isEqual(Val, ThisBucket->first)) { 488193323Sed FoundBucket = ThisBucket; 489193323Sed return true; 490193323Sed } 491193323Sed 492193323Sed // If we found an empty bucket, the key doesn't exist in the set. 493193323Sed // Insert it and return the default value. 494193323Sed if (KeyInfoT::isEqual(ThisBucket->first, EmptyKey)) { 495193323Sed // If we've already seen a tombstone while probing, fill it in instead 496193323Sed // of the empty bucket we eventually probed to. 497193323Sed FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket; 498193323Sed return false; 499193323Sed } 500193323Sed 501193323Sed // If this is a tombstone, remember it. If Val ends up not in the map, we 502193323Sed // prefer to return it than something that would require more probing. 503193323Sed if (KeyInfoT::isEqual(ThisBucket->first, TombstoneKey) && !FoundTombstone) 504193323Sed FoundTombstone = ThisBucket; // Remember the first tombstone found. 505193323Sed 506193323Sed // Otherwise, it's a hash collision or a tombstone, continue quadratic 507193323Sed // probing. 508193323Sed BucketNo += ProbeAmt++; 509245431Sdim BucketNo &= (NumBuckets-1); 510193323Sed } 511193323Sed } 512193323Sed 513245431Sdim template <typename LookupKeyT> 514245431Sdim bool LookupBucketFor(const LookupKeyT &Val, BucketT *&FoundBucket) { 515245431Sdim const BucketT *ConstFoundBucket; 516245431Sdim bool Result = const_cast<const DenseMapBase *>(this) 517245431Sdim ->LookupBucketFor(Val, ConstFoundBucket); 518245431Sdim FoundBucket = const_cast<BucketT *>(ConstFoundBucket); 519245431Sdim return Result; 520245431Sdim } 521221345Sdim 522245431Sdimpublic: 523245431Sdim /// Return the approximate size (in bytes) of the actual map. 524245431Sdim /// This is just the raw memory used by DenseMap. 525245431Sdim /// If entries are pointers to objects, the size of the referenced objects 526245431Sdim /// are not included. 527245431Sdim size_t getMemorySize() const { 528245431Sdim return getNumBuckets() * sizeof(BucketT); 529245431Sdim } 530245431Sdim}; 531245431Sdim 532245431Sdimtemplate<typename KeyT, typename ValueT, 533245431Sdim typename KeyInfoT = DenseMapInfo<KeyT> > 534245431Sdimclass DenseMap 535245431Sdim : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT>, 536245431Sdim KeyT, ValueT, KeyInfoT> { 537245431Sdim // Lift some types from the dependent base class into this class for 538245431Sdim // simplicity of referring to them. 539245431Sdim typedef DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT> BaseT; 540245431Sdim typedef typename BaseT::BucketT BucketT; 541245431Sdim friend class DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT>; 542245431Sdim 543245431Sdim BucketT *Buckets; 544245431Sdim unsigned NumEntries; 545245431Sdim unsigned NumTombstones; 546245431Sdim unsigned NumBuckets; 547245431Sdim 548245431Sdimpublic: 549245431Sdim explicit DenseMap(unsigned NumInitBuckets = 0) { 550245431Sdim init(NumInitBuckets); 551245431Sdim } 552245431Sdim 553252723Sdim DenseMap(const DenseMap &other) : BaseT() { 554245431Sdim init(0); 555245431Sdim copyFrom(other); 556245431Sdim } 557245431Sdim 558252723Sdim#if LLVM_HAS_RVALUE_REFERENCES 559252723Sdim DenseMap(DenseMap &&other) : BaseT() { 560245431Sdim init(0); 561245431Sdim swap(other); 562245431Sdim } 563245431Sdim#endif 564245431Sdim 565245431Sdim template<typename InputIt> 566245431Sdim DenseMap(const InputIt &I, const InputIt &E) { 567245431Sdim init(NextPowerOf2(std::distance(I, E))); 568245431Sdim this->insert(I, E); 569245431Sdim } 570245431Sdim 571245431Sdim ~DenseMap() { 572245431Sdim this->destroyAll(); 573245431Sdim operator delete(Buckets); 574245431Sdim } 575245431Sdim 576245431Sdim void swap(DenseMap& RHS) { 577245431Sdim std::swap(Buckets, RHS.Buckets); 578245431Sdim std::swap(NumEntries, RHS.NumEntries); 579245431Sdim std::swap(NumTombstones, RHS.NumTombstones); 580245431Sdim std::swap(NumBuckets, RHS.NumBuckets); 581245431Sdim } 582245431Sdim 583245431Sdim DenseMap& operator=(const DenseMap& other) { 584245431Sdim copyFrom(other); 585245431Sdim return *this; 586245431Sdim } 587245431Sdim 588252723Sdim#if LLVM_HAS_RVALUE_REFERENCES 589245431Sdim DenseMap& operator=(DenseMap &&other) { 590245431Sdim this->destroyAll(); 591245431Sdim operator delete(Buckets); 592245431Sdim init(0); 593245431Sdim swap(other); 594245431Sdim return *this; 595245431Sdim } 596245431Sdim#endif 597245431Sdim 598245431Sdim void copyFrom(const DenseMap& other) { 599245431Sdim this->destroyAll(); 600245431Sdim operator delete(Buckets); 601245431Sdim if (allocateBuckets(other.NumBuckets)) { 602245431Sdim this->BaseT::copyFrom(other); 603245431Sdim } else { 604245431Sdim NumEntries = 0; 605245431Sdim NumTombstones = 0; 606221345Sdim } 607245431Sdim } 608221345Sdim 609245431Sdim void init(unsigned InitBuckets) { 610245431Sdim if (allocateBuckets(InitBuckets)) { 611245431Sdim this->BaseT::initEmpty(); 612245431Sdim } else { 613245431Sdim NumEntries = 0; 614245431Sdim NumTombstones = 0; 615245431Sdim } 616193323Sed } 617193323Sed 618193323Sed void grow(unsigned AtLeast) { 619193323Sed unsigned OldNumBuckets = NumBuckets; 620193323Sed BucketT *OldBuckets = Buckets; 621193323Sed 622252723Sdim allocateBuckets(std::max<unsigned>(64, static_cast<unsigned>(NextPowerOf2(AtLeast-1)))); 623245431Sdim assert(Buckets); 624245431Sdim if (!OldBuckets) { 625245431Sdim this->BaseT::initEmpty(); 626245431Sdim return; 627245431Sdim } 628221345Sdim 629245431Sdim this->moveFromOldBuckets(OldBuckets, OldBuckets+OldNumBuckets); 630193323Sed 631245431Sdim // Free the old table. 632245431Sdim operator delete(OldBuckets); 633245431Sdim } 634193323Sed 635245431Sdim void shrink_and_clear() { 636245431Sdim unsigned OldNumEntries = NumEntries; 637245431Sdim this->destroyAll(); 638193323Sed 639245431Sdim // Reduce the number of buckets. 640245431Sdim unsigned NewNumBuckets = 0; 641245431Sdim if (OldNumEntries) 642245431Sdim NewNumBuckets = std::max(64, 1 << (Log2_32_Ceil(OldNumEntries) + 1)); 643245431Sdim if (NewNumBuckets == NumBuckets) { 644245431Sdim this->BaseT::initEmpty(); 645245431Sdim return; 646245431Sdim } 647245431Sdim 648245431Sdim operator delete(Buckets); 649245431Sdim init(NewNumBuckets); 650245431Sdim } 651245431Sdim 652245431Sdimprivate: 653245431Sdim unsigned getNumEntries() const { 654245431Sdim return NumEntries; 655245431Sdim } 656245431Sdim void setNumEntries(unsigned Num) { 657245431Sdim NumEntries = Num; 658245431Sdim } 659245431Sdim 660245431Sdim unsigned getNumTombstones() const { 661245431Sdim return NumTombstones; 662245431Sdim } 663245431Sdim void setNumTombstones(unsigned Num) { 664245431Sdim NumTombstones = Num; 665245431Sdim } 666245431Sdim 667245431Sdim BucketT *getBuckets() const { 668245431Sdim return Buckets; 669245431Sdim } 670245431Sdim 671245431Sdim unsigned getNumBuckets() const { 672245431Sdim return NumBuckets; 673245431Sdim } 674245431Sdim 675245431Sdim bool allocateBuckets(unsigned Num) { 676245431Sdim NumBuckets = Num; 677245431Sdim if (NumBuckets == 0) { 678245431Sdim Buckets = 0; 679245431Sdim return false; 680245431Sdim } 681245431Sdim 682245431Sdim Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT) * NumBuckets)); 683245431Sdim return true; 684245431Sdim } 685245431Sdim}; 686245431Sdim 687245431Sdimtemplate<typename KeyT, typename ValueT, 688245431Sdim unsigned InlineBuckets = 4, 689245431Sdim typename KeyInfoT = DenseMapInfo<KeyT> > 690245431Sdimclass SmallDenseMap 691245431Sdim : public DenseMapBase<SmallDenseMap<KeyT, ValueT, InlineBuckets, KeyInfoT>, 692245431Sdim KeyT, ValueT, KeyInfoT> { 693245431Sdim // Lift some types from the dependent base class into this class for 694245431Sdim // simplicity of referring to them. 695245431Sdim typedef DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT> BaseT; 696245431Sdim typedef typename BaseT::BucketT BucketT; 697245431Sdim friend class DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT>; 698245431Sdim 699245431Sdim unsigned Small : 1; 700245431Sdim unsigned NumEntries : 31; 701245431Sdim unsigned NumTombstones; 702245431Sdim 703245431Sdim struct LargeRep { 704245431Sdim BucketT *Buckets; 705245431Sdim unsigned NumBuckets; 706245431Sdim }; 707245431Sdim 708245431Sdim /// A "union" of an inline bucket array and the struct representing 709245431Sdim /// a large bucket. This union will be discriminated by the 'Small' bit. 710245431Sdim AlignedCharArrayUnion<BucketT[InlineBuckets], LargeRep> storage; 711245431Sdim 712245431Sdimpublic: 713245431Sdim explicit SmallDenseMap(unsigned NumInitBuckets = 0) { 714245431Sdim init(NumInitBuckets); 715245431Sdim } 716245431Sdim 717263509Sdim SmallDenseMap(const SmallDenseMap &other) : BaseT() { 718245431Sdim init(0); 719245431Sdim copyFrom(other); 720245431Sdim } 721245431Sdim 722252723Sdim#if LLVM_HAS_RVALUE_REFERENCES 723263509Sdim SmallDenseMap(SmallDenseMap &&other) : BaseT() { 724245431Sdim init(0); 725245431Sdim swap(other); 726245431Sdim } 727245431Sdim#endif 728245431Sdim 729245431Sdim template<typename InputIt> 730245431Sdim SmallDenseMap(const InputIt &I, const InputIt &E) { 731245431Sdim init(NextPowerOf2(std::distance(I, E))); 732245431Sdim this->insert(I, E); 733245431Sdim } 734245431Sdim 735245431Sdim ~SmallDenseMap() { 736245431Sdim this->destroyAll(); 737245431Sdim deallocateBuckets(); 738245431Sdim } 739245431Sdim 740245431Sdim void swap(SmallDenseMap& RHS) { 741245431Sdim unsigned TmpNumEntries = RHS.NumEntries; 742245431Sdim RHS.NumEntries = NumEntries; 743245431Sdim NumEntries = TmpNumEntries; 744245431Sdim std::swap(NumTombstones, RHS.NumTombstones); 745245431Sdim 746245431Sdim const KeyT EmptyKey = this->getEmptyKey(); 747245431Sdim const KeyT TombstoneKey = this->getTombstoneKey(); 748245431Sdim if (Small && RHS.Small) { 749245431Sdim // If we're swapping inline bucket arrays, we have to cope with some of 750245431Sdim // the tricky bits of DenseMap's storage system: the buckets are not 751245431Sdim // fully initialized. Thus we swap every key, but we may have 752245431Sdim // a one-directional move of the value. 753245431Sdim for (unsigned i = 0, e = InlineBuckets; i != e; ++i) { 754245431Sdim BucketT *LHSB = &getInlineBuckets()[i], 755245431Sdim *RHSB = &RHS.getInlineBuckets()[i]; 756245431Sdim bool hasLHSValue = (!KeyInfoT::isEqual(LHSB->first, EmptyKey) && 757245431Sdim !KeyInfoT::isEqual(LHSB->first, TombstoneKey)); 758245431Sdim bool hasRHSValue = (!KeyInfoT::isEqual(RHSB->first, EmptyKey) && 759245431Sdim !KeyInfoT::isEqual(RHSB->first, TombstoneKey)); 760245431Sdim if (hasLHSValue && hasRHSValue) { 761245431Sdim // Swap together if we can... 762245431Sdim std::swap(*LHSB, *RHSB); 763245431Sdim continue; 764245431Sdim } 765245431Sdim // Swap separately and handle any assymetry. 766245431Sdim std::swap(LHSB->first, RHSB->first); 767245431Sdim if (hasLHSValue) { 768245431Sdim new (&RHSB->second) ValueT(llvm_move(LHSB->second)); 769245431Sdim LHSB->second.~ValueT(); 770245431Sdim } else if (hasRHSValue) { 771245431Sdim new (&LHSB->second) ValueT(llvm_move(RHSB->second)); 772245431Sdim RHSB->second.~ValueT(); 773245431Sdim } 774193323Sed } 775245431Sdim return; 776193323Sed } 777245431Sdim if (!Small && !RHS.Small) { 778245431Sdim std::swap(getLargeRep()->Buckets, RHS.getLargeRep()->Buckets); 779245431Sdim std::swap(getLargeRep()->NumBuckets, RHS.getLargeRep()->NumBuckets); 780245431Sdim return; 781245431Sdim } 782193323Sed 783245431Sdim SmallDenseMap &SmallSide = Small ? *this : RHS; 784245431Sdim SmallDenseMap &LargeSide = Small ? RHS : *this; 785245431Sdim 786245431Sdim // First stash the large side's rep and move the small side across. 787245431Sdim LargeRep TmpRep = llvm_move(*LargeSide.getLargeRep()); 788245431Sdim LargeSide.getLargeRep()->~LargeRep(); 789245431Sdim LargeSide.Small = true; 790245431Sdim // This is similar to the standard move-from-old-buckets, but the bucket 791245431Sdim // count hasn't actually rotated in this case. So we have to carefully 792245431Sdim // move construct the keys and values into their new locations, but there 793245431Sdim // is no need to re-hash things. 794245431Sdim for (unsigned i = 0, e = InlineBuckets; i != e; ++i) { 795245431Sdim BucketT *NewB = &LargeSide.getInlineBuckets()[i], 796245431Sdim *OldB = &SmallSide.getInlineBuckets()[i]; 797245431Sdim new (&NewB->first) KeyT(llvm_move(OldB->first)); 798245431Sdim OldB->first.~KeyT(); 799245431Sdim if (!KeyInfoT::isEqual(NewB->first, EmptyKey) && 800245431Sdim !KeyInfoT::isEqual(NewB->first, TombstoneKey)) { 801245431Sdim new (&NewB->second) ValueT(llvm_move(OldB->second)); 802245431Sdim OldB->second.~ValueT(); 803245431Sdim } 804245431Sdim } 805245431Sdim 806245431Sdim // The hard part of moving the small buckets across is done, just move 807245431Sdim // the TmpRep into its new home. 808245431Sdim SmallSide.Small = false; 809245431Sdim new (SmallSide.getLargeRep()) LargeRep(llvm_move(TmpRep)); 810245431Sdim } 811245431Sdim 812245431Sdim SmallDenseMap& operator=(const SmallDenseMap& other) { 813245431Sdim copyFrom(other); 814245431Sdim return *this; 815245431Sdim } 816245431Sdim 817252723Sdim#if LLVM_HAS_RVALUE_REFERENCES 818245431Sdim SmallDenseMap& operator=(SmallDenseMap &&other) { 819245431Sdim this->destroyAll(); 820245431Sdim deallocateBuckets(); 821245431Sdim init(0); 822245431Sdim swap(other); 823245431Sdim return *this; 824245431Sdim } 825198090Srdivacky#endif 826245431Sdim 827245431Sdim void copyFrom(const SmallDenseMap& other) { 828245431Sdim this->destroyAll(); 829245431Sdim deallocateBuckets(); 830245431Sdim Small = true; 831245431Sdim if (other.getNumBuckets() > InlineBuckets) { 832245431Sdim Small = false; 833245431Sdim allocateBuckets(other.getNumBuckets()); 834245431Sdim } 835245431Sdim this->BaseT::copyFrom(other); 836193323Sed } 837193323Sed 838245431Sdim void init(unsigned InitBuckets) { 839245431Sdim Small = true; 840245431Sdim if (InitBuckets > InlineBuckets) { 841245431Sdim Small = false; 842245431Sdim new (getLargeRep()) LargeRep(allocateBuckets(InitBuckets)); 843245431Sdim } 844245431Sdim this->BaseT::initEmpty(); 845245431Sdim } 846193323Sed 847245431Sdim void grow(unsigned AtLeast) { 848245431Sdim if (AtLeast >= InlineBuckets) 849245431Sdim AtLeast = std::max<unsigned>(64, NextPowerOf2(AtLeast-1)); 850193323Sed 851245431Sdim if (Small) { 852245431Sdim if (AtLeast < InlineBuckets) 853245431Sdim return; // Nothing to do. 854193323Sed 855245431Sdim // First move the inline buckets into a temporary storage. 856245431Sdim AlignedCharArrayUnion<BucketT[InlineBuckets]> TmpStorage; 857245431Sdim BucketT *TmpBegin = reinterpret_cast<BucketT *>(TmpStorage.buffer); 858245431Sdim BucketT *TmpEnd = TmpBegin; 859245431Sdim 860245431Sdim // Loop over the buckets, moving non-empty, non-tombstones into the 861245431Sdim // temporary storage. Have the loop move the TmpEnd forward as it goes. 862245431Sdim const KeyT EmptyKey = this->getEmptyKey(); 863245431Sdim const KeyT TombstoneKey = this->getTombstoneKey(); 864245431Sdim for (BucketT *P = getBuckets(), *E = P + InlineBuckets; P != E; ++P) { 865245431Sdim if (!KeyInfoT::isEqual(P->first, EmptyKey) && 866245431Sdim !KeyInfoT::isEqual(P->first, TombstoneKey)) { 867245431Sdim assert(size_t(TmpEnd - TmpBegin) < InlineBuckets && 868245431Sdim "Too many inline buckets!"); 869245431Sdim new (&TmpEnd->first) KeyT(llvm_move(P->first)); 870245431Sdim new (&TmpEnd->second) ValueT(llvm_move(P->second)); 871245431Sdim ++TmpEnd; 872245431Sdim P->second.~ValueT(); 873245431Sdim } 874245431Sdim P->first.~KeyT(); 875193323Sed } 876245431Sdim 877245431Sdim // Now make this map use the large rep, and move all the entries back 878245431Sdim // into it. 879245431Sdim Small = false; 880245431Sdim new (getLargeRep()) LargeRep(allocateBuckets(AtLeast)); 881245431Sdim this->moveFromOldBuckets(TmpBegin, TmpEnd); 882245431Sdim return; 883193323Sed } 884193323Sed 885245431Sdim LargeRep OldRep = llvm_move(*getLargeRep()); 886245431Sdim getLargeRep()->~LargeRep(); 887245431Sdim if (AtLeast <= InlineBuckets) { 888245431Sdim Small = true; 889245431Sdim } else { 890245431Sdim new (getLargeRep()) LargeRep(allocateBuckets(AtLeast)); 891245431Sdim } 892245431Sdim 893245431Sdim this->moveFromOldBuckets(OldRep.Buckets, OldRep.Buckets+OldRep.NumBuckets); 894245431Sdim 895193323Sed // Free the old table. 896245431Sdim operator delete(OldRep.Buckets); 897245431Sdim } 898193323Sed 899245431Sdim void shrink_and_clear() { 900245431Sdim unsigned OldSize = this->size(); 901245431Sdim this->destroyAll(); 902245431Sdim 903245431Sdim // Reduce the number of buckets. 904245431Sdim unsigned NewNumBuckets = 0; 905245431Sdim if (OldSize) { 906245431Sdim NewNumBuckets = 1 << (Log2_32_Ceil(OldSize) + 1); 907245431Sdim if (NewNumBuckets > InlineBuckets && NewNumBuckets < 64u) 908245431Sdim NewNumBuckets = 64; 909245431Sdim } 910245431Sdim if ((Small && NewNumBuckets <= InlineBuckets) || 911245431Sdim (!Small && NewNumBuckets == getLargeRep()->NumBuckets)) { 912245431Sdim this->BaseT::initEmpty(); 913245431Sdim return; 914245431Sdim } 915245431Sdim 916245431Sdim deallocateBuckets(); 917245431Sdim init(NewNumBuckets); 918193323Sed } 919245431Sdim 920245431Sdimprivate: 921245431Sdim unsigned getNumEntries() const { 922245431Sdim return NumEntries; 923221345Sdim } 924245431Sdim void setNumEntries(unsigned Num) { 925245431Sdim assert(Num < INT_MAX && "Cannot support more than INT_MAX entries"); 926245431Sdim NumEntries = Num; 927245431Sdim } 928245431Sdim 929245431Sdim unsigned getNumTombstones() const { 930245431Sdim return NumTombstones; 931245431Sdim } 932245431Sdim void setNumTombstones(unsigned Num) { 933245431Sdim NumTombstones = Num; 934245431Sdim } 935245431Sdim 936245431Sdim const BucketT *getInlineBuckets() const { 937245431Sdim assert(Small); 938245431Sdim // Note that this cast does not violate aliasing rules as we assert that 939245431Sdim // the memory's dynamic type is the small, inline bucket buffer, and the 940245431Sdim // 'storage.buffer' static type is 'char *'. 941245431Sdim return reinterpret_cast<const BucketT *>(storage.buffer); 942245431Sdim } 943245431Sdim BucketT *getInlineBuckets() { 944245431Sdim return const_cast<BucketT *>( 945245431Sdim const_cast<const SmallDenseMap *>(this)->getInlineBuckets()); 946245431Sdim } 947245431Sdim const LargeRep *getLargeRep() const { 948245431Sdim assert(!Small); 949245431Sdim // Note, same rule about aliasing as with getInlineBuckets. 950245431Sdim return reinterpret_cast<const LargeRep *>(storage.buffer); 951245431Sdim } 952245431Sdim LargeRep *getLargeRep() { 953245431Sdim return const_cast<LargeRep *>( 954245431Sdim const_cast<const SmallDenseMap *>(this)->getLargeRep()); 955245431Sdim } 956245431Sdim 957245431Sdim const BucketT *getBuckets() const { 958245431Sdim return Small ? getInlineBuckets() : getLargeRep()->Buckets; 959245431Sdim } 960245431Sdim BucketT *getBuckets() { 961245431Sdim return const_cast<BucketT *>( 962245431Sdim const_cast<const SmallDenseMap *>(this)->getBuckets()); 963245431Sdim } 964245431Sdim unsigned getNumBuckets() const { 965245431Sdim return Small ? InlineBuckets : getLargeRep()->NumBuckets; 966245431Sdim } 967245431Sdim 968245431Sdim void deallocateBuckets() { 969245431Sdim if (Small) 970245431Sdim return; 971245431Sdim 972245431Sdim operator delete(getLargeRep()->Buckets); 973245431Sdim getLargeRep()->~LargeRep(); 974245431Sdim } 975245431Sdim 976245431Sdim LargeRep allocateBuckets(unsigned Num) { 977245431Sdim assert(Num > InlineBuckets && "Must allocate more buckets than are inline"); 978245431Sdim LargeRep Rep = { 979245431Sdim static_cast<BucketT*>(operator new(sizeof(BucketT) * Num)), Num 980245431Sdim }; 981245431Sdim return Rep; 982245431Sdim } 983193323Sed}; 984193323Sed 985199481Srdivackytemplate<typename KeyT, typename ValueT, 986235633Sdim typename KeyInfoT, bool IsConst> 987199481Srdivackyclass DenseMapIterator { 988199481Srdivacky typedef std::pair<KeyT, ValueT> Bucket; 989199481Srdivacky typedef DenseMapIterator<KeyT, ValueT, 990235633Sdim KeyInfoT, true> ConstIterator; 991235633Sdim friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, true>; 992193323Sedpublic: 993199481Srdivacky typedef ptrdiff_t difference_type; 994199481Srdivacky typedef typename conditional<IsConst, const Bucket, Bucket>::type value_type; 995199481Srdivacky typedef value_type *pointer; 996199481Srdivacky typedef value_type &reference; 997199481Srdivacky typedef std::forward_iterator_tag iterator_category; 998199481Srdivackyprivate: 999199481Srdivacky pointer Ptr, End; 1000199481Srdivackypublic: 1001198090Srdivacky DenseMapIterator() : Ptr(0), End(0) {} 1002193323Sed 1003235633Sdim DenseMapIterator(pointer Pos, pointer E, bool NoAdvance = false) 1004235633Sdim : Ptr(Pos), End(E) { 1005235633Sdim if (!NoAdvance) AdvancePastEmptyBuckets(); 1006193323Sed } 1007193323Sed 1008199481Srdivacky // If IsConst is true this is a converting constructor from iterator to 1009199481Srdivacky // const_iterator and the default copy constructor is used. 1010199481Srdivacky // Otherwise this is a copy constructor for iterator. 1011199481Srdivacky DenseMapIterator(const DenseMapIterator<KeyT, ValueT, 1012235633Sdim KeyInfoT, false>& I) 1013199481Srdivacky : Ptr(I.Ptr), End(I.End) {} 1014199481Srdivacky 1015199481Srdivacky reference operator*() const { 1016199481Srdivacky return *Ptr; 1017193323Sed } 1018199481Srdivacky pointer operator->() const { 1019199481Srdivacky return Ptr; 1020193323Sed } 1021193323Sed 1022199481Srdivacky bool operator==(const ConstIterator &RHS) const { 1023199481Srdivacky return Ptr == RHS.operator->(); 1024193323Sed } 1025199481Srdivacky bool operator!=(const ConstIterator &RHS) const { 1026199481Srdivacky return Ptr != RHS.operator->(); 1027193323Sed } 1028193323Sed 1029198892Srdivacky inline DenseMapIterator& operator++() { // Preincrement 1030193323Sed ++Ptr; 1031193323Sed AdvancePastEmptyBuckets(); 1032193323Sed return *this; 1033193323Sed } 1034198892Srdivacky DenseMapIterator operator++(int) { // Postincrement 1035193323Sed DenseMapIterator tmp = *this; ++*this; return tmp; 1036193323Sed } 1037193323Sed 1038193323Sedprivate: 1039193323Sed void AdvancePastEmptyBuckets() { 1040193323Sed const KeyT Empty = KeyInfoT::getEmptyKey(); 1041193323Sed const KeyT Tombstone = KeyInfoT::getTombstoneKey(); 1042193323Sed 1043193323Sed while (Ptr != End && 1044193323Sed (KeyInfoT::isEqual(Ptr->first, Empty) || 1045193323Sed KeyInfoT::isEqual(Ptr->first, Tombstone))) 1046193323Sed ++Ptr; 1047193323Sed } 1048193323Sed}; 1049252723Sdim 1050235633Sdimtemplate<typename KeyT, typename ValueT, typename KeyInfoT> 1051226890Sdimstatic inline size_t 1052235633Sdimcapacity_in_bytes(const DenseMap<KeyT, ValueT, KeyInfoT> &X) { 1053226890Sdim return X.getMemorySize(); 1054226890Sdim} 1055193323Sed 1056193323Sed} // end namespace llvm 1057193323Sed 1058193323Sed#endif 1059