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 6748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth bool empty() const { return getNumEntries() == 0; } 6848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned size() const { return getNumEntries(); } 69d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin 70d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin /// Grow the densemap so that it has at least Size buckets. Does not shrink 7149d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer void resize(size_t Size) { 727f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth if (Size > getNumBuckets()) 7349d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer grow(Size); 7449d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer } 753a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 766e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner void clear() { 7748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth if (getNumEntries() == 0 && getNumTombstones() == 0) return; 78255cd6f317f3a0bad6e7939ca5ce49b33c6676f9NAKAMURA Takumi 7942e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner // If the capacity of the array is huge, and the # elements used is small, 8042e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner // shrink the array. 8148f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth if (getNumEntries() * 4 < getNumBuckets() && getNumBuckets() > 64) { 826ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson shrink_and_clear(); 836ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson return; 846ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 853a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 866e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 877f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) { 8805831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(P->first, EmptyKey)) { 8905831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(P->first, TombstoneKey)) { 907b54452c84e478ab4d49ac08759ca4ec1badf2b2Chris Lattner P->second.~ValueT(); 9148f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth decrementNumEntries(); 927b54452c84e478ab4d49ac08759ca4ec1badf2b2Chris Lattner } 93f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner P->first = EmptyKey; 946e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 956e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 9648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth assert(getNumEntries() == 0 && "Node count imbalance!"); 9748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth setNumTombstones(0); 986e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 996ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson 1006e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// count - Return true if the specified key is in the map. 1016e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner bool count(const KeyT &Val) const { 102dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const BucketT *TheBucket; 1036e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return LookupBucketFor(Val, TheBucket); 1046e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 1053a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 106569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner iterator find(const KeyT &Val) { 10770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner BucketT *TheBucket; 10870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner if (LookupBucketFor(Val, TheBucket)) 1097f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return iterator(TheBucket, getBucketsEnd(), true); 11070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return end(); 11170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 112569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner const_iterator find(const KeyT &Val) const { 113dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const BucketT *TheBucket; 114569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner if (LookupBucketFor(Val, TheBucket)) 1157f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return const_iterator(TheBucket, getBucketsEnd(), true); 116569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner return end(); 117569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner } 1183a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 119babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin /// Alternate version of find() which allows a different, and possibly 120babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin /// less expensive, key type. 121babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin /// The DenseMapInfo is responsible for supplying methods 122babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key 123babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin /// type used. 124babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin template<class LookupKeyT> 125babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin iterator find_as(const LookupKeyT &Val) { 126babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin BucketT *TheBucket; 127babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin if (LookupBucketFor(Val, TheBucket)) 1287f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return iterator(TheBucket, getBucketsEnd(), true); 129babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin return end(); 130babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin } 131babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin template<class LookupKeyT> 132babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin const_iterator find_as(const LookupKeyT &Val) const { 133dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const BucketT *TheBucket; 134babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin if (LookupBucketFor(Val, TheBucket)) 1357f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return const_iterator(TheBucket, getBucketsEnd(), true); 136babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin return end(); 137babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin } 138babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin 1397b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar /// lookup - Return the entry for the specified key, or a default 1407b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar /// constructed value if no such entry exists. 1417b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar ValueT lookup(const KeyT &Val) const { 142dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const BucketT *TheBucket; 1437b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar if (LookupBucketFor(Val, TheBucket)) 1447b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar return TheBucket->second; 1457b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar return ValueT(); 1467b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar } 1477b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar 148127445818efd810b138dd5362129ab3c7f8b9963Torok Edwin // Inserts key,value pair into the map if the key isn't already in the map. 149127445818efd810b138dd5362129ab3c7f8b9963Torok Edwin // If the key is already in the map, it returns false and doesn't update the 150127445818efd810b138dd5362129ab3c7f8b9963Torok Edwin // value. 1516b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) { 15228f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner BucketT *TheBucket; 15328f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner if (LookupBucketFor(KV.first, TheBucket)) 1547f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), 1556b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman false); // Already in map. 1563a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 15728f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner // Otherwise, insert the new element. 1586b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman TheBucket = InsertIntoBucket(KV.first, KV.second, TheBucket); 1597f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), true); 16028f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner } 1613a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 162289148afcb68b28e155ee87aa5a9efcf75adb444Joe Groff#if LLVM_HAS_RVALUE_REFERENCES 163a662a9862501fc86904e90054f7c1519101d9126Joe Groff // Inserts key,value pair into the map if the key isn't already in the map. 164a662a9862501fc86904e90054f7c1519101d9126Joe Groff // If the key is already in the map, it returns false and doesn't update the 165a662a9862501fc86904e90054f7c1519101d9126Joe Groff // value. 166a662a9862501fc86904e90054f7c1519101d9126Joe Groff std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) { 167a662a9862501fc86904e90054f7c1519101d9126Joe Groff BucketT *TheBucket; 168a662a9862501fc86904e90054f7c1519101d9126Joe Groff if (LookupBucketFor(KV.first, TheBucket)) 169a662a9862501fc86904e90054f7c1519101d9126Joe Groff return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), 170a662a9862501fc86904e90054f7c1519101d9126Joe Groff false); // Already in map. 171a662a9862501fc86904e90054f7c1519101d9126Joe Groff 172a662a9862501fc86904e90054f7c1519101d9126Joe Groff // Otherwise, insert the new element. 173a662a9862501fc86904e90054f7c1519101d9126Joe Groff TheBucket = InsertIntoBucket(std::move(KV.first), 174a662a9862501fc86904e90054f7c1519101d9126Joe Groff std::move(KV.second), 175a662a9862501fc86904e90054f7c1519101d9126Joe Groff TheBucket); 176a662a9862501fc86904e90054f7c1519101d9126Joe Groff return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), true); 177a662a9862501fc86904e90054f7c1519101d9126Joe Groff } 178a662a9862501fc86904e90054f7c1519101d9126Joe Groff#endif 179a662a9862501fc86904e90054f7c1519101d9126Joe Groff 180b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner /// insert - Range insertion of pairs. 181b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner template<typename InputIt> 182b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner void insert(InputIt I, InputIt E) { 183b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner for (; I != E; ++I) 184b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner insert(*I); 185b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner } 186b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner 1873a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 18870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner bool erase(const KeyT &Val) { 18970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner BucketT *TheBucket; 19070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner if (!LookupBucketFor(Val, TheBucket)) 19170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return false; // not in map. 19270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner 19370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->second.~ValueT(); 19470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->first = getTombstoneKey(); 19548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth decrementNumEntries(); 19648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth incrementNumTombstones(); 19770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return true; 19870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 199e3955df639ff9aff990f628ef6a219ff5efdbc81Dan Gohman void erase(iterator I) { 20070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner BucketT *TheBucket = &*I; 20170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->second.~ValueT(); 20270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->first = getTombstoneKey(); 20348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth decrementNumEntries(); 20448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth incrementNumTombstones(); 20570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 206aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek 207aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek value_type& FindAndConstruct(const KeyT &Key) { 2086e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *TheBucket; 20928f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner if (LookupBucketFor(Key, TheBucket)) 210aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek return *TheBucket; 2113a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 212aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek return *InsertIntoBucket(Key, ValueT(), TheBucket); 213aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek } 2143a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 215aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek ValueT &operator[](const KeyT &Key) { 216aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek return FindAndConstruct(Key).second; 21728f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner } 2183a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2194334dd96a9e622fdcf2825a8f73a2d941d67be72Chandler Carruth#if LLVM_HAS_RVALUE_REFERENCES 220aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer value_type& FindAndConstruct(KeyT &&Key) { 221aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer BucketT *TheBucket; 222aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer if (LookupBucketFor(Key, TheBucket)) 223aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer return *TheBucket; 224aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 225da8b91a0731e34b97aadb0241ba6cefa4481cffaBenjamin Kramer return *InsertIntoBucket(std::move(Key), ValueT(), TheBucket); 226aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer } 227aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 228aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer ValueT &operator[](KeyT &&Key) { 229da8b91a0731e34b97aadb0241ba6cefa4481cffaBenjamin Kramer return FindAndConstruct(std::move(Key)).second; 230aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer } 231aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer#endif 232aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 233bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// isPointerIntoBucketsArray - Return true if the specified pointer points 234bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// somewhere into the DenseMap's array of buckets (i.e. either to a key or 235bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// value in the DenseMap). 236bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner bool isPointerIntoBucketsArray(const void *Ptr) const { 2377f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return Ptr >= getBuckets() && Ptr < getBucketsEnd(); 238bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner } 239bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner 240bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets 241bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// array. In conjunction with the previous method, this can be used to 242bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// determine whether an insertion caused the DenseMap to reallocate. 2437f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth const void *getPointerIntoBucketsArray() const { return getBuckets(); } 244bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner 2457f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthprotected: 24648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth DenseMapBase() {} 2477f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 2487f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void destroyAll() { 2497f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth if (getNumBuckets() == 0) // Nothing to do. 2508e337120133c746640246feb9383556d383a94beBenjamin Kramer return; 2518e337120133c746640246feb9383556d383a94beBenjamin Kramer 252295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 2537f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) { 254295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer if (!KeyInfoT::isEqual(P->first, EmptyKey) && 255295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer !KeyInfoT::isEqual(P->first, TombstoneKey)) 256295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer P->second.~ValueT(); 257295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer P->first.~KeyT(); 25867280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson } 2593a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 260d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#ifndef NDEBUG 2617f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth memset((void*)getBuckets(), 0x5a, sizeof(BucketT)*getNumBuckets()); 262d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#endif 263295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer } 26488b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer 2657f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void initEmpty() { 26648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth setNumEntries(0); 26748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth setNumTombstones(0); 2687f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 2697f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth assert((getNumBuckets() & (getNumBuckets()-1)) == 0 && 2707f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth "# initial buckets must be a power of two!"); 2717f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth const KeyT EmptyKey = getEmptyKey(); 2727f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth for (BucketT *B = getBuckets(), *E = getBucketsEnd(); B != E; ++B) 2737f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth new (&B->first) KeyT(EmptyKey); 2747f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 275295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer 2767f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void moveFromOldBuckets(BucketT *OldBucketsBegin, BucketT *OldBucketsEnd) { 2777f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth initEmpty(); 27888b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer 2797f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth // Insert all the old elements. 2807f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth const KeyT EmptyKey = getEmptyKey(); 2817f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth const KeyT TombstoneKey = getTombstoneKey(); 2827f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth for (BucketT *B = OldBucketsBegin, *E = OldBucketsEnd; B != E; ++B) { 2837f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth if (!KeyInfoT::isEqual(B->first, EmptyKey) && 2847f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth !KeyInfoT::isEqual(B->first, TombstoneKey)) { 2857f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth // Insert the key/value into the new table. 2867f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth BucketT *DestBucket; 2877f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth bool FoundVal = LookupBucketFor(B->first, DestBucket); 2887f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth (void)FoundVal; // silence warning. 2897f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth assert(!FoundVal && "Key already in new map?"); 2907f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth DestBucket->first = llvm_move(B->first); 2917f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth new (&DestBucket->second) ValueT(llvm_move(B->second)); 29248f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth incrementNumEntries(); 2937f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 2947f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth // Free the value. 2957f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth B->second.~ValueT(); 2967f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 2977f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth B->first.~KeyT(); 29888b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer } 29988b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer 3007f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth#ifndef NDEBUG 3017f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth if (OldBucketsBegin != OldBucketsEnd) 3027f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth memset((void*)OldBucketsBegin, 0x5a, 3037f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth sizeof(BucketT) * (OldBucketsEnd - OldBucketsBegin)); 3047f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth#endif 3057f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 3067f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 3077f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth template <typename OtherBaseT> 3087f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void copyFrom(const DenseMapBase<OtherBaseT, KeyT, ValueT, KeyInfoT>& other) { 3097f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth assert(getNumBuckets() == other.getNumBuckets()); 3107f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 31148f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth setNumEntries(other.getNumEntries()); 31248f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth setNumTombstones(other.getNumTombstones()); 3133a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3144e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer if (isPodLike<KeyT>::value && isPodLike<ValueT>::value) 3157f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth memcpy(getBuckets(), other.getBuckets(), 3167f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth getNumBuckets() * sizeof(BucketT)); 3179544dc294f63ce116fbab398a8874ebf834cf41eOwen Anderson else 3187f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth for (size_t i = 0; i < getNumBuckets(); ++i) { 3197f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth new (&getBuckets()[i].first) KeyT(other.getBuckets()[i].first); 3207f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth if (!KeyInfoT::isEqual(getBuckets()[i].first, getEmptyKey()) && 3217f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth !KeyInfoT::isEqual(getBuckets()[i].first, getTombstoneKey())) 3227f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth new (&getBuckets()[i].second) ValueT(other.getBuckets()[i].second); 3239544dc294f63ce116fbab398a8874ebf834cf41eOwen Anderson } 32467280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson } 3253a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3267f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void swap(DenseMapBase& RHS) { 32748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth std::swap(getNumEntries(), RHS.getNumEntries()); 32848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth std::swap(getNumTombstones(), RHS.getNumTombstones()); 3297f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 3307f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 3317f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth static unsigned getHashValue(const KeyT &Val) { 3327f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return KeyInfoT::getHashValue(Val); 3337f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 3347f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth template<typename LookupKeyT> 3357f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth static unsigned getHashValue(const LookupKeyT &Val) { 3367f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return KeyInfoT::getHashValue(Val); 3377f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 3387f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth static const KeyT getEmptyKey() { 3397f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return KeyInfoT::getEmptyKey(); 3407f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 3417f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth static const KeyT getTombstoneKey() { 3427f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return KeyInfoT::getTombstoneKey(); 3437f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 3447f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 3456446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruthprivate: 34648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned getNumEntries() const { 34748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth return static_cast<const DerivedT *>(this)->getNumEntries(); 34848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 34948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth void setNumEntries(unsigned Num) { 35048f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth static_cast<DerivedT *>(this)->setNumEntries(Num); 35148f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 35248f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth void incrementNumEntries() { 35348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth setNumEntries(getNumEntries() + 1); 35448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 35548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth void decrementNumEntries() { 35648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth setNumEntries(getNumEntries() - 1); 35748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 35848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned getNumTombstones() const { 35948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth return static_cast<const DerivedT *>(this)->getNumTombstones(); 36048f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 36148f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth void setNumTombstones(unsigned Num) { 36248f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth static_cast<DerivedT *>(this)->setNumTombstones(Num); 36348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 36448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth void incrementNumTombstones() { 36548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth setNumTombstones(getNumTombstones() + 1); 36648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 36748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth void decrementNumTombstones() { 36848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth setNumTombstones(getNumTombstones() - 1); 36948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 370dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const BucketT *getBuckets() const { 3717f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return static_cast<const DerivedT *>(this)->getBuckets(); 3727f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 373dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth BucketT *getBuckets() { 374dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return static_cast<DerivedT *>(this)->getBuckets(); 375dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 3767f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth unsigned getNumBuckets() const { 3777f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return static_cast<const DerivedT *>(this)->getNumBuckets(); 3787f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 379dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth BucketT *getBucketsEnd() { 380dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return getBuckets() + getNumBuckets(); 381dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 382dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const BucketT *getBucketsEnd() const { 3837f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return getBuckets() + getNumBuckets(); 3847f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 3857f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 3867f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void grow(unsigned AtLeast) { 3877f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth static_cast<DerivedT *>(this)->grow(AtLeast); 3887f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 3897f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 3907f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void shrink_and_clear() { 3917f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth static_cast<DerivedT *>(this)->shrink_and_clear(); 3927f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 3937f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 3947f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 39528f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner BucketT *InsertIntoBucket(const KeyT &Key, const ValueT &Value, 39628f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner BucketT *TheBucket) { 397aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer TheBucket = InsertIntoBucketImpl(Key, TheBucket); 398aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 399aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer TheBucket->first = Key; 400aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer new (&TheBucket->second) ValueT(Value); 401aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer return TheBucket; 402aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer } 403aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 4044334dd96a9e622fdcf2825a8f73a2d941d67be72Chandler Carruth#if LLVM_HAS_RVALUE_REFERENCES 405aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer BucketT *InsertIntoBucket(const KeyT &Key, ValueT &&Value, 406aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer BucketT *TheBucket) { 407aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer TheBucket = InsertIntoBucketImpl(Key, TheBucket); 408aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 409aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer TheBucket->first = Key; 410aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer new (&TheBucket->second) ValueT(std::move(Value)); 411aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer return TheBucket; 412aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer } 413aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 414aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer BucketT *InsertIntoBucket(KeyT &&Key, ValueT &&Value, BucketT *TheBucket) { 415aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer TheBucket = InsertIntoBucketImpl(Key, TheBucket); 416aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 417aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer TheBucket->first = std::move(Key); 418aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer new (&TheBucket->second) ValueT(std::move(Value)); 419aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer return TheBucket; 420aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer } 421aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer#endif 422aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 423aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer BucketT *InsertIntoBucketImpl(const KeyT &Key, BucketT *TheBucket) { 42404a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // If the load of the hash table is more than 3/4, or if fewer than 1/8 of 42504a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // the buckets are empty (meaning that many are filled with tombstones), 42604a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // grow the table. 42704a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // 42804a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // The later case is tricky. For example, if we had one empty bucket with 42904a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // tons of tombstones, failing lookups (e.g. for insertion) would have to 43004a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // probe almost the entire table until it found the empty bucket. If the 43104a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // table completely filled with tombstones, no lookup would ever succeed, 43204a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // causing infinite loops in lookup. 43348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned NewNumEntries = getNumEntries() + 1; 434dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned NumBuckets = getNumBuckets(); 435dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (NewNumEntries*4 >= NumBuckets*3) { 436dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->grow(NumBuckets * 2); 43728f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner LookupBucketFor(Key, TheBucket); 438dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth NumBuckets = getNumBuckets(); 4396e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 440dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (NumBuckets-(NewNumEntries+getNumTombstones()) <= NumBuckets/8) { 4412430973fb657eb84dfbacb1e8886d3a29190e0b5Pete Cooper this->grow(NumBuckets * 2); 442414fdbdb0104fdc8c570287f94df8bb697e7b7c1Jakob Stoklund Olesen LookupBucketFor(Key, TheBucket); 443414fdbdb0104fdc8c570287f94df8bb697e7b7c1Jakob Stoklund Olesen } 4443bbdddf527c762085802544665d6e77471ea035bJordan Rose assert(TheBucket); 4453a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4467f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth // Only update the state after we've grown our bucket space appropriately 4477f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth // so that when growing buckets we have self-consistent entry count. 44848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth incrementNumEntries(); 4497f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 45004a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // If we are writing over a tombstone, remember this. 4515d295b41a3f4194778b6bc01a828b2115bd3a3f1NAKAMURA Takumi const KeyT EmptyKey = getEmptyKey(); 4525d295b41a3f4194778b6bc01a828b2115bd3a3f1NAKAMURA Takumi if (!KeyInfoT::isEqual(TheBucket->first, EmptyKey)) 45348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth decrementNumTombstones(); 4543a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 45528f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner return TheBucket; 4566e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 45728f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner 4586e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in 4596e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// FoundBucket. If the bucket contains the key and a value, this returns 4606e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// true, otherwise it returns a bucket with an empty marker or tombstone and 4616e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// returns false. 462babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin template<typename LookupKeyT> 463dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth bool LookupBucketFor(const LookupKeyT &Val, 464dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const BucketT *&FoundBucket) const { 465dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const BucketT *BucketsPtr = getBuckets(); 466ce9a04132d1bf85967d6ad062d45dd75f148eef1Chandler Carruth const unsigned NumBuckets = getNumBuckets(); 4673a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 468ce9a04132d1bf85967d6ad062d45dd75f148eef1Chandler Carruth if (NumBuckets == 0) { 46949d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer FoundBucket = 0; 47049d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer return false; 47149d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer } 47249d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer 4736e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // FoundTombstone - Keep track of whether we find a tombstone while probing. 474dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const BucketT *FoundTombstone = 0; 4756e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(); 4766e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT TombstoneKey = getTombstoneKey(); 47705831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner assert(!KeyInfoT::isEqual(Val, EmptyKey) && 47805831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(Val, TombstoneKey) && 4796e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner "Empty/Tombstone value shouldn't be inserted into map!"); 4803a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 481ce9a04132d1bf85967d6ad062d45dd75f148eef1Chandler Carruth unsigned BucketNo = getHashValue(Val) & (NumBuckets-1); 482ce9a04132d1bf85967d6ad062d45dd75f148eef1Chandler Carruth unsigned ProbeAmt = 1; 4836e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner while (1) { 484ce9a04132d1bf85967d6ad062d45dd75f148eef1Chandler Carruth const BucketT *ThisBucket = BucketsPtr + BucketNo; 4856e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Found Val's bucket? If so, return it. 486babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin if (KeyInfoT::isEqual(Val, ThisBucket->first)) { 4876e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundBucket = ThisBucket; 4886e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return true; 4896e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 4903a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4916e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If we found an empty bucket, the key doesn't exist in the set. 4926e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Insert it and return the default value. 49376c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner if (KeyInfoT::isEqual(ThisBucket->first, EmptyKey)) { 4946e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If we've already seen a tombstone while probing, fill it in instead 4956e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // of the empty bucket we eventually probed to. 4966e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket; 4976e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return false; 4986e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 4993a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5006e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If this is a tombstone, remember it. If Val ends up not in the map, we 5016e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // prefer to return it than something that would require more probing. 50276c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner if (KeyInfoT::isEqual(ThisBucket->first, TombstoneKey) && !FoundTombstone) 5036e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundTombstone = ThisBucket; // Remember the first tombstone found. 5043a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5056e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Otherwise, it's a hash collision or a tombstone, continue quadratic 5066e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // probing. 5076e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketNo += ProbeAmt++; 508ce9a04132d1bf85967d6ad062d45dd75f148eef1Chandler Carruth BucketNo &= (NumBuckets-1); 5096e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 5106e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 5116e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 512dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth template <typename LookupKeyT> 513dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth bool LookupBucketFor(const LookupKeyT &Val, BucketT *&FoundBucket) { 51490420105964371571ccacdf47771c6ca05db2e67David Blaikie const BucketT *ConstFoundBucket; 515dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth bool Result = const_cast<const DenseMapBase *>(this) 516dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth ->LookupBucketFor(Val, ConstFoundBucket); 517dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth FoundBucket = const_cast<BucketT *>(ConstFoundBucket); 518dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return Result; 519dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 520dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 5217f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthpublic: 5227f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth /// Return the approximate size (in bytes) of the actual map. 5237f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth /// This is just the raw memory used by DenseMap. 5247f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth /// If entries are pointers to objects, the size of the referenced objects 5257f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth /// are not included. 5267f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth size_t getMemorySize() const { 5277f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return getNumBuckets() * sizeof(BucketT); 5287f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5297f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth}; 53049d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer 5317f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthtemplate<typename KeyT, typename ValueT, 5327f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth typename KeyInfoT = DenseMapInfo<KeyT> > 5337f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthclass DenseMap 5347f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT>, 5357f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth KeyT, ValueT, KeyInfoT> { 5367f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth // Lift some types from the dependent base class into this class for 5377f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth // simplicity of referring to them. 5387f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth typedef DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT> BaseT; 5397f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth typedef typename BaseT::BucketT BucketT; 5407f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth friend class DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT>; 54149d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer 5427f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth BucketT *Buckets; 54348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned NumEntries; 54448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned NumTombstones; 5457f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth unsigned NumBuckets; 5467f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 5477f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthpublic: 5487f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth explicit DenseMap(unsigned NumInitBuckets = 0) { 5497f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth init(NumInitBuckets); 5506e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 5513a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 552319120f6229dcf37f288be2719bc095a2f454d55Alex Rosenberg DenseMap(const DenseMap &other) : BaseT() { 5537f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth init(0); 5547f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth copyFrom(other); 5557f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5563a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5574334dd96a9e622fdcf2825a8f73a2d941d67be72Chandler Carruth#if LLVM_HAS_RVALUE_REFERENCES 558319120f6229dcf37f288be2719bc095a2f454d55Alex Rosenberg DenseMap(DenseMap &&other) : BaseT() { 5597f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth init(0); 5607f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth swap(other); 5617f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5627f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth#endif 56349d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer 5647f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth template<typename InputIt> 5657f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth DenseMap(const InputIt &I, const InputIt &E) { 5667f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth init(NextPowerOf2(std::distance(I, E))); 5677f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->insert(I, E); 5687f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5696e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 5707f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth ~DenseMap() { 5717f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->destroyAll(); 5727f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth operator delete(Buckets); 5737f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5746e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 5757f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void swap(DenseMap& RHS) { 5767f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth std::swap(Buckets, RHS.Buckets); 57748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth std::swap(NumEntries, RHS.NumEntries); 57848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth std::swap(NumTombstones, RHS.NumTombstones); 57948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth std::swap(NumBuckets, RHS.NumBuckets); 5807f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5813a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5827f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth DenseMap& operator=(const DenseMap& other) { 5837f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth copyFrom(other); 5847f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return *this; 5857f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5867f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 5874334dd96a9e622fdcf2825a8f73a2d941d67be72Chandler Carruth#if LLVM_HAS_RVALUE_REFERENCES 5887f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth DenseMap& operator=(DenseMap &&other) { 5897f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->destroyAll(); 5907f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth operator delete(Buckets); 5917f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth init(0); 5927f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth swap(other); 5937f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return *this; 5947f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 595d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#endif 5967f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 5977f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void copyFrom(const DenseMap& other) { 5987f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->destroyAll(); 5997f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth operator delete(Buckets); 60048f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth if (allocateBuckets(other.NumBuckets)) { 6017f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->BaseT::copyFrom(other); 60248f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } else { 60348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth NumEntries = 0; 60448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth NumTombstones = 0; 60548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 6066e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 6073a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 6087f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void init(unsigned InitBuckets) { 60948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth if (allocateBuckets(InitBuckets)) { 6107f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->BaseT::initEmpty(); 61148f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } else { 61248f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth NumEntries = 0; 61348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth NumTombstones = 0; 61448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 6157f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 6167f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 6177f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void grow(unsigned AtLeast) { 6186ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson unsigned OldNumBuckets = NumBuckets; 6196ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson BucketT *OldBuckets = Buckets; 6203a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 621711d324d50e5b335e98e576ce6725b056427e3f3Peng Cheng allocateBuckets(std::max<unsigned>(64, static_cast<unsigned>(NextPowerOf2(AtLeast-1)))); 6227f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth assert(Buckets); 6237f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth if (!OldBuckets) { 6247f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->BaseT::initEmpty(); 6257f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return; 6266ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 6273a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 6287f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->moveFromOldBuckets(OldBuckets, OldBuckets+OldNumBuckets); 6297f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 6306ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson // Free the old table. 63108c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman operator delete(OldBuckets); 6327f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 6333a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 6347f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void shrink_and_clear() { 63548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned OldNumEntries = NumEntries; 6367f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->destroyAll(); 6377f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 6387f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth // Reduce the number of buckets. 639b8ea08ca8c43016f5bc35e1a3b6557d414448faeRichard Smith unsigned NewNumBuckets = 0; 640b8ea08ca8c43016f5bc35e1a3b6557d414448faeRichard Smith if (OldNumEntries) 641b8ea08ca8c43016f5bc35e1a3b6557d414448faeRichard Smith NewNumBuckets = std::max(64, 1 << (Log2_32_Ceil(OldNumEntries) + 1)); 6427f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth if (NewNumBuckets == NumBuckets) { 6437f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->BaseT::initEmpty(); 6447f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return; 6457f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 6467f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 6477f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth operator delete(Buckets); 6487f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth init(NewNumBuckets); 6496ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 6507f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 6517f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthprivate: 65248f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned getNumEntries() const { 65348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth return NumEntries; 65448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 65548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth void setNumEntries(unsigned Num) { 65648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth NumEntries = Num; 65748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 65848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth 65948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned getNumTombstones() const { 66048f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth return NumTombstones; 66148f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 66248f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth void setNumTombstones(unsigned Num) { 66348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth NumTombstones = Num; 66448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 66548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth 6667f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth BucketT *getBuckets() const { 6677f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return Buckets; 6687f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 6697f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 6707f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth unsigned getNumBuckets() const { 6717f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return NumBuckets; 6727f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 6737f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 6747f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth bool allocateBuckets(unsigned Num) { 6757f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth NumBuckets = Num; 6767f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth if (NumBuckets == 0) { 6777f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth Buckets = 0; 6787f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return false; 6797f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 6807f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 6817f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT) * NumBuckets)); 6827f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return true; 683e6b693db8cc07be91229bef0d8577ce8b5caf34bTed Kremenek } 6846e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner}; 6856e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 68681cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskintemplate<typename KeyT, typename ValueT, 687dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned InlineBuckets = 4, 688dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth typename KeyInfoT = DenseMapInfo<KeyT> > 689dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruthclass SmallDenseMap 690dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth : public DenseMapBase<SmallDenseMap<KeyT, ValueT, InlineBuckets, KeyInfoT>, 691dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth KeyT, ValueT, KeyInfoT> { 692dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // Lift some types from the dependent base class into this class for 693dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // simplicity of referring to them. 694dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth typedef DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT> BaseT; 695dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth typedef typename BaseT::BucketT BucketT; 696dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth friend class DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT>; 697dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 698dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned Small : 1; 699dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned NumEntries : 31; 700dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned NumTombstones; 701dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 702dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth struct LargeRep { 703dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth BucketT *Buckets; 704dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned NumBuckets; 705dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth }; 706dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 707dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth /// A "union" of an inline bucket array and the struct representing 708dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth /// a large bucket. This union will be discriminated by the 'Small' bit. 709cbeb8d9869aafec3c2c1ee0922f0a4d5bb4a916aChandler Carruth AlignedCharArrayUnion<BucketT[InlineBuckets], LargeRep> storage; 710dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 711dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruthpublic: 712dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth explicit SmallDenseMap(unsigned NumInitBuckets = 0) { 713dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth init(NumInitBuckets); 714dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 715dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 716dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth SmallDenseMap(const SmallDenseMap &other) { 717dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth init(0); 718dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth copyFrom(other); 719dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 720dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 7214334dd96a9e622fdcf2825a8f73a2d941d67be72Chandler Carruth#if LLVM_HAS_RVALUE_REFERENCES 722dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth SmallDenseMap(SmallDenseMap &&other) { 723dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth init(0); 724dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth swap(other); 725dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 726dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth#endif 727dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 728dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth template<typename InputIt> 729dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth SmallDenseMap(const InputIt &I, const InputIt &E) { 730dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth init(NextPowerOf2(std::distance(I, E))); 731dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->insert(I, E); 732dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 733dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 734dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth ~SmallDenseMap() { 735dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->destroyAll(); 736dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth deallocateBuckets(); 737dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 738dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 739dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth void swap(SmallDenseMap& RHS) { 7408dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth unsigned TmpNumEntries = RHS.NumEntries; 7418dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth RHS.NumEntries = NumEntries; 7428dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth NumEntries = TmpNumEntries; 743dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth std::swap(NumTombstones, RHS.NumTombstones); 7448dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth 7458dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth const KeyT EmptyKey = this->getEmptyKey(); 7468dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth const KeyT TombstoneKey = this->getTombstoneKey(); 747dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (Small && RHS.Small) { 7488dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth // If we're swapping inline bucket arrays, we have to cope with some of 7498dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth // the tricky bits of DenseMap's storage system: the buckets are not 7508dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth // fully initialized. Thus we swap every key, but we may have 7518dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth // a one-directional move of the value. 7528dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth for (unsigned i = 0, e = InlineBuckets; i != e; ++i) { 7538dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth BucketT *LHSB = &getInlineBuckets()[i], 7548dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth *RHSB = &RHS.getInlineBuckets()[i]; 7558dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth bool hasLHSValue = (!KeyInfoT::isEqual(LHSB->first, EmptyKey) && 7568dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth !KeyInfoT::isEqual(LHSB->first, TombstoneKey)); 7578dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth bool hasRHSValue = (!KeyInfoT::isEqual(RHSB->first, EmptyKey) && 7588dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth !KeyInfoT::isEqual(RHSB->first, TombstoneKey)); 7598dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth if (hasLHSValue && hasRHSValue) { 7608dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth // Swap together if we can... 7618dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth std::swap(*LHSB, *RHSB); 7628dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth continue; 7638dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth } 7648dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth // Swap separately and handle any assymetry. 7658dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth std::swap(LHSB->first, RHSB->first); 7668dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth if (hasLHSValue) { 7678dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth new (&RHSB->second) ValueT(llvm_move(LHSB->second)); 7688dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth LHSB->second.~ValueT(); 7698dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth } else if (hasRHSValue) { 7708dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth new (&LHSB->second) ValueT(llvm_move(RHSB->second)); 7718dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth RHSB->second.~ValueT(); 7728dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth } 7738dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth } 774dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return; 775dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 776dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (!Small && !RHS.Small) { 777dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth std::swap(getLargeRep()->Buckets, RHS.getLargeRep()->Buckets); 778dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth std::swap(getLargeRep()->NumBuckets, RHS.getLargeRep()->NumBuckets); 779dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return; 780dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 781dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 782dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth SmallDenseMap &SmallSide = Small ? *this : RHS; 783dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth SmallDenseMap &LargeSide = Small ? RHS : *this; 784dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 785dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // First stash the large side's rep and move the small side across. 786dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth LargeRep TmpRep = llvm_move(*LargeSide.getLargeRep()); 787dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth LargeSide.getLargeRep()->~LargeRep(); 788dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth LargeSide.Small = true; 789dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // This is similar to the standard move-from-old-buckets, but the bucket 7908dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth // count hasn't actually rotated in this case. So we have to carefully 791dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // move construct the keys and values into their new locations, but there 792dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // is no need to re-hash things. 793dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth for (unsigned i = 0, e = InlineBuckets; i != e; ++i) { 794dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth BucketT *NewB = &LargeSide.getInlineBuckets()[i], 795dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth *OldB = &SmallSide.getInlineBuckets()[i]; 796dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth new (&NewB->first) KeyT(llvm_move(OldB->first)); 7978dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth OldB->first.~KeyT(); 798dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (!KeyInfoT::isEqual(NewB->first, EmptyKey) && 799dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth !KeyInfoT::isEqual(NewB->first, TombstoneKey)) { 800dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth new (&NewB->second) ValueT(llvm_move(OldB->second)); 801dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth OldB->second.~ValueT(); 802dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 803dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 804dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 805dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // The hard part of moving the small buckets across is done, just move 806dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // the TmpRep into its new home. 807dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth SmallSide.Small = false; 808dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth new (SmallSide.getLargeRep()) LargeRep(llvm_move(TmpRep)); 809dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 810dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 811dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth SmallDenseMap& operator=(const SmallDenseMap& other) { 812dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth copyFrom(other); 813dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return *this; 814dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 815dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 8164334dd96a9e622fdcf2825a8f73a2d941d67be72Chandler Carruth#if LLVM_HAS_RVALUE_REFERENCES 817dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth SmallDenseMap& operator=(SmallDenseMap &&other) { 818dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->destroyAll(); 819dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth deallocateBuckets(); 820dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth init(0); 821dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth swap(other); 822dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return *this; 823dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 824dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth#endif 825dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 826dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth void copyFrom(const SmallDenseMap& other) { 827dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->destroyAll(); 828dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth deallocateBuckets(); 829dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth Small = true; 830dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (other.getNumBuckets() > InlineBuckets) { 831dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth Small = false; 832dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth allocateBuckets(other.getNumBuckets()); 833dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 834dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->BaseT::copyFrom(other); 835dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 836dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 837dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth void init(unsigned InitBuckets) { 838dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth Small = true; 839dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (InitBuckets > InlineBuckets) { 840dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth Small = false; 841dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth new (getLargeRep()) LargeRep(allocateBuckets(InitBuckets)); 842dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 843dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->BaseT::initEmpty(); 844dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 845dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 846dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth void grow(unsigned AtLeast) { 84799112c6b193c54409e2a3a5ea76c3759d5c1244cPete Cooper if (AtLeast >= InlineBuckets) 84899112c6b193c54409e2a3a5ea76c3759d5c1244cPete Cooper AtLeast = std::max<unsigned>(64, NextPowerOf2(AtLeast-1)); 849dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 850dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (Small) { 851fbaf206f470b5a6a54811547641ee41368a2cccdPete Cooper if (AtLeast < InlineBuckets) 852dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return; // Nothing to do. 853dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 8546446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth // First move the inline buckets into a temporary storage. 855cbeb8d9869aafec3c2c1ee0922f0a4d5bb4a916aChandler Carruth AlignedCharArrayUnion<BucketT[InlineBuckets]> TmpStorage; 8566446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth BucketT *TmpBegin = reinterpret_cast<BucketT *>(TmpStorage.buffer); 8576446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth BucketT *TmpEnd = TmpBegin; 8586446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth 8596446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth // Loop over the buckets, moving non-empty, non-tombstones into the 8606446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth // temporary storage. Have the loop move the TmpEnd forward as it goes. 8616446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth const KeyT EmptyKey = this->getEmptyKey(); 8626446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth const KeyT TombstoneKey = this->getTombstoneKey(); 8636446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth for (BucketT *P = getBuckets(), *E = P + InlineBuckets; P != E; ++P) { 8646446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth if (!KeyInfoT::isEqual(P->first, EmptyKey) && 8656446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth !KeyInfoT::isEqual(P->first, TombstoneKey)) { 866ac24e251014de60a16558fc0a1f2340c334d2aa8Benjamin Kramer assert(size_t(TmpEnd - TmpBegin) < InlineBuckets && 8676446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth "Too many inline buckets!"); 8686446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth new (&TmpEnd->first) KeyT(llvm_move(P->first)); 8696446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth new (&TmpEnd->second) ValueT(llvm_move(P->second)); 8706446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth ++TmpEnd; 8716446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth P->second.~ValueT(); 8726446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth } 8736446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth P->first.~KeyT(); 8746446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth } 8756446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth 8766446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth // Now make this map use the large rep, and move all the entries back 8776446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth // into it. 878dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth Small = false; 8796446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth new (getLargeRep()) LargeRep(allocateBuckets(AtLeast)); 8806446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth this->moveFromOldBuckets(TmpBegin, TmpEnd); 881dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return; 882dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 883dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 884dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth LargeRep OldRep = llvm_move(*getLargeRep()); 885dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth getLargeRep()->~LargeRep(); 886dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (AtLeast <= InlineBuckets) { 887dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth Small = true; 888dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } else { 889dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth new (getLargeRep()) LargeRep(allocateBuckets(AtLeast)); 890dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 891dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 892dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->moveFromOldBuckets(OldRep.Buckets, OldRep.Buckets+OldRep.NumBuckets); 893dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 894dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // Free the old table. 895dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth operator delete(OldRep.Buckets); 896dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 897dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 898dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth void shrink_and_clear() { 899dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned OldSize = this->size(); 900dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->destroyAll(); 901dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 902dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // Reduce the number of buckets. 903dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned NewNumBuckets = 0; 904dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (OldSize) { 905dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth NewNumBuckets = 1 << (Log2_32_Ceil(OldSize) + 1); 906dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (NewNumBuckets > InlineBuckets && NewNumBuckets < 64u) 907dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth NewNumBuckets = 64; 908dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 909dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if ((Small && NewNumBuckets <= InlineBuckets) || 910dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth (!Small && NewNumBuckets == getLargeRep()->NumBuckets)) { 911dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->BaseT::initEmpty(); 912dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return; 913dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 914dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 915dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth deallocateBuckets(); 916dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth init(NewNumBuckets); 917dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 918dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 919dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruthprivate: 920dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned getNumEntries() const { 921dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return NumEntries; 922dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 923dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth void setNumEntries(unsigned Num) { 924dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth assert(Num < INT_MAX && "Cannot support more than INT_MAX entries"); 925dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth NumEntries = Num; 926dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 927dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 928dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned getNumTombstones() const { 929dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return NumTombstones; 930dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 931dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth void setNumTombstones(unsigned Num) { 932dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth NumTombstones = Num; 933dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 934dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 935dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const BucketT *getInlineBuckets() const { 936dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth assert(Small); 937dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // Note that this cast does not violate aliasing rules as we assert that 938dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // the memory's dynamic type is the small, inline bucket buffer, and the 939dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // 'storage.buffer' static type is 'char *'. 940dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return reinterpret_cast<const BucketT *>(storage.buffer); 941dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 942dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth BucketT *getInlineBuckets() { 943dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return const_cast<BucketT *>( 944dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const_cast<const SmallDenseMap *>(this)->getInlineBuckets()); 945dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 946dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const LargeRep *getLargeRep() const { 947dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth assert(!Small); 948dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // Note, same rule about aliasing as with getInlineBuckets. 949dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return reinterpret_cast<const LargeRep *>(storage.buffer); 950dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 951dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth LargeRep *getLargeRep() { 952dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return const_cast<LargeRep *>( 953dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const_cast<const SmallDenseMap *>(this)->getLargeRep()); 954dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 955dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 956dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const BucketT *getBuckets() const { 957dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return Small ? getInlineBuckets() : getLargeRep()->Buckets; 958dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 959dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth BucketT *getBuckets() { 960dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return const_cast<BucketT *>( 961dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const_cast<const SmallDenseMap *>(this)->getBuckets()); 962dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 963dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned getNumBuckets() const { 964dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return Small ? InlineBuckets : getLargeRep()->NumBuckets; 965dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 966dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 967dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth void deallocateBuckets() { 968dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (Small) 969dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return; 970dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 971dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth operator delete(getLargeRep()->Buckets); 972dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth getLargeRep()->~LargeRep(); 973dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 974dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 975dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth LargeRep allocateBuckets(unsigned Num) { 976dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth assert(Num > InlineBuckets && "Must allocate more buckets than are inline"); 977dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth LargeRep Rep = { 978dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth static_cast<BucketT*>(operator new(sizeof(BucketT) * Num)), Num 979dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth }; 980dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return Rep; 981dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 982dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth}; 983dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 984dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruthtemplate<typename KeyT, typename ValueT, 9854e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer typename KeyInfoT, bool IsConst> 98681cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskinclass DenseMapIterator { 98781cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef std::pair<KeyT, ValueT> Bucket; 98881cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef DenseMapIterator<KeyT, ValueT, 9894e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer KeyInfoT, true> ConstIterator; 9904e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, true>; 99181cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskinpublic: 99281cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef ptrdiff_t difference_type; 99381cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef typename conditional<IsConst, const Bucket, Bucket>::type value_type; 99481cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef value_type *pointer; 99581cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef value_type &reference; 99681cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef std::forward_iterator_tag iterator_category; 99781cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskinprivate: 99881cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin pointer Ptr, End; 999f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerpublic: 1000a9ad04191cb56c42944b17980b8b2bb2afe11ab2Dan Gohman DenseMapIterator() : Ptr(0), End(0) {} 100113e781ebe7a39e008dd5e5de78983e095e8a1d02David Greene 1002f0be7ca7e42915779175a9332c6baba18a2a840cBenjamin Kramer DenseMapIterator(pointer Pos, pointer E, bool NoAdvance = false) 1003f0be7ca7e42915779175a9332c6baba18a2a840cBenjamin Kramer : Ptr(Pos), End(E) { 1004f0be7ca7e42915779175a9332c6baba18a2a840cBenjamin Kramer if (!NoAdvance) AdvancePastEmptyBuckets(); 1005f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 10063a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 100781cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin // If IsConst is true this is a converting constructor from iterator to 100881cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin // const_iterator and the default copy constructor is used. 100981cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin // Otherwise this is a copy constructor for iterator. 101081cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin DenseMapIterator(const DenseMapIterator<KeyT, ValueT, 10114e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer KeyInfoT, false>& I) 101281cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin : Ptr(I.Ptr), End(I.End) {} 101381cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin 101481cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin reference operator*() const { 101581cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin return *Ptr; 1016f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 101781cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin pointer operator->() const { 101881cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin return Ptr; 1019f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 10203a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 102181cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin bool operator==(const ConstIterator &RHS) const { 102281cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin return Ptr == RHS.operator->(); 1023f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 102481cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin bool operator!=(const ConstIterator &RHS) const { 102581cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin return Ptr != RHS.operator->(); 1026f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 10273a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 10284ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin inline DenseMapIterator& operator++() { // Preincrement 1029f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner ++Ptr; 1030f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner AdvancePastEmptyBuckets(); 1031f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner return *this; 1032f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 10334ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin DenseMapIterator operator++(int) { // Postincrement 1034f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner DenseMapIterator tmp = *this; ++*this; return tmp; 1035f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 10363a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1037f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerprivate: 1038f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner void AdvancePastEmptyBuckets() { 1039a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner const KeyT Empty = KeyInfoT::getEmptyKey(); 1040a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner const KeyT Tombstone = KeyInfoT::getTombstoneKey(); 1041f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 10423a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman while (Ptr != End && 104376c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner (KeyInfoT::isEqual(Ptr->first, Empty) || 104476c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner KeyInfoT::isEqual(Ptr->first, Tombstone))) 1045f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner ++Ptr; 1046f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 1047f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner}; 1048255cd6f317f3a0bad6e7939ca5ce49b33c6676f9NAKAMURA Takumi 10494e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramertemplate<typename KeyT, typename ValueT, typename KeyInfoT> 105018dceba0bb5e38250535401ecc9d9737943d0657Ted Kremenekstatic inline size_t 10514e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramercapacity_in_bytes(const DenseMap<KeyT, ValueT, KeyInfoT> &X) { 105218dceba0bb5e38250535401ecc9d9737943d0657Ted Kremenek return X.getMemorySize(); 105318dceba0bb5e38250535401ecc9d9737943d0657Ted Kremenek} 1054f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 10556e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner} // end namespace llvm 10566e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 10576e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner#endif 1058