DenseMap.h revision 48f4dcf0f7fd64df00839018d633944bc2464501
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 17ac5802bca0285eee49c1c372846552823d819181Benjamin Kramer#include "llvm/Support/Compiler.h" 18398b40671b13018f88371b74822fa8ee2638577eOwen Anderson#include "llvm/Support/MathExtras.h" 1981cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin#include "llvm/Support/PointerLikeTypeTraits.h" 2081cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin#include "llvm/Support/type_traits.h" 21fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman#include "llvm/ADT/DenseMapInfo.h" 22476b242fe7a61e5f9ac6214b0bc5c680d24f152eNick Lewycky#include <algorithm> 23724f6751442e2006856a9365ef3d3bc6f1b31c98Chris Lattner#include <iterator> 24724f6751442e2006856a9365ef3d3bc6f1b31c98Chris Lattner#include <new> 25724f6751442e2006856a9365ef3d3bc6f1b31c98Chris Lattner#include <utility> 266e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner#include <cassert> 27345b378309eabd74a7a43f095dca9a4894bc371eDuncan Sands#include <cstddef> 28d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#include <cstring> 296e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 306e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnernamespace llvm { 313a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 323a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukmantemplate<typename KeyT, typename ValueT, 3376c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner typename KeyInfoT = DenseMapInfo<KeyT>, 344e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer bool IsConst = false> 35f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerclass DenseMapIterator; 366e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 377f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthtemplate<typename DerivedT, 387f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth typename KeyT, typename ValueT, typename KeyInfoT> 397f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthclass DenseMapBase { 407f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthprotected: 41f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner typedef std::pair<KeyT, ValueT> BucketT; 427f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 436e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnerpublic: 4413e781ebe7a39e008dd5e5de78983e095e8a1d02David Greene typedef KeyT key_type; 4513e781ebe7a39e008dd5e5de78983e095e8a1d02David Greene typedef ValueT mapped_type; 46aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek typedef BucketT value_type; 473a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 48a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner typedef DenseMapIterator<KeyT, ValueT, KeyInfoT> iterator; 4981cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef DenseMapIterator<KeyT, ValueT, 504e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer KeyInfoT, true> const_iterator; 5170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline iterator begin() { 52b843d9f833aa474ae700363a445b7409665c4a6eJakob Stoklund Olesen // When the map is empty, avoid the overhead of AdvancePastEmptyBuckets(). 537f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return empty() ? end() : iterator(getBuckets(), getBucketsEnd()); 5470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 5570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline iterator end() { 567f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return iterator(getBucketsEnd(), getBucketsEnd(), true); 5770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 5870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline const_iterator begin() const { 597f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return empty() ? end() : const_iterator(getBuckets(), getBucketsEnd()); 6070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 6170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline const_iterator end() const { 627f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return const_iterator(getBucketsEnd(), getBucketsEnd(), true); 6370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 643a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 6548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth bool empty() const { return getNumEntries() == 0; } 6648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned size() const { return getNumEntries(); } 67d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin 68d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin /// Grow the densemap so that it has at least Size buckets. Does not shrink 6949d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer void resize(size_t Size) { 707f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth if (Size > getNumBuckets()) 7149d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer grow(Size); 7249d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer } 733a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 746e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner void clear() { 7548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth if (getNumEntries() == 0 && getNumTombstones() == 0) return; 7632859c71d6ba9cd5e38662611a73d82335f4ba41Chris Lattner 7742e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner // If the capacity of the array is huge, and the # elements used is small, 7842e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner // shrink the array. 7948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth if (getNumEntries() * 4 < getNumBuckets() && getNumBuckets() > 64) { 806ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson shrink_and_clear(); 816ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson return; 826ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 833a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 846e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 857f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) { 8605831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(P->first, EmptyKey)) { 8705831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(P->first, TombstoneKey)) { 887b54452c84e478ab4d49ac08759ca4ec1badf2b2Chris Lattner P->second.~ValueT(); 8948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth decrementNumEntries(); 907b54452c84e478ab4d49ac08759ca4ec1badf2b2Chris Lattner } 91f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner P->first = EmptyKey; 926e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 936e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 9448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth assert(getNumEntries() == 0 && "Node count imbalance!"); 9548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth setNumTombstones(0); 966e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 976ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson 986e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// count - Return true if the specified key is in the map. 996e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner bool count(const KeyT &Val) const { 1006e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *TheBucket; 1016e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return LookupBucketFor(Val, TheBucket); 1026e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1033a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 104569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner iterator find(const KeyT &Val) { 10570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner BucketT *TheBucket; 10670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner if (LookupBucketFor(Val, TheBucket)) 1077f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return iterator(TheBucket, getBucketsEnd(), true); 10870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return end(); 10970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 110569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner const_iterator find(const KeyT &Val) const { 111569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner BucketT *TheBucket; 112569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner if (LookupBucketFor(Val, TheBucket)) 1137f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return const_iterator(TheBucket, getBucketsEnd(), true); 114569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner return end(); 115569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner } 1163a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 117babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin /// Alternate version of find() which allows a different, and possibly 118babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin /// less expensive, key type. 119babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin /// The DenseMapInfo is responsible for supplying methods 120babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key 121babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin /// type used. 122babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin template<class LookupKeyT> 123babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin iterator find_as(const LookupKeyT &Val) { 124babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin BucketT *TheBucket; 125babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin if (LookupBucketFor(Val, TheBucket)) 1267f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return iterator(TheBucket, getBucketsEnd(), true); 127babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin return end(); 128babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin } 129babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin template<class LookupKeyT> 130babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin const_iterator find_as(const LookupKeyT &Val) const { 131babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin BucketT *TheBucket; 132babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin if (LookupBucketFor(Val, TheBucket)) 1337f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return const_iterator(TheBucket, getBucketsEnd(), true); 134babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin return end(); 135babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin } 136babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin 1377b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar /// lookup - Return the entry for the specified key, or a default 1387b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar /// constructed value if no such entry exists. 1397b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar ValueT lookup(const KeyT &Val) const { 1407b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar BucketT *TheBucket; 1417b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar if (LookupBucketFor(Val, TheBucket)) 1427b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar return TheBucket->second; 1437b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar return ValueT(); 1447b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar } 1457b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar 146127445818efd810b138dd5362129ab3c7f8b9963Torok Edwin // Inserts key,value pair into the map if the key isn't already in the map. 147127445818efd810b138dd5362129ab3c7f8b9963Torok Edwin // If the key is already in the map, it returns false and doesn't update the 148127445818efd810b138dd5362129ab3c7f8b9963Torok Edwin // value. 1496b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { 15028f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner BucketT *TheBucket; 15128f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner if (LookupBucketFor(KV.first, TheBucket)) 1527f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), 1536b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman false); // Already in map. 1543a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 15528f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner // Otherwise, insert the new element. 1566b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman TheBucket = InsertIntoBucket(KV.first, KV.second, TheBucket); 1577f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), true); 15828f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner } 1593a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 160b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner /// insert - Range insertion of pairs. 161b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner template<typename InputIt> 162b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner void insert(InputIt I, InputIt E) { 163b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner for (; I != E; ++I) 164b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner insert(*I); 165b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner } 166b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner 1673a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 16870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner bool erase(const KeyT &Val) { 16970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner BucketT *TheBucket; 17070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner if (!LookupBucketFor(Val, TheBucket)) 17170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return false; // not in map. 17270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner 17370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->second.~ValueT(); 17470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->first = getTombstoneKey(); 17548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth decrementNumEntries(); 17648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth incrementNumTombstones(); 17770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return true; 17870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 179e3955df639ff9aff990f628ef6a219ff5efdbc81Dan Gohman void erase(iterator I) { 18070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner BucketT *TheBucket = &*I; 18170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->second.~ValueT(); 18270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->first = getTombstoneKey(); 18348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth decrementNumEntries(); 18448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth incrementNumTombstones(); 18570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 186aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek 187aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek value_type& FindAndConstruct(const KeyT &Key) { 1886e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *TheBucket; 18928f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner if (LookupBucketFor(Key, TheBucket)) 190aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek return *TheBucket; 1913a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 192aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek return *InsertIntoBucket(Key, ValueT(), TheBucket); 193aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek } 1943a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 195aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek ValueT &operator[](const KeyT &Key) { 196aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek return FindAndConstruct(Key).second; 19728f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner } 1983a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 199aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer#if LLVM_USE_RVALUE_REFERENCES 200aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer value_type& FindAndConstruct(KeyT &&Key) { 201aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer BucketT *TheBucket; 202aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer if (LookupBucketFor(Key, TheBucket)) 203aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer return *TheBucket; 204aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 205aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer return *InsertIntoBucket(Key, ValueT(), TheBucket); 206aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer } 207aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 208aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer ValueT &operator[](KeyT &&Key) { 209aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer return FindAndConstruct(Key).second; 210aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer } 211aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer#endif 212aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 213bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// isPointerIntoBucketsArray - Return true if the specified pointer points 214bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// somewhere into the DenseMap's array of buckets (i.e. either to a key or 215bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// value in the DenseMap). 216bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner bool isPointerIntoBucketsArray(const void *Ptr) const { 2177f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return Ptr >= getBuckets() && Ptr < getBucketsEnd(); 218bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner } 219bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner 220bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets 221bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// array. In conjunction with the previous method, this can be used to 222bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// determine whether an insertion caused the DenseMap to reallocate. 2237f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth const void *getPointerIntoBucketsArray() const { return getBuckets(); } 224bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner 2257f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthprotected: 22648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth DenseMapBase() {} 2277f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 2287f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void destroyAll() { 2297f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth if (getNumBuckets() == 0) // Nothing to do. 2308e337120133c746640246feb9383556d383a94beBenjamin Kramer return; 2318e337120133c746640246feb9383556d383a94beBenjamin Kramer 232295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 2337f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) { 234295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer if (!KeyInfoT::isEqual(P->first, EmptyKey) && 235295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer !KeyInfoT::isEqual(P->first, TombstoneKey)) 236295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer P->second.~ValueT(); 237295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer P->first.~KeyT(); 23867280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson } 2393a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 240d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#ifndef NDEBUG 2417f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth memset((void*)getBuckets(), 0x5a, sizeof(BucketT)*getNumBuckets()); 242d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#endif 243295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer } 24488b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer 2457f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void initEmpty() { 24648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth setNumEntries(0); 24748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth setNumTombstones(0); 2487f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 2497f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth assert((getNumBuckets() & (getNumBuckets()-1)) == 0 && 2507f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth "# initial buckets must be a power of two!"); 2517f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth const KeyT EmptyKey = getEmptyKey(); 2527f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth for (BucketT *B = getBuckets(), *E = getBucketsEnd(); B != E; ++B) 2537f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth new (&B->first) KeyT(EmptyKey); 2547f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 255295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer 2567f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void moveFromOldBuckets(BucketT *OldBucketsBegin, BucketT *OldBucketsEnd) { 2577f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth initEmpty(); 25888b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer 2597f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth // Insert all the old elements. 2607f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth const KeyT EmptyKey = getEmptyKey(); 2617f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth const KeyT TombstoneKey = getTombstoneKey(); 2627f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth for (BucketT *B = OldBucketsBegin, *E = OldBucketsEnd; B != E; ++B) { 2637f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth if (!KeyInfoT::isEqual(B->first, EmptyKey) && 2647f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth !KeyInfoT::isEqual(B->first, TombstoneKey)) { 2657f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth // Insert the key/value into the new table. 2667f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth BucketT *DestBucket; 2677f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth bool FoundVal = LookupBucketFor(B->first, DestBucket); 2687f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth (void)FoundVal; // silence warning. 2697f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth assert(!FoundVal && "Key already in new map?"); 2707f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth DestBucket->first = llvm_move(B->first); 2717f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth new (&DestBucket->second) ValueT(llvm_move(B->second)); 27248f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth incrementNumEntries(); 2737f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 2747f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth // Free the value. 2757f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth B->second.~ValueT(); 2767f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 2777f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth B->first.~KeyT(); 27888b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer } 27988b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer 2807f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth#ifndef NDEBUG 2817f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth if (OldBucketsBegin != OldBucketsEnd) 2827f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth memset((void*)OldBucketsBegin, 0x5a, 2837f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth sizeof(BucketT) * (OldBucketsEnd - OldBucketsBegin)); 2847f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth#endif 2857f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 2867f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 2877f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth template <typename OtherBaseT> 2887f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void copyFrom(const DenseMapBase<OtherBaseT, KeyT, ValueT, KeyInfoT>& other) { 2897f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth assert(getNumBuckets() == other.getNumBuckets()); 2907f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 29148f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth setNumEntries(other.getNumEntries()); 29248f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth setNumTombstones(other.getNumTombstones()); 2933a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2944e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer if (isPodLike<KeyT>::value && isPodLike<ValueT>::value) 2957f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth memcpy(getBuckets(), other.getBuckets(), 2967f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth getNumBuckets() * sizeof(BucketT)); 2979544dc294f63ce116fbab398a8874ebf834cf41eOwen Anderson else 2987f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth for (size_t i = 0; i < getNumBuckets(); ++i) { 2997f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth new (&getBuckets()[i].first) KeyT(other.getBuckets()[i].first); 3007f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth if (!KeyInfoT::isEqual(getBuckets()[i].first, getEmptyKey()) && 3017f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth !KeyInfoT::isEqual(getBuckets()[i].first, getTombstoneKey())) 3027f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth new (&getBuckets()[i].second) ValueT(other.getBuckets()[i].second); 3039544dc294f63ce116fbab398a8874ebf834cf41eOwen Anderson } 30467280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson } 3053a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3067f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void swap(DenseMapBase& RHS) { 30748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth std::swap(getNumEntries(), RHS.getNumEntries()); 30848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth std::swap(getNumTombstones(), RHS.getNumTombstones()); 3097f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 3107f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 3117f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthprivate: 3127f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth static unsigned getHashValue(const KeyT &Val) { 3137f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return KeyInfoT::getHashValue(Val); 3147f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 3157f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth template<typename LookupKeyT> 3167f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth static unsigned getHashValue(const LookupKeyT &Val) { 3177f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return KeyInfoT::getHashValue(Val); 3187f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 3197f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth static const KeyT getEmptyKey() { 3207f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return KeyInfoT::getEmptyKey(); 3217f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 3227f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth static const KeyT getTombstoneKey() { 3237f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return KeyInfoT::getTombstoneKey(); 3247f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 3257f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 32648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned getNumEntries() const { 32748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth return static_cast<const DerivedT *>(this)->getNumEntries(); 32848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 32948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth void setNumEntries(unsigned Num) { 33048f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth static_cast<DerivedT *>(this)->setNumEntries(Num); 33148f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 33248f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth void incrementNumEntries() { 33348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth setNumEntries(getNumEntries() + 1); 33448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 33548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth void decrementNumEntries() { 33648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth setNumEntries(getNumEntries() - 1); 33748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 33848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned getNumTombstones() const { 33948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth return static_cast<const DerivedT *>(this)->getNumTombstones(); 34048f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 34148f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth void setNumTombstones(unsigned Num) { 34248f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth static_cast<DerivedT *>(this)->setNumTombstones(Num); 34348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 34448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth void incrementNumTombstones() { 34548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth setNumTombstones(getNumTombstones() + 1); 34648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 34748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth void decrementNumTombstones() { 34848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth setNumTombstones(getNumTombstones() - 1); 34948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 3507f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth BucketT *getBuckets() const { 3517f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return static_cast<const DerivedT *>(this)->getBuckets(); 3527f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 3537f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth unsigned getNumBuckets() const { 3547f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return static_cast<const DerivedT *>(this)->getNumBuckets(); 3557f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 3567f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth BucketT *getBucketsEnd() const { 3577f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return getBuckets() + getNumBuckets(); 3587f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 3597f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 3607f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void grow(unsigned AtLeast) { 3617f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth static_cast<DerivedT *>(this)->grow(AtLeast); 3627f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 3637f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 3647f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void shrink_and_clear() { 3657f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth static_cast<DerivedT *>(this)->shrink_and_clear(); 3667f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 3677f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 3687f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 36928f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner BucketT *InsertIntoBucket(const KeyT &Key, const ValueT &Value, 37028f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner BucketT *TheBucket) { 371aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer TheBucket = InsertIntoBucketImpl(Key, TheBucket); 372aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 373aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer TheBucket->first = Key; 374aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer new (&TheBucket->second) ValueT(Value); 375aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer return TheBucket; 376aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer } 377aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 378aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer#if LLVM_USE_RVALUE_REFERENCES 379aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer BucketT *InsertIntoBucket(const KeyT &Key, ValueT &&Value, 380aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer BucketT *TheBucket) { 381aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer TheBucket = InsertIntoBucketImpl(Key, TheBucket); 382aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 383aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer TheBucket->first = Key; 384aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer new (&TheBucket->second) ValueT(std::move(Value)); 385aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer return TheBucket; 386aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer } 387aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 388aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer BucketT *InsertIntoBucket(KeyT &&Key, ValueT &&Value, BucketT *TheBucket) { 389aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer TheBucket = InsertIntoBucketImpl(Key, TheBucket); 390aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 391aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer TheBucket->first = std::move(Key); 392aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer new (&TheBucket->second) ValueT(std::move(Value)); 393aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer return TheBucket; 394aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer } 395aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer#endif 396aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 397aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer BucketT *InsertIntoBucketImpl(const KeyT &Key, BucketT *TheBucket) { 39804a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // If the load of the hash table is more than 3/4, or if fewer than 1/8 of 39904a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // the buckets are empty (meaning that many are filled with tombstones), 40004a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // grow the table. 40104a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // 40204a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // The later case is tricky. For example, if we had one empty bucket with 40304a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // tons of tombstones, failing lookups (e.g. for insertion) would have to 40404a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // probe almost the entire table until it found the empty bucket. If the 40504a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // table completely filled with tombstones, no lookup would ever succeed, 40604a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // causing infinite loops in lookup. 40748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned NewNumEntries = getNumEntries() + 1; 4087f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth if (NewNumEntries*4 >= getNumBuckets()*3) { 4097f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->grow(getNumBuckets() * 2); 41028f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner LookupBucketFor(Key, TheBucket); 4116e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 41248f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth if (getNumBuckets()-(NewNumEntries+getNumTombstones()) < getNumBuckets()/8) { 4137f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->grow(getNumBuckets()); 414414fdbdb0104fdc8c570287f94df8bb697e7b7c1Jakob Stoklund Olesen LookupBucketFor(Key, TheBucket); 415414fdbdb0104fdc8c570287f94df8bb697e7b7c1Jakob Stoklund Olesen } 4163a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4177f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth // Only update the state after we've grown our bucket space appropriately 4187f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth // so that when growing buckets we have self-consistent entry count. 41948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth incrementNumEntries(); 4207f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 42104a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // If we are writing over a tombstone, remember this. 42205831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(TheBucket->first, getEmptyKey())) 42348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth decrementNumTombstones(); 4243a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 42528f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner return TheBucket; 4266e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 42728f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner 4286e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in 4296e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// FoundBucket. If the bucket contains the key and a value, this returns 4306e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// true, otherwise it returns a bucket with an empty marker or tombstone and 4316e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// returns false. 432babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin template<typename LookupKeyT> 433babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin bool LookupBucketFor(const LookupKeyT &Val, BucketT *&FoundBucket) const { 4346e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned BucketNo = getHashValue(Val); 4356e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned ProbeAmt = 1; 4367f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth BucketT *BucketsPtr = getBuckets(); 4373a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4387f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth if (getNumBuckets() == 0) { 43949d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer FoundBucket = 0; 44049d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer return false; 44149d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer } 44249d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer 4436e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // FoundTombstone - Keep track of whether we find a tombstone while probing. 4446e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *FoundTombstone = 0; 4456e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(); 4466e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT TombstoneKey = getTombstoneKey(); 44705831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner assert(!KeyInfoT::isEqual(Val, EmptyKey) && 44805831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(Val, TombstoneKey) && 4496e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner "Empty/Tombstone value shouldn't be inserted into map!"); 4503a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4516e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner while (1) { 4527f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth BucketT *ThisBucket = BucketsPtr + (BucketNo & (getNumBuckets()-1)); 4536e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Found Val's bucket? If so, return it. 454babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin if (KeyInfoT::isEqual(Val, ThisBucket->first)) { 4556e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundBucket = ThisBucket; 4566e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return true; 4576e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 4583a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4596e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If we found an empty bucket, the key doesn't exist in the set. 4606e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Insert it and return the default value. 46176c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner if (KeyInfoT::isEqual(ThisBucket->first, EmptyKey)) { 4626e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If we've already seen a tombstone while probing, fill it in instead 4636e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // of the empty bucket we eventually probed to. 4646e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner if (FoundTombstone) ThisBucket = FoundTombstone; 4656e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket; 4666e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return false; 4676e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 4683a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4696e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If this is a tombstone, remember it. If Val ends up not in the map, we 4706e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // prefer to return it than something that would require more probing. 47176c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner if (KeyInfoT::isEqual(ThisBucket->first, TombstoneKey) && !FoundTombstone) 4726e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundTombstone = ThisBucket; // Remember the first tombstone found. 4733a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4746e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Otherwise, it's a hash collision or a tombstone, continue quadratic 4756e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // probing. 4766e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketNo += ProbeAmt++; 4776e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 4786e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 4796e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 4807f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthpublic: 4817f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth /// Return the approximate size (in bytes) of the actual map. 4827f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth /// This is just the raw memory used by DenseMap. 4837f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth /// If entries are pointers to objects, the size of the referenced objects 4847f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth /// are not included. 4857f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth size_t getMemorySize() const { 4867f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return getNumBuckets() * sizeof(BucketT); 4877f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 4887f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth}; 48949d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer 4907f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthtemplate<typename KeyT, typename ValueT, 4917f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth typename KeyInfoT = DenseMapInfo<KeyT> > 4927f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthclass DenseMap 4937f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT>, 4947f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth KeyT, ValueT, KeyInfoT> { 4957f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth // Lift some types from the dependent base class into this class for 4967f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth // simplicity of referring to them. 4977f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth typedef DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT> BaseT; 4987f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth typedef typename BaseT::BucketT BucketT; 4997f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth friend class DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT>; 50049d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer 5017f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth BucketT *Buckets; 50248f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned NumEntries; 50348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned NumTombstones; 5047f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth unsigned NumBuckets; 5057f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 5067f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthpublic: 5077f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth explicit DenseMap(unsigned NumInitBuckets = 0) { 5087f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth init(NumInitBuckets); 5096e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 5103a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5117f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth DenseMap(const DenseMap &other) { 5127f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth init(0); 5137f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth copyFrom(other); 5147f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5153a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5167f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth#if LLVM_USE_RVALUE_REFERENCES 5177f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth DenseMap(DenseMap &&other) { 5187f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth init(0); 5197f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth swap(other); 5207f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5217f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth#endif 52249d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer 5237f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth template<typename InputIt> 5247f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth DenseMap(const InputIt &I, const InputIt &E) { 5257f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth init(NextPowerOf2(std::distance(I, E))); 5267f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->insert(I, E); 5277f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5286e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 5297f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth ~DenseMap() { 5307f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->destroyAll(); 5317f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth operator delete(Buckets); 5327f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5336e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 5347f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void swap(DenseMap& RHS) { 5357f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth std::swap(Buckets, RHS.Buckets); 53648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth std::swap(NumEntries, RHS.NumEntries); 53748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth std::swap(NumTombstones, RHS.NumTombstones); 53848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth std::swap(NumBuckets, RHS.NumBuckets); 5397f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5403a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5417f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth DenseMap& operator=(const DenseMap& other) { 5427f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth copyFrom(other); 5437f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return *this; 5447f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5457f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 5467f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth#if LLVM_USE_RVALUE_REFERENCES 5477f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth DenseMap& operator=(DenseMap &&other) { 5487f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->destroyAll(); 5497f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth operator delete(Buckets); 5507f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth init(0); 5517f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth swap(other); 5527f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return *this; 5537f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 554d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#endif 5557f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 5567f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void copyFrom(const DenseMap& other) { 5577f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->destroyAll(); 5587f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth operator delete(Buckets); 55948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth if (allocateBuckets(other.NumBuckets)) { 5607f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->BaseT::copyFrom(other); 56148f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } else { 56248f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth NumEntries = 0; 56348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth NumTombstones = 0; 56448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 5656e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 5663a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5677f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void init(unsigned InitBuckets) { 56848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth if (allocateBuckets(InitBuckets)) { 5697f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->BaseT::initEmpty(); 57048f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } else { 57148f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth NumEntries = 0; 57248f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth NumTombstones = 0; 57348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 5747f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5757f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 5767f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void grow(unsigned AtLeast) { 5776ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson unsigned OldNumBuckets = NumBuckets; 5786ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson BucketT *OldBuckets = Buckets; 5793a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5807f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth allocateBuckets(std::max<unsigned>(64, NextPowerOf2(AtLeast))); 5817f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth assert(Buckets); 5827f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth if (!OldBuckets) { 5837f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->BaseT::initEmpty(); 5847f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return; 5856ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 5863a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5877f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->moveFromOldBuckets(OldBuckets, OldBuckets+OldNumBuckets); 5887f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 5896ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson // Free the old table. 59008c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman operator delete(OldBuckets); 5917f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5923a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5937f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void shrink_and_clear() { 59448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned OldNumEntries = NumEntries; 5957f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->destroyAll(); 5967f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 5977f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth // Reduce the number of buckets. 5987f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth unsigned NewNumBuckets 59948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth = std::max(64, 1 << (Log2_32_Ceil(OldNumEntries) + 1)); 6007f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth if (NewNumBuckets == NumBuckets) { 6017f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->BaseT::initEmpty(); 6027f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return; 6037f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 6047f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 6057f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth operator delete(Buckets); 6067f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth init(NewNumBuckets); 6076ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 6087f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 6097f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthprivate: 61048f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned getNumEntries() const { 61148f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth return NumEntries; 61248f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 61348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth void setNumEntries(unsigned Num) { 61448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth NumEntries = Num; 61548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 61648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth 61748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned getNumTombstones() const { 61848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth return NumTombstones; 61948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 62048f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth void setNumTombstones(unsigned Num) { 62148f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth NumTombstones = Num; 62248f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 62348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth 6247f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth BucketT *getBuckets() const { 6257f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return Buckets; 6267f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 6277f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 6287f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth unsigned getNumBuckets() const { 6297f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return NumBuckets; 6307f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 6317f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 6327f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth bool allocateBuckets(unsigned Num) { 6337f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth NumBuckets = Num; 6347f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth if (NumBuckets == 0) { 6357f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth Buckets = 0; 6367f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return false; 6377f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 6387f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 6397f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT) * NumBuckets)); 6407f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return true; 641e6b693db8cc07be91229bef0d8577ce8b5caf34bTed Kremenek } 6426e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner}; 6436e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 64481cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskintemplate<typename KeyT, typename ValueT, 6454e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer typename KeyInfoT, bool IsConst> 64681cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskinclass DenseMapIterator { 64781cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef std::pair<KeyT, ValueT> Bucket; 64881cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef DenseMapIterator<KeyT, ValueT, 6494e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer KeyInfoT, true> ConstIterator; 6504e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, true>; 65181cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskinpublic: 65281cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef ptrdiff_t difference_type; 65381cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef typename conditional<IsConst, const Bucket, Bucket>::type value_type; 65481cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef value_type *pointer; 65581cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef value_type &reference; 65681cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef std::forward_iterator_tag iterator_category; 65781cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskinprivate: 65881cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin pointer Ptr, End; 659f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerpublic: 660a9ad04191cb56c42944b17980b8b2bb2afe11ab2Dan Gohman DenseMapIterator() : Ptr(0), End(0) {} 66113e781ebe7a39e008dd5e5de78983e095e8a1d02David Greene 662f0be7ca7e42915779175a9332c6baba18a2a840cBenjamin Kramer DenseMapIterator(pointer Pos, pointer E, bool NoAdvance = false) 663f0be7ca7e42915779175a9332c6baba18a2a840cBenjamin Kramer : Ptr(Pos), End(E) { 664f0be7ca7e42915779175a9332c6baba18a2a840cBenjamin Kramer if (!NoAdvance) AdvancePastEmptyBuckets(); 665f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 6663a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 66781cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin // If IsConst is true this is a converting constructor from iterator to 66881cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin // const_iterator and the default copy constructor is used. 66981cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin // Otherwise this is a copy constructor for iterator. 67081cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin DenseMapIterator(const DenseMapIterator<KeyT, ValueT, 6714e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer KeyInfoT, false>& I) 67281cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin : Ptr(I.Ptr), End(I.End) {} 67381cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin 67481cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin reference operator*() const { 67581cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin return *Ptr; 676f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 67781cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin pointer operator->() const { 67881cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin return Ptr; 679f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 6803a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 68181cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin bool operator==(const ConstIterator &RHS) const { 68281cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin return Ptr == RHS.operator->(); 683f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 68481cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin bool operator!=(const ConstIterator &RHS) const { 68581cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin return Ptr != RHS.operator->(); 686f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 6873a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 6884ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin inline DenseMapIterator& operator++() { // Preincrement 689f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner ++Ptr; 690f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner AdvancePastEmptyBuckets(); 691f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner return *this; 692f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 6934ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin DenseMapIterator operator++(int) { // Postincrement 694f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner DenseMapIterator tmp = *this; ++*this; return tmp; 695f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 6963a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 697f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerprivate: 698f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner void AdvancePastEmptyBuckets() { 699a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner const KeyT Empty = KeyInfoT::getEmptyKey(); 700a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner const KeyT Tombstone = KeyInfoT::getTombstoneKey(); 701f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 7023a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman while (Ptr != End && 70376c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner (KeyInfoT::isEqual(Ptr->first, Empty) || 70476c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner KeyInfoT::isEqual(Ptr->first, Tombstone))) 705f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner ++Ptr; 706f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 707f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner}; 70818dceba0bb5e38250535401ecc9d9737943d0657Ted Kremenek 7094e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramertemplate<typename KeyT, typename ValueT, typename KeyInfoT> 71018dceba0bb5e38250535401ecc9d9737943d0657Ted Kremenekstatic inline size_t 7114e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramercapacity_in_bytes(const DenseMap<KeyT, ValueT, KeyInfoT> &X) { 71218dceba0bb5e38250535401ecc9d9737943d0657Ted Kremenek return X.getMemorySize(); 71318dceba0bb5e38250535401ecc9d9737943d0657Ted Kremenek} 714f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 7156e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner} // end namespace llvm 7166e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 7176e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner#endif 718