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 17249423Sdim#include "llvm/ADT/DenseMapInfo.h" 18249423Sdim#include "llvm/Support/AlignOf.h" 19239462Sdim#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> 25239462Sdim#include <climits> 26210299Sed#include <cstddef> 27198090Srdivacky#include <cstring> 28249423Sdim#include <iterator> 29249423Sdim#include <new> 30249423Sdim#include <utility> 31193323Sed 32193323Sednamespace llvm { 33193323Sed 34193323Sedtemplate<typename KeyT, typename ValueT, 35193323Sed typename KeyInfoT = DenseMapInfo<KeyT>, 36234353Sdim bool IsConst = false> 37193323Sedclass DenseMapIterator; 38193323Sed 39239462Sdimtemplate<typename DerivedT, 40239462Sdim typename KeyT, typename ValueT, typename KeyInfoT> 41239462Sdimclass DenseMapBase { 42239462Sdimprotected: 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, 52234353Sdim KeyInfoT, true> const_iterator; 53193323Sed inline iterator begin() { 54208599Srdivacky // When the map is empty, avoid the overhead of AdvancePastEmptyBuckets(). 55239462Sdim return empty() ? end() : iterator(getBuckets(), getBucketsEnd()); 56193323Sed } 57193323Sed inline iterator end() { 58239462Sdim return iterator(getBucketsEnd(), getBucketsEnd(), true); 59193323Sed } 60193323Sed inline const_iterator begin() const { 61239462Sdim return empty() ? end() : const_iterator(getBuckets(), getBucketsEnd()); 62193323Sed } 63193323Sed inline const_iterator end() const { 64239462Sdim return const_iterator(getBucketsEnd(), getBucketsEnd(), true); 65193323Sed } 66193323Sed 67239462Sdim bool empty() const { return getNumEntries() == 0; } 68239462Sdim unsigned size() const { return getNumEntries(); } 69193323Sed 70193323Sed /// Grow the densemap so that it has at least Size buckets. Does not shrink 71221345Sdim void resize(size_t Size) { 72239462Sdim if (Size > getNumBuckets()) 73221345Sdim grow(Size); 74221345Sdim } 75193323Sed 76193323Sed void clear() { 77239462Sdim if (getNumEntries() == 0 && getNumTombstones() == 0) return; 78249423Sdim 79193323Sed // If the capacity of the array is huge, and the # elements used is small, 80193323Sed // shrink the array. 81239462Sdim if (getNumEntries() * 4 < getNumBuckets() && getNumBuckets() > 64) { 82193323Sed shrink_and_clear(); 83193323Sed return; 84193323Sed } 85193323Sed 86193323Sed const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 87239462Sdim for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) { 88193323Sed if (!KeyInfoT::isEqual(P->first, EmptyKey)) { 89193323Sed if (!KeyInfoT::isEqual(P->first, TombstoneKey)) { 90193323Sed P->second.~ValueT(); 91239462Sdim decrementNumEntries(); 92193323Sed } 93193323Sed P->first = EmptyKey; 94193323Sed } 95193323Sed } 96239462Sdim assert(getNumEntries() == 0 && "Node count imbalance!"); 97239462Sdim setNumTombstones(0); 98193323Sed } 99193323Sed 100193323Sed /// count - Return true if the specified key is in the map. 101193323Sed bool count(const KeyT &Val) const { 102239462Sdim const BucketT *TheBucket; 103193323Sed return LookupBucketFor(Val, TheBucket); 104193323Sed } 105193323Sed 106193323Sed iterator find(const KeyT &Val) { 107193323Sed BucketT *TheBucket; 108193323Sed if (LookupBucketFor(Val, TheBucket)) 109239462Sdim return iterator(TheBucket, getBucketsEnd(), true); 110193323Sed return end(); 111193323Sed } 112193323Sed const_iterator find(const KeyT &Val) const { 113239462Sdim const BucketT *TheBucket; 114193323Sed if (LookupBucketFor(Val, TheBucket)) 115239462Sdim return const_iterator(TheBucket, getBucketsEnd(), true); 116193323Sed return end(); 117193323Sed } 118193323Sed 119234353Sdim /// Alternate version of find() which allows a different, and possibly 120234353Sdim /// less expensive, key type. 121234353Sdim /// The DenseMapInfo is responsible for supplying methods 122234353Sdim /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key 123234353Sdim /// type used. 124234353Sdim template<class LookupKeyT> 125234353Sdim iterator find_as(const LookupKeyT &Val) { 126234353Sdim BucketT *TheBucket; 127234353Sdim if (LookupBucketFor(Val, TheBucket)) 128239462Sdim return iterator(TheBucket, getBucketsEnd(), true); 129234353Sdim return end(); 130234353Sdim } 131234353Sdim template<class LookupKeyT> 132234353Sdim const_iterator find_as(const LookupKeyT &Val) const { 133239462Sdim const BucketT *TheBucket; 134234353Sdim if (LookupBucketFor(Val, TheBucket)) 135239462Sdim return const_iterator(TheBucket, getBucketsEnd(), true); 136234353Sdim return end(); 137234353Sdim } 138234353Sdim 139193323Sed /// lookup - Return the entry for the specified key, or a default 140193323Sed /// constructed value if no such entry exists. 141193323Sed ValueT lookup(const KeyT &Val) const { 142239462Sdim const BucketT *TheBucket; 143193323Sed if (LookupBucketFor(Val, TheBucket)) 144193323Sed return TheBucket->second; 145193323Sed return ValueT(); 146193323Sed } 147193323Sed 148198090Srdivacky // Inserts key,value pair into the map if the key isn't already in the map. 149198090Srdivacky // If the key is already in the map, it returns false and doesn't update the 150198090Srdivacky // value. 151193323Sed std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { 152193323Sed BucketT *TheBucket; 153193323Sed if (LookupBucketFor(KV.first, TheBucket)) 154239462Sdim return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), 155193323Sed false); // Already in map. 156193323Sed 157193323Sed // Otherwise, insert the new element. 158193323Sed TheBucket = InsertIntoBucket(KV.first, KV.second, TheBucket); 159239462Sdim return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), true); 160193323Sed } 161193323Sed 162249423Sdim#if LLVM_HAS_RVALUE_REFERENCES 163249423Sdim // Inserts key,value pair into the map if the key isn't already in the map. 164249423Sdim // If the key is already in the map, it returns false and doesn't update the 165249423Sdim // value. 166249423Sdim std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) { 167249423Sdim BucketT *TheBucket; 168249423Sdim if (LookupBucketFor(KV.first, TheBucket)) 169249423Sdim return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), 170249423Sdim false); // Already in map. 171249423Sdim 172249423Sdim // Otherwise, insert the new element. 173249423Sdim TheBucket = InsertIntoBucket(std::move(KV.first), 174249423Sdim std::move(KV.second), 175249423Sdim TheBucket); 176249423Sdim return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), true); 177249423Sdim } 178249423Sdim#endif 179249423Sdim 180193323Sed /// insert - Range insertion of pairs. 181193323Sed template<typename InputIt> 182193323Sed void insert(InputIt I, InputIt E) { 183193323Sed for (; I != E; ++I) 184193323Sed insert(*I); 185193323Sed } 186193323Sed 187193323Sed 188193323Sed bool erase(const KeyT &Val) { 189193323Sed BucketT *TheBucket; 190193323Sed if (!LookupBucketFor(Val, TheBucket)) 191193323Sed return false; // not in map. 192193323Sed 193193323Sed TheBucket->second.~ValueT(); 194193323Sed TheBucket->first = getTombstoneKey(); 195239462Sdim decrementNumEntries(); 196239462Sdim incrementNumTombstones(); 197193323Sed return true; 198193323Sed } 199212904Sdim void erase(iterator I) { 200193323Sed BucketT *TheBucket = &*I; 201193323Sed TheBucket->second.~ValueT(); 202193323Sed TheBucket->first = getTombstoneKey(); 203239462Sdim decrementNumEntries(); 204239462Sdim incrementNumTombstones(); 205193323Sed } 206193323Sed 207193323Sed value_type& FindAndConstruct(const KeyT &Key) { 208193323Sed BucketT *TheBucket; 209193323Sed if (LookupBucketFor(Key, TheBucket)) 210193323Sed return *TheBucket; 211193323Sed 212193323Sed return *InsertIntoBucket(Key, ValueT(), TheBucket); 213193323Sed } 214193323Sed 215193323Sed ValueT &operator[](const KeyT &Key) { 216193323Sed return FindAndConstruct(Key).second; 217193323Sed } 218193323Sed 219249423Sdim#if LLVM_HAS_RVALUE_REFERENCES 220239462Sdim value_type& FindAndConstruct(KeyT &&Key) { 221239462Sdim BucketT *TheBucket; 222239462Sdim if (LookupBucketFor(Key, TheBucket)) 223239462Sdim return *TheBucket; 224239462Sdim 225239462Sdim return *InsertIntoBucket(Key, ValueT(), TheBucket); 226193323Sed } 227193323Sed 228239462Sdim ValueT &operator[](KeyT &&Key) { 229239462Sdim return FindAndConstruct(Key).second; 230239462Sdim } 231239462Sdim#endif 232239462Sdim 233193323Sed /// isPointerIntoBucketsArray - Return true if the specified pointer points 234193323Sed /// somewhere into the DenseMap's array of buckets (i.e. either to a key or 235193323Sed /// value in the DenseMap). 236193323Sed bool isPointerIntoBucketsArray(const void *Ptr) const { 237239462Sdim return Ptr >= getBuckets() && Ptr < getBucketsEnd(); 238193323Sed } 239193323Sed 240193323Sed /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets 241193323Sed /// array. In conjunction with the previous method, this can be used to 242193323Sed /// determine whether an insertion caused the DenseMap to reallocate. 243239462Sdim const void *getPointerIntoBucketsArray() const { return getBuckets(); } 244193323Sed 245239462Sdimprotected: 246239462Sdim DenseMapBase() {} 247239462Sdim 248239462Sdim void destroyAll() { 249239462Sdim if (getNumBuckets() == 0) // Nothing to do. 250239462Sdim return; 251239462Sdim 252239462Sdim const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 253239462Sdim for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) { 254239462Sdim if (!KeyInfoT::isEqual(P->first, EmptyKey) && 255239462Sdim !KeyInfoT::isEqual(P->first, TombstoneKey)) 256239462Sdim P->second.~ValueT(); 257239462Sdim P->first.~KeyT(); 258193323Sed } 259193323Sed 260198090Srdivacky#ifndef NDEBUG 261239462Sdim memset((void*)getBuckets(), 0x5a, sizeof(BucketT)*getNumBuckets()); 262198090Srdivacky#endif 263239462Sdim } 264193323Sed 265239462Sdim void initEmpty() { 266239462Sdim setNumEntries(0); 267239462Sdim setNumTombstones(0); 268221345Sdim 269239462Sdim assert((getNumBuckets() & (getNumBuckets()-1)) == 0 && 270239462Sdim "# initial buckets must be a power of two!"); 271239462Sdim const KeyT EmptyKey = getEmptyKey(); 272239462Sdim for (BucketT *B = getBuckets(), *E = getBucketsEnd(); B != E; ++B) 273239462Sdim new (&B->first) KeyT(EmptyKey); 274239462Sdim } 275239462Sdim 276239462Sdim void moveFromOldBuckets(BucketT *OldBucketsBegin, BucketT *OldBucketsEnd) { 277239462Sdim initEmpty(); 278239462Sdim 279239462Sdim // Insert all the old elements. 280239462Sdim const KeyT EmptyKey = getEmptyKey(); 281239462Sdim const KeyT TombstoneKey = getTombstoneKey(); 282239462Sdim for (BucketT *B = OldBucketsBegin, *E = OldBucketsEnd; B != E; ++B) { 283239462Sdim if (!KeyInfoT::isEqual(B->first, EmptyKey) && 284239462Sdim !KeyInfoT::isEqual(B->first, TombstoneKey)) { 285239462Sdim // Insert the key/value into the new table. 286239462Sdim BucketT *DestBucket; 287239462Sdim bool FoundVal = LookupBucketFor(B->first, DestBucket); 288239462Sdim (void)FoundVal; // silence warning. 289239462Sdim assert(!FoundVal && "Key already in new map?"); 290239462Sdim DestBucket->first = llvm_move(B->first); 291239462Sdim new (&DestBucket->second) ValueT(llvm_move(B->second)); 292239462Sdim incrementNumEntries(); 293239462Sdim 294239462Sdim // Free the value. 295239462Sdim B->second.~ValueT(); 296239462Sdim } 297239462Sdim B->first.~KeyT(); 298221345Sdim } 299221345Sdim 300239462Sdim#ifndef NDEBUG 301239462Sdim if (OldBucketsBegin != OldBucketsEnd) 302239462Sdim memset((void*)OldBucketsBegin, 0x5a, 303239462Sdim sizeof(BucketT) * (OldBucketsEnd - OldBucketsBegin)); 304239462Sdim#endif 305239462Sdim } 306221345Sdim 307239462Sdim template <typename OtherBaseT> 308239462Sdim void copyFrom(const DenseMapBase<OtherBaseT, KeyT, ValueT, KeyInfoT>& other) { 309239462Sdim assert(getNumBuckets() == other.getNumBuckets()); 310239462Sdim 311239462Sdim setNumEntries(other.getNumEntries()); 312239462Sdim setNumTombstones(other.getNumTombstones()); 313239462Sdim 314234353Sdim if (isPodLike<KeyT>::value && isPodLike<ValueT>::value) 315239462Sdim memcpy(getBuckets(), other.getBuckets(), 316239462Sdim getNumBuckets() * sizeof(BucketT)); 317193323Sed else 318239462Sdim for (size_t i = 0; i < getNumBuckets(); ++i) { 319239462Sdim new (&getBuckets()[i].first) KeyT(other.getBuckets()[i].first); 320239462Sdim if (!KeyInfoT::isEqual(getBuckets()[i].first, getEmptyKey()) && 321239462Sdim !KeyInfoT::isEqual(getBuckets()[i].first, getTombstoneKey())) 322239462Sdim new (&getBuckets()[i].second) ValueT(other.getBuckets()[i].second); 323193323Sed } 324193323Sed } 325193323Sed 326239462Sdim void swap(DenseMapBase& RHS) { 327239462Sdim std::swap(getNumEntries(), RHS.getNumEntries()); 328239462Sdim std::swap(getNumTombstones(), RHS.getNumTombstones()); 329239462Sdim } 330239462Sdim 331239462Sdim static unsigned getHashValue(const KeyT &Val) { 332239462Sdim return KeyInfoT::getHashValue(Val); 333239462Sdim } 334239462Sdim template<typename LookupKeyT> 335239462Sdim static unsigned getHashValue(const LookupKeyT &Val) { 336239462Sdim return KeyInfoT::getHashValue(Val); 337239462Sdim } 338239462Sdim static const KeyT getEmptyKey() { 339239462Sdim return KeyInfoT::getEmptyKey(); 340239462Sdim } 341239462Sdim static const KeyT getTombstoneKey() { 342239462Sdim return KeyInfoT::getTombstoneKey(); 343239462Sdim } 344239462Sdim 345239462Sdimprivate: 346239462Sdim unsigned getNumEntries() const { 347239462Sdim return static_cast<const DerivedT *>(this)->getNumEntries(); 348239462Sdim } 349239462Sdim void setNumEntries(unsigned Num) { 350239462Sdim static_cast<DerivedT *>(this)->setNumEntries(Num); 351239462Sdim } 352239462Sdim void incrementNumEntries() { 353239462Sdim setNumEntries(getNumEntries() + 1); 354239462Sdim } 355239462Sdim void decrementNumEntries() { 356239462Sdim setNumEntries(getNumEntries() - 1); 357239462Sdim } 358239462Sdim unsigned getNumTombstones() const { 359239462Sdim return static_cast<const DerivedT *>(this)->getNumTombstones(); 360239462Sdim } 361239462Sdim void setNumTombstones(unsigned Num) { 362239462Sdim static_cast<DerivedT *>(this)->setNumTombstones(Num); 363239462Sdim } 364239462Sdim void incrementNumTombstones() { 365239462Sdim setNumTombstones(getNumTombstones() + 1); 366239462Sdim } 367239462Sdim void decrementNumTombstones() { 368239462Sdim setNumTombstones(getNumTombstones() - 1); 369239462Sdim } 370239462Sdim const BucketT *getBuckets() const { 371239462Sdim return static_cast<const DerivedT *>(this)->getBuckets(); 372239462Sdim } 373239462Sdim BucketT *getBuckets() { 374239462Sdim return static_cast<DerivedT *>(this)->getBuckets(); 375239462Sdim } 376239462Sdim unsigned getNumBuckets() const { 377239462Sdim return static_cast<const DerivedT *>(this)->getNumBuckets(); 378239462Sdim } 379239462Sdim BucketT *getBucketsEnd() { 380239462Sdim return getBuckets() + getNumBuckets(); 381239462Sdim } 382239462Sdim const BucketT *getBucketsEnd() const { 383239462Sdim return getBuckets() + getNumBuckets(); 384239462Sdim } 385239462Sdim 386239462Sdim void grow(unsigned AtLeast) { 387239462Sdim static_cast<DerivedT *>(this)->grow(AtLeast); 388239462Sdim } 389239462Sdim 390239462Sdim void shrink_and_clear() { 391239462Sdim static_cast<DerivedT *>(this)->shrink_and_clear(); 392239462Sdim } 393239462Sdim 394239462Sdim 395193323Sed BucketT *InsertIntoBucket(const KeyT &Key, const ValueT &Value, 396193323Sed BucketT *TheBucket) { 397239462Sdim TheBucket = InsertIntoBucketImpl(Key, TheBucket); 398239462Sdim 399239462Sdim TheBucket->first = Key; 400239462Sdim new (&TheBucket->second) ValueT(Value); 401239462Sdim return TheBucket; 402239462Sdim } 403239462Sdim 404249423Sdim#if LLVM_HAS_RVALUE_REFERENCES 405239462Sdim BucketT *InsertIntoBucket(const KeyT &Key, ValueT &&Value, 406239462Sdim BucketT *TheBucket) { 407239462Sdim TheBucket = InsertIntoBucketImpl(Key, TheBucket); 408239462Sdim 409239462Sdim TheBucket->first = Key; 410239462Sdim new (&TheBucket->second) ValueT(std::move(Value)); 411239462Sdim return TheBucket; 412239462Sdim } 413239462Sdim 414239462Sdim BucketT *InsertIntoBucket(KeyT &&Key, ValueT &&Value, BucketT *TheBucket) { 415239462Sdim TheBucket = InsertIntoBucketImpl(Key, TheBucket); 416239462Sdim 417239462Sdim TheBucket->first = std::move(Key); 418239462Sdim new (&TheBucket->second) ValueT(std::move(Value)); 419239462Sdim return TheBucket; 420239462Sdim } 421239462Sdim#endif 422239462Sdim 423239462Sdim BucketT *InsertIntoBucketImpl(const KeyT &Key, BucketT *TheBucket) { 424193323Sed // If the load of the hash table is more than 3/4, or if fewer than 1/8 of 425193323Sed // the buckets are empty (meaning that many are filled with tombstones), 426193323Sed // grow the table. 427193323Sed // 428193323Sed // The later case is tricky. For example, if we had one empty bucket with 429193323Sed // tons of tombstones, failing lookups (e.g. for insertion) would have to 430193323Sed // probe almost the entire table until it found the empty bucket. If the 431193323Sed // table completely filled with tombstones, no lookup would ever succeed, 432193323Sed // causing infinite loops in lookup. 433239462Sdim unsigned NewNumEntries = getNumEntries() + 1; 434239462Sdim unsigned NumBuckets = getNumBuckets(); 435239462Sdim if (NewNumEntries*4 >= NumBuckets*3) { 436193323Sed this->grow(NumBuckets * 2); 437193323Sed LookupBucketFor(Key, TheBucket); 438239462Sdim NumBuckets = getNumBuckets(); 439193323Sed } 440239462Sdim if (NumBuckets-(NewNumEntries+getNumTombstones()) <= NumBuckets/8) { 441243830Sdim this->grow(NumBuckets * 2); 442221345Sdim LookupBucketFor(Key, TheBucket); 443221345Sdim } 444243830Sdim assert(TheBucket); 445193323Sed 446239462Sdim // Only update the state after we've grown our bucket space appropriately 447239462Sdim // so that when growing buckets we have self-consistent entry count. 448239462Sdim incrementNumEntries(); 449239462Sdim 450193323Sed // If we are writing over a tombstone, remember this. 451249423Sdim const KeyT EmptyKey = getEmptyKey(); 452249423Sdim if (!KeyInfoT::isEqual(TheBucket->first, EmptyKey)) 453239462Sdim decrementNumTombstones(); 454193323Sed 455193323Sed return TheBucket; 456193323Sed } 457193323Sed 458193323Sed /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in 459193323Sed /// FoundBucket. If the bucket contains the key and a value, this returns 460193323Sed /// true, otherwise it returns a bucket with an empty marker or tombstone and 461193323Sed /// returns false. 462234353Sdim template<typename LookupKeyT> 463239462Sdim bool LookupBucketFor(const LookupKeyT &Val, 464239462Sdim const BucketT *&FoundBucket) const { 465239462Sdim const BucketT *BucketsPtr = getBuckets(); 466239462Sdim const unsigned NumBuckets = getNumBuckets(); 467193323Sed 468221345Sdim if (NumBuckets == 0) { 469221345Sdim FoundBucket = 0; 470221345Sdim return false; 471221345Sdim } 472221345Sdim 473193323Sed // FoundTombstone - Keep track of whether we find a tombstone while probing. 474239462Sdim const BucketT *FoundTombstone = 0; 475193323Sed const KeyT EmptyKey = getEmptyKey(); 476193323Sed const KeyT TombstoneKey = getTombstoneKey(); 477193323Sed assert(!KeyInfoT::isEqual(Val, EmptyKey) && 478193323Sed !KeyInfoT::isEqual(Val, TombstoneKey) && 479193323Sed "Empty/Tombstone value shouldn't be inserted into map!"); 480193323Sed 481239462Sdim unsigned BucketNo = getHashValue(Val) & (NumBuckets-1); 482239462Sdim unsigned ProbeAmt = 1; 483193323Sed while (1) { 484239462Sdim const BucketT *ThisBucket = BucketsPtr + BucketNo; 485193323Sed // Found Val's bucket? If so, return it. 486234353Sdim if (KeyInfoT::isEqual(Val, ThisBucket->first)) { 487193323Sed FoundBucket = ThisBucket; 488193323Sed return true; 489193323Sed } 490193323Sed 491193323Sed // If we found an empty bucket, the key doesn't exist in the set. 492193323Sed // Insert it and return the default value. 493193323Sed if (KeyInfoT::isEqual(ThisBucket->first, EmptyKey)) { 494193323Sed // If we've already seen a tombstone while probing, fill it in instead 495193323Sed // of the empty bucket we eventually probed to. 496193323Sed FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket; 497193323Sed return false; 498193323Sed } 499193323Sed 500193323Sed // If this is a tombstone, remember it. If Val ends up not in the map, we 501193323Sed // prefer to return it than something that would require more probing. 502193323Sed if (KeyInfoT::isEqual(ThisBucket->first, TombstoneKey) && !FoundTombstone) 503193323Sed FoundTombstone = ThisBucket; // Remember the first tombstone found. 504193323Sed 505193323Sed // Otherwise, it's a hash collision or a tombstone, continue quadratic 506193323Sed // probing. 507193323Sed BucketNo += ProbeAmt++; 508239462Sdim BucketNo &= (NumBuckets-1); 509193323Sed } 510193323Sed } 511193323Sed 512239462Sdim template <typename LookupKeyT> 513239462Sdim bool LookupBucketFor(const LookupKeyT &Val, BucketT *&FoundBucket) { 514239462Sdim const BucketT *ConstFoundBucket; 515239462Sdim bool Result = const_cast<const DenseMapBase *>(this) 516239462Sdim ->LookupBucketFor(Val, ConstFoundBucket); 517239462Sdim FoundBucket = const_cast<BucketT *>(ConstFoundBucket); 518239462Sdim return Result; 519239462Sdim } 520221345Sdim 521239462Sdimpublic: 522239462Sdim /// Return the approximate size (in bytes) of the actual map. 523239462Sdim /// This is just the raw memory used by DenseMap. 524239462Sdim /// If entries are pointers to objects, the size of the referenced objects 525239462Sdim /// are not included. 526239462Sdim size_t getMemorySize() const { 527239462Sdim return getNumBuckets() * sizeof(BucketT); 528239462Sdim } 529239462Sdim}; 530239462Sdim 531239462Sdimtemplate<typename KeyT, typename ValueT, 532239462Sdim typename KeyInfoT = DenseMapInfo<KeyT> > 533239462Sdimclass DenseMap 534239462Sdim : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT>, 535239462Sdim KeyT, ValueT, KeyInfoT> { 536239462Sdim // Lift some types from the dependent base class into this class for 537239462Sdim // simplicity of referring to them. 538239462Sdim typedef DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT> BaseT; 539239462Sdim typedef typename BaseT::BucketT BucketT; 540239462Sdim friend class DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT>; 541239462Sdim 542239462Sdim BucketT *Buckets; 543239462Sdim unsigned NumEntries; 544239462Sdim unsigned NumTombstones; 545239462Sdim unsigned NumBuckets; 546239462Sdim 547239462Sdimpublic: 548239462Sdim explicit DenseMap(unsigned NumInitBuckets = 0) { 549239462Sdim init(NumInitBuckets); 550239462Sdim } 551239462Sdim 552249423Sdim DenseMap(const DenseMap &other) : BaseT() { 553239462Sdim init(0); 554239462Sdim copyFrom(other); 555239462Sdim } 556239462Sdim 557249423Sdim#if LLVM_HAS_RVALUE_REFERENCES 558249423Sdim DenseMap(DenseMap &&other) : BaseT() { 559239462Sdim init(0); 560239462Sdim swap(other); 561239462Sdim } 562239462Sdim#endif 563239462Sdim 564239462Sdim template<typename InputIt> 565239462Sdim DenseMap(const InputIt &I, const InputIt &E) { 566239462Sdim init(NextPowerOf2(std::distance(I, E))); 567239462Sdim this->insert(I, E); 568239462Sdim } 569239462Sdim 570239462Sdim ~DenseMap() { 571239462Sdim this->destroyAll(); 572239462Sdim operator delete(Buckets); 573239462Sdim } 574239462Sdim 575239462Sdim void swap(DenseMap& RHS) { 576239462Sdim std::swap(Buckets, RHS.Buckets); 577239462Sdim std::swap(NumEntries, RHS.NumEntries); 578239462Sdim std::swap(NumTombstones, RHS.NumTombstones); 579239462Sdim std::swap(NumBuckets, RHS.NumBuckets); 580239462Sdim } 581239462Sdim 582239462Sdim DenseMap& operator=(const DenseMap& other) { 583239462Sdim copyFrom(other); 584239462Sdim return *this; 585239462Sdim } 586239462Sdim 587249423Sdim#if LLVM_HAS_RVALUE_REFERENCES 588239462Sdim DenseMap& operator=(DenseMap &&other) { 589239462Sdim this->destroyAll(); 590239462Sdim operator delete(Buckets); 591239462Sdim init(0); 592239462Sdim swap(other); 593239462Sdim return *this; 594239462Sdim } 595239462Sdim#endif 596239462Sdim 597239462Sdim void copyFrom(const DenseMap& other) { 598239462Sdim this->destroyAll(); 599239462Sdim operator delete(Buckets); 600239462Sdim if (allocateBuckets(other.NumBuckets)) { 601239462Sdim this->BaseT::copyFrom(other); 602239462Sdim } else { 603239462Sdim NumEntries = 0; 604239462Sdim NumTombstones = 0; 605221345Sdim } 606239462Sdim } 607221345Sdim 608239462Sdim void init(unsigned InitBuckets) { 609239462Sdim if (allocateBuckets(InitBuckets)) { 610239462Sdim this->BaseT::initEmpty(); 611239462Sdim } else { 612239462Sdim NumEntries = 0; 613239462Sdim NumTombstones = 0; 614239462Sdim } 615193323Sed } 616193323Sed 617193323Sed void grow(unsigned AtLeast) { 618193323Sed unsigned OldNumBuckets = NumBuckets; 619193323Sed BucketT *OldBuckets = Buckets; 620193323Sed 621251662Sdim allocateBuckets(std::max<unsigned>(64, static_cast<unsigned>(NextPowerOf2(AtLeast-1)))); 622239462Sdim assert(Buckets); 623239462Sdim if (!OldBuckets) { 624239462Sdim this->BaseT::initEmpty(); 625239462Sdim return; 626239462Sdim } 627221345Sdim 628239462Sdim this->moveFromOldBuckets(OldBuckets, OldBuckets+OldNumBuckets); 629193323Sed 630239462Sdim // Free the old table. 631239462Sdim operator delete(OldBuckets); 632239462Sdim } 633193323Sed 634239462Sdim void shrink_and_clear() { 635239462Sdim unsigned OldNumEntries = NumEntries; 636239462Sdim this->destroyAll(); 637193323Sed 638239462Sdim // Reduce the number of buckets. 639239462Sdim unsigned NewNumBuckets = 0; 640239462Sdim if (OldNumEntries) 641239462Sdim NewNumBuckets = std::max(64, 1 << (Log2_32_Ceil(OldNumEntries) + 1)); 642239462Sdim if (NewNumBuckets == NumBuckets) { 643239462Sdim this->BaseT::initEmpty(); 644239462Sdim return; 645239462Sdim } 646239462Sdim 647239462Sdim operator delete(Buckets); 648239462Sdim init(NewNumBuckets); 649239462Sdim } 650239462Sdim 651239462Sdimprivate: 652239462Sdim unsigned getNumEntries() const { 653239462Sdim return NumEntries; 654239462Sdim } 655239462Sdim void setNumEntries(unsigned Num) { 656239462Sdim NumEntries = Num; 657239462Sdim } 658239462Sdim 659239462Sdim unsigned getNumTombstones() const { 660239462Sdim return NumTombstones; 661239462Sdim } 662239462Sdim void setNumTombstones(unsigned Num) { 663239462Sdim NumTombstones = Num; 664239462Sdim } 665239462Sdim 666239462Sdim BucketT *getBuckets() const { 667239462Sdim return Buckets; 668239462Sdim } 669239462Sdim 670239462Sdim unsigned getNumBuckets() const { 671239462Sdim return NumBuckets; 672239462Sdim } 673239462Sdim 674239462Sdim bool allocateBuckets(unsigned Num) { 675239462Sdim NumBuckets = Num; 676239462Sdim if (NumBuckets == 0) { 677239462Sdim Buckets = 0; 678239462Sdim return false; 679239462Sdim } 680239462Sdim 681239462Sdim Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT) * NumBuckets)); 682239462Sdim return true; 683239462Sdim } 684239462Sdim}; 685239462Sdim 686239462Sdimtemplate<typename KeyT, typename ValueT, 687239462Sdim unsigned InlineBuckets = 4, 688239462Sdim typename KeyInfoT = DenseMapInfo<KeyT> > 689239462Sdimclass SmallDenseMap 690239462Sdim : public DenseMapBase<SmallDenseMap<KeyT, ValueT, InlineBuckets, KeyInfoT>, 691239462Sdim KeyT, ValueT, KeyInfoT> { 692239462Sdim // Lift some types from the dependent base class into this class for 693239462Sdim // simplicity of referring to them. 694239462Sdim typedef DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT> BaseT; 695239462Sdim typedef typename BaseT::BucketT BucketT; 696239462Sdim friend class DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT>; 697239462Sdim 698239462Sdim unsigned Small : 1; 699239462Sdim unsigned NumEntries : 31; 700239462Sdim unsigned NumTombstones; 701239462Sdim 702239462Sdim struct LargeRep { 703239462Sdim BucketT *Buckets; 704239462Sdim unsigned NumBuckets; 705239462Sdim }; 706239462Sdim 707239462Sdim /// A "union" of an inline bucket array and the struct representing 708239462Sdim /// a large bucket. This union will be discriminated by the 'Small' bit. 709239462Sdim AlignedCharArrayUnion<BucketT[InlineBuckets], LargeRep> storage; 710239462Sdim 711239462Sdimpublic: 712239462Sdim explicit SmallDenseMap(unsigned NumInitBuckets = 0) { 713239462Sdim init(NumInitBuckets); 714239462Sdim } 715239462Sdim 716239462Sdim SmallDenseMap(const SmallDenseMap &other) { 717239462Sdim init(0); 718239462Sdim copyFrom(other); 719239462Sdim } 720239462Sdim 721249423Sdim#if LLVM_HAS_RVALUE_REFERENCES 722239462Sdim SmallDenseMap(SmallDenseMap &&other) { 723239462Sdim init(0); 724239462Sdim swap(other); 725239462Sdim } 726239462Sdim#endif 727239462Sdim 728239462Sdim template<typename InputIt> 729239462Sdim SmallDenseMap(const InputIt &I, const InputIt &E) { 730239462Sdim init(NextPowerOf2(std::distance(I, E))); 731239462Sdim this->insert(I, E); 732239462Sdim } 733239462Sdim 734239462Sdim ~SmallDenseMap() { 735239462Sdim this->destroyAll(); 736239462Sdim deallocateBuckets(); 737239462Sdim } 738239462Sdim 739239462Sdim void swap(SmallDenseMap& RHS) { 740239462Sdim unsigned TmpNumEntries = RHS.NumEntries; 741239462Sdim RHS.NumEntries = NumEntries; 742239462Sdim NumEntries = TmpNumEntries; 743239462Sdim std::swap(NumTombstones, RHS.NumTombstones); 744239462Sdim 745239462Sdim const KeyT EmptyKey = this->getEmptyKey(); 746239462Sdim const KeyT TombstoneKey = this->getTombstoneKey(); 747239462Sdim if (Small && RHS.Small) { 748239462Sdim // If we're swapping inline bucket arrays, we have to cope with some of 749239462Sdim // the tricky bits of DenseMap's storage system: the buckets are not 750239462Sdim // fully initialized. Thus we swap every key, but we may have 751239462Sdim // a one-directional move of the value. 752239462Sdim for (unsigned i = 0, e = InlineBuckets; i != e; ++i) { 753239462Sdim BucketT *LHSB = &getInlineBuckets()[i], 754239462Sdim *RHSB = &RHS.getInlineBuckets()[i]; 755239462Sdim bool hasLHSValue = (!KeyInfoT::isEqual(LHSB->first, EmptyKey) && 756239462Sdim !KeyInfoT::isEqual(LHSB->first, TombstoneKey)); 757239462Sdim bool hasRHSValue = (!KeyInfoT::isEqual(RHSB->first, EmptyKey) && 758239462Sdim !KeyInfoT::isEqual(RHSB->first, TombstoneKey)); 759239462Sdim if (hasLHSValue && hasRHSValue) { 760239462Sdim // Swap together if we can... 761239462Sdim std::swap(*LHSB, *RHSB); 762239462Sdim continue; 763239462Sdim } 764239462Sdim // Swap separately and handle any assymetry. 765239462Sdim std::swap(LHSB->first, RHSB->first); 766239462Sdim if (hasLHSValue) { 767239462Sdim new (&RHSB->second) ValueT(llvm_move(LHSB->second)); 768239462Sdim LHSB->second.~ValueT(); 769239462Sdim } else if (hasRHSValue) { 770239462Sdim new (&LHSB->second) ValueT(llvm_move(RHSB->second)); 771239462Sdim RHSB->second.~ValueT(); 772239462Sdim } 773193323Sed } 774239462Sdim return; 775193323Sed } 776239462Sdim if (!Small && !RHS.Small) { 777239462Sdim std::swap(getLargeRep()->Buckets, RHS.getLargeRep()->Buckets); 778239462Sdim std::swap(getLargeRep()->NumBuckets, RHS.getLargeRep()->NumBuckets); 779239462Sdim return; 780239462Sdim } 781193323Sed 782239462Sdim SmallDenseMap &SmallSide = Small ? *this : RHS; 783239462Sdim SmallDenseMap &LargeSide = Small ? RHS : *this; 784239462Sdim 785239462Sdim // First stash the large side's rep and move the small side across. 786239462Sdim LargeRep TmpRep = llvm_move(*LargeSide.getLargeRep()); 787239462Sdim LargeSide.getLargeRep()->~LargeRep(); 788239462Sdim LargeSide.Small = true; 789239462Sdim // This is similar to the standard move-from-old-buckets, but the bucket 790239462Sdim // count hasn't actually rotated in this case. So we have to carefully 791239462Sdim // move construct the keys and values into their new locations, but there 792239462Sdim // is no need to re-hash things. 793239462Sdim for (unsigned i = 0, e = InlineBuckets; i != e; ++i) { 794239462Sdim BucketT *NewB = &LargeSide.getInlineBuckets()[i], 795239462Sdim *OldB = &SmallSide.getInlineBuckets()[i]; 796239462Sdim new (&NewB->first) KeyT(llvm_move(OldB->first)); 797239462Sdim OldB->first.~KeyT(); 798239462Sdim if (!KeyInfoT::isEqual(NewB->first, EmptyKey) && 799239462Sdim !KeyInfoT::isEqual(NewB->first, TombstoneKey)) { 800239462Sdim new (&NewB->second) ValueT(llvm_move(OldB->second)); 801239462Sdim OldB->second.~ValueT(); 802239462Sdim } 803239462Sdim } 804239462Sdim 805239462Sdim // The hard part of moving the small buckets across is done, just move 806239462Sdim // the TmpRep into its new home. 807239462Sdim SmallSide.Small = false; 808239462Sdim new (SmallSide.getLargeRep()) LargeRep(llvm_move(TmpRep)); 809239462Sdim } 810239462Sdim 811239462Sdim SmallDenseMap& operator=(const SmallDenseMap& other) { 812239462Sdim copyFrom(other); 813239462Sdim return *this; 814239462Sdim } 815239462Sdim 816249423Sdim#if LLVM_HAS_RVALUE_REFERENCES 817239462Sdim SmallDenseMap& operator=(SmallDenseMap &&other) { 818239462Sdim this->destroyAll(); 819239462Sdim deallocateBuckets(); 820239462Sdim init(0); 821239462Sdim swap(other); 822239462Sdim return *this; 823239462Sdim } 824198090Srdivacky#endif 825239462Sdim 826239462Sdim void copyFrom(const SmallDenseMap& other) { 827239462Sdim this->destroyAll(); 828239462Sdim deallocateBuckets(); 829239462Sdim Small = true; 830239462Sdim if (other.getNumBuckets() > InlineBuckets) { 831239462Sdim Small = false; 832239462Sdim allocateBuckets(other.getNumBuckets()); 833239462Sdim } 834239462Sdim this->BaseT::copyFrom(other); 835193323Sed } 836193323Sed 837239462Sdim void init(unsigned InitBuckets) { 838239462Sdim Small = true; 839239462Sdim if (InitBuckets > InlineBuckets) { 840239462Sdim Small = false; 841239462Sdim new (getLargeRep()) LargeRep(allocateBuckets(InitBuckets)); 842239462Sdim } 843239462Sdim this->BaseT::initEmpty(); 844239462Sdim } 845193323Sed 846239462Sdim void grow(unsigned AtLeast) { 847243830Sdim if (AtLeast >= InlineBuckets) 848243830Sdim AtLeast = std::max<unsigned>(64, NextPowerOf2(AtLeast-1)); 849193323Sed 850239462Sdim if (Small) { 851243830Sdim if (AtLeast < InlineBuckets) 852239462Sdim return; // Nothing to do. 853193323Sed 854239462Sdim // First move the inline buckets into a temporary storage. 855239462Sdim AlignedCharArrayUnion<BucketT[InlineBuckets]> TmpStorage; 856239462Sdim BucketT *TmpBegin = reinterpret_cast<BucketT *>(TmpStorage.buffer); 857239462Sdim BucketT *TmpEnd = TmpBegin; 858239462Sdim 859239462Sdim // Loop over the buckets, moving non-empty, non-tombstones into the 860239462Sdim // temporary storage. Have the loop move the TmpEnd forward as it goes. 861239462Sdim const KeyT EmptyKey = this->getEmptyKey(); 862239462Sdim const KeyT TombstoneKey = this->getTombstoneKey(); 863239462Sdim for (BucketT *P = getBuckets(), *E = P + InlineBuckets; P != E; ++P) { 864239462Sdim if (!KeyInfoT::isEqual(P->first, EmptyKey) && 865239462Sdim !KeyInfoT::isEqual(P->first, TombstoneKey)) { 866239462Sdim assert(size_t(TmpEnd - TmpBegin) < InlineBuckets && 867239462Sdim "Too many inline buckets!"); 868239462Sdim new (&TmpEnd->first) KeyT(llvm_move(P->first)); 869239462Sdim new (&TmpEnd->second) ValueT(llvm_move(P->second)); 870239462Sdim ++TmpEnd; 871239462Sdim P->second.~ValueT(); 872239462Sdim } 873239462Sdim P->first.~KeyT(); 874193323Sed } 875239462Sdim 876239462Sdim // Now make this map use the large rep, and move all the entries back 877239462Sdim // into it. 878239462Sdim Small = false; 879239462Sdim new (getLargeRep()) LargeRep(allocateBuckets(AtLeast)); 880239462Sdim this->moveFromOldBuckets(TmpBegin, TmpEnd); 881239462Sdim return; 882193323Sed } 883193323Sed 884239462Sdim LargeRep OldRep = llvm_move(*getLargeRep()); 885239462Sdim getLargeRep()->~LargeRep(); 886239462Sdim if (AtLeast <= InlineBuckets) { 887239462Sdim Small = true; 888239462Sdim } else { 889239462Sdim new (getLargeRep()) LargeRep(allocateBuckets(AtLeast)); 890239462Sdim } 891239462Sdim 892239462Sdim this->moveFromOldBuckets(OldRep.Buckets, OldRep.Buckets+OldRep.NumBuckets); 893239462Sdim 894193323Sed // Free the old table. 895239462Sdim operator delete(OldRep.Buckets); 896239462Sdim } 897193323Sed 898239462Sdim void shrink_and_clear() { 899239462Sdim unsigned OldSize = this->size(); 900239462Sdim this->destroyAll(); 901239462Sdim 902239462Sdim // Reduce the number of buckets. 903239462Sdim unsigned NewNumBuckets = 0; 904239462Sdim if (OldSize) { 905239462Sdim NewNumBuckets = 1 << (Log2_32_Ceil(OldSize) + 1); 906239462Sdim if (NewNumBuckets > InlineBuckets && NewNumBuckets < 64u) 907239462Sdim NewNumBuckets = 64; 908239462Sdim } 909239462Sdim if ((Small && NewNumBuckets <= InlineBuckets) || 910239462Sdim (!Small && NewNumBuckets == getLargeRep()->NumBuckets)) { 911239462Sdim this->BaseT::initEmpty(); 912239462Sdim return; 913239462Sdim } 914239462Sdim 915239462Sdim deallocateBuckets(); 916239462Sdim init(NewNumBuckets); 917193323Sed } 918239462Sdim 919239462Sdimprivate: 920239462Sdim unsigned getNumEntries() const { 921239462Sdim return NumEntries; 922221345Sdim } 923239462Sdim void setNumEntries(unsigned Num) { 924239462Sdim assert(Num < INT_MAX && "Cannot support more than INT_MAX entries"); 925239462Sdim NumEntries = Num; 926239462Sdim } 927239462Sdim 928239462Sdim unsigned getNumTombstones() const { 929239462Sdim return NumTombstones; 930239462Sdim } 931239462Sdim void setNumTombstones(unsigned Num) { 932239462Sdim NumTombstones = Num; 933239462Sdim } 934239462Sdim 935239462Sdim const BucketT *getInlineBuckets() const { 936239462Sdim assert(Small); 937239462Sdim // Note that this cast does not violate aliasing rules as we assert that 938239462Sdim // the memory's dynamic type is the small, inline bucket buffer, and the 939239462Sdim // 'storage.buffer' static type is 'char *'. 940239462Sdim return reinterpret_cast<const BucketT *>(storage.buffer); 941239462Sdim } 942239462Sdim BucketT *getInlineBuckets() { 943239462Sdim return const_cast<BucketT *>( 944239462Sdim const_cast<const SmallDenseMap *>(this)->getInlineBuckets()); 945239462Sdim } 946239462Sdim const LargeRep *getLargeRep() const { 947239462Sdim assert(!Small); 948239462Sdim // Note, same rule about aliasing as with getInlineBuckets. 949239462Sdim return reinterpret_cast<const LargeRep *>(storage.buffer); 950239462Sdim } 951239462Sdim LargeRep *getLargeRep() { 952239462Sdim return const_cast<LargeRep *>( 953239462Sdim const_cast<const SmallDenseMap *>(this)->getLargeRep()); 954239462Sdim } 955239462Sdim 956239462Sdim const BucketT *getBuckets() const { 957239462Sdim return Small ? getInlineBuckets() : getLargeRep()->Buckets; 958239462Sdim } 959239462Sdim BucketT *getBuckets() { 960239462Sdim return const_cast<BucketT *>( 961239462Sdim const_cast<const SmallDenseMap *>(this)->getBuckets()); 962239462Sdim } 963239462Sdim unsigned getNumBuckets() const { 964239462Sdim return Small ? InlineBuckets : getLargeRep()->NumBuckets; 965239462Sdim } 966239462Sdim 967239462Sdim void deallocateBuckets() { 968239462Sdim if (Small) 969239462Sdim return; 970239462Sdim 971239462Sdim operator delete(getLargeRep()->Buckets); 972239462Sdim getLargeRep()->~LargeRep(); 973239462Sdim } 974239462Sdim 975239462Sdim LargeRep allocateBuckets(unsigned Num) { 976239462Sdim assert(Num > InlineBuckets && "Must allocate more buckets than are inline"); 977239462Sdim LargeRep Rep = { 978239462Sdim static_cast<BucketT*>(operator new(sizeof(BucketT) * Num)), Num 979239462Sdim }; 980239462Sdim return Rep; 981239462Sdim } 982193323Sed}; 983193323Sed 984199481Srdivackytemplate<typename KeyT, typename ValueT, 985234353Sdim typename KeyInfoT, bool IsConst> 986199481Srdivackyclass DenseMapIterator { 987199481Srdivacky typedef std::pair<KeyT, ValueT> Bucket; 988199481Srdivacky typedef DenseMapIterator<KeyT, ValueT, 989234353Sdim KeyInfoT, true> ConstIterator; 990234353Sdim friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, true>; 991193323Sedpublic: 992199481Srdivacky typedef ptrdiff_t difference_type; 993199481Srdivacky typedef typename conditional<IsConst, const Bucket, Bucket>::type value_type; 994199481Srdivacky typedef value_type *pointer; 995199481Srdivacky typedef value_type &reference; 996199481Srdivacky typedef std::forward_iterator_tag iterator_category; 997199481Srdivackyprivate: 998199481Srdivacky pointer Ptr, End; 999199481Srdivackypublic: 1000198090Srdivacky DenseMapIterator() : Ptr(0), End(0) {} 1001193323Sed 1002234353Sdim DenseMapIterator(pointer Pos, pointer E, bool NoAdvance = false) 1003234353Sdim : Ptr(Pos), End(E) { 1004234353Sdim if (!NoAdvance) AdvancePastEmptyBuckets(); 1005193323Sed } 1006193323Sed 1007199481Srdivacky // If IsConst is true this is a converting constructor from iterator to 1008199481Srdivacky // const_iterator and the default copy constructor is used. 1009199481Srdivacky // Otherwise this is a copy constructor for iterator. 1010199481Srdivacky DenseMapIterator(const DenseMapIterator<KeyT, ValueT, 1011234353Sdim KeyInfoT, false>& I) 1012199481Srdivacky : Ptr(I.Ptr), End(I.End) {} 1013199481Srdivacky 1014199481Srdivacky reference operator*() const { 1015199481Srdivacky return *Ptr; 1016193323Sed } 1017199481Srdivacky pointer operator->() const { 1018199481Srdivacky return Ptr; 1019193323Sed } 1020193323Sed 1021199481Srdivacky bool operator==(const ConstIterator &RHS) const { 1022199481Srdivacky return Ptr == RHS.operator->(); 1023193323Sed } 1024199481Srdivacky bool operator!=(const ConstIterator &RHS) const { 1025199481Srdivacky return Ptr != RHS.operator->(); 1026193323Sed } 1027193323Sed 1028198892Srdivacky inline DenseMapIterator& operator++() { // Preincrement 1029193323Sed ++Ptr; 1030193323Sed AdvancePastEmptyBuckets(); 1031193323Sed return *this; 1032193323Sed } 1033198892Srdivacky DenseMapIterator operator++(int) { // Postincrement 1034193323Sed DenseMapIterator tmp = *this; ++*this; return tmp; 1035193323Sed } 1036193323Sed 1037193323Sedprivate: 1038193323Sed void AdvancePastEmptyBuckets() { 1039193323Sed const KeyT Empty = KeyInfoT::getEmptyKey(); 1040193323Sed const KeyT Tombstone = KeyInfoT::getTombstoneKey(); 1041193323Sed 1042193323Sed while (Ptr != End && 1043193323Sed (KeyInfoT::isEqual(Ptr->first, Empty) || 1044193323Sed KeyInfoT::isEqual(Ptr->first, Tombstone))) 1045193323Sed ++Ptr; 1046193323Sed } 1047193323Sed}; 1048249423Sdim 1049234353Sdimtemplate<typename KeyT, typename ValueT, typename KeyInfoT> 1050226633Sdimstatic inline size_t 1051234353Sdimcapacity_in_bytes(const DenseMap<KeyT, ValueT, KeyInfoT> &X) { 1052226633Sdim return X.getMemorySize(); 1053226633Sdim} 1054193323Sed 1055193323Sed} // end namespace llvm 1056193323Sed 1057193323Sed#endif 1058