DenseMap.h revision 8e337120133c746640246feb9383556d383a94be
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 37a76b1febd4fd258e8054395adedcbd477668d956Chris Lattnertemplate<typename KeyT, typename ValueT, 384e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer typename KeyInfoT = DenseMapInfo<KeyT> > 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 56aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer#if LLVM_USE_RVALUE_REFERENCES 57aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer DenseMap(DenseMap &&other) { 58aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer init(0); 59aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer swap(other); 60aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer } 61aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer#endif 62aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 6349d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer explicit DenseMap(unsigned NumInitBuckets = 0) { 646e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner init(NumInitBuckets); 656e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 663a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 676a363782fe4ecba4f0a72c2edf03596004470c4aChris Lattner template<typename InputIt> 686a363782fe4ecba4f0a72c2edf03596004470c4aChris Lattner DenseMap(const InputIt &I, const InputIt &E) { 6949d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer init(NextPowerOf2(std::distance(I, E))); 706a363782fe4ecba4f0a72c2edf03596004470c4aChris Lattner insert(I, E); 716a363782fe4ecba4f0a72c2edf03596004470c4aChris Lattner } 72295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer 736e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner ~DenseMap() { 74295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer DestroyAll(); 756e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 763a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 77a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner typedef DenseMapIterator<KeyT, ValueT, KeyInfoT> iterator; 7881cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef DenseMapIterator<KeyT, ValueT, 794e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer KeyInfoT, true> const_iterator; 8070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline iterator begin() { 81b843d9f833aa474ae700363a445b7409665c4a6eJakob Stoklund Olesen // When the map is empty, avoid the overhead of AdvancePastEmptyBuckets(). 82b843d9f833aa474ae700363a445b7409665c4a6eJakob Stoklund Olesen return empty() ? end() : iterator(Buckets, Buckets+NumBuckets); 8370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 8470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline iterator end() { 85f0be7ca7e42915779175a9332c6baba18a2a840cBenjamin Kramer return iterator(Buckets+NumBuckets, Buckets+NumBuckets, true); 8670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 8770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline const_iterator begin() const { 88b843d9f833aa474ae700363a445b7409665c4a6eJakob Stoklund Olesen return empty() ? end() : const_iterator(Buckets, Buckets+NumBuckets); 8970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 9070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline const_iterator end() const { 91f0be7ca7e42915779175a9332c6baba18a2a840cBenjamin Kramer return const_iterator(Buckets+NumBuckets, Buckets+NumBuckets, true); 9270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 933a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 9470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner bool empty() const { return NumEntries == 0; } 956e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned size() const { return NumEntries; } 96d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin 97d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin /// Grow the densemap so that it has at least Size buckets. Does not shrink 9849d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer void resize(size_t Size) { 9949d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer if (Size > NumBuckets) 10049d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer grow(Size); 10149d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer } 1023a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1036e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner void clear() { 10432859c71d6ba9cd5e38662611a73d82335f4ba41Chris Lattner if (NumEntries == 0 && NumTombstones == 0) return; 10532859c71d6ba9cd5e38662611a73d82335f4ba41Chris Lattner 10642e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner // If the capacity of the array is huge, and the # elements used is small, 10742e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner // shrink the array. 1086ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson if (NumEntries * 4 < NumBuckets && NumBuckets > 64) { 1096ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson shrink_and_clear(); 1106ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson return; 1116ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 1123a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1136e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 1146e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { 11505831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(P->first, EmptyKey)) { 11605831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(P->first, TombstoneKey)) { 1177b54452c84e478ab4d49ac08759ca4ec1badf2b2Chris Lattner P->second.~ValueT(); 1187b54452c84e478ab4d49ac08759ca4ec1badf2b2Chris Lattner --NumEntries; 1197b54452c84e478ab4d49ac08759ca4ec1badf2b2Chris Lattner } 120f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner P->first = EmptyKey; 1216e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1226e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1236e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner assert(NumEntries == 0 && "Node count imbalance!"); 12404a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner NumTombstones = 0; 1256e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1266ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson 1276e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// count - Return true if the specified key is in the map. 1286e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner bool count(const KeyT &Val) const { 1296e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *TheBucket; 1306e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return LookupBucketFor(Val, TheBucket); 1316e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1323a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 133569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner iterator find(const KeyT &Val) { 13470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner BucketT *TheBucket; 13570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner if (LookupBucketFor(Val, TheBucket)) 136f0be7ca7e42915779175a9332c6baba18a2a840cBenjamin Kramer return iterator(TheBucket, Buckets+NumBuckets, true); 13770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return end(); 13870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 139569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner const_iterator find(const KeyT &Val) const { 140569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner BucketT *TheBucket; 141569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner if (LookupBucketFor(Val, TheBucket)) 142f0be7ca7e42915779175a9332c6baba18a2a840cBenjamin Kramer return const_iterator(TheBucket, Buckets+NumBuckets, true); 143569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner return end(); 144569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner } 1453a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 146babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin /// Alternate version of find() which allows a different, and possibly 147babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin /// less expensive, key type. 148babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin /// The DenseMapInfo is responsible for supplying methods 149babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key 150babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin /// type used. 151babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin template<class LookupKeyT> 152babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin iterator find_as(const LookupKeyT &Val) { 153babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin BucketT *TheBucket; 154babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin if (LookupBucketFor(Val, TheBucket)) 155babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin return iterator(TheBucket, Buckets+NumBuckets, true); 156babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin return end(); 157babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin } 158babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin template<class LookupKeyT> 159babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin const_iterator find_as(const LookupKeyT &Val) const { 160babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin BucketT *TheBucket; 161babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin if (LookupBucketFor(Val, TheBucket)) 162babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin return const_iterator(TheBucket, Buckets+NumBuckets, true); 163babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin return end(); 164babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin } 165babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin 1667b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar /// lookup - Return the entry for the specified key, or a default 1677b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar /// constructed value if no such entry exists. 1687b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar ValueT lookup(const KeyT &Val) const { 1697b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar BucketT *TheBucket; 1707b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar if (LookupBucketFor(Val, TheBucket)) 1717b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar return TheBucket->second; 1727b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar return ValueT(); 1737b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar } 1747b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar 175127445818efd810b138dd5362129ab3c7f8b9963Torok Edwin // Inserts key,value pair into the map if the key isn't already in the map. 176127445818efd810b138dd5362129ab3c7f8b9963Torok Edwin // If the key is already in the map, it returns false and doesn't update the 177127445818efd810b138dd5362129ab3c7f8b9963Torok Edwin // value. 1786b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { 17928f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner BucketT *TheBucket; 18028f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner if (LookupBucketFor(KV.first, TheBucket)) 181f0be7ca7e42915779175a9332c6baba18a2a840cBenjamin Kramer return std::make_pair(iterator(TheBucket, Buckets+NumBuckets, true), 1826b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman false); // Already in map. 1833a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 18428f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner // Otherwise, insert the new element. 1856b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman TheBucket = InsertIntoBucket(KV.first, KV.second, TheBucket); 186f0be7ca7e42915779175a9332c6baba18a2a840cBenjamin Kramer return std::make_pair(iterator(TheBucket, Buckets+NumBuckets, true), true); 18728f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner } 1883a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 189b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner /// insert - Range insertion of pairs. 190b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner template<typename InputIt> 191b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner void insert(InputIt I, InputIt E) { 192b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner for (; I != E; ++I) 193b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner insert(*I); 194b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner } 195b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner 1963a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 19770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner bool erase(const KeyT &Val) { 19870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner BucketT *TheBucket; 19970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner if (!LookupBucketFor(Val, TheBucket)) 20070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return false; // not in map. 20170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner 20270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->second.~ValueT(); 20370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->first = getTombstoneKey(); 20470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner --NumEntries; 20504a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner ++NumTombstones; 20670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return true; 20770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 208e3955df639ff9aff990f628ef6a219ff5efdbc81Dan Gohman void erase(iterator I) { 20970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner BucketT *TheBucket = &*I; 21070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->second.~ValueT(); 21170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->first = getTombstoneKey(); 21270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner --NumEntries; 21304a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner ++NumTombstones; 21470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 215aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek 216ccb4f2d813380d8cf139062b8c829e4b8b322c0dAndrew Lenharth void swap(DenseMap& RHS) { 217ccb4f2d813380d8cf139062b8c829e4b8b322c0dAndrew Lenharth std::swap(NumBuckets, RHS.NumBuckets); 218ccb4f2d813380d8cf139062b8c829e4b8b322c0dAndrew Lenharth std::swap(Buckets, RHS.Buckets); 219ccb4f2d813380d8cf139062b8c829e4b8b322c0dAndrew Lenharth std::swap(NumEntries, RHS.NumEntries); 220ccb4f2d813380d8cf139062b8c829e4b8b322c0dAndrew Lenharth std::swap(NumTombstones, RHS.NumTombstones); 221ccb4f2d813380d8cf139062b8c829e4b8b322c0dAndrew Lenharth } 222ccb4f2d813380d8cf139062b8c829e4b8b322c0dAndrew Lenharth 223aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek value_type& FindAndConstruct(const KeyT &Key) { 2246e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *TheBucket; 22528f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner if (LookupBucketFor(Key, TheBucket)) 226aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek return *TheBucket; 2273a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 228aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek return *InsertIntoBucket(Key, ValueT(), TheBucket); 229aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek } 2303a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 231aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek ValueT &operator[](const KeyT &Key) { 232aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek return FindAndConstruct(Key).second; 23328f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner } 2343a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 235aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer#if LLVM_USE_RVALUE_REFERENCES 236aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer value_type& FindAndConstruct(KeyT &&Key) { 237aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer BucketT *TheBucket; 238aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer if (LookupBucketFor(Key, TheBucket)) 239aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer return *TheBucket; 240aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 241aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer return *InsertIntoBucket(Key, ValueT(), TheBucket); 242aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer } 243aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 244aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer ValueT &operator[](KeyT &&Key) { 245aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer return FindAndConstruct(Key).second; 246aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer } 247aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer#endif 248aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 24967280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson DenseMap& operator=(const DenseMap& other) { 25067280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson CopyFrom(other); 2513d345631db71174ffc4997a88c09f21eb9ed052bOwen Anderson return *this; 25267280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson } 2533a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 254aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer#if LLVM_USE_RVALUE_REFERENCES 255aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer DenseMap& operator=(DenseMap &&other) { 256aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer DestroyAll(); 257aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer init(0); 258aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer swap(other); 259aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer } 260aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer#endif 261aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 262bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// isPointerIntoBucketsArray - Return true if the specified pointer points 263bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// somewhere into the DenseMap's array of buckets (i.e. either to a key or 264bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// value in the DenseMap). 265bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner bool isPointerIntoBucketsArray(const void *Ptr) const { 266bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner return Ptr >= Buckets && Ptr < Buckets+NumBuckets; 267bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner } 268bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner 269bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets 270bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// array. In conjunction with the previous method, this can be used to 271bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// determine whether an insertion caused the DenseMap to reallocate. 272bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner const void *getPointerIntoBucketsArray() const { return Buckets; } 273bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner 27428f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattnerprivate: 275295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer void DestroyAll() { 2768e337120133c746640246feb9383556d383a94beBenjamin Kramer if (NumBuckets == 0) // Nothing to do. 2778e337120133c746640246feb9383556d383a94beBenjamin Kramer return; 2788e337120133c746640246feb9383556d383a94beBenjamin Kramer 279295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 280295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { 281295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer if (!KeyInfoT::isEqual(P->first, EmptyKey) && 282295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer !KeyInfoT::isEqual(P->first, TombstoneKey)) 283295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer P->second.~ValueT(); 284295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer P->first.~KeyT(); 28567280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson } 2863a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 287d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#ifndef NDEBUG 2888e337120133c746640246feb9383556d383a94beBenjamin Kramer memset((void*)Buckets, 0x5a, sizeof(BucketT)*NumBuckets); 289d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#endif 2908e337120133c746640246feb9383556d383a94beBenjamin Kramer operator delete(Buckets); 291295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer } 29288b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer 293295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer void CopyFrom(const DenseMap& other) { 294295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer DestroyAll(); 295295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer 296295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer NumEntries = other.NumEntries; 297295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer NumTombstones = other.NumTombstones; 29888b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer NumBuckets = other.NumBuckets; 29988b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer 30088b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer if (NumBuckets == 0) { 30188b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer Buckets = 0; 30288b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer return; 30388b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer } 30488b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer 30588b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT) * NumBuckets)); 3063a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3074e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer if (isPodLike<KeyT>::value && isPodLike<ValueT>::value) 30888b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer memcpy(Buckets, other.Buckets, NumBuckets * sizeof(BucketT)); 3099544dc294f63ce116fbab398a8874ebf834cf41eOwen Anderson else 31088b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer for (size_t i = 0; i < NumBuckets; ++i) { 3112b7470eb54880ce7f74469d6e09eaf7f0864f8abOwen Anderson new (&Buckets[i].first) KeyT(other.Buckets[i].first); 31205831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(Buckets[i].first, getEmptyKey()) && 31305831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(Buckets[i].first, getTombstoneKey())) 3144938d347723d452786c1a7c1d1b9ec79121b0040Owen Anderson new (&Buckets[i].second) ValueT(other.Buckets[i].second); 3159544dc294f63ce116fbab398a8874ebf834cf41eOwen Anderson } 31667280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson } 3173a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 31828f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner BucketT *InsertIntoBucket(const KeyT &Key, const ValueT &Value, 31928f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner BucketT *TheBucket) { 320aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer TheBucket = InsertIntoBucketImpl(Key, TheBucket); 321aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 322aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer TheBucket->first = Key; 323aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer new (&TheBucket->second) ValueT(Value); 324aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer return TheBucket; 325aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer } 326aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 327aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer#if LLVM_USE_RVALUE_REFERENCES 328aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer BucketT *InsertIntoBucket(const KeyT &Key, ValueT &&Value, 329aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer BucketT *TheBucket) { 330aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer TheBucket = InsertIntoBucketImpl(Key, TheBucket); 331aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 332aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer TheBucket->first = Key; 333aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer new (&TheBucket->second) ValueT(std::move(Value)); 334aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer return TheBucket; 335aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer } 336aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 337aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer BucketT *InsertIntoBucket(KeyT &&Key, ValueT &&Value, BucketT *TheBucket) { 338aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer TheBucket = InsertIntoBucketImpl(Key, TheBucket); 339aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 340aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer TheBucket->first = std::move(Key); 341aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer new (&TheBucket->second) ValueT(std::move(Value)); 342aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer return TheBucket; 343aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer } 344aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer#endif 345aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 346aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer BucketT *InsertIntoBucketImpl(const KeyT &Key, BucketT *TheBucket) { 34704a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // If the load of the hash table is more than 3/4, or if fewer than 1/8 of 34804a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // the buckets are empty (meaning that many are filled with tombstones), 34904a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // grow the table. 35004a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // 35104a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // The later case is tricky. For example, if we had one empty bucket with 35204a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // tons of tombstones, failing lookups (e.g. for insertion) would have to 35304a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // probe almost the entire table until it found the empty bucket. If the 35404a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // table completely filled with tombstones, no lookup would ever succeed, 35504a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // causing infinite loops in lookup. 356f0e4cac7ebdee07639bd1fc3eadf204f45868556Stuart Hastings ++NumEntries; 357414fdbdb0104fdc8c570287f94df8bb697e7b7c1Jakob Stoklund Olesen if (NumEntries*4 >= NumBuckets*3) { 358d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin this->grow(NumBuckets * 2); 35928f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner LookupBucketFor(Key, TheBucket); 3606e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 361414fdbdb0104fdc8c570287f94df8bb697e7b7c1Jakob Stoklund Olesen if (NumBuckets-(NumEntries+NumTombstones) < NumBuckets/8) { 362414fdbdb0104fdc8c570287f94df8bb697e7b7c1Jakob Stoklund Olesen this->grow(NumBuckets); 363414fdbdb0104fdc8c570287f94df8bb697e7b7c1Jakob Stoklund Olesen LookupBucketFor(Key, TheBucket); 364414fdbdb0104fdc8c570287f94df8bb697e7b7c1Jakob Stoklund Olesen } 3653a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 36604a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // If we are writing over a tombstone, remember this. 36705831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(TheBucket->first, getEmptyKey())) 36804a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner --NumTombstones; 3693a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 37028f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner return TheBucket; 3716e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 37228f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner 37370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner static unsigned getHashValue(const KeyT &Val) { 374a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return KeyInfoT::getHashValue(Val); 3756e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 376babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin template<typename LookupKeyT> 377babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin static unsigned getHashValue(const LookupKeyT &Val) { 378babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin return KeyInfoT::getHashValue(Val); 379babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin } 38070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner static const KeyT getEmptyKey() { 381a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return KeyInfoT::getEmptyKey(); 38270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 38370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner static const KeyT getTombstoneKey() { 384a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner return KeyInfoT::getTombstoneKey(); 3856e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 3863a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3876e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in 3886e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// FoundBucket. If the bucket contains the key and a value, this returns 3896e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// true, otherwise it returns a bucket with an empty marker or tombstone and 3906e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// returns false. 391babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin template<typename LookupKeyT> 392babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin bool LookupBucketFor(const LookupKeyT &Val, BucketT *&FoundBucket) const { 3936e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned BucketNo = getHashValue(Val); 3946e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned ProbeAmt = 1; 3956e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *BucketsPtr = Buckets; 3963a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 39749d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer if (NumBuckets == 0) { 39849d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer FoundBucket = 0; 39949d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer return false; 40049d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer } 40149d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer 4026e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // FoundTombstone - Keep track of whether we find a tombstone while probing. 4036e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *FoundTombstone = 0; 4046e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(); 4056e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT TombstoneKey = getTombstoneKey(); 40605831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner assert(!KeyInfoT::isEqual(Val, EmptyKey) && 40705831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(Val, TombstoneKey) && 4086e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner "Empty/Tombstone value shouldn't be inserted into map!"); 4093a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4106e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner while (1) { 4116e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *ThisBucket = BucketsPtr + (BucketNo & (NumBuckets-1)); 4126e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Found Val's bucket? If so, return it. 413babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin if (KeyInfoT::isEqual(Val, ThisBucket->first)) { 4146e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundBucket = ThisBucket; 4156e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return true; 4166e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 4173a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4186e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If we found an empty bucket, the key doesn't exist in the set. 4196e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Insert it and return the default value. 42076c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner if (KeyInfoT::isEqual(ThisBucket->first, EmptyKey)) { 4216e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If we've already seen a tombstone while probing, fill it in instead 4226e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // of the empty bucket we eventually probed to. 4236e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner if (FoundTombstone) ThisBucket = FoundTombstone; 4246e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket; 4256e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return false; 4266e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 4273a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4286e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If this is a tombstone, remember it. If Val ends up not in the map, we 4296e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // prefer to return it than something that would require more probing. 43076c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner if (KeyInfoT::isEqual(ThisBucket->first, TombstoneKey) && !FoundTombstone) 4316e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundTombstone = ThisBucket; // Remember the first tombstone found. 4323a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4336e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Otherwise, it's a hash collision or a tombstone, continue quadratic 4346e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // probing. 4356e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketNo += ProbeAmt++; 4366e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 4376e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 4386e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 4396e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner void init(unsigned InitBuckets) { 4406e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner NumEntries = 0; 44104a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner NumTombstones = 0; 4426e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner NumBuckets = InitBuckets; 44349d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer 44449d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer if (InitBuckets == 0) { 44549d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer Buckets = 0; 44649d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer return; 44749d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer } 44849d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer 449ae9f3a3b7c915f725aef5a7250e88eaeddda03c6Anton Korobeynikov assert(InitBuckets && (InitBuckets & (InitBuckets-1)) == 0 && 4506e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner "# initial buckets must be a power of two!"); 45108c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*InitBuckets)); 4526e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Initialize all the keys to EmptyKey. 4536e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(); 4546e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (unsigned i = 0; i != InitBuckets; ++i) 455f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner new (&Buckets[i].first) KeyT(EmptyKey); 4566e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 4573a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 458d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin void grow(unsigned AtLeast) { 4596e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner unsigned OldNumBuckets = NumBuckets; 4606e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *OldBuckets = Buckets; 4613a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 46249d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer if (NumBuckets < 64) 46349d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer NumBuckets = 64; 46449d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer 4656e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Double the number of buckets. 466fcb0ee8ffeae12aa866f4e7da12a4dd2a1d0dc35Junjie Gu while (NumBuckets < AtLeast) 467d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin NumBuckets <<= 1; 46804a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner NumTombstones = 0; 46908c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*NumBuckets)); 4706e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 4716e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Initialize all the keys to EmptyKey. 4726e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(); 4736e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (unsigned i = 0, e = NumBuckets; i != e; ++i) 474f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner new (&Buckets[i].first) KeyT(EmptyKey); 4756e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 4766e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Insert all the old elements. 4776e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT TombstoneKey = getTombstoneKey(); 4786e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) { 47905831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(B->first, EmptyKey) && 48005831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(B->first, TombstoneKey)) { 4816e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Insert the key/value into the new table. 4826e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *DestBucket; 483f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner bool FoundVal = LookupBucketFor(B->first, DestBucket); 4849d38acb254108db0ee9e746bb3f7aa64168f7e36Nick Lewycky (void)FoundVal; // silence warning. 4856e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner assert(!FoundVal && "Key already in new map?"); 486ac5802bca0285eee49c1c372846552823d819181Benjamin Kramer DestBucket->first = llvm_move(B->first); 487ac5802bca0285eee49c1c372846552823d819181Benjamin Kramer new (&DestBucket->second) ValueT(llvm_move(B->second)); 4883a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4896e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Free the value. 490f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner B->second.~ValueT(); 4916e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 492f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner B->first.~KeyT(); 4936e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 4943a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 495d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#ifndef NDEBUG 496d01f2633b9aab6281c936da04226b46a0dde7ba9Jay Foad if (OldNumBuckets) 497450ed1a05bd5e12c141629b0d0ba275958634980Chris Lattner memset((void*)OldBuckets, 0x5a, sizeof(BucketT)*OldNumBuckets); 498d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#endif 4996e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Free the old table. 50008c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman operator delete(OldBuckets); 5016e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 5023a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5036ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson void shrink_and_clear() { 5046ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson unsigned OldNumBuckets = NumBuckets; 5056ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson BucketT *OldBuckets = Buckets; 5063a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 507398b40671b13018f88371b74822fa8ee2638577eOwen Anderson // Reduce the number of buckets. 508398b40671b13018f88371b74822fa8ee2638577eOwen Anderson NumBuckets = NumEntries > 32 ? 1 << (Log2_32_Ceil(NumEntries) + 1) 509398b40671b13018f88371b74822fa8ee2638577eOwen Anderson : 64; 5106ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson NumTombstones = 0; 51108c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*NumBuckets)); 5126ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson 5136ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson // Initialize all the keys to EmptyKey. 5146ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson const KeyT EmptyKey = getEmptyKey(); 5156ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson for (unsigned i = 0, e = NumBuckets; i != e; ++i) 5166ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson new (&Buckets[i].first) KeyT(EmptyKey); 5176ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson 5186ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson // Free the old buckets. 5196ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson const KeyT TombstoneKey = getTombstoneKey(); 5206ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) { 52105831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(B->first, EmptyKey) && 52205831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(B->first, TombstoneKey)) { 5236ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson // Free the value. 5246ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson B->second.~ValueT(); 5256ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 5266ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson B->first.~KeyT(); 5276ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 5283a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 529d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#ifndef NDEBUG 530776157ac926102de7a8e40e936dd9efcd7f9dd1bChandler Carruth memset((void*)OldBuckets, 0x5a, sizeof(BucketT)*OldNumBuckets); 531d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#endif 5326ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson // Free the old table. 53308c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman operator delete(OldBuckets); 5343a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5356ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson NumEntries = 0; 5366ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 537e6b693db8cc07be91229bef0d8577ce8b5caf34bTed Kremenek 538e6b693db8cc07be91229bef0d8577ce8b5caf34bTed Kremenekpublic: 539e6b693db8cc07be91229bef0d8577ce8b5caf34bTed Kremenek /// Return the approximate size (in bytes) of the actual map. 540e6b693db8cc07be91229bef0d8577ce8b5caf34bTed Kremenek /// This is just the raw memory used by DenseMap. 541e6b693db8cc07be91229bef0d8577ce8b5caf34bTed Kremenek /// If entries are pointers to objects, the size of the referenced objects 542e6b693db8cc07be91229bef0d8577ce8b5caf34bTed Kremenek /// are not included. 543e6b693db8cc07be91229bef0d8577ce8b5caf34bTed Kremenek size_t getMemorySize() const { 544e6b693db8cc07be91229bef0d8577ce8b5caf34bTed Kremenek return NumBuckets * sizeof(BucketT); 545e6b693db8cc07be91229bef0d8577ce8b5caf34bTed Kremenek } 5466e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner}; 5476e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 54881cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskintemplate<typename KeyT, typename ValueT, 5494e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer typename KeyInfoT, bool IsConst> 55081cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskinclass DenseMapIterator { 55181cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef std::pair<KeyT, ValueT> Bucket; 55281cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef DenseMapIterator<KeyT, ValueT, 5534e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer KeyInfoT, true> ConstIterator; 5544e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, true>; 55581cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskinpublic: 55681cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef ptrdiff_t difference_type; 55781cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef typename conditional<IsConst, const Bucket, Bucket>::type value_type; 55881cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef value_type *pointer; 55981cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef value_type &reference; 56081cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef std::forward_iterator_tag iterator_category; 56181cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskinprivate: 56281cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin pointer Ptr, End; 563f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerpublic: 564a9ad04191cb56c42944b17980b8b2bb2afe11ab2Dan Gohman DenseMapIterator() : Ptr(0), End(0) {} 56513e781ebe7a39e008dd5e5de78983e095e8a1d02David Greene 566f0be7ca7e42915779175a9332c6baba18a2a840cBenjamin Kramer DenseMapIterator(pointer Pos, pointer E, bool NoAdvance = false) 567f0be7ca7e42915779175a9332c6baba18a2a840cBenjamin Kramer : Ptr(Pos), End(E) { 568f0be7ca7e42915779175a9332c6baba18a2a840cBenjamin Kramer if (!NoAdvance) AdvancePastEmptyBuckets(); 569f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 5703a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 57181cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin // If IsConst is true this is a converting constructor from iterator to 57281cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin // const_iterator and the default copy constructor is used. 57381cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin // Otherwise this is a copy constructor for iterator. 57481cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin DenseMapIterator(const DenseMapIterator<KeyT, ValueT, 5754e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer KeyInfoT, false>& I) 57681cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin : Ptr(I.Ptr), End(I.End) {} 57781cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin 57881cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin reference operator*() const { 57981cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin return *Ptr; 580f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 58181cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin pointer operator->() const { 58281cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin return Ptr; 583f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 5843a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 58581cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin bool operator==(const ConstIterator &RHS) const { 58681cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin return Ptr == RHS.operator->(); 587f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 58881cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin bool operator!=(const ConstIterator &RHS) const { 58981cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin return Ptr != RHS.operator->(); 590f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 5913a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5924ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin inline DenseMapIterator& operator++() { // Preincrement 593f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner ++Ptr; 594f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner AdvancePastEmptyBuckets(); 595f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner return *this; 596f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 5974ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin DenseMapIterator operator++(int) { // Postincrement 598f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner DenseMapIterator tmp = *this; ++*this; return tmp; 599f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 6003a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 601f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerprivate: 602f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner void AdvancePastEmptyBuckets() { 603a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner const KeyT Empty = KeyInfoT::getEmptyKey(); 604a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner const KeyT Tombstone = KeyInfoT::getTombstoneKey(); 605f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 6063a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman while (Ptr != End && 60776c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner (KeyInfoT::isEqual(Ptr->first, Empty) || 60876c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner KeyInfoT::isEqual(Ptr->first, Tombstone))) 609f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner ++Ptr; 610f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 611f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner}; 61218dceba0bb5e38250535401ecc9d9737943d0657Ted Kremenek 6134e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramertemplate<typename KeyT, typename ValueT, typename KeyInfoT> 61418dceba0bb5e38250535401ecc9d9737943d0657Ted Kremenekstatic inline size_t 6154e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramercapacity_in_bytes(const DenseMap<KeyT, ValueT, KeyInfoT> &X) { 61618dceba0bb5e38250535401ecc9d9737943d0657Ted Kremenek return X.getMemorySize(); 61718dceba0bb5e38250535401ecc9d9737943d0657Ted Kremenek} 618f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 6196e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner} // end namespace llvm 6206e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 6216e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner#endif 622