DenseMap.h revision cbe40cfe96a6bb3f2da56445269c2c71e55e0e56
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 17255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/ADT/DenseMapInfo.h" 18dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth#include "llvm/Support/AlignOf.h" 19255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/Support/Compiler.h" 20398b40671b13018f88371b74822fa8ee2638577eOwen Anderson#include "llvm/Support/MathExtras.h" 2181cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin#include "llvm/Support/PointerLikeTypeTraits.h" 2281cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin#include "llvm/Support/type_traits.h" 23476b242fe7a61e5f9ac6214b0bc5c680d24f152eNick Lewycky#include <algorithm> 246e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner#include <cassert> 25dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth#include <climits> 26345b378309eabd74a7a43f095dca9a4894bc371eDuncan Sands#include <cstddef> 27d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#include <cstring> 28255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include <iterator> 29255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include <new> 30255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include <utility> 316e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 326e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnernamespace llvm { 333a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 343a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukmantemplate<typename KeyT, typename ValueT, 3576c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner typename KeyInfoT = DenseMapInfo<KeyT>, 364e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer bool IsConst = false> 37f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerclass DenseMapIterator; 386e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 397f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthtemplate<typename DerivedT, 407f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth typename KeyT, typename ValueT, typename KeyInfoT> 417f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthclass DenseMapBase { 427f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthprotected: 43f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner typedef std::pair<KeyT, ValueT> BucketT; 447f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 456e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattnerpublic: 4613e781ebe7a39e008dd5e5de78983e095e8a1d02David Greene typedef KeyT key_type; 4713e781ebe7a39e008dd5e5de78983e095e8a1d02David Greene typedef ValueT mapped_type; 48aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek typedef BucketT value_type; 493a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 50a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner typedef DenseMapIterator<KeyT, ValueT, KeyInfoT> iterator; 5181cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef DenseMapIterator<KeyT, ValueT, 524e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer KeyInfoT, true> const_iterator; 5370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline iterator begin() { 54b843d9f833aa474ae700363a445b7409665c4a6eJakob Stoklund Olesen // When the map is empty, avoid the overhead of AdvancePastEmptyBuckets(). 557f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return empty() ? end() : iterator(getBuckets(), getBucketsEnd()); 5670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 5770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline iterator end() { 587f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return iterator(getBucketsEnd(), getBucketsEnd(), true); 5970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 6070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline const_iterator begin() const { 617f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return empty() ? end() : const_iterator(getBuckets(), getBucketsEnd()); 6270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 6370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner inline const_iterator end() const { 647f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return const_iterator(getBucketsEnd(), getBucketsEnd(), true); 6570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 663a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 67cbe40cfe96a6bb3f2da56445269c2c71e55e0e56Benjamin Kramer bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const { 68cbe40cfe96a6bb3f2da56445269c2c71e55e0e56Benjamin Kramer return getNumEntries() == 0; 69cbe40cfe96a6bb3f2da56445269c2c71e55e0e56Benjamin Kramer } 7048f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned size() const { return getNumEntries(); } 71d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin 72d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin /// Grow the densemap so that it has at least Size buckets. Does not shrink 7349d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer void resize(size_t Size) { 747f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth if (Size > getNumBuckets()) 7549d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer grow(Size); 7649d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer } 773a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 786e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner void clear() { 7948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth if (getNumEntries() == 0 && getNumTombstones() == 0) return; 80255cd6f317f3a0bad6e7939ca5ce49b33c6676f9NAKAMURA Takumi 8142e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner // If the capacity of the array is huge, and the # elements used is small, 8242e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner // shrink the array. 8348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth if (getNumEntries() * 4 < getNumBuckets() && getNumBuckets() > 64) { 846ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson shrink_and_clear(); 856ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson return; 866ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 873a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 886e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 897f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) { 9005831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(P->first, EmptyKey)) { 9105831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(P->first, TombstoneKey)) { 927b54452c84e478ab4d49ac08759ca4ec1badf2b2Chris Lattner P->second.~ValueT(); 9348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth decrementNumEntries(); 947b54452c84e478ab4d49ac08759ca4ec1badf2b2Chris Lattner } 95f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner P->first = EmptyKey; 966e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 976e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 9848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth assert(getNumEntries() == 0 && "Node count imbalance!"); 9948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth setNumTombstones(0); 1006e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1016ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson 1026e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// count - Return true if the specified key is in the map. 1036e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner bool count(const KeyT &Val) const { 104dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const BucketT *TheBucket; 1056e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return LookupBucketFor(Val, TheBucket); 1066e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1073a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 108569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner iterator find(const KeyT &Val) { 10970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner BucketT *TheBucket; 11070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner if (LookupBucketFor(Val, TheBucket)) 1117f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return iterator(TheBucket, getBucketsEnd(), true); 11270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return end(); 11370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 114569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner const_iterator find(const KeyT &Val) const { 115dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const BucketT *TheBucket; 116569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner if (LookupBucketFor(Val, TheBucket)) 1177f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return const_iterator(TheBucket, getBucketsEnd(), true); 118569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner return end(); 119569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner } 1203a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 121babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin /// Alternate version of find() which allows a different, and possibly 122babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin /// less expensive, key type. 123babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin /// The DenseMapInfo is responsible for supplying methods 124babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key 125babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin /// type used. 126babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin template<class LookupKeyT> 127babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin iterator find_as(const LookupKeyT &Val) { 128babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin BucketT *TheBucket; 129babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin if (LookupBucketFor(Val, TheBucket)) 1307f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return iterator(TheBucket, getBucketsEnd(), true); 131babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin return end(); 132babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin } 133babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin template<class LookupKeyT> 134babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin const_iterator find_as(const LookupKeyT &Val) const { 135dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const BucketT *TheBucket; 136babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin if (LookupBucketFor(Val, TheBucket)) 1377f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return const_iterator(TheBucket, getBucketsEnd(), true); 138babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin return end(); 139babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin } 140babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin 1417b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar /// lookup - Return the entry for the specified key, or a default 1427b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar /// constructed value if no such entry exists. 1437b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar ValueT lookup(const KeyT &Val) const { 144dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const BucketT *TheBucket; 1457b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar if (LookupBucketFor(Val, TheBucket)) 1467b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar return TheBucket->second; 1477b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar return ValueT(); 1487b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar } 1497b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar 150127445818efd810b138dd5362129ab3c7f8b9963Torok Edwin // Inserts key,value pair into the map if the key isn't already in the map. 151127445818efd810b138dd5362129ab3c7f8b9963Torok Edwin // If the key is already in the map, it returns false and doesn't update the 152127445818efd810b138dd5362129ab3c7f8b9963Torok Edwin // value. 1536b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { 15428f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner BucketT *TheBucket; 15528f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner if (LookupBucketFor(KV.first, TheBucket)) 1567f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), 1576b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman false); // Already in map. 1583a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 15928f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner // Otherwise, insert the new element. 1606b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman TheBucket = InsertIntoBucket(KV.first, KV.second, TheBucket); 1617f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), true); 16228f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner } 1633a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 164289148afcb68b28e155ee87aa5a9efcf75adb444Joe Groff#if LLVM_HAS_RVALUE_REFERENCES 165a662a9862501fc86904e90054f7c1519101d9126Joe Groff // Inserts key,value pair into the map if the key isn't already in the map. 166a662a9862501fc86904e90054f7c1519101d9126Joe Groff // If the key is already in the map, it returns false and doesn't update the 167a662a9862501fc86904e90054f7c1519101d9126Joe Groff // value. 168a662a9862501fc86904e90054f7c1519101d9126Joe Groff std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) { 169a662a9862501fc86904e90054f7c1519101d9126Joe Groff BucketT *TheBucket; 170a662a9862501fc86904e90054f7c1519101d9126Joe Groff if (LookupBucketFor(KV.first, TheBucket)) 171a662a9862501fc86904e90054f7c1519101d9126Joe Groff return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), 172a662a9862501fc86904e90054f7c1519101d9126Joe Groff false); // Already in map. 173a662a9862501fc86904e90054f7c1519101d9126Joe Groff 174a662a9862501fc86904e90054f7c1519101d9126Joe Groff // Otherwise, insert the new element. 175a662a9862501fc86904e90054f7c1519101d9126Joe Groff TheBucket = InsertIntoBucket(std::move(KV.first), 176a662a9862501fc86904e90054f7c1519101d9126Joe Groff std::move(KV.second), 177a662a9862501fc86904e90054f7c1519101d9126Joe Groff TheBucket); 178a662a9862501fc86904e90054f7c1519101d9126Joe Groff return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), true); 179a662a9862501fc86904e90054f7c1519101d9126Joe Groff } 180a662a9862501fc86904e90054f7c1519101d9126Joe Groff#endif 181a662a9862501fc86904e90054f7c1519101d9126Joe Groff 182b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner /// insert - Range insertion of pairs. 183b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner template<typename InputIt> 184b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner void insert(InputIt I, InputIt E) { 185b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner for (; I != E; ++I) 186b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner insert(*I); 187b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner } 188b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner 1893a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 19070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner bool erase(const KeyT &Val) { 19170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner BucketT *TheBucket; 19270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner if (!LookupBucketFor(Val, TheBucket)) 19370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return false; // not in map. 19470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner 19570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->second.~ValueT(); 19670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->first = getTombstoneKey(); 19748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth decrementNumEntries(); 19848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth incrementNumTombstones(); 19970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return true; 20070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 201e3955df639ff9aff990f628ef6a219ff5efdbc81Dan Gohman void erase(iterator I) { 20270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner BucketT *TheBucket = &*I; 20370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->second.~ValueT(); 20470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->first = getTombstoneKey(); 20548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth decrementNumEntries(); 20648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth incrementNumTombstones(); 20770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 208aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek 209aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek value_type& FindAndConstruct(const KeyT &Key) { 2106e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *TheBucket; 21128f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner if (LookupBucketFor(Key, TheBucket)) 212aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek return *TheBucket; 2133a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 214aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek return *InsertIntoBucket(Key, ValueT(), TheBucket); 215aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek } 2163a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 217aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek ValueT &operator[](const KeyT &Key) { 218aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek return FindAndConstruct(Key).second; 21928f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner } 2203a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2214334dd96a9e622fdcf2825a8f73a2d941d67be72Chandler Carruth#if LLVM_HAS_RVALUE_REFERENCES 222aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer value_type& FindAndConstruct(KeyT &&Key) { 223aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer BucketT *TheBucket; 224aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer if (LookupBucketFor(Key, TheBucket)) 225aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer return *TheBucket; 226aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 227da8b91a0731e34b97aadb0241ba6cefa4481cffaBenjamin Kramer return *InsertIntoBucket(std::move(Key), ValueT(), TheBucket); 228aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer } 229aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 230aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer ValueT &operator[](KeyT &&Key) { 231da8b91a0731e34b97aadb0241ba6cefa4481cffaBenjamin Kramer return FindAndConstruct(std::move(Key)).second; 232aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer } 233aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer#endif 234aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 235bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// isPointerIntoBucketsArray - Return true if the specified pointer points 236bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// somewhere into the DenseMap's array of buckets (i.e. either to a key or 237bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// value in the DenseMap). 238bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner bool isPointerIntoBucketsArray(const void *Ptr) const { 2397f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return Ptr >= getBuckets() && Ptr < getBucketsEnd(); 240bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner } 241bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner 242bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets 243bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// array. In conjunction with the previous method, this can be used to 244bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// determine whether an insertion caused the DenseMap to reallocate. 2457f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth const void *getPointerIntoBucketsArray() const { return getBuckets(); } 246bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner 2477f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthprotected: 24848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth DenseMapBase() {} 2497f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 2507f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void destroyAll() { 2517f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth if (getNumBuckets() == 0) // Nothing to do. 2528e337120133c746640246feb9383556d383a94beBenjamin Kramer return; 2538e337120133c746640246feb9383556d383a94beBenjamin Kramer 254295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 2557f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) { 256295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer if (!KeyInfoT::isEqual(P->first, EmptyKey) && 257295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer !KeyInfoT::isEqual(P->first, TombstoneKey)) 258295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer P->second.~ValueT(); 259295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer P->first.~KeyT(); 26067280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson } 2613a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 262d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#ifndef NDEBUG 2637f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth memset((void*)getBuckets(), 0x5a, sizeof(BucketT)*getNumBuckets()); 264d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#endif 265295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer } 26688b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer 2677f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void initEmpty() { 26848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth setNumEntries(0); 26948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth setNumTombstones(0); 2707f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 2717f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth assert((getNumBuckets() & (getNumBuckets()-1)) == 0 && 2727f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth "# initial buckets must be a power of two!"); 2737f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth const KeyT EmptyKey = getEmptyKey(); 2747f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth for (BucketT *B = getBuckets(), *E = getBucketsEnd(); B != E; ++B) 2757f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth new (&B->first) KeyT(EmptyKey); 2767f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 277295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer 2787f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void moveFromOldBuckets(BucketT *OldBucketsBegin, BucketT *OldBucketsEnd) { 2797f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth initEmpty(); 28088b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer 2817f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth // Insert all the old elements. 2827f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth const KeyT EmptyKey = getEmptyKey(); 2837f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth const KeyT TombstoneKey = getTombstoneKey(); 2847f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth for (BucketT *B = OldBucketsBegin, *E = OldBucketsEnd; B != E; ++B) { 2857f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth if (!KeyInfoT::isEqual(B->first, EmptyKey) && 2867f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth !KeyInfoT::isEqual(B->first, TombstoneKey)) { 2877f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth // Insert the key/value into the new table. 2887f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth BucketT *DestBucket; 2897f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth bool FoundVal = LookupBucketFor(B->first, DestBucket); 2907f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth (void)FoundVal; // silence warning. 2917f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth assert(!FoundVal && "Key already in new map?"); 2927f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth DestBucket->first = llvm_move(B->first); 2937f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth new (&DestBucket->second) ValueT(llvm_move(B->second)); 29448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth incrementNumEntries(); 2957f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 2967f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth // Free the value. 2977f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth B->second.~ValueT(); 2987f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 2997f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth B->first.~KeyT(); 30088b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer } 30188b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer 3027f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth#ifndef NDEBUG 3037f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth if (OldBucketsBegin != OldBucketsEnd) 3047f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth memset((void*)OldBucketsBegin, 0x5a, 3057f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth sizeof(BucketT) * (OldBucketsEnd - OldBucketsBegin)); 3067f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth#endif 3077f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 3087f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 3097f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth template <typename OtherBaseT> 3107f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void copyFrom(const DenseMapBase<OtherBaseT, KeyT, ValueT, KeyInfoT>& other) { 3117f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth assert(getNumBuckets() == other.getNumBuckets()); 3127f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 31348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth setNumEntries(other.getNumEntries()); 31448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth setNumTombstones(other.getNumTombstones()); 3153a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3164e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer if (isPodLike<KeyT>::value && isPodLike<ValueT>::value) 3177f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth memcpy(getBuckets(), other.getBuckets(), 3187f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth getNumBuckets() * sizeof(BucketT)); 3199544dc294f63ce116fbab398a8874ebf834cf41eOwen Anderson else 3207f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth for (size_t i = 0; i < getNumBuckets(); ++i) { 3217f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth new (&getBuckets()[i].first) KeyT(other.getBuckets()[i].first); 3227f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth if (!KeyInfoT::isEqual(getBuckets()[i].first, getEmptyKey()) && 3237f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth !KeyInfoT::isEqual(getBuckets()[i].first, getTombstoneKey())) 3247f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth new (&getBuckets()[i].second) ValueT(other.getBuckets()[i].second); 3259544dc294f63ce116fbab398a8874ebf834cf41eOwen Anderson } 32667280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson } 3273a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3287f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void swap(DenseMapBase& RHS) { 32948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth std::swap(getNumEntries(), RHS.getNumEntries()); 33048f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth std::swap(getNumTombstones(), RHS.getNumTombstones()); 3317f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 3327f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 3337f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth static unsigned getHashValue(const KeyT &Val) { 3347f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return KeyInfoT::getHashValue(Val); 3357f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 3367f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth template<typename LookupKeyT> 3377f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth static unsigned getHashValue(const LookupKeyT &Val) { 3387f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return KeyInfoT::getHashValue(Val); 3397f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 3407f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth static const KeyT getEmptyKey() { 3417f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return KeyInfoT::getEmptyKey(); 3427f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 3437f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth static const KeyT getTombstoneKey() { 3447f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return KeyInfoT::getTombstoneKey(); 3457f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 3467f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 3476446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruthprivate: 34848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned getNumEntries() const { 34948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth return static_cast<const DerivedT *>(this)->getNumEntries(); 35048f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 35148f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth void setNumEntries(unsigned Num) { 35248f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth static_cast<DerivedT *>(this)->setNumEntries(Num); 35348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 35448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth void incrementNumEntries() { 35548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth setNumEntries(getNumEntries() + 1); 35648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 35748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth void decrementNumEntries() { 35848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth setNumEntries(getNumEntries() - 1); 35948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 36048f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned getNumTombstones() const { 36148f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth return static_cast<const DerivedT *>(this)->getNumTombstones(); 36248f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 36348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth void setNumTombstones(unsigned Num) { 36448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth static_cast<DerivedT *>(this)->setNumTombstones(Num); 36548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 36648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth void incrementNumTombstones() { 36748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth setNumTombstones(getNumTombstones() + 1); 36848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 36948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth void decrementNumTombstones() { 37048f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth setNumTombstones(getNumTombstones() - 1); 37148f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 372dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const BucketT *getBuckets() const { 3737f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return static_cast<const DerivedT *>(this)->getBuckets(); 3747f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 375dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth BucketT *getBuckets() { 376dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return static_cast<DerivedT *>(this)->getBuckets(); 377dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 3787f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth unsigned getNumBuckets() const { 3797f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return static_cast<const DerivedT *>(this)->getNumBuckets(); 3807f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 381dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth BucketT *getBucketsEnd() { 382dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return getBuckets() + getNumBuckets(); 383dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 384dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const BucketT *getBucketsEnd() const { 3857f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return getBuckets() + getNumBuckets(); 3867f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 3877f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 3887f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void grow(unsigned AtLeast) { 3897f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth static_cast<DerivedT *>(this)->grow(AtLeast); 3907f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 3917f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 3927f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void shrink_and_clear() { 3937f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth static_cast<DerivedT *>(this)->shrink_and_clear(); 3947f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 3957f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 3967f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 39728f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner BucketT *InsertIntoBucket(const KeyT &Key, const ValueT &Value, 39828f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner BucketT *TheBucket) { 399aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer TheBucket = InsertIntoBucketImpl(Key, TheBucket); 400aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 401aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer TheBucket->first = Key; 402aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer new (&TheBucket->second) ValueT(Value); 403aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer return TheBucket; 404aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer } 405aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 4064334dd96a9e622fdcf2825a8f73a2d941d67be72Chandler Carruth#if LLVM_HAS_RVALUE_REFERENCES 407aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer BucketT *InsertIntoBucket(const KeyT &Key, ValueT &&Value, 408aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer BucketT *TheBucket) { 409aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer TheBucket = InsertIntoBucketImpl(Key, TheBucket); 410aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 411aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer TheBucket->first = Key; 412aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer new (&TheBucket->second) ValueT(std::move(Value)); 413aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer return TheBucket; 414aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer } 415aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 416aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer BucketT *InsertIntoBucket(KeyT &&Key, ValueT &&Value, BucketT *TheBucket) { 417aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer TheBucket = InsertIntoBucketImpl(Key, TheBucket); 418aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 419aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer TheBucket->first = std::move(Key); 420aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer new (&TheBucket->second) ValueT(std::move(Value)); 421aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer return TheBucket; 422aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer } 423aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer#endif 424aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 425aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer BucketT *InsertIntoBucketImpl(const KeyT &Key, BucketT *TheBucket) { 42604a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // If the load of the hash table is more than 3/4, or if fewer than 1/8 of 42704a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // the buckets are empty (meaning that many are filled with tombstones), 42804a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // grow the table. 42904a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // 43004a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // The later case is tricky. For example, if we had one empty bucket with 43104a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // tons of tombstones, failing lookups (e.g. for insertion) would have to 43204a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // probe almost the entire table until it found the empty bucket. If the 43304a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // table completely filled with tombstones, no lookup would ever succeed, 43404a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // causing infinite loops in lookup. 43548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned NewNumEntries = getNumEntries() + 1; 436dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned NumBuckets = getNumBuckets(); 437dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (NewNumEntries*4 >= NumBuckets*3) { 438dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->grow(NumBuckets * 2); 43928f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner LookupBucketFor(Key, TheBucket); 440dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth NumBuckets = getNumBuckets(); 4416e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 442dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (NumBuckets-(NewNumEntries+getNumTombstones()) <= NumBuckets/8) { 4432430973fb657eb84dfbacb1e8886d3a29190e0b5Pete Cooper this->grow(NumBuckets * 2); 444414fdbdb0104fdc8c570287f94df8bb697e7b7c1Jakob Stoklund Olesen LookupBucketFor(Key, TheBucket); 445414fdbdb0104fdc8c570287f94df8bb697e7b7c1Jakob Stoklund Olesen } 4463bbdddf527c762085802544665d6e77471ea035bJordan Rose assert(TheBucket); 4473a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4487f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth // Only update the state after we've grown our bucket space appropriately 4497f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth // so that when growing buckets we have self-consistent entry count. 45048f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth incrementNumEntries(); 4517f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 45204a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // If we are writing over a tombstone, remember this. 4535d295b41a3f4194778b6bc01a828b2115bd3a3f1NAKAMURA Takumi const KeyT EmptyKey = getEmptyKey(); 4545d295b41a3f4194778b6bc01a828b2115bd3a3f1NAKAMURA Takumi if (!KeyInfoT::isEqual(TheBucket->first, EmptyKey)) 45548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth decrementNumTombstones(); 4563a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 45728f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner return TheBucket; 4586e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 45928f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner 4606e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in 4616e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// FoundBucket. If the bucket contains the key and a value, this returns 4626e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// true, otherwise it returns a bucket with an empty marker or tombstone and 4636e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// returns false. 464babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin template<typename LookupKeyT> 465dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth bool LookupBucketFor(const LookupKeyT &Val, 466dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const BucketT *&FoundBucket) const { 467dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const BucketT *BucketsPtr = getBuckets(); 468ce9a04132d1bf85967d6ad062d45dd75f148eef1Chandler Carruth const unsigned NumBuckets = getNumBuckets(); 4693a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 470ce9a04132d1bf85967d6ad062d45dd75f148eef1Chandler Carruth if (NumBuckets == 0) { 47149d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer FoundBucket = 0; 47249d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer return false; 47349d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer } 47449d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer 4756e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // FoundTombstone - Keep track of whether we find a tombstone while probing. 476dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const BucketT *FoundTombstone = 0; 4776e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(); 4786e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT TombstoneKey = getTombstoneKey(); 47905831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner assert(!KeyInfoT::isEqual(Val, EmptyKey) && 48005831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(Val, TombstoneKey) && 4816e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner "Empty/Tombstone value shouldn't be inserted into map!"); 4823a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 483ce9a04132d1bf85967d6ad062d45dd75f148eef1Chandler Carruth unsigned BucketNo = getHashValue(Val) & (NumBuckets-1); 484ce9a04132d1bf85967d6ad062d45dd75f148eef1Chandler Carruth unsigned ProbeAmt = 1; 4856e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner while (1) { 486ce9a04132d1bf85967d6ad062d45dd75f148eef1Chandler Carruth const BucketT *ThisBucket = BucketsPtr + BucketNo; 4876e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Found Val's bucket? If so, return it. 488babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin if (KeyInfoT::isEqual(Val, ThisBucket->first)) { 4896e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundBucket = ThisBucket; 4906e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return true; 4916e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 4923a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4936e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If we found an empty bucket, the key doesn't exist in the set. 4946e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Insert it and return the default value. 49576c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner if (KeyInfoT::isEqual(ThisBucket->first, EmptyKey)) { 4966e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If we've already seen a tombstone while probing, fill it in instead 4976e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // of the empty bucket we eventually probed to. 4986e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket; 4996e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return false; 5006e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 5013a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5026e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If this is a tombstone, remember it. If Val ends up not in the map, we 5036e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // prefer to return it than something that would require more probing. 50476c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner if (KeyInfoT::isEqual(ThisBucket->first, TombstoneKey) && !FoundTombstone) 5056e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundTombstone = ThisBucket; // Remember the first tombstone found. 5063a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5076e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Otherwise, it's a hash collision or a tombstone, continue quadratic 5086e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // probing. 5096e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketNo += ProbeAmt++; 510ce9a04132d1bf85967d6ad062d45dd75f148eef1Chandler Carruth BucketNo &= (NumBuckets-1); 5116e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 5126e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 5136e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 514dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth template <typename LookupKeyT> 515dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth bool LookupBucketFor(const LookupKeyT &Val, BucketT *&FoundBucket) { 51690420105964371571ccacdf47771c6ca05db2e67David Blaikie const BucketT *ConstFoundBucket; 517dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth bool Result = const_cast<const DenseMapBase *>(this) 518dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth ->LookupBucketFor(Val, ConstFoundBucket); 519dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth FoundBucket = const_cast<BucketT *>(ConstFoundBucket); 520dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return Result; 521dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 522dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 5237f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthpublic: 5247f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth /// Return the approximate size (in bytes) of the actual map. 5257f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth /// This is just the raw memory used by DenseMap. 5267f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth /// If entries are pointers to objects, the size of the referenced objects 5277f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth /// are not included. 5287f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth size_t getMemorySize() const { 5297f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return getNumBuckets() * sizeof(BucketT); 5307f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5317f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth}; 53249d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer 5337f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthtemplate<typename KeyT, typename ValueT, 5347f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth typename KeyInfoT = DenseMapInfo<KeyT> > 5357f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthclass DenseMap 5367f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT>, 5377f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth KeyT, ValueT, KeyInfoT> { 5387f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth // Lift some types from the dependent base class into this class for 5397f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth // simplicity of referring to them. 5407f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth typedef DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT> BaseT; 5417f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth typedef typename BaseT::BucketT BucketT; 5427f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth friend class DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT>; 54349d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer 5447f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth BucketT *Buckets; 54548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned NumEntries; 54648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned NumTombstones; 5477f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth unsigned NumBuckets; 5487f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 5497f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthpublic: 5507f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth explicit DenseMap(unsigned NumInitBuckets = 0) { 5517f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth init(NumInitBuckets); 5526e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 5533a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 554319120f6229dcf37f288be2719bc095a2f454d55Alex Rosenberg DenseMap(const DenseMap &other) : BaseT() { 5557f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth init(0); 5567f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth copyFrom(other); 5577f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5583a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5594334dd96a9e622fdcf2825a8f73a2d941d67be72Chandler Carruth#if LLVM_HAS_RVALUE_REFERENCES 560319120f6229dcf37f288be2719bc095a2f454d55Alex Rosenberg DenseMap(DenseMap &&other) : BaseT() { 5617f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth init(0); 5627f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth swap(other); 5637f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5647f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth#endif 56549d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer 5667f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth template<typename InputIt> 5677f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth DenseMap(const InputIt &I, const InputIt &E) { 5687f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth init(NextPowerOf2(std::distance(I, E))); 5697f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->insert(I, E); 5707f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5716e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 5727f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth ~DenseMap() { 5737f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->destroyAll(); 5747f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth operator delete(Buckets); 5757f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5766e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 5777f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void swap(DenseMap& RHS) { 5787f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth std::swap(Buckets, RHS.Buckets); 57948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth std::swap(NumEntries, RHS.NumEntries); 58048f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth std::swap(NumTombstones, RHS.NumTombstones); 58148f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth std::swap(NumBuckets, RHS.NumBuckets); 5827f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5833a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5847f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth DenseMap& operator=(const DenseMap& other) { 5857f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth copyFrom(other); 5867f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return *this; 5877f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5887f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 5894334dd96a9e622fdcf2825a8f73a2d941d67be72Chandler Carruth#if LLVM_HAS_RVALUE_REFERENCES 5907f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth DenseMap& operator=(DenseMap &&other) { 5917f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->destroyAll(); 5927f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth operator delete(Buckets); 5937f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth init(0); 5947f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth swap(other); 5957f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return *this; 5967f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 597d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#endif 5987f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 5997f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void copyFrom(const DenseMap& other) { 6007f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->destroyAll(); 6017f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth operator delete(Buckets); 60248f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth if (allocateBuckets(other.NumBuckets)) { 6037f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->BaseT::copyFrom(other); 60448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } else { 60548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth NumEntries = 0; 60648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth NumTombstones = 0; 60748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 6086e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 6093a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 6107f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void init(unsigned InitBuckets) { 61148f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth if (allocateBuckets(InitBuckets)) { 6127f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->BaseT::initEmpty(); 61348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } else { 61448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth NumEntries = 0; 61548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth NumTombstones = 0; 61648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 6177f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 6187f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 6197f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void grow(unsigned AtLeast) { 6206ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson unsigned OldNumBuckets = NumBuckets; 6216ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson BucketT *OldBuckets = Buckets; 6223a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 623711d324d50e5b335e98e576ce6725b056427e3f3Peng Cheng allocateBuckets(std::max<unsigned>(64, static_cast<unsigned>(NextPowerOf2(AtLeast-1)))); 6247f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth assert(Buckets); 6257f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth if (!OldBuckets) { 6267f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->BaseT::initEmpty(); 6277f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return; 6286ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 6293a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 6307f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->moveFromOldBuckets(OldBuckets, OldBuckets+OldNumBuckets); 6317f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 6326ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson // Free the old table. 63308c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman operator delete(OldBuckets); 6347f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 6353a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 6367f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void shrink_and_clear() { 63748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned OldNumEntries = NumEntries; 6387f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->destroyAll(); 6397f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 6407f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth // Reduce the number of buckets. 641b8ea08ca8c43016f5bc35e1a3b6557d414448faeRichard Smith unsigned NewNumBuckets = 0; 642b8ea08ca8c43016f5bc35e1a3b6557d414448faeRichard Smith if (OldNumEntries) 643b8ea08ca8c43016f5bc35e1a3b6557d414448faeRichard Smith NewNumBuckets = std::max(64, 1 << (Log2_32_Ceil(OldNumEntries) + 1)); 6447f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth if (NewNumBuckets == NumBuckets) { 6457f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->BaseT::initEmpty(); 6467f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return; 6477f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 6487f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 6497f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth operator delete(Buckets); 6507f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth init(NewNumBuckets); 6516ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 6527f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 6537f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthprivate: 65448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned getNumEntries() const { 65548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth return NumEntries; 65648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 65748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth void setNumEntries(unsigned Num) { 65848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth NumEntries = Num; 65948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 66048f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth 66148f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned getNumTombstones() const { 66248f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth return NumTombstones; 66348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 66448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth void setNumTombstones(unsigned Num) { 66548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth NumTombstones = Num; 66648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 66748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth 6687f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth BucketT *getBuckets() const { 6697f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return Buckets; 6707f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 6717f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 6727f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth unsigned getNumBuckets() const { 6737f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return NumBuckets; 6747f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 6757f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 6767f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth bool allocateBuckets(unsigned Num) { 6777f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth NumBuckets = Num; 6787f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth if (NumBuckets == 0) { 6797f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth Buckets = 0; 6807f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return false; 6817f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 6827f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 6837f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT) * NumBuckets)); 6847f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return true; 685e6b693db8cc07be91229bef0d8577ce8b5caf34bTed Kremenek } 6866e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner}; 6876e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 68881cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskintemplate<typename KeyT, typename ValueT, 689dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned InlineBuckets = 4, 690dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth typename KeyInfoT = DenseMapInfo<KeyT> > 691dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruthclass SmallDenseMap 692dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth : public DenseMapBase<SmallDenseMap<KeyT, ValueT, InlineBuckets, KeyInfoT>, 693dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth KeyT, ValueT, KeyInfoT> { 694dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // Lift some types from the dependent base class into this class for 695dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // simplicity of referring to them. 696dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth typedef DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT> BaseT; 697dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth typedef typename BaseT::BucketT BucketT; 698dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth friend class DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT>; 699dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 700dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned Small : 1; 701dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned NumEntries : 31; 702dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned NumTombstones; 703dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 704dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth struct LargeRep { 705dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth BucketT *Buckets; 706dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned NumBuckets; 707dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth }; 708dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 709dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth /// A "union" of an inline bucket array and the struct representing 710dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth /// a large bucket. This union will be discriminated by the 'Small' bit. 711cbeb8d9869aafec3c2c1ee0922f0a4d5bb4a916aChandler Carruth AlignedCharArrayUnion<BucketT[InlineBuckets], LargeRep> storage; 712dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 713dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruthpublic: 714dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth explicit SmallDenseMap(unsigned NumInitBuckets = 0) { 715dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth init(NumInitBuckets); 716dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 717dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 7184e31acb558a7f157244a11ae382c0138ee12d60bAaron Ballman SmallDenseMap(const SmallDenseMap &other) : BaseT() { 719dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth init(0); 720dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth copyFrom(other); 721dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 722dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 7234334dd96a9e622fdcf2825a8f73a2d941d67be72Chandler Carruth#if LLVM_HAS_RVALUE_REFERENCES 7244e31acb558a7f157244a11ae382c0138ee12d60bAaron Ballman SmallDenseMap(SmallDenseMap &&other) : BaseT() { 725dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth init(0); 726dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth swap(other); 727dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 728dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth#endif 729dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 730dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth template<typename InputIt> 731dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth SmallDenseMap(const InputIt &I, const InputIt &E) { 732dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth init(NextPowerOf2(std::distance(I, E))); 733dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->insert(I, E); 734dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 735dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 736dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth ~SmallDenseMap() { 737dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->destroyAll(); 738dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth deallocateBuckets(); 739dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 740dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 741dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth void swap(SmallDenseMap& RHS) { 7428dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth unsigned TmpNumEntries = RHS.NumEntries; 7438dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth RHS.NumEntries = NumEntries; 7448dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth NumEntries = TmpNumEntries; 745dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth std::swap(NumTombstones, RHS.NumTombstones); 7468dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth 7478dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth const KeyT EmptyKey = this->getEmptyKey(); 7488dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth const KeyT TombstoneKey = this->getTombstoneKey(); 749dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (Small && RHS.Small) { 7508dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth // If we're swapping inline bucket arrays, we have to cope with some of 7518dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth // the tricky bits of DenseMap's storage system: the buckets are not 7528dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth // fully initialized. Thus we swap every key, but we may have 7538dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth // a one-directional move of the value. 7548dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth for (unsigned i = 0, e = InlineBuckets; i != e; ++i) { 7558dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth BucketT *LHSB = &getInlineBuckets()[i], 7568dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth *RHSB = &RHS.getInlineBuckets()[i]; 7578dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth bool hasLHSValue = (!KeyInfoT::isEqual(LHSB->first, EmptyKey) && 7588dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth !KeyInfoT::isEqual(LHSB->first, TombstoneKey)); 7598dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth bool hasRHSValue = (!KeyInfoT::isEqual(RHSB->first, EmptyKey) && 7608dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth !KeyInfoT::isEqual(RHSB->first, TombstoneKey)); 7618dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth if (hasLHSValue && hasRHSValue) { 7628dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth // Swap together if we can... 7638dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth std::swap(*LHSB, *RHSB); 7648dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth continue; 7658dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth } 7668dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth // Swap separately and handle any assymetry. 7678dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth std::swap(LHSB->first, RHSB->first); 7688dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth if (hasLHSValue) { 7698dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth new (&RHSB->second) ValueT(llvm_move(LHSB->second)); 7708dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth LHSB->second.~ValueT(); 7718dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth } else if (hasRHSValue) { 7728dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth new (&LHSB->second) ValueT(llvm_move(RHSB->second)); 7738dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth RHSB->second.~ValueT(); 7748dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth } 7758dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth } 776dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return; 777dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 778dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (!Small && !RHS.Small) { 779dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth std::swap(getLargeRep()->Buckets, RHS.getLargeRep()->Buckets); 780dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth std::swap(getLargeRep()->NumBuckets, RHS.getLargeRep()->NumBuckets); 781dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return; 782dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 783dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 784dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth SmallDenseMap &SmallSide = Small ? *this : RHS; 785dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth SmallDenseMap &LargeSide = Small ? RHS : *this; 786dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 787dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // First stash the large side's rep and move the small side across. 788dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth LargeRep TmpRep = llvm_move(*LargeSide.getLargeRep()); 789dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth LargeSide.getLargeRep()->~LargeRep(); 790dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth LargeSide.Small = true; 791dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // This is similar to the standard move-from-old-buckets, but the bucket 7928dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth // count hasn't actually rotated in this case. So we have to carefully 793dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // move construct the keys and values into their new locations, but there 794dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // is no need to re-hash things. 795dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth for (unsigned i = 0, e = InlineBuckets; i != e; ++i) { 796dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth BucketT *NewB = &LargeSide.getInlineBuckets()[i], 797dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth *OldB = &SmallSide.getInlineBuckets()[i]; 798dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth new (&NewB->first) KeyT(llvm_move(OldB->first)); 7998dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth OldB->first.~KeyT(); 800dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (!KeyInfoT::isEqual(NewB->first, EmptyKey) && 801dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth !KeyInfoT::isEqual(NewB->first, TombstoneKey)) { 802dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth new (&NewB->second) ValueT(llvm_move(OldB->second)); 803dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth OldB->second.~ValueT(); 804dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 805dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 806dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 807dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // The hard part of moving the small buckets across is done, just move 808dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // the TmpRep into its new home. 809dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth SmallSide.Small = false; 810dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth new (SmallSide.getLargeRep()) LargeRep(llvm_move(TmpRep)); 811dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 812dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 813dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth SmallDenseMap& operator=(const SmallDenseMap& other) { 814dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth copyFrom(other); 815dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return *this; 816dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 817dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 8184334dd96a9e622fdcf2825a8f73a2d941d67be72Chandler Carruth#if LLVM_HAS_RVALUE_REFERENCES 819dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth SmallDenseMap& operator=(SmallDenseMap &&other) { 820dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->destroyAll(); 821dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth deallocateBuckets(); 822dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth init(0); 823dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth swap(other); 824dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return *this; 825dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 826dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth#endif 827dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 828dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth void copyFrom(const SmallDenseMap& other) { 829dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->destroyAll(); 830dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth deallocateBuckets(); 831dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth Small = true; 832dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (other.getNumBuckets() > InlineBuckets) { 833dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth Small = false; 834dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth allocateBuckets(other.getNumBuckets()); 835dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 836dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->BaseT::copyFrom(other); 837dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 838dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 839dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth void init(unsigned InitBuckets) { 840dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth Small = true; 841dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (InitBuckets > InlineBuckets) { 842dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth Small = false; 843dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth new (getLargeRep()) LargeRep(allocateBuckets(InitBuckets)); 844dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 845dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->BaseT::initEmpty(); 846dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 847dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 848dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth void grow(unsigned AtLeast) { 84999112c6b193c54409e2a3a5ea76c3759d5c1244cPete Cooper if (AtLeast >= InlineBuckets) 85099112c6b193c54409e2a3a5ea76c3759d5c1244cPete Cooper AtLeast = std::max<unsigned>(64, NextPowerOf2(AtLeast-1)); 851dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 852dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (Small) { 853fbaf206f470b5a6a54811547641ee41368a2cccdPete Cooper if (AtLeast < InlineBuckets) 854dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return; // Nothing to do. 855dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 8566446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth // First move the inline buckets into a temporary storage. 857cbeb8d9869aafec3c2c1ee0922f0a4d5bb4a916aChandler Carruth AlignedCharArrayUnion<BucketT[InlineBuckets]> TmpStorage; 8586446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth BucketT *TmpBegin = reinterpret_cast<BucketT *>(TmpStorage.buffer); 8596446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth BucketT *TmpEnd = TmpBegin; 8606446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth 8616446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth // Loop over the buckets, moving non-empty, non-tombstones into the 8626446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth // temporary storage. Have the loop move the TmpEnd forward as it goes. 8636446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth const KeyT EmptyKey = this->getEmptyKey(); 8646446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth const KeyT TombstoneKey = this->getTombstoneKey(); 8656446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth for (BucketT *P = getBuckets(), *E = P + InlineBuckets; P != E; ++P) { 8666446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth if (!KeyInfoT::isEqual(P->first, EmptyKey) && 8676446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth !KeyInfoT::isEqual(P->first, TombstoneKey)) { 868ac24e251014de60a16558fc0a1f2340c334d2aa8Benjamin Kramer assert(size_t(TmpEnd - TmpBegin) < InlineBuckets && 8696446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth "Too many inline buckets!"); 8706446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth new (&TmpEnd->first) KeyT(llvm_move(P->first)); 8716446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth new (&TmpEnd->second) ValueT(llvm_move(P->second)); 8726446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth ++TmpEnd; 8736446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth P->second.~ValueT(); 8746446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth } 8756446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth P->first.~KeyT(); 8766446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth } 8776446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth 8786446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth // Now make this map use the large rep, and move all the entries back 8796446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth // into it. 880dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth Small = false; 8816446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth new (getLargeRep()) LargeRep(allocateBuckets(AtLeast)); 8826446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth this->moveFromOldBuckets(TmpBegin, TmpEnd); 883dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return; 884dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 885dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 886dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth LargeRep OldRep = llvm_move(*getLargeRep()); 887dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth getLargeRep()->~LargeRep(); 888dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (AtLeast <= InlineBuckets) { 889dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth Small = true; 890dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } else { 891dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth new (getLargeRep()) LargeRep(allocateBuckets(AtLeast)); 892dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 893dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 894dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->moveFromOldBuckets(OldRep.Buckets, OldRep.Buckets+OldRep.NumBuckets); 895dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 896dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // Free the old table. 897dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth operator delete(OldRep.Buckets); 898dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 899dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 900dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth void shrink_and_clear() { 901dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned OldSize = this->size(); 902dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->destroyAll(); 903dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 904dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // Reduce the number of buckets. 905dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned NewNumBuckets = 0; 906dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (OldSize) { 907dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth NewNumBuckets = 1 << (Log2_32_Ceil(OldSize) + 1); 908dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (NewNumBuckets > InlineBuckets && NewNumBuckets < 64u) 909dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth NewNumBuckets = 64; 910dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 911dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if ((Small && NewNumBuckets <= InlineBuckets) || 912dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth (!Small && NewNumBuckets == getLargeRep()->NumBuckets)) { 913dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->BaseT::initEmpty(); 914dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return; 915dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 916dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 917dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth deallocateBuckets(); 918dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth init(NewNumBuckets); 919dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 920dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 921dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruthprivate: 922dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned getNumEntries() const { 923dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return NumEntries; 924dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 925dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth void setNumEntries(unsigned Num) { 926dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth assert(Num < INT_MAX && "Cannot support more than INT_MAX entries"); 927dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth NumEntries = Num; 928dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 929dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 930dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned getNumTombstones() const { 931dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return NumTombstones; 932dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 933dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth void setNumTombstones(unsigned Num) { 934dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth NumTombstones = Num; 935dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 936dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 937dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const BucketT *getInlineBuckets() const { 938dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth assert(Small); 939dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // Note that this cast does not violate aliasing rules as we assert that 940dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // the memory's dynamic type is the small, inline bucket buffer, and the 941dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // 'storage.buffer' static type is 'char *'. 942dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return reinterpret_cast<const BucketT *>(storage.buffer); 943dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 944dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth BucketT *getInlineBuckets() { 945dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return const_cast<BucketT *>( 946dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const_cast<const SmallDenseMap *>(this)->getInlineBuckets()); 947dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 948dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const LargeRep *getLargeRep() const { 949dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth assert(!Small); 950dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // Note, same rule about aliasing as with getInlineBuckets. 951dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return reinterpret_cast<const LargeRep *>(storage.buffer); 952dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 953dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth LargeRep *getLargeRep() { 954dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return const_cast<LargeRep *>( 955dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const_cast<const SmallDenseMap *>(this)->getLargeRep()); 956dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 957dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 958dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const BucketT *getBuckets() const { 959dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return Small ? getInlineBuckets() : getLargeRep()->Buckets; 960dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 961dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth BucketT *getBuckets() { 962dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return const_cast<BucketT *>( 963dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const_cast<const SmallDenseMap *>(this)->getBuckets()); 964dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 965dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned getNumBuckets() const { 966dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return Small ? InlineBuckets : getLargeRep()->NumBuckets; 967dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 968dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 969dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth void deallocateBuckets() { 970dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (Small) 971dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return; 972dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 973dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth operator delete(getLargeRep()->Buckets); 974dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth getLargeRep()->~LargeRep(); 975dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 976dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 977dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth LargeRep allocateBuckets(unsigned Num) { 978dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth assert(Num > InlineBuckets && "Must allocate more buckets than are inline"); 979dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth LargeRep Rep = { 980dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth static_cast<BucketT*>(operator new(sizeof(BucketT) * Num)), Num 981dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth }; 982dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return Rep; 983dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 984dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth}; 985dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 986dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruthtemplate<typename KeyT, typename ValueT, 9874e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer typename KeyInfoT, bool IsConst> 98881cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskinclass DenseMapIterator { 98981cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef std::pair<KeyT, ValueT> Bucket; 99081cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef DenseMapIterator<KeyT, ValueT, 9914e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer KeyInfoT, true> ConstIterator; 9924e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, true>; 99381cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskinpublic: 99481cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef ptrdiff_t difference_type; 99581cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef typename conditional<IsConst, const Bucket, Bucket>::type value_type; 99681cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef value_type *pointer; 99781cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef value_type &reference; 99881cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef std::forward_iterator_tag iterator_category; 99981cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskinprivate: 100081cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin pointer Ptr, End; 1001f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerpublic: 1002a9ad04191cb56c42944b17980b8b2bb2afe11ab2Dan Gohman DenseMapIterator() : Ptr(0), End(0) {} 100313e781ebe7a39e008dd5e5de78983e095e8a1d02David Greene 1004f0be7ca7e42915779175a9332c6baba18a2a840cBenjamin Kramer DenseMapIterator(pointer Pos, pointer E, bool NoAdvance = false) 1005f0be7ca7e42915779175a9332c6baba18a2a840cBenjamin Kramer : Ptr(Pos), End(E) { 1006f0be7ca7e42915779175a9332c6baba18a2a840cBenjamin Kramer if (!NoAdvance) AdvancePastEmptyBuckets(); 1007f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 10083a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 100981cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin // If IsConst is true this is a converting constructor from iterator to 101081cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin // const_iterator and the default copy constructor is used. 101181cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin // Otherwise this is a copy constructor for iterator. 101281cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin DenseMapIterator(const DenseMapIterator<KeyT, ValueT, 10134e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer KeyInfoT, false>& I) 101481cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin : Ptr(I.Ptr), End(I.End) {} 101581cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin 101681cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin reference operator*() const { 101781cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin return *Ptr; 1018f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 101981cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin pointer operator->() const { 102081cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin return Ptr; 1021f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 10223a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 102381cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin bool operator==(const ConstIterator &RHS) const { 102481cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin return Ptr == RHS.operator->(); 1025f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 102681cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin bool operator!=(const ConstIterator &RHS) const { 102781cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin return Ptr != RHS.operator->(); 1028f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 10293a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 10304ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin inline DenseMapIterator& operator++() { // Preincrement 1031f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner ++Ptr; 1032f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner AdvancePastEmptyBuckets(); 1033f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner return *this; 1034f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 10354ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin DenseMapIterator operator++(int) { // Postincrement 1036f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner DenseMapIterator tmp = *this; ++*this; return tmp; 1037f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 10383a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1039f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerprivate: 1040f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner void AdvancePastEmptyBuckets() { 1041a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner const KeyT Empty = KeyInfoT::getEmptyKey(); 1042a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner const KeyT Tombstone = KeyInfoT::getTombstoneKey(); 1043f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 10443a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman while (Ptr != End && 104576c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner (KeyInfoT::isEqual(Ptr->first, Empty) || 104676c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner KeyInfoT::isEqual(Ptr->first, Tombstone))) 1047f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner ++Ptr; 1048f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 1049f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner}; 1050255cd6f317f3a0bad6e7939ca5ce49b33c6676f9NAKAMURA Takumi 10514e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramertemplate<typename KeyT, typename ValueT, typename KeyInfoT> 105218dceba0bb5e38250535401ecc9d9737943d0657Ted Kremenekstatic inline size_t 10534e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramercapacity_in_bytes(const DenseMap<KeyT, ValueT, KeyInfoT> &X) { 105418dceba0bb5e38250535401ecc9d9737943d0657Ted Kremenek return X.getMemorySize(); 105518dceba0bb5e38250535401ecc9d9737943d0657Ted Kremenek} 1056f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 10576e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner} // end namespace llvm 10586e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 10596e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner#endif 1060