DenseMap.h revision 414fdbdb0104fdc8c570287f94df8bb697e7b7c1
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 17398b40671b13018f88371b74822fa8ee2638577eOwen Anderson#include "llvm/Support/MathExtras.h" 1881cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin#include "llvm/Support/PointerLikeTypeTraits.h" 1981cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin#include "llvm/Support/type_traits.h" 20fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman#include "llvm/ADT/DenseMapInfo.h" 21476b242fe7a61e5f9ac6214b0bc5c680d24f152eNick Lewycky#include <algorithm> 22724f6751442e2006856a9365ef3d3bc6f1b31c98Chris Lattner#include <iterator> 23724f6751442e2006856a9365ef3d3bc6f1b31c98Chris Lattner#include <new> 24724f6751442e2006856a9365ef3d3bc6f1b31c98Chris Lattner#include <utility> 256e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner#include <cassert> 26345b378309eabd74a7a43f095dca9a4894bc371eDuncan Sands#include <cstddef> 27d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#include <cstring> 286e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 296e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnernamespace llvm { 303a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 313a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukmantemplate<typename KeyT, typename ValueT, 3276c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner typename KeyInfoT = DenseMapInfo<KeyT>, 3381cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typename ValueInfoT = DenseMapInfo<ValueT>, bool IsConst = false> 34f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerclass DenseMapIterator; 356e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 36a76b1febd4fd258e8054395adedcbd477668d956Chris Lattnertemplate<typename KeyT, typename ValueT, 3776c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner typename KeyInfoT = DenseMapInfo<KeyT>, 3876c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner typename ValueInfoT = DenseMapInfo<ValueT> > 396e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnerclass DenseMap { 40f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner typedef std::pair<KeyT, ValueT> BucketT; 416e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned NumBuckets; 426e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *Buckets; 433a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 446e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned NumEntries; 4504a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner unsigned NumTombstones; 466e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnerpublic: 4713e781ebe7a39e008dd5e5de78983e095e8a1d02David Greene typedef KeyT key_type; 4813e781ebe7a39e008dd5e5de78983e095e8a1d02David Greene typedef ValueT mapped_type; 49aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek typedef BucketT value_type; 503a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 516a363782fe4ecba4f0a72c2edf03596004470c4aChris Lattner DenseMap(const DenseMap &other) { 5267280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson NumBuckets = 0; 5367280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson CopyFrom(other); 5467280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson } 553a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5649d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer explicit DenseMap(unsigned NumInitBuckets = 0) { 576e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner init(NumInitBuckets); 586e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 593a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 606a363782fe4ecba4f0a72c2edf03596004470c4aChris Lattner template<typename InputIt> 616a363782fe4ecba4f0a72c2edf03596004470c4aChris Lattner DenseMap(const InputIt &I, const InputIt &E) { 6249d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer init(NextPowerOf2(std::distance(I, E))); 636a363782fe4ecba4f0a72c2edf03596004470c4aChris Lattner insert(I, E); 646a363782fe4ecba4f0a72c2edf03596004470c4aChris Lattner } 656a363782fe4ecba4f0a72c2edf03596004470c4aChris Lattner 666e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner ~DenseMap() { 676e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 686e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { 6905831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(P->first, EmptyKey) && 7005831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(P->first, TombstoneKey)) 71f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner P->second.~ValueT(); 72f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner P->first.~KeyT(); 736e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 74d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#ifndef NDEBUG 75e54f64899fbaaa95fc3241236aabfaa37003a658Duncan Sands if (NumBuckets) 76e54f64899fbaaa95fc3241236aabfaa37003a658Duncan Sands memset(Buckets, 0x5a, sizeof(BucketT)*NumBuckets); 77d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#endif 7808c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman operator delete(Buckets); 796e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 803a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 81a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner typedef DenseMapIterator<KeyT, ValueT, KeyInfoT> iterator; 8281cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef DenseMapIterator<KeyT, ValueT, 8381cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin KeyInfoT, ValueInfoT, true> const_iterator; 8470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline iterator begin() { 85b843d9f833aa474ae700363a445b7409665c4a6eJakob Stoklund Olesen // When the map is empty, avoid the overhead of AdvancePastEmptyBuckets(). 86b843d9f833aa474ae700363a445b7409665c4a6eJakob Stoklund Olesen return empty() ? end() : iterator(Buckets, Buckets+NumBuckets); 8770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 8870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline iterator end() { 89a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return iterator(Buckets+NumBuckets, Buckets+NumBuckets); 9070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 9170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline const_iterator begin() const { 92b843d9f833aa474ae700363a445b7409665c4a6eJakob Stoklund Olesen return empty() ? end() : const_iterator(Buckets, Buckets+NumBuckets); 9370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 9470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline const_iterator end() const { 95a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return const_iterator(Buckets+NumBuckets, Buckets+NumBuckets); 9670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 973a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 9870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner bool empty() const { return NumEntries == 0; } 996e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned size() const { return NumEntries; } 100d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin 101d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin /// Grow the densemap so that it has at least Size buckets. Does not shrink 10249d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer void resize(size_t Size) { 10349d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer if (Size > NumBuckets) 10449d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer grow(Size); 10549d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer } 1063a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1076e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner void clear() { 10832859c71d6ba9cd5e38662611a73d82335f4ba41Chris Lattner if (NumEntries == 0 && NumTombstones == 0) return; 10932859c71d6ba9cd5e38662611a73d82335f4ba41Chris Lattner 11042e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner // If the capacity of the array is huge, and the # elements used is small, 11142e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner // shrink the array. 1126ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson if (NumEntries * 4 < NumBuckets && NumBuckets > 64) { 1136ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson shrink_and_clear(); 1146ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson return; 1156ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 1163a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1176e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 1186e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { 11905831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(P->first, EmptyKey)) { 12005831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(P->first, TombstoneKey)) { 1217b54452c84e478ab4d49ac08759ca4ec1badf2b2Chris Lattner P->second.~ValueT(); 1227b54452c84e478ab4d49ac08759ca4ec1badf2b2Chris Lattner --NumEntries; 1237b54452c84e478ab4d49ac08759ca4ec1badf2b2Chris Lattner } 124f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner P->first = EmptyKey; 1256e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1266e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1276e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner assert(NumEntries == 0 && "Node count imbalance!"); 12804a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner NumTombstones = 0; 1296e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1306ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson 1316e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// count - Return true if the specified key is in the map. 1326e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner bool count(const KeyT &Val) const { 1336e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *TheBucket; 1346e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return LookupBucketFor(Val, TheBucket); 1356e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1363a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 137569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner iterator find(const KeyT &Val) { 13870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner BucketT *TheBucket; 13970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner if (LookupBucketFor(Val, TheBucket)) 14070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return iterator(TheBucket, Buckets+NumBuckets); 14170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return end(); 14270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 143569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner const_iterator find(const KeyT &Val) const { 144569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner BucketT *TheBucket; 145569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner if (LookupBucketFor(Val, TheBucket)) 146569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner return const_iterator(TheBucket, Buckets+NumBuckets); 147569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner return end(); 148569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner } 1493a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1507b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar /// lookup - Return the entry for the specified key, or a default 1517b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar /// constructed value if no such entry exists. 1527b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar ValueT lookup(const KeyT &Val) const { 1537b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar BucketT *TheBucket; 1547b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar if (LookupBucketFor(Val, TheBucket)) 1557b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar return TheBucket->second; 1567b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar return ValueT(); 1577b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar } 1587b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar 159127445818efd810b138dd5362129ab3c7f8b9963Torok Edwin // Inserts key,value pair into the map if the key isn't already in the map. 160127445818efd810b138dd5362129ab3c7f8b9963Torok Edwin // If the key is already in the map, it returns false and doesn't update the 161127445818efd810b138dd5362129ab3c7f8b9963Torok Edwin // value. 1626b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { 16328f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner BucketT *TheBucket; 16428f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner if (LookupBucketFor(KV.first, TheBucket)) 1656b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman return std::make_pair(iterator(TheBucket, Buckets+NumBuckets), 1666b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman false); // Already in map. 1673a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 16828f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner // Otherwise, insert the new element. 1696b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman TheBucket = InsertIntoBucket(KV.first, KV.second, TheBucket); 1706b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman return std::make_pair(iterator(TheBucket, Buckets+NumBuckets), 1716b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman true); 17228f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner } 1733a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 174b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner /// insert - Range insertion of pairs. 175b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner template<typename InputIt> 176b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner void insert(InputIt I, InputIt E) { 177b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner for (; I != E; ++I) 178b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner insert(*I); 179b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner } 180b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner 1813a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 18270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner bool erase(const KeyT &Val) { 18370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner BucketT *TheBucket; 18470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner if (!LookupBucketFor(Val, TheBucket)) 18570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return false; // not in map. 18670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner 18770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->second.~ValueT(); 18870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->first = getTombstoneKey(); 18970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner --NumEntries; 19004a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner ++NumTombstones; 19170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return true; 19270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 193e3955df639ff9aff990f628ef6a219ff5efdbc81Dan Gohman void erase(iterator I) { 19470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner BucketT *TheBucket = &*I; 19570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->second.~ValueT(); 19670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->first = getTombstoneKey(); 19770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner --NumEntries; 19804a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner ++NumTombstones; 19970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 200aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek 201ccb4f2d813380d8cf139062b8c829e4b8b322c0dAndrew Lenharth void swap(DenseMap& RHS) { 202ccb4f2d813380d8cf139062b8c829e4b8b322c0dAndrew Lenharth std::swap(NumBuckets, RHS.NumBuckets); 203ccb4f2d813380d8cf139062b8c829e4b8b322c0dAndrew Lenharth std::swap(Buckets, RHS.Buckets); 204ccb4f2d813380d8cf139062b8c829e4b8b322c0dAndrew Lenharth std::swap(NumEntries, RHS.NumEntries); 205ccb4f2d813380d8cf139062b8c829e4b8b322c0dAndrew Lenharth std::swap(NumTombstones, RHS.NumTombstones); 206ccb4f2d813380d8cf139062b8c829e4b8b322c0dAndrew Lenharth } 207ccb4f2d813380d8cf139062b8c829e4b8b322c0dAndrew Lenharth 208aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek value_type& FindAndConstruct(const KeyT &Key) { 2096e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *TheBucket; 21028f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner if (LookupBucketFor(Key, TheBucket)) 211aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek return *TheBucket; 2123a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 213aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek return *InsertIntoBucket(Key, ValueT(), TheBucket); 214aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek } 2153a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 216aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek ValueT &operator[](const KeyT &Key) { 217aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek return FindAndConstruct(Key).second; 21828f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner } 2193a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 22067280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson DenseMap& operator=(const DenseMap& other) { 22167280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson CopyFrom(other); 2223d345631db71174ffc4997a88c09f21eb9ed052bOwen Anderson return *this; 22367280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson } 2243a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 225bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// isPointerIntoBucketsArray - Return true if the specified pointer points 226bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// somewhere into the DenseMap's array of buckets (i.e. either to a key or 227bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// value in the DenseMap). 228bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner bool isPointerIntoBucketsArray(const void *Ptr) const { 229bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner return Ptr >= Buckets && Ptr < Buckets+NumBuckets; 230bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner } 231bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner 232bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets 233bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// array. In conjunction with the previous method, this can be used to 234bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// determine whether an insertion caused the DenseMap to reallocate. 235bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner const void *getPointerIntoBucketsArray() const { return Buckets; } 236bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner 23728f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattnerprivate: 23867280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson void CopyFrom(const DenseMap& other) { 2394bbf4ee1491637c247e195e19e3e4a8ee5ad72faChris Lattner if (NumBuckets != 0 && 2404bbf4ee1491637c247e195e19e3e4a8ee5ad72faChris Lattner (!isPodLike<KeyInfoT>::value || !isPodLike<ValueInfoT>::value)) { 24167280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 24267280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { 24305831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(P->first, EmptyKey) && 24405831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(P->first, TombstoneKey)) 24567280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson P->second.~ValueT(); 24667280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson P->first.~KeyT(); 24767280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson } 24867280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson } 2493a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 25067280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson NumEntries = other.NumEntries; 25167280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson NumTombstones = other.NumTombstones; 2523a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 253d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin if (NumBuckets) { 254d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#ifndef NDEBUG 255d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin memset(Buckets, 0x5a, sizeof(BucketT)*NumBuckets); 256d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#endif 25708c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman operator delete(Buckets); 258d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin } 25988b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer 26088b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer NumBuckets = other.NumBuckets; 26188b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer 26288b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer if (NumBuckets == 0) { 26388b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer Buckets = 0; 26488b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer return; 26588b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer } 26688b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer 26788b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT) * NumBuckets)); 2683a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2694bbf4ee1491637c247e195e19e3e4a8ee5ad72faChris Lattner if (isPodLike<KeyInfoT>::value && isPodLike<ValueInfoT>::value) 27088b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer memcpy(Buckets, other.Buckets, NumBuckets * sizeof(BucketT)); 2719544dc294f63ce116fbab398a8874ebf834cf41eOwen Anderson else 27288b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer for (size_t i = 0; i < NumBuckets; ++i) { 2732b7470eb54880ce7f74469d6e09eaf7f0864f8abOwen Anderson new (&Buckets[i].first) KeyT(other.Buckets[i].first); 27405831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(Buckets[i].first, getEmptyKey()) && 27505831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(Buckets[i].first, getTombstoneKey())) 2764938d347723d452786c1a7c1d1b9ec79121b0040Owen Anderson new (&Buckets[i].second) ValueT(other.Buckets[i].second); 2779544dc294f63ce116fbab398a8874ebf834cf41eOwen Anderson } 27867280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson } 2793a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 28028f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner BucketT *InsertIntoBucket(const KeyT &Key, const ValueT &Value, 28128f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner BucketT *TheBucket) { 28204a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // If the load of the hash table is more than 3/4, or if fewer than 1/8 of 28304a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // the buckets are empty (meaning that many are filled with tombstones), 28404a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // grow the table. 28504a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // 28604a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // The later case is tricky. For example, if we had one empty bucket with 28704a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // tons of tombstones, failing lookups (e.g. for insertion) would have to 28804a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // probe almost the entire table until it found the empty bucket. If the 28904a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // table completely filled with tombstones, no lookup would ever succeed, 29004a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // causing infinite loops in lookup. 291f0e4cac7ebdee07639bd1fc3eadf204f45868556Stuart Hastings ++NumEntries; 292414fdbdb0104fdc8c570287f94df8bb697e7b7c1Jakob Stoklund Olesen if (NumEntries*4 >= NumBuckets*3) { 293d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin this->grow(NumBuckets * 2); 29428f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner LookupBucketFor(Key, TheBucket); 2956e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 296414fdbdb0104fdc8c570287f94df8bb697e7b7c1Jakob Stoklund Olesen if (NumBuckets-(NumEntries+NumTombstones) < NumBuckets/8) { 297414fdbdb0104fdc8c570287f94df8bb697e7b7c1Jakob Stoklund Olesen this->grow(NumBuckets); 298414fdbdb0104fdc8c570287f94df8bb697e7b7c1Jakob Stoklund Olesen LookupBucketFor(Key, TheBucket); 299414fdbdb0104fdc8c570287f94df8bb697e7b7c1Jakob Stoklund Olesen } 3003a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 30104a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // If we are writing over a tombstone, remember this. 30205831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(TheBucket->first, getEmptyKey())) 30304a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner --NumTombstones; 3043a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 30528f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner TheBucket->first = Key; 30628f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner new (&TheBucket->second) ValueT(Value); 30728f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner return TheBucket; 3086e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 30928f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner 31070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner static unsigned getHashValue(const KeyT &Val) { 311a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return KeyInfoT::getHashValue(Val); 3126e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 31370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner static const KeyT getEmptyKey() { 314a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return KeyInfoT::getEmptyKey(); 31570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 31670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner static const KeyT getTombstoneKey() { 317a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return KeyInfoT::getTombstoneKey(); 3186e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 3193a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3206e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in 3216e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// FoundBucket. If the bucket contains the key and a value, this returns 3226e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// true, otherwise it returns a bucket with an empty marker or tombstone and 3236e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// returns false. 3246e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner bool LookupBucketFor(const KeyT &Val, BucketT *&FoundBucket) const { 3256e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned BucketNo = getHashValue(Val); 3266e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned ProbeAmt = 1; 3276e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *BucketsPtr = Buckets; 3283a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 32949d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer if (NumBuckets == 0) { 33049d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer FoundBucket = 0; 33149d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer return false; 33249d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer } 33349d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer 3346e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // FoundTombstone - Keep track of whether we find a tombstone while probing. 3356e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *FoundTombstone = 0; 3366e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(); 3376e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT TombstoneKey = getTombstoneKey(); 33805831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner assert(!KeyInfoT::isEqual(Val, EmptyKey) && 33905831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(Val, TombstoneKey) && 3406e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner "Empty/Tombstone value shouldn't be inserted into map!"); 3413a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3426e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner while (1) { 3436e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *ThisBucket = BucketsPtr + (BucketNo & (NumBuckets-1)); 3446e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Found Val's bucket? If so, return it. 34576c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner if (KeyInfoT::isEqual(ThisBucket->first, Val)) { 3466e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundBucket = ThisBucket; 3476e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return true; 3486e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 3493a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3506e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If we found an empty bucket, the key doesn't exist in the set. 3516e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Insert it and return the default value. 35276c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner if (KeyInfoT::isEqual(ThisBucket->first, EmptyKey)) { 3536e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If we've already seen a tombstone while probing, fill it in instead 3546e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // of the empty bucket we eventually probed to. 3556e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner if (FoundTombstone) ThisBucket = FoundTombstone; 3566e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket; 3576e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return false; 3586e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 3593a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3606e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If this is a tombstone, remember it. If Val ends up not in the map, we 3616e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // prefer to return it than something that would require more probing. 36276c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner if (KeyInfoT::isEqual(ThisBucket->first, TombstoneKey) && !FoundTombstone) 3636e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundTombstone = ThisBucket; // Remember the first tombstone found. 3643a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3656e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Otherwise, it's a hash collision or a tombstone, continue quadratic 3666e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // probing. 3676e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketNo += ProbeAmt++; 3686e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 3696e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 3706e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 3716e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner void init(unsigned InitBuckets) { 3726e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner NumEntries = 0; 37304a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner NumTombstones = 0; 3746e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner NumBuckets = InitBuckets; 37549d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer 37649d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer if (InitBuckets == 0) { 37749d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer Buckets = 0; 37849d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer return; 37949d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer } 38049d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer 381ae9f3a3b7c915f725aef5a7250e88eaeddda03c6Anton Korobeynikov assert(InitBuckets && (InitBuckets & (InitBuckets-1)) == 0 && 3826e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner "# initial buckets must be a power of two!"); 38308c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*InitBuckets)); 3846e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Initialize all the keys to EmptyKey. 3856e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(); 3866e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (unsigned i = 0; i != InitBuckets; ++i) 387f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner new (&Buckets[i].first) KeyT(EmptyKey); 3886e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 3893a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 390d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin void grow(unsigned AtLeast) { 3916e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned OldNumBuckets = NumBuckets; 3926e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *OldBuckets = Buckets; 3933a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 39449d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer if (NumBuckets < 64) 39549d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer NumBuckets = 64; 39649d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer 3976e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Double the number of buckets. 398fcb0ee8ffeae12aa866f4e7da12a4dd2a1d0dc35Junjie Gu while (NumBuckets < AtLeast) 399d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin NumBuckets <<= 1; 40004a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner NumTombstones = 0; 40108c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*NumBuckets)); 4026e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 4036e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Initialize all the keys to EmptyKey. 4046e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(); 4056e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (unsigned i = 0, e = NumBuckets; i != e; ++i) 406f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner new (&Buckets[i].first) KeyT(EmptyKey); 4076e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 4086e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Insert all the old elements. 4096e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT TombstoneKey = getTombstoneKey(); 4106e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) { 41105831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(B->first, EmptyKey) && 41205831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(B->first, TombstoneKey)) { 4136e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Insert the key/value into the new table. 4146e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *DestBucket; 415f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner bool FoundVal = LookupBucketFor(B->first, DestBucket); 4169d38acb254108db0ee9e746bb3f7aa64168f7e36Nick Lewycky (void)FoundVal; // silence warning. 4176e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner assert(!FoundVal && "Key already in new map?"); 418f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner DestBucket->first = B->first; 419f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner new (&DestBucket->second) ValueT(B->second); 4203a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4216e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Free the value. 422f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner B->second.~ValueT(); 4236e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 424f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner B->first.~KeyT(); 4256e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 4263a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 427d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#ifndef NDEBUG 428d01f2633b9aab6281c936da04226b46a0dde7ba9Jay Foad if (OldNumBuckets) 429d01f2633b9aab6281c936da04226b46a0dde7ba9Jay Foad memset(OldBuckets, 0x5a, sizeof(BucketT)*OldNumBuckets); 430d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#endif 4316e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Free the old table. 43208c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman operator delete(OldBuckets); 4336e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 4343a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4356ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson void shrink_and_clear() { 4366ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson unsigned OldNumBuckets = NumBuckets; 4376ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson BucketT *OldBuckets = Buckets; 4383a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 439398b40671b13018f88371b74822fa8ee2638577eOwen Anderson // Reduce the number of buckets. 440398b40671b13018f88371b74822fa8ee2638577eOwen Anderson NumBuckets = NumEntries > 32 ? 1 << (Log2_32_Ceil(NumEntries) + 1) 441398b40671b13018f88371b74822fa8ee2638577eOwen Anderson : 64; 4426ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson NumTombstones = 0; 44308c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*NumBuckets)); 4446ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson 4456ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson // Initialize all the keys to EmptyKey. 4466ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson const KeyT EmptyKey = getEmptyKey(); 4476ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson for (unsigned i = 0, e = NumBuckets; i != e; ++i) 4486ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson new (&Buckets[i].first) KeyT(EmptyKey); 4496ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson 4506ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson // Free the old buckets. 4516ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson const KeyT TombstoneKey = getTombstoneKey(); 4526ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) { 45305831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(B->first, EmptyKey) && 45405831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(B->first, TombstoneKey)) { 4556ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson // Free the value. 4566ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson B->second.~ValueT(); 4576ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 4586ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson B->first.~KeyT(); 4596ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 4603a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 461d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#ifndef NDEBUG 462d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin memset(OldBuckets, 0x5a, sizeof(BucketT)*OldNumBuckets); 463d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#endif 4646ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson // Free the old table. 46508c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman operator delete(OldBuckets); 4663a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4676ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson NumEntries = 0; 4686ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 4696e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner}; 4706e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 47181cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskintemplate<typename KeyT, typename ValueT, 47281cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typename KeyInfoT, typename ValueInfoT, bool IsConst> 47381cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskinclass DenseMapIterator { 47481cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef std::pair<KeyT, ValueT> Bucket; 47581cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef DenseMapIterator<KeyT, ValueT, 47681cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin KeyInfoT, ValueInfoT, true> ConstIterator; 47781cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, ValueInfoT, true>; 47881cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskinpublic: 47981cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef ptrdiff_t difference_type; 48081cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef typename conditional<IsConst, const Bucket, Bucket>::type value_type; 48181cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef value_type *pointer; 48281cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef value_type &reference; 48381cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef std::forward_iterator_tag iterator_category; 48481cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskinprivate: 48581cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin pointer Ptr, End; 486f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerpublic: 487a9ad04191cb56c42944b17980b8b2bb2afe11ab2Dan Gohman DenseMapIterator() : Ptr(0), End(0) {} 48813e781ebe7a39e008dd5e5de78983e095e8a1d02David Greene 48981cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin DenseMapIterator(pointer Pos, pointer E) : Ptr(Pos), End(E) { 490f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner AdvancePastEmptyBuckets(); 491f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 4923a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 49381cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin // If IsConst is true this is a converting constructor from iterator to 49481cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin // const_iterator and the default copy constructor is used. 49581cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin // Otherwise this is a copy constructor for iterator. 49681cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin DenseMapIterator(const DenseMapIterator<KeyT, ValueT, 49781cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin KeyInfoT, ValueInfoT, false>& I) 49881cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin : Ptr(I.Ptr), End(I.End) {} 49981cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin 50081cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin reference operator*() const { 50181cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin return *Ptr; 502f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 50381cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin pointer operator->() const { 50481cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin return Ptr; 505f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 5063a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 50781cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin bool operator==(const ConstIterator &RHS) const { 50881cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin return Ptr == RHS.operator->(); 509f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 51081cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin bool operator!=(const ConstIterator &RHS) const { 51181cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin return Ptr != RHS.operator->(); 512f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 5133a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5144ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin inline DenseMapIterator& operator++() { // Preincrement 515f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner ++Ptr; 516f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner AdvancePastEmptyBuckets(); 517f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner return *this; 518f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 5194ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin DenseMapIterator operator++(int) { // Postincrement 520f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner DenseMapIterator tmp = *this; ++*this; return tmp; 521f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 5223a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 523f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerprivate: 524f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner void AdvancePastEmptyBuckets() { 525a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner const KeyT Empty = KeyInfoT::getEmptyKey(); 526a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner const KeyT Tombstone = KeyInfoT::getTombstoneKey(); 527f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 5283a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman while (Ptr != End && 52976c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner (KeyInfoT::isEqual(Ptr->first, Empty) || 53076c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner KeyInfoT::isEqual(Ptr->first, Tombstone))) 531f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner ++Ptr; 532f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 533f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner}; 534f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 5356e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner} // end namespace llvm 5366e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 5376e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner#endif 538