DenseMap.h revision 3a54b3dc87a581c203b18050b4f787b4ca28a12c
16e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner//===- llvm/ADT/DenseMap.h - Dense probed hash table ------------*- C++ -*-===// 26e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner// 36e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner// The LLVM Compiler Infrastructure 46e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 76e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner// 86e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner//===----------------------------------------------------------------------===// 96e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner// 106e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner// This file defines the DenseMap class. 116e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner// 126e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner//===----------------------------------------------------------------------===// 136e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 146e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner#ifndef LLVM_ADT_DENSEMAP_H 156e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner#define LLVM_ADT_DENSEMAP_H 166e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 176e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner#include "llvm/Support/DataTypes.h" 18398b40671b13018f88371b74822fa8ee2638577eOwen Anderson#include "llvm/Support/MathExtras.h" 196e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner#include <cassert> 20f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner#include <utility> 216e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 226e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnernamespace llvm { 233a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 246e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnertemplate<typename T> 2576c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattnerstruct DenseMapInfo { 266e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner //static inline T getEmptyKey(); 276e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner //static inline T getTombstoneKey(); 286e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner //static unsigned getHashValue(const T &Val); 2976c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner //static bool isEqual(const T &LHS, const T &RHS); 306e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner //static bool isPod() 316e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner}; 326e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 3376c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner// Provide DenseMapInfo for all pointers. 346e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnertemplate<typename T> 3576c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattnerstruct DenseMapInfo<T*> { 36276222a5ae189ed5c6a2afb248d4c8f0335585b4Reid Spencer static inline T* getEmptyKey() { return reinterpret_cast<T*>(-1); } 37276222a5ae189ed5c6a2afb248d4c8f0335585b4Reid Spencer static inline T* getTombstoneKey() { return reinterpret_cast<T*>(-2); } 386e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner static unsigned getHashValue(const T *PtrVal) { 393a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman return (unsigned((uintptr_t)PtrVal) >> 4) ^ 40f8a3ee1d637a747c87f72bc880445e6a82280ff0Chris Lattner (unsigned((uintptr_t)PtrVal) >> 9); 416e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 4276c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; } 4329ce95511f905df3a63e3b953a4a0179ead46865Owen Anderson static bool isPod() { return true; } 4429ce95511f905df3a63e3b953a4a0179ead46865Owen Anderson}; 4529ce95511f905df3a63e3b953a4a0179ead46865Owen Anderson 462dba6a1bdb7d78b4d1e5e69b81989816193e6b70Chris Lattner// Provide DenseMapInfo for unsigned ints. 472dba6a1bdb7d78b4d1e5e69b81989816193e6b70Chris Lattnertemplate<> struct DenseMapInfo<uint32_t> { 482dba6a1bdb7d78b4d1e5e69b81989816193e6b70Chris Lattner static inline uint32_t getEmptyKey() { return ~0; } 492dba6a1bdb7d78b4d1e5e69b81989816193e6b70Chris Lattner static inline uint32_t getTombstoneKey() { return ~0 - 1; } 502dba6a1bdb7d78b4d1e5e69b81989816193e6b70Chris Lattner static unsigned getHashValue(const uint32_t& Val) { return Val * 37; } 512dba6a1bdb7d78b4d1e5e69b81989816193e6b70Chris Lattner static bool isPod() { return true; } 522dba6a1bdb7d78b4d1e5e69b81989816193e6b70Chris Lattner static bool isEqual(const uint32_t& LHS, const uint32_t& RHS) { 532dba6a1bdb7d78b4d1e5e69b81989816193e6b70Chris Lattner return LHS == RHS; 542dba6a1bdb7d78b4d1e5e69b81989816193e6b70Chris Lattner } 552dba6a1bdb7d78b4d1e5e69b81989816193e6b70Chris Lattner}; 562dba6a1bdb7d78b4d1e5e69b81989816193e6b70Chris Lattner 572dba6a1bdb7d78b4d1e5e69b81989816193e6b70Chris Lattner// Provide DenseMapInfo for all pairs whose members have info. 582dba6a1bdb7d78b4d1e5e69b81989816193e6b70Chris Lattnertemplate<typename T, typename U> 592dba6a1bdb7d78b4d1e5e69b81989816193e6b70Chris Lattnerstruct DenseMapInfo<std::pair<T, U> > { 602dba6a1bdb7d78b4d1e5e69b81989816193e6b70Chris Lattner typedef std::pair<T, U> Pair; 612dba6a1bdb7d78b4d1e5e69b81989816193e6b70Chris Lattner typedef DenseMapInfo<T> FirstInfo; 622dba6a1bdb7d78b4d1e5e69b81989816193e6b70Chris Lattner typedef DenseMapInfo<U> SecondInfo; 632dba6a1bdb7d78b4d1e5e69b81989816193e6b70Chris Lattner 643a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman static inline Pair getEmptyKey() { 653a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman return std::make_pair(FirstInfo::getEmptyKey(), 663a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman SecondInfo::getEmptyKey()); 672dba6a1bdb7d78b4d1e5e69b81989816193e6b70Chris Lattner } 683a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman static inline Pair getTombstoneKey() { 693a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman return std::make_pair(FirstInfo::getTombstoneKey(), 70b9118246201592e7e6c1353a09f69e8a4d469d9dChris Lattner SecondInfo::getEmptyKey()); 71b9118246201592e7e6c1353a09f69e8a4d469d9dChris Lattner } 72b9118246201592e7e6c1353a09f69e8a4d469d9dChris Lattner static unsigned getHashValue(const Pair& PairVal) { 73b9118246201592e7e6c1353a09f69e8a4d469d9dChris Lattner uint64_t key = (uint64_t)FirstInfo::getHashValue(PairVal.first) << 32 74b9118246201592e7e6c1353a09f69e8a4d469d9dChris Lattner | (uint64_t)SecondInfo::getHashValue(PairVal.second); 75b9118246201592e7e6c1353a09f69e8a4d469d9dChris Lattner key += ~(key << 32); 76b9118246201592e7e6c1353a09f69e8a4d469d9dChris Lattner key ^= (key >> 22); 77b9118246201592e7e6c1353a09f69e8a4d469d9dChris Lattner key += ~(key << 13); 78b9118246201592e7e6c1353a09f69e8a4d469d9dChris Lattner key ^= (key >> 8); 79b9118246201592e7e6c1353a09f69e8a4d469d9dChris Lattner key += (key << 3); 80b9118246201592e7e6c1353a09f69e8a4d469d9dChris Lattner key ^= (key >> 15); 81b9118246201592e7e6c1353a09f69e8a4d469d9dChris Lattner key += ~(key << 27); 82b9118246201592e7e6c1353a09f69e8a4d469d9dChris Lattner key ^= (key >> 31); 83b9118246201592e7e6c1353a09f69e8a4d469d9dChris Lattner return (unsigned)key; 84b9118246201592e7e6c1353a09f69e8a4d469d9dChris Lattner } 85b9118246201592e7e6c1353a09f69e8a4d469d9dChris Lattner static bool isEqual(const Pair& LHS, const Pair& RHS) { return LHS == RHS; } 86b9118246201592e7e6c1353a09f69e8a4d469d9dChris Lattner static bool isPod() { return FirstInfo::isPod() && SecondInfo::isPod(); } 872dba6a1bdb7d78b4d1e5e69b81989816193e6b70Chris Lattner}; 882dba6a1bdb7d78b4d1e5e69b81989816193e6b70Chris Lattner 893a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukmantemplate<typename KeyT, typename ValueT, 9076c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner typename KeyInfoT = DenseMapInfo<KeyT>, 9176c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner typename ValueInfoT = DenseMapInfo<ValueT> > 92f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerclass DenseMapIterator; 93a76b1febd4fd258e8054395adedcbd477668d956Chris Lattnertemplate<typename KeyT, typename ValueT, 9476c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner typename KeyInfoT = DenseMapInfo<KeyT>, 9576c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner typename ValueInfoT = DenseMapInfo<ValueT> > 9670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattnerclass DenseMapConstIterator; 976e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 98a76b1febd4fd258e8054395adedcbd477668d956Chris Lattnertemplate<typename KeyT, typename ValueT, 9976c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner typename KeyInfoT = DenseMapInfo<KeyT>, 10076c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner typename ValueInfoT = DenseMapInfo<ValueT> > 1016e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnerclass DenseMap { 102f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner typedef std::pair<KeyT, ValueT> BucketT; 1036e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned NumBuckets; 1046e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *Buckets; 1053a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1066e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned NumEntries; 10704a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner unsigned NumTombstones; 1086e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnerpublic: 10913e781ebe7a39e008dd5e5de78983e095e8a1d02David Greene typedef KeyT key_type; 11013e781ebe7a39e008dd5e5de78983e095e8a1d02David Greene typedef ValueT mapped_type; 111aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek typedef BucketT value_type; 1123a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 11367280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson DenseMap(const DenseMap& other) { 11467280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson NumBuckets = 0; 11567280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson CopyFrom(other); 11667280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson } 1173a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1185a5f6b6e38b7155200903816f22501cce4ca36a7Chris Lattner explicit DenseMap(unsigned NumInitBuckets = 64) { 1196e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner init(NumInitBuckets); 1206e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1213a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1226e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner ~DenseMap() { 1236e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 1246e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { 12505831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(P->first, EmptyKey) && 12605831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(P->first, TombstoneKey)) 127f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner P->second.~ValueT(); 128f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner P->first.~KeyT(); 1296e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 13008c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman operator delete(Buckets); 1316e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1323a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 133a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner typedef DenseMapIterator<KeyT, ValueT, KeyInfoT> iterator; 134a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner typedef DenseMapConstIterator<KeyT, ValueT, KeyInfoT> const_iterator; 13570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline iterator begin() { 136a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return iterator(Buckets, Buckets+NumBuckets); 13770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 13870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline iterator end() { 139a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return iterator(Buckets+NumBuckets, Buckets+NumBuckets); 14070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 14170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline const_iterator begin() const { 142a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return const_iterator(Buckets, Buckets+NumBuckets); 14370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 14470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline const_iterator end() const { 145a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return const_iterator(Buckets+NumBuckets, Buckets+NumBuckets); 14670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 1473a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 14870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner bool empty() const { return NumEntries == 0; } 1496e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned size() const { return NumEntries; } 150d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin 151d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin /// Grow the densemap so that it has at least Size buckets. Does not shrink 152d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin void resize(size_t Size) { grow(Size); } 1533a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1546e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner void clear() { 15542e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner // If the capacity of the array is huge, and the # elements used is small, 15642e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner // shrink the array. 1576ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson if (NumEntries * 4 < NumBuckets && NumBuckets > 64) { 1586ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson shrink_and_clear(); 1596ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson return; 1606ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 1613a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1626e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 1636e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { 16405831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(P->first, EmptyKey)) { 16505831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(P->first, TombstoneKey)) { 1667b54452c84e478ab4d49ac08759ca4ec1badf2b2Chris Lattner P->second.~ValueT(); 1677b54452c84e478ab4d49ac08759ca4ec1badf2b2Chris Lattner --NumEntries; 1687b54452c84e478ab4d49ac08759ca4ec1badf2b2Chris Lattner } 169f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner P->first = EmptyKey; 1706e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1716e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1726e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner assert(NumEntries == 0 && "Node count imbalance!"); 17304a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner NumTombstones = 0; 1746e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1756ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson 1766e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// count - Return true if the specified key is in the map. 1776e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner bool count(const KeyT &Val) const { 1786e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *TheBucket; 1796e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return LookupBucketFor(Val, TheBucket); 1806e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1813a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 182569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner iterator find(const KeyT &Val) { 18370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner BucketT *TheBucket; 18470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner if (LookupBucketFor(Val, TheBucket)) 18570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return iterator(TheBucket, Buckets+NumBuckets); 18670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return end(); 18770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 188569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner const_iterator find(const KeyT &Val) const { 189569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner BucketT *TheBucket; 190569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner if (LookupBucketFor(Val, TheBucket)) 191569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner return const_iterator(TheBucket, Buckets+NumBuckets); 192569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner return end(); 193569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner } 1943a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1957b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar /// lookup - Return the entry for the specified key, or a default 1967b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar /// constructed value if no such entry exists. 1977b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar ValueT lookup(const KeyT &Val) const { 1987b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar BucketT *TheBucket; 1997b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar if (LookupBucketFor(Val, TheBucket)) 2007b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar return TheBucket->second; 2017b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar return ValueT(); 2027b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar } 2037b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar 2046b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { 20528f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner BucketT *TheBucket; 20628f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner if (LookupBucketFor(KV.first, TheBucket)) 2076b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman return std::make_pair(iterator(TheBucket, Buckets+NumBuckets), 2086b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman false); // Already in map. 2093a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 21028f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner // Otherwise, insert the new element. 2116b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman TheBucket = InsertIntoBucket(KV.first, KV.second, TheBucket); 2126b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman return std::make_pair(iterator(TheBucket, Buckets+NumBuckets), 2136b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman true); 21428f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner } 2153a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 216b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner /// insert - Range insertion of pairs. 217b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner template<typename InputIt> 218b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner void insert(InputIt I, InputIt E) { 219b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner for (; I != E; ++I) 220b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner insert(*I); 221b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner } 222b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner 2233a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 22470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner bool erase(const KeyT &Val) { 22570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner BucketT *TheBucket; 22670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner if (!LookupBucketFor(Val, TheBucket)) 22770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return false; // not in map. 22870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner 22970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->second.~ValueT(); 23070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->first = getTombstoneKey(); 23170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner --NumEntries; 23204a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner ++NumTombstones; 23370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return true; 23470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 23570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner bool erase(iterator I) { 23670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner BucketT *TheBucket = &*I; 23770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->second.~ValueT(); 23870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->first = getTombstoneKey(); 23970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner --NumEntries; 24004a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner ++NumTombstones; 24170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return true; 24270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 243aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek 244aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek value_type& FindAndConstruct(const KeyT &Key) { 2456e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *TheBucket; 24628f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner if (LookupBucketFor(Key, TheBucket)) 247aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek return *TheBucket; 2483a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 249aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek return *InsertIntoBucket(Key, ValueT(), TheBucket); 250aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek } 2513a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 252aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek ValueT &operator[](const KeyT &Key) { 253aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek return FindAndConstruct(Key).second; 25428f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner } 2553a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 25667280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson DenseMap& operator=(const DenseMap& other) { 25767280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson CopyFrom(other); 2583d345631db71174ffc4997a88c09f21eb9ed052bOwen Anderson return *this; 25967280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson } 2603a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 26128f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattnerprivate: 26267280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson void CopyFrom(const DenseMap& other) { 26329ce95511f905df3a63e3b953a4a0179ead46865Owen Anderson if (NumBuckets != 0 && (!KeyInfoT::isPod() || !ValueInfoT::isPod())) { 26467280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 26567280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { 26605831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(P->first, EmptyKey) && 26705831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(P->first, TombstoneKey)) 26867280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson P->second.~ValueT(); 26967280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson P->first.~KeyT(); 27067280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson } 27167280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson } 2723a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 27367280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson NumEntries = other.NumEntries; 27467280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson NumTombstones = other.NumTombstones; 2753a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 27667280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson if (NumBuckets) 27708c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman operator delete(Buckets); 27808c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT) * 27908c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman other.NumBuckets)); 2803a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 28129ce95511f905df3a63e3b953a4a0179ead46865Owen Anderson if (KeyInfoT::isPod() && ValueInfoT::isPod()) 2829544dc294f63ce116fbab398a8874ebf834cf41eOwen Anderson memcpy(Buckets, other.Buckets, other.NumBuckets * sizeof(BucketT)); 2839544dc294f63ce116fbab398a8874ebf834cf41eOwen Anderson else 2849544dc294f63ce116fbab398a8874ebf834cf41eOwen Anderson for (size_t i = 0; i < other.NumBuckets; ++i) { 2852b7470eb54880ce7f74469d6e09eaf7f0864f8abOwen Anderson new (&Buckets[i].first) KeyT(other.Buckets[i].first); 28605831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(Buckets[i].first, getEmptyKey()) && 28705831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(Buckets[i].first, getTombstoneKey())) 2884938d347723d452786c1a7c1d1b9ec79121b0040Owen Anderson new (&Buckets[i].second) ValueT(other.Buckets[i].second); 2899544dc294f63ce116fbab398a8874ebf834cf41eOwen Anderson } 29067280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson NumBuckets = other.NumBuckets; 29167280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson } 2923a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 29328f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner BucketT *InsertIntoBucket(const KeyT &Key, const ValueT &Value, 29428f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner BucketT *TheBucket) { 29504a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // If the load of the hash table is more than 3/4, or if fewer than 1/8 of 29604a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // the buckets are empty (meaning that many are filled with tombstones), 29704a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // grow the table. 29804a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // 29904a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // The later case is tricky. For example, if we had one empty bucket with 30004a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // tons of tombstones, failing lookups (e.g. for insertion) would have to 30104a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // probe almost the entire table until it found the empty bucket. If the 30204a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // table completely filled with tombstones, no lookup would ever succeed, 30304a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // causing infinite loops in lookup. 30404a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner if (NumEntries*4 >= NumBuckets*3 || 3053a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman NumBuckets-(NumEntries+NumTombstones) < NumBuckets/8) { 306d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin this->grow(NumBuckets * 2); 30728f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner LookupBucketFor(Key, TheBucket); 3086e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 3096e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner ++NumEntries; 3103a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 31104a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // If we are writing over a tombstone, remember this. 31205831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(TheBucket->first, getEmptyKey())) 31304a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner --NumTombstones; 3143a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 31528f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner TheBucket->first = Key; 31628f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner new (&TheBucket->second) ValueT(Value); 31728f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner return TheBucket; 3186e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 31928f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner 32070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner static unsigned getHashValue(const KeyT &Val) { 321a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return KeyInfoT::getHashValue(Val); 3226e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 32370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner static const KeyT getEmptyKey() { 324a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return KeyInfoT::getEmptyKey(); 32570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 32670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner static const KeyT getTombstoneKey() { 327a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return KeyInfoT::getTombstoneKey(); 3286e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 3293a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3306e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in 3316e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// FoundBucket. If the bucket contains the key and a value, this returns 3326e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// true, otherwise it returns a bucket with an empty marker or tombstone and 3336e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// returns false. 3346e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner bool LookupBucketFor(const KeyT &Val, BucketT *&FoundBucket) const { 3356e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned BucketNo = getHashValue(Val); 3366e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned ProbeAmt = 1; 3376e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *BucketsPtr = Buckets; 3383a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3396e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // FoundTombstone - Keep track of whether we find a tombstone while probing. 3406e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *FoundTombstone = 0; 3416e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(); 3426e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT TombstoneKey = getTombstoneKey(); 34305831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner assert(!KeyInfoT::isEqual(Val, EmptyKey) && 34405831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(Val, TombstoneKey) && 3456e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner "Empty/Tombstone value shouldn't be inserted into map!"); 3463a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3476e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner while (1) { 3486e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *ThisBucket = BucketsPtr + (BucketNo & (NumBuckets-1)); 3496e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Found Val's bucket? If so, return it. 35076c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner if (KeyInfoT::isEqual(ThisBucket->first, Val)) { 3516e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundBucket = ThisBucket; 3526e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return true; 3536e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 3543a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3556e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If we found an empty bucket, the key doesn't exist in the set. 3566e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Insert it and return the default value. 35776c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner if (KeyInfoT::isEqual(ThisBucket->first, EmptyKey)) { 3586e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If we've already seen a tombstone while probing, fill it in instead 3596e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // of the empty bucket we eventually probed to. 3606e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner if (FoundTombstone) ThisBucket = FoundTombstone; 3616e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket; 3626e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return false; 3636e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 3643a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3656e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If this is a tombstone, remember it. If Val ends up not in the map, we 3666e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // prefer to return it than something that would require more probing. 36776c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner if (KeyInfoT::isEqual(ThisBucket->first, TombstoneKey) && !FoundTombstone) 3686e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundTombstone = ThisBucket; // Remember the first tombstone found. 3693a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3706e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Otherwise, it's a hash collision or a tombstone, continue quadratic 3716e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // probing. 3726e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketNo += ProbeAmt++; 3736e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 3746e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 3756e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 3766e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner void init(unsigned InitBuckets) { 3776e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner NumEntries = 0; 37804a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner NumTombstones = 0; 3796e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner NumBuckets = InitBuckets; 380ae9f3a3b7c915f725aef5a7250e88eaeddda03c6Anton Korobeynikov assert(InitBuckets && (InitBuckets & (InitBuckets-1)) == 0 && 3816e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner "# initial buckets must be a power of two!"); 38208c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*InitBuckets)); 3836e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Initialize all the keys to EmptyKey. 3846e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(); 3856e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (unsigned i = 0; i != InitBuckets; ++i) 386f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner new (&Buckets[i].first) KeyT(EmptyKey); 3876e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 3883a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 389d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin void grow(unsigned AtLeast) { 3906e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned OldNumBuckets = NumBuckets; 3916e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *OldBuckets = Buckets; 3923a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3936e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Double the number of buckets. 394d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin while (NumBuckets <= AtLeast) 395d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin NumBuckets <<= 1; 39604a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner NumTombstones = 0; 39708c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*NumBuckets)); 3986e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 3996e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Initialize all the keys to EmptyKey. 4006e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(); 4016e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (unsigned i = 0, e = NumBuckets; i != e; ++i) 402f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner new (&Buckets[i].first) KeyT(EmptyKey); 4036e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 4046e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Insert all the old elements. 4056e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT TombstoneKey = getTombstoneKey(); 4066e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) { 40705831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(B->first, EmptyKey) && 40805831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(B->first, TombstoneKey)) { 4096e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Insert the key/value into the new table. 4106e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *DestBucket; 411f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner bool FoundVal = LookupBucketFor(B->first, DestBucket); 412137d4b253384adce88bfa2a1c37695d90f0a9d6cChris Lattner FoundVal = FoundVal; // silence warning. 4136e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner assert(!FoundVal && "Key already in new map?"); 414f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner DestBucket->first = B->first; 415f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner new (&DestBucket->second) ValueT(B->second); 4163a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4176e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Free the value. 418f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner B->second.~ValueT(); 4196e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 420f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner B->first.~KeyT(); 4216e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 4223a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4236e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Free the old table. 42408c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman operator delete(OldBuckets); 4256e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 4263a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4276ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson void shrink_and_clear() { 4286ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson unsigned OldNumBuckets = NumBuckets; 4296ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson BucketT *OldBuckets = Buckets; 4303a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 431398b40671b13018f88371b74822fa8ee2638577eOwen Anderson // Reduce the number of buckets. 432398b40671b13018f88371b74822fa8ee2638577eOwen Anderson NumBuckets = NumEntries > 32 ? 1 << (Log2_32_Ceil(NumEntries) + 1) 433398b40671b13018f88371b74822fa8ee2638577eOwen Anderson : 64; 4346ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson NumTombstones = 0; 43508c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*NumBuckets)); 4366ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson 4376ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson // Initialize all the keys to EmptyKey. 4386ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson const KeyT EmptyKey = getEmptyKey(); 4396ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson for (unsigned i = 0, e = NumBuckets; i != e; ++i) 4406ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson new (&Buckets[i].first) KeyT(EmptyKey); 4416ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson 4426ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson // Free the old buckets. 4436ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson const KeyT TombstoneKey = getTombstoneKey(); 4446ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) { 44505831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(B->first, EmptyKey) && 44605831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(B->first, TombstoneKey)) { 4476ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson // Free the value. 4486ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson B->second.~ValueT(); 4496ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 4506ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson B->first.~KeyT(); 4516ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 4523a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4536ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson // Free the old table. 45408c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman operator delete(OldBuckets); 4553a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4566ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson NumEntries = 0; 4576ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 4586e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner}; 4596e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 46029ce95511f905df3a63e3b953a4a0179ead46865Owen Andersontemplate<typename KeyT, typename ValueT, typename KeyInfoT, typename ValueInfoT> 461f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerclass DenseMapIterator { 462f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner typedef std::pair<KeyT, ValueT> BucketT; 46370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattnerprotected: 464f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner const BucketT *Ptr, *End; 465f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerpublic: 46613e781ebe7a39e008dd5e5de78983e095e8a1d02David Greene DenseMapIterator(void) : Ptr(0), End(0) {} 46713e781ebe7a39e008dd5e5de78983e095e8a1d02David Greene 468f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner DenseMapIterator(const BucketT *Pos, const BucketT *E) : Ptr(Pos), End(E) { 469f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner AdvancePastEmptyBuckets(); 470f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 4713a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 47270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner std::pair<KeyT, ValueT> &operator*() const { 47370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return *const_cast<BucketT*>(Ptr); 474f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 47570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner std::pair<KeyT, ValueT> *operator->() const { 47670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return const_cast<BucketT*>(Ptr); 477f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 4783a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 479f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner bool operator==(const DenseMapIterator &RHS) const { 480f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner return Ptr == RHS.Ptr; 481f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 482f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner bool operator!=(const DenseMapIterator &RHS) const { 483f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner return Ptr != RHS.Ptr; 484f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 4853a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 486f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner inline DenseMapIterator& operator++() { // Preincrement 487f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner ++Ptr; 488f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner AdvancePastEmptyBuckets(); 489f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner return *this; 490f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 491f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner DenseMapIterator operator++(int) { // Postincrement 492f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner DenseMapIterator tmp = *this; ++*this; return tmp; 493f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 4943a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 495f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerprivate: 496f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner void AdvancePastEmptyBuckets() { 497a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner const KeyT Empty = KeyInfoT::getEmptyKey(); 498a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner const KeyT Tombstone = KeyInfoT::getTombstoneKey(); 499f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 5003a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman while (Ptr != End && 50176c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner (KeyInfoT::isEqual(Ptr->first, Empty) || 50276c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner KeyInfoT::isEqual(Ptr->first, Tombstone))) 503f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner ++Ptr; 504f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 505f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner}; 506f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 50729ce95511f905df3a63e3b953a4a0179ead46865Owen Andersontemplate<typename KeyT, typename ValueT, typename KeyInfoT, typename ValueInfoT> 508a76b1febd4fd258e8054395adedcbd477668d956Chris Lattnerclass DenseMapConstIterator : public DenseMapIterator<KeyT, ValueT, KeyInfoT> { 50970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattnerpublic: 51013e781ebe7a39e008dd5e5de78983e095e8a1d02David Greene DenseMapConstIterator(void) : DenseMapIterator<KeyT, ValueT, KeyInfoT>() {} 51170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner DenseMapConstIterator(const std::pair<KeyT, ValueT> *Pos, 51270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner const std::pair<KeyT, ValueT> *E) 513569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner : DenseMapIterator<KeyT, ValueT, KeyInfoT>(Pos, E) { 51470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 51570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner const std::pair<KeyT, ValueT> &operator*() const { 51670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return *this->Ptr; 51770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 51870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner const std::pair<KeyT, ValueT> *operator->() const { 51970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return this->Ptr; 52070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 52170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner}; 522f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 5236e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner} // end namespace llvm 5246e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 5256e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner#endif 526