DenseMap.h revision 5d295b41a3f4194778b6bc01a828b2115bd3a3f1
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; 7832859c71d6ba9cd5e38662611a73d82335f4ba41Chris Lattner 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 162b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner /// insert - Range insertion of pairs. 163b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner template<typename InputIt> 164b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner void insert(InputIt I, InputIt E) { 165b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner for (; I != E; ++I) 166b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner insert(*I); 167b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner } 168b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner 1693a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 17070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner bool erase(const KeyT &Val) { 17170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner BucketT *TheBucket; 17270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner if (!LookupBucketFor(Val, TheBucket)) 17370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return false; // not in map. 17470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner 17570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->second.~ValueT(); 17670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->first = getTombstoneKey(); 17748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth decrementNumEntries(); 17848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth incrementNumTombstones(); 17970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner return true; 18070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 181e3955df639ff9aff990f628ef6a219ff5efdbc81Dan Gohman void erase(iterator I) { 18270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner BucketT *TheBucket = &*I; 18370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->second.~ValueT(); 18470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner TheBucket->first = getTombstoneKey(); 18548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth decrementNumEntries(); 18648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth incrementNumTombstones(); 18770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner } 188aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek 189aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek value_type& FindAndConstruct(const KeyT &Key) { 1906e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketT *TheBucket; 19128f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner if (LookupBucketFor(Key, TheBucket)) 192aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek return *TheBucket; 1933a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 194aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek return *InsertIntoBucket(Key, ValueT(), TheBucket); 195aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek } 1963a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 197aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek ValueT &operator[](const KeyT &Key) { 198aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek return FindAndConstruct(Key).second; 19928f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner } 2003a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2014334dd96a9e622fdcf2825a8f73a2d941d67be72Chandler Carruth#if LLVM_HAS_RVALUE_REFERENCES 202aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer value_type& FindAndConstruct(KeyT &&Key) { 203aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer BucketT *TheBucket; 204aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer if (LookupBucketFor(Key, TheBucket)) 205aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer return *TheBucket; 206aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 207aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer return *InsertIntoBucket(Key, ValueT(), TheBucket); 208aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer } 209aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 210aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer ValueT &operator[](KeyT &&Key) { 211aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer return FindAndConstruct(Key).second; 212aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer } 213aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer#endif 214aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 215bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// isPointerIntoBucketsArray - Return true if the specified pointer points 216bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// somewhere into the DenseMap's array of buckets (i.e. either to a key or 217bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// value in the DenseMap). 218bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner bool isPointerIntoBucketsArray(const void *Ptr) const { 2197f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return Ptr >= getBuckets() && Ptr < getBucketsEnd(); 220bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner } 221bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner 222bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets 223bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// array. In conjunction with the previous method, this can be used to 224bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner /// determine whether an insertion caused the DenseMap to reallocate. 2257f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth const void *getPointerIntoBucketsArray() const { return getBuckets(); } 226bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner 2277f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthprotected: 22848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth DenseMapBase() {} 2297f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 2307f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void destroyAll() { 2317f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth if (getNumBuckets() == 0) // Nothing to do. 2328e337120133c746640246feb9383556d383a94beBenjamin Kramer return; 2338e337120133c746640246feb9383556d383a94beBenjamin Kramer 234295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); 2357f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) { 236295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer if (!KeyInfoT::isEqual(P->first, EmptyKey) && 237295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer !KeyInfoT::isEqual(P->first, TombstoneKey)) 238295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer P->second.~ValueT(); 239295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer P->first.~KeyT(); 24067280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson } 2413a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 242d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#ifndef NDEBUG 2437f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth memset((void*)getBuckets(), 0x5a, sizeof(BucketT)*getNumBuckets()); 244d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#endif 245295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer } 24688b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer 2477f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void initEmpty() { 24848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth setNumEntries(0); 24948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth setNumTombstones(0); 2507f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 2517f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth assert((getNumBuckets() & (getNumBuckets()-1)) == 0 && 2527f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth "# initial buckets must be a power of two!"); 2537f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth const KeyT EmptyKey = getEmptyKey(); 2547f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth for (BucketT *B = getBuckets(), *E = getBucketsEnd(); B != E; ++B) 2557f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth new (&B->first) KeyT(EmptyKey); 2567f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 257295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer 2587f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void moveFromOldBuckets(BucketT *OldBucketsBegin, BucketT *OldBucketsEnd) { 2597f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth initEmpty(); 26088b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer 2617f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth // Insert all the old elements. 2627f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth const KeyT EmptyKey = getEmptyKey(); 2637f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth const KeyT TombstoneKey = getTombstoneKey(); 2647f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth for (BucketT *B = OldBucketsBegin, *E = OldBucketsEnd; B != E; ++B) { 2657f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth if (!KeyInfoT::isEqual(B->first, EmptyKey) && 2667f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth !KeyInfoT::isEqual(B->first, TombstoneKey)) { 2677f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth // Insert the key/value into the new table. 2687f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth BucketT *DestBucket; 2697f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth bool FoundVal = LookupBucketFor(B->first, DestBucket); 2707f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth (void)FoundVal; // silence warning. 2717f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth assert(!FoundVal && "Key already in new map?"); 2727f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth DestBucket->first = llvm_move(B->first); 2737f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth new (&DestBucket->second) ValueT(llvm_move(B->second)); 27448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth incrementNumEntries(); 2757f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 2767f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth // Free the value. 2777f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth B->second.~ValueT(); 2787f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 2797f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth B->first.~KeyT(); 28088b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer } 28188b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer 2827f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth#ifndef NDEBUG 2837f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth if (OldBucketsBegin != OldBucketsEnd) 2847f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth memset((void*)OldBucketsBegin, 0x5a, 2857f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth sizeof(BucketT) * (OldBucketsEnd - OldBucketsBegin)); 2867f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth#endif 2877f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 2887f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 2897f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth template <typename OtherBaseT> 2907f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void copyFrom(const DenseMapBase<OtherBaseT, KeyT, ValueT, KeyInfoT>& other) { 2917f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth assert(getNumBuckets() == other.getNumBuckets()); 2927f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 29348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth setNumEntries(other.getNumEntries()); 29448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth setNumTombstones(other.getNumTombstones()); 2953a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 2964e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer if (isPodLike<KeyT>::value && isPodLike<ValueT>::value) 2977f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth memcpy(getBuckets(), other.getBuckets(), 2987f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth getNumBuckets() * sizeof(BucketT)); 2999544dc294f63ce116fbab398a8874ebf834cf41eOwen Anderson else 3007f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth for (size_t i = 0; i < getNumBuckets(); ++i) { 3017f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth new (&getBuckets()[i].first) KeyT(other.getBuckets()[i].first); 3027f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth if (!KeyInfoT::isEqual(getBuckets()[i].first, getEmptyKey()) && 3037f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth !KeyInfoT::isEqual(getBuckets()[i].first, getTombstoneKey())) 3047f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth new (&getBuckets()[i].second) ValueT(other.getBuckets()[i].second); 3059544dc294f63ce116fbab398a8874ebf834cf41eOwen Anderson } 30667280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson } 3073a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 3087f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void swap(DenseMapBase& RHS) { 30948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth std::swap(getNumEntries(), RHS.getNumEntries()); 31048f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth std::swap(getNumTombstones(), RHS.getNumTombstones()); 3117f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 3127f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 3137f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth static unsigned getHashValue(const KeyT &Val) { 3147f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return KeyInfoT::getHashValue(Val); 3157f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 3167f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth template<typename LookupKeyT> 3177f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth static unsigned getHashValue(const LookupKeyT &Val) { 3187f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return KeyInfoT::getHashValue(Val); 3197f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 3207f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth static const KeyT getEmptyKey() { 3217f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return KeyInfoT::getEmptyKey(); 3227f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 3237f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth static const KeyT getTombstoneKey() { 3247f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return KeyInfoT::getTombstoneKey(); 3257f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 3267f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 3276446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruthprivate: 32848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned getNumEntries() const { 32948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth return static_cast<const DerivedT *>(this)->getNumEntries(); 33048f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 33148f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth void setNumEntries(unsigned Num) { 33248f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth static_cast<DerivedT *>(this)->setNumEntries(Num); 33348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 33448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth void incrementNumEntries() { 33548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth setNumEntries(getNumEntries() + 1); 33648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 33748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth void decrementNumEntries() { 33848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth setNumEntries(getNumEntries() - 1); 33948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 34048f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned getNumTombstones() const { 34148f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth return static_cast<const DerivedT *>(this)->getNumTombstones(); 34248f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 34348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth void setNumTombstones(unsigned Num) { 34448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth static_cast<DerivedT *>(this)->setNumTombstones(Num); 34548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 34648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth void incrementNumTombstones() { 34748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth setNumTombstones(getNumTombstones() + 1); 34848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 34948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth void decrementNumTombstones() { 35048f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth setNumTombstones(getNumTombstones() - 1); 35148f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 352dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const BucketT *getBuckets() const { 3537f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return static_cast<const DerivedT *>(this)->getBuckets(); 3547f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 355dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth BucketT *getBuckets() { 356dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return static_cast<DerivedT *>(this)->getBuckets(); 357dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 3587f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth unsigned getNumBuckets() const { 3597f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return static_cast<const DerivedT *>(this)->getNumBuckets(); 3607f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 361dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth BucketT *getBucketsEnd() { 362dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return getBuckets() + getNumBuckets(); 363dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 364dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const BucketT *getBucketsEnd() const { 3657f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return getBuckets() + getNumBuckets(); 3667f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 3677f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 3687f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void grow(unsigned AtLeast) { 3697f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth static_cast<DerivedT *>(this)->grow(AtLeast); 3707f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 3717f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 3727f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void shrink_and_clear() { 3737f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth static_cast<DerivedT *>(this)->shrink_and_clear(); 3747f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 3757f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 3767f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 37728f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner BucketT *InsertIntoBucket(const KeyT &Key, const ValueT &Value, 37828f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner BucketT *TheBucket) { 379aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer TheBucket = InsertIntoBucketImpl(Key, TheBucket); 380aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 381aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer TheBucket->first = Key; 382aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer new (&TheBucket->second) ValueT(Value); 383aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer return TheBucket; 384aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer } 385aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 3864334dd96a9e622fdcf2825a8f73a2d941d67be72Chandler Carruth#if LLVM_HAS_RVALUE_REFERENCES 387aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer BucketT *InsertIntoBucket(const KeyT &Key, ValueT &&Value, 388aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer BucketT *TheBucket) { 389aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer TheBucket = InsertIntoBucketImpl(Key, TheBucket); 390aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 391aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer TheBucket->first = Key; 392aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer new (&TheBucket->second) ValueT(std::move(Value)); 393aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer return TheBucket; 394aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer } 395aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 396aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer BucketT *InsertIntoBucket(KeyT &&Key, ValueT &&Value, BucketT *TheBucket) { 397aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer TheBucket = InsertIntoBucketImpl(Key, TheBucket); 398aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 399aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer TheBucket->first = std::move(Key); 400aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer new (&TheBucket->second) ValueT(std::move(Value)); 401aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer return TheBucket; 402aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer } 403aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer#endif 404aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer 405aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer BucketT *InsertIntoBucketImpl(const KeyT &Key, BucketT *TheBucket) { 40604a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // If the load of the hash table is more than 3/4, or if fewer than 1/8 of 40704a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // the buckets are empty (meaning that many are filled with tombstones), 40804a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // grow the table. 40904a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // 41004a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // The later case is tricky. For example, if we had one empty bucket with 41104a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // tons of tombstones, failing lookups (e.g. for insertion) would have to 41204a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // probe almost the entire table until it found the empty bucket. If the 41304a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // table completely filled with tombstones, no lookup would ever succeed, 41404a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // causing infinite loops in lookup. 41548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned NewNumEntries = getNumEntries() + 1; 416dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned NumBuckets = getNumBuckets(); 417dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (NewNumEntries*4 >= NumBuckets*3) { 418dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->grow(NumBuckets * 2); 41928f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner LookupBucketFor(Key, TheBucket); 420dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth NumBuckets = getNumBuckets(); 4216e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 422dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (NumBuckets-(NewNumEntries+getNumTombstones()) <= NumBuckets/8) { 4232430973fb657eb84dfbacb1e8886d3a29190e0b5Pete Cooper this->grow(NumBuckets * 2); 424414fdbdb0104fdc8c570287f94df8bb697e7b7c1Jakob Stoklund Olesen LookupBucketFor(Key, TheBucket); 425414fdbdb0104fdc8c570287f94df8bb697e7b7c1Jakob Stoklund Olesen } 4263bbdddf527c762085802544665d6e77471ea035bJordan Rose assert(TheBucket); 4273a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4287f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth // Only update the state after we've grown our bucket space appropriately 4297f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth // so that when growing buckets we have self-consistent entry count. 43048f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth incrementNumEntries(); 4317f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 43204a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // If we are writing over a tombstone, remember this. 4335d295b41a3f4194778b6bc01a828b2115bd3a3f1NAKAMURA Takumi const KeyT EmptyKey = getEmptyKey(); 4345d295b41a3f4194778b6bc01a828b2115bd3a3f1NAKAMURA Takumi if (!KeyInfoT::isEqual(TheBucket->first, EmptyKey)) 43548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth decrementNumTombstones(); 4363a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 43728f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner return TheBucket; 4386e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 43928f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner 4406e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in 4416e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// FoundBucket. If the bucket contains the key and a value, this returns 4426e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// true, otherwise it returns a bucket with an empty marker or tombstone and 4436e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// returns false. 444babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin template<typename LookupKeyT> 445dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth bool LookupBucketFor(const LookupKeyT &Val, 446dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const BucketT *&FoundBucket) const { 447dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const BucketT *BucketsPtr = getBuckets(); 448ce9a04132d1bf85967d6ad062d45dd75f148eef1Chandler Carruth const unsigned NumBuckets = getNumBuckets(); 4493a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 450ce9a04132d1bf85967d6ad062d45dd75f148eef1Chandler Carruth if (NumBuckets == 0) { 45149d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer FoundBucket = 0; 45249d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer return false; 45349d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer } 45449d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer 4556e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // FoundTombstone - Keep track of whether we find a tombstone while probing. 456dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const BucketT *FoundTombstone = 0; 4576e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(); 4586e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT TombstoneKey = getTombstoneKey(); 45905831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner assert(!KeyInfoT::isEqual(Val, EmptyKey) && 46005831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(Val, TombstoneKey) && 4616e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner "Empty/Tombstone value shouldn't be inserted into map!"); 4623a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 463ce9a04132d1bf85967d6ad062d45dd75f148eef1Chandler Carruth unsigned BucketNo = getHashValue(Val) & (NumBuckets-1); 464ce9a04132d1bf85967d6ad062d45dd75f148eef1Chandler Carruth unsigned ProbeAmt = 1; 4656e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner while (1) { 466ce9a04132d1bf85967d6ad062d45dd75f148eef1Chandler Carruth const BucketT *ThisBucket = BucketsPtr + BucketNo; 4676e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Found Val's bucket? If so, return it. 468babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin if (KeyInfoT::isEqual(Val, ThisBucket->first)) { 4696e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundBucket = ThisBucket; 4706e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return true; 4716e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 4723a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4736e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If we found an empty bucket, the key doesn't exist in the set. 4746e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Insert it and return the default value. 47576c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner if (KeyInfoT::isEqual(ThisBucket->first, EmptyKey)) { 4766e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If we've already seen a tombstone while probing, fill it in instead 4776e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // of the empty bucket we eventually probed to. 4786e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner if (FoundTombstone) ThisBucket = FoundTombstone; 4796e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket; 4806e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return false; 4816e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 4823a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4836e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If this is a tombstone, remember it. If Val ends up not in the map, we 4846e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // prefer to return it than something that would require more probing. 48576c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner if (KeyInfoT::isEqual(ThisBucket->first, TombstoneKey) && !FoundTombstone) 4866e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundTombstone = ThisBucket; // Remember the first tombstone found. 4873a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4886e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Otherwise, it's a hash collision or a tombstone, continue quadratic 4896e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // probing. 4906e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketNo += ProbeAmt++; 491ce9a04132d1bf85967d6ad062d45dd75f148eef1Chandler Carruth BucketNo &= (NumBuckets-1); 4926e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 4936e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 4946e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 495dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth template <typename LookupKeyT> 496dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth bool LookupBucketFor(const LookupKeyT &Val, BucketT *&FoundBucket) { 49790420105964371571ccacdf47771c6ca05db2e67David Blaikie const BucketT *ConstFoundBucket; 498dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth bool Result = const_cast<const DenseMapBase *>(this) 499dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth ->LookupBucketFor(Val, ConstFoundBucket); 500dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth FoundBucket = const_cast<BucketT *>(ConstFoundBucket); 501dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return Result; 502dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 503dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 5047f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthpublic: 5057f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth /// Return the approximate size (in bytes) of the actual map. 5067f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth /// This is just the raw memory used by DenseMap. 5077f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth /// If entries are pointers to objects, the size of the referenced objects 5087f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth /// are not included. 5097f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth size_t getMemorySize() const { 5107f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return getNumBuckets() * sizeof(BucketT); 5117f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5127f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth}; 51349d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer 5147f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthtemplate<typename KeyT, typename ValueT, 5157f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth typename KeyInfoT = DenseMapInfo<KeyT> > 5167f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthclass DenseMap 5177f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT>, 5187f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth KeyT, ValueT, KeyInfoT> { 5197f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth // Lift some types from the dependent base class into this class for 5207f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth // simplicity of referring to them. 5217f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth typedef DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT> BaseT; 5227f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth typedef typename BaseT::BucketT BucketT; 5237f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth friend class DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT>; 52449d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer 5257f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth BucketT *Buckets; 52648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned NumEntries; 52748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned NumTombstones; 5287f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth unsigned NumBuckets; 5297f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 5307f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthpublic: 5317f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth explicit DenseMap(unsigned NumInitBuckets = 0) { 5327f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth init(NumInitBuckets); 5336e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 5343a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 535319120f6229dcf37f288be2719bc095a2f454d55Alex Rosenberg DenseMap(const DenseMap &other) : BaseT() { 5367f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth init(0); 5377f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth copyFrom(other); 5387f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5393a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5404334dd96a9e622fdcf2825a8f73a2d941d67be72Chandler Carruth#if LLVM_HAS_RVALUE_REFERENCES 541319120f6229dcf37f288be2719bc095a2f454d55Alex Rosenberg DenseMap(DenseMap &&other) : BaseT() { 5427f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth init(0); 5437f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth swap(other); 5447f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5457f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth#endif 54649d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer 5477f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth template<typename InputIt> 5487f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth DenseMap(const InputIt &I, const InputIt &E) { 5497f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth init(NextPowerOf2(std::distance(I, E))); 5507f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->insert(I, E); 5517f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5526e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 5537f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth ~DenseMap() { 5547f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->destroyAll(); 5557f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth operator delete(Buckets); 5567f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5576e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 5587f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void swap(DenseMap& RHS) { 5597f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth std::swap(Buckets, RHS.Buckets); 56048f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth std::swap(NumEntries, RHS.NumEntries); 56148f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth std::swap(NumTombstones, RHS.NumTombstones); 56248f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth std::swap(NumBuckets, RHS.NumBuckets); 5637f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5643a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5657f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth DenseMap& operator=(const DenseMap& other) { 5667f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth copyFrom(other); 5677f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return *this; 5687f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5697f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 5704334dd96a9e622fdcf2825a8f73a2d941d67be72Chandler Carruth#if LLVM_HAS_RVALUE_REFERENCES 5717f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth DenseMap& operator=(DenseMap &&other) { 5727f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->destroyAll(); 5737f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth operator delete(Buckets); 5747f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth init(0); 5757f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth swap(other); 5767f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return *this; 5777f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 578d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#endif 5797f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 5807f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void copyFrom(const DenseMap& other) { 5817f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->destroyAll(); 5827f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth operator delete(Buckets); 58348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth if (allocateBuckets(other.NumBuckets)) { 5847f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->BaseT::copyFrom(other); 58548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } else { 58648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth NumEntries = 0; 58748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth NumTombstones = 0; 58848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 5896e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 5903a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5917f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void init(unsigned InitBuckets) { 59248f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth if (allocateBuckets(InitBuckets)) { 5937f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->BaseT::initEmpty(); 59448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } else { 59548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth NumEntries = 0; 59648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth NumTombstones = 0; 59748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 5987f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5997f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 6007f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void grow(unsigned AtLeast) { 6016ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson unsigned OldNumBuckets = NumBuckets; 6026ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson BucketT *OldBuckets = Buckets; 6033a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 60499112c6b193c54409e2a3a5ea76c3759d5c1244cPete Cooper allocateBuckets(std::max<unsigned>(64, NextPowerOf2(AtLeast-1))); 6057f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth assert(Buckets); 6067f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth if (!OldBuckets) { 6077f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->BaseT::initEmpty(); 6087f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return; 6096ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 6103a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 6117f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->moveFromOldBuckets(OldBuckets, OldBuckets+OldNumBuckets); 6127f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 6136ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson // Free the old table. 61408c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman operator delete(OldBuckets); 6157f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 6163a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 6177f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void shrink_and_clear() { 61848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned OldNumEntries = NumEntries; 6197f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->destroyAll(); 6207f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 6217f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth // Reduce the number of buckets. 622b8ea08ca8c43016f5bc35e1a3b6557d414448faeRichard Smith unsigned NewNumBuckets = 0; 623b8ea08ca8c43016f5bc35e1a3b6557d414448faeRichard Smith if (OldNumEntries) 624b8ea08ca8c43016f5bc35e1a3b6557d414448faeRichard Smith NewNumBuckets = std::max(64, 1 << (Log2_32_Ceil(OldNumEntries) + 1)); 6257f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth if (NewNumBuckets == NumBuckets) { 6267f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->BaseT::initEmpty(); 6277f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return; 6287f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 6297f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 6307f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth operator delete(Buckets); 6317f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth init(NewNumBuckets); 6326ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 6337f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 6347f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthprivate: 63548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned getNumEntries() const { 63648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth return NumEntries; 63748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 63848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth void setNumEntries(unsigned Num) { 63948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth NumEntries = Num; 64048f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 64148f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth 64248f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned getNumTombstones() const { 64348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth return NumTombstones; 64448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 64548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth void setNumTombstones(unsigned Num) { 64648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth NumTombstones = Num; 64748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 64848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth 6497f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth BucketT *getBuckets() const { 6507f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return Buckets; 6517f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 6527f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 6537f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth unsigned getNumBuckets() const { 6547f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return NumBuckets; 6557f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 6567f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 6577f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth bool allocateBuckets(unsigned Num) { 6587f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth NumBuckets = Num; 6597f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth if (NumBuckets == 0) { 6607f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth Buckets = 0; 6617f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return false; 6627f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 6637f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 6647f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT) * NumBuckets)); 6657f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return true; 666e6b693db8cc07be91229bef0d8577ce8b5caf34bTed Kremenek } 6676e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner}; 6686e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 66981cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskintemplate<typename KeyT, typename ValueT, 670dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned InlineBuckets = 4, 671dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth typename KeyInfoT = DenseMapInfo<KeyT> > 672dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruthclass SmallDenseMap 673dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth : public DenseMapBase<SmallDenseMap<KeyT, ValueT, InlineBuckets, KeyInfoT>, 674dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth KeyT, ValueT, KeyInfoT> { 675dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // Lift some types from the dependent base class into this class for 676dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // simplicity of referring to them. 677dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth typedef DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT> BaseT; 678dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth typedef typename BaseT::BucketT BucketT; 679dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth friend class DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT>; 680dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 681dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned Small : 1; 682dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned NumEntries : 31; 683dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned NumTombstones; 684dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 685dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth struct LargeRep { 686dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth BucketT *Buckets; 687dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned NumBuckets; 688dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth }; 689dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 690dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth /// A "union" of an inline bucket array and the struct representing 691dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth /// a large bucket. This union will be discriminated by the 'Small' bit. 692cbeb8d9869aafec3c2c1ee0922f0a4d5bb4a916aChandler Carruth AlignedCharArrayUnion<BucketT[InlineBuckets], LargeRep> storage; 693dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 694dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruthpublic: 695dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth explicit SmallDenseMap(unsigned NumInitBuckets = 0) { 696dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth init(NumInitBuckets); 697dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 698dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 699dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth SmallDenseMap(const SmallDenseMap &other) { 700dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth init(0); 701dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth copyFrom(other); 702dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 703dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 7044334dd96a9e622fdcf2825a8f73a2d941d67be72Chandler Carruth#if LLVM_HAS_RVALUE_REFERENCES 705dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth SmallDenseMap(SmallDenseMap &&other) { 706dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth init(0); 707dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth swap(other); 708dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 709dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth#endif 710dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 711dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth template<typename InputIt> 712dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth SmallDenseMap(const InputIt &I, const InputIt &E) { 713dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth init(NextPowerOf2(std::distance(I, E))); 714dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->insert(I, E); 715dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 716dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 717dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth ~SmallDenseMap() { 718dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->destroyAll(); 719dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth deallocateBuckets(); 720dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 721dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 722dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth void swap(SmallDenseMap& RHS) { 7238dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth unsigned TmpNumEntries = RHS.NumEntries; 7248dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth RHS.NumEntries = NumEntries; 7258dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth NumEntries = TmpNumEntries; 726dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth std::swap(NumTombstones, RHS.NumTombstones); 7278dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth 7288dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth const KeyT EmptyKey = this->getEmptyKey(); 7298dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth const KeyT TombstoneKey = this->getTombstoneKey(); 730dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (Small && RHS.Small) { 7318dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth // If we're swapping inline bucket arrays, we have to cope with some of 7328dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth // the tricky bits of DenseMap's storage system: the buckets are not 7338dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth // fully initialized. Thus we swap every key, but we may have 7348dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth // a one-directional move of the value. 7358dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth for (unsigned i = 0, e = InlineBuckets; i != e; ++i) { 7368dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth BucketT *LHSB = &getInlineBuckets()[i], 7378dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth *RHSB = &RHS.getInlineBuckets()[i]; 7388dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth bool hasLHSValue = (!KeyInfoT::isEqual(LHSB->first, EmptyKey) && 7398dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth !KeyInfoT::isEqual(LHSB->first, TombstoneKey)); 7408dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth bool hasRHSValue = (!KeyInfoT::isEqual(RHSB->first, EmptyKey) && 7418dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth !KeyInfoT::isEqual(RHSB->first, TombstoneKey)); 7428dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth if (hasLHSValue && hasRHSValue) { 7438dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth // Swap together if we can... 7448dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth std::swap(*LHSB, *RHSB); 7458dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth continue; 7468dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth } 7478dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth // Swap separately and handle any assymetry. 7488dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth std::swap(LHSB->first, RHSB->first); 7498dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth if (hasLHSValue) { 7508dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth new (&RHSB->second) ValueT(llvm_move(LHSB->second)); 7518dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth LHSB->second.~ValueT(); 7528dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth } else if (hasRHSValue) { 7538dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth new (&LHSB->second) ValueT(llvm_move(RHSB->second)); 7548dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth RHSB->second.~ValueT(); 7558dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth } 7568dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth } 757dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return; 758dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 759dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (!Small && !RHS.Small) { 760dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth std::swap(getLargeRep()->Buckets, RHS.getLargeRep()->Buckets); 761dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth std::swap(getLargeRep()->NumBuckets, RHS.getLargeRep()->NumBuckets); 762dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return; 763dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 764dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 765dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth SmallDenseMap &SmallSide = Small ? *this : RHS; 766dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth SmallDenseMap &LargeSide = Small ? RHS : *this; 767dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 768dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // First stash the large side's rep and move the small side across. 769dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth LargeRep TmpRep = llvm_move(*LargeSide.getLargeRep()); 770dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth LargeSide.getLargeRep()->~LargeRep(); 771dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth LargeSide.Small = true; 772dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // This is similar to the standard move-from-old-buckets, but the bucket 7738dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth // count hasn't actually rotated in this case. So we have to carefully 774dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // move construct the keys and values into their new locations, but there 775dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // is no need to re-hash things. 776dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth for (unsigned i = 0, e = InlineBuckets; i != e; ++i) { 777dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth BucketT *NewB = &LargeSide.getInlineBuckets()[i], 778dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth *OldB = &SmallSide.getInlineBuckets()[i]; 779dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth new (&NewB->first) KeyT(llvm_move(OldB->first)); 7808dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth OldB->first.~KeyT(); 781dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (!KeyInfoT::isEqual(NewB->first, EmptyKey) && 782dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth !KeyInfoT::isEqual(NewB->first, TombstoneKey)) { 783dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth new (&NewB->second) ValueT(llvm_move(OldB->second)); 784dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth OldB->second.~ValueT(); 785dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 786dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 787dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 788dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // The hard part of moving the small buckets across is done, just move 789dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // the TmpRep into its new home. 790dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth SmallSide.Small = false; 791dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth new (SmallSide.getLargeRep()) LargeRep(llvm_move(TmpRep)); 792dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 793dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 794dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth SmallDenseMap& operator=(const SmallDenseMap& other) { 795dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth copyFrom(other); 796dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return *this; 797dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 798dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 7994334dd96a9e622fdcf2825a8f73a2d941d67be72Chandler Carruth#if LLVM_HAS_RVALUE_REFERENCES 800dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth SmallDenseMap& operator=(SmallDenseMap &&other) { 801dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->destroyAll(); 802dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth deallocateBuckets(); 803dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth init(0); 804dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth swap(other); 805dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return *this; 806dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 807dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth#endif 808dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 809dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth void copyFrom(const SmallDenseMap& other) { 810dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->destroyAll(); 811dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth deallocateBuckets(); 812dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth Small = true; 813dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (other.getNumBuckets() > InlineBuckets) { 814dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth Small = false; 815dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth allocateBuckets(other.getNumBuckets()); 816dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 817dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->BaseT::copyFrom(other); 818dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 819dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 820dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth void init(unsigned InitBuckets) { 821dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth Small = true; 822dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (InitBuckets > InlineBuckets) { 823dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth Small = false; 824dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth new (getLargeRep()) LargeRep(allocateBuckets(InitBuckets)); 825dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 826dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->BaseT::initEmpty(); 827dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 828dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 829dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth void grow(unsigned AtLeast) { 83099112c6b193c54409e2a3a5ea76c3759d5c1244cPete Cooper if (AtLeast >= InlineBuckets) 83199112c6b193c54409e2a3a5ea76c3759d5c1244cPete Cooper AtLeast = std::max<unsigned>(64, NextPowerOf2(AtLeast-1)); 832dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 833dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (Small) { 834fbaf206f470b5a6a54811547641ee41368a2cccdPete Cooper if (AtLeast < InlineBuckets) 835dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return; // Nothing to do. 836dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 8376446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth // First move the inline buckets into a temporary storage. 838cbeb8d9869aafec3c2c1ee0922f0a4d5bb4a916aChandler Carruth AlignedCharArrayUnion<BucketT[InlineBuckets]> TmpStorage; 8396446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth BucketT *TmpBegin = reinterpret_cast<BucketT *>(TmpStorage.buffer); 8406446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth BucketT *TmpEnd = TmpBegin; 8416446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth 8426446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth // Loop over the buckets, moving non-empty, non-tombstones into the 8436446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth // temporary storage. Have the loop move the TmpEnd forward as it goes. 8446446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth const KeyT EmptyKey = this->getEmptyKey(); 8456446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth const KeyT TombstoneKey = this->getTombstoneKey(); 8466446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth for (BucketT *P = getBuckets(), *E = P + InlineBuckets; P != E; ++P) { 8476446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth if (!KeyInfoT::isEqual(P->first, EmptyKey) && 8486446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth !KeyInfoT::isEqual(P->first, TombstoneKey)) { 849ac24e251014de60a16558fc0a1f2340c334d2aa8Benjamin Kramer assert(size_t(TmpEnd - TmpBegin) < InlineBuckets && 8506446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth "Too many inline buckets!"); 8516446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth new (&TmpEnd->first) KeyT(llvm_move(P->first)); 8526446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth new (&TmpEnd->second) ValueT(llvm_move(P->second)); 8536446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth ++TmpEnd; 8546446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth P->second.~ValueT(); 8556446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth } 8566446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth P->first.~KeyT(); 8576446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth } 8586446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth 8596446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth // Now make this map use the large rep, and move all the entries back 8606446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth // into it. 861dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth Small = false; 8626446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth new (getLargeRep()) LargeRep(allocateBuckets(AtLeast)); 8636446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth this->moveFromOldBuckets(TmpBegin, TmpEnd); 864dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return; 865dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 866dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 867dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth LargeRep OldRep = llvm_move(*getLargeRep()); 868dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth getLargeRep()->~LargeRep(); 869dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (AtLeast <= InlineBuckets) { 870dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth Small = true; 871dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } else { 872dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth new (getLargeRep()) LargeRep(allocateBuckets(AtLeast)); 873dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 874dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 875dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->moveFromOldBuckets(OldRep.Buckets, OldRep.Buckets+OldRep.NumBuckets); 876dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 877dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // Free the old table. 878dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth operator delete(OldRep.Buckets); 879dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 880dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 881dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth void shrink_and_clear() { 882dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned OldSize = this->size(); 883dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->destroyAll(); 884dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 885dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // Reduce the number of buckets. 886dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned NewNumBuckets = 0; 887dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (OldSize) { 888dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth NewNumBuckets = 1 << (Log2_32_Ceil(OldSize) + 1); 889dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (NewNumBuckets > InlineBuckets && NewNumBuckets < 64u) 890dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth NewNumBuckets = 64; 891dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 892dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if ((Small && NewNumBuckets <= InlineBuckets) || 893dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth (!Small && NewNumBuckets == getLargeRep()->NumBuckets)) { 894dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->BaseT::initEmpty(); 895dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return; 896dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 897dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 898dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth deallocateBuckets(); 899dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth init(NewNumBuckets); 900dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 901dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 902dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruthprivate: 903dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned getNumEntries() const { 904dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return NumEntries; 905dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 906dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth void setNumEntries(unsigned Num) { 907dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth assert(Num < INT_MAX && "Cannot support more than INT_MAX entries"); 908dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth NumEntries = Num; 909dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 910dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 911dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned getNumTombstones() const { 912dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return NumTombstones; 913dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 914dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth void setNumTombstones(unsigned Num) { 915dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth NumTombstones = Num; 916dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 917dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 918dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const BucketT *getInlineBuckets() const { 919dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth assert(Small); 920dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // Note that this cast does not violate aliasing rules as we assert that 921dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // the memory's dynamic type is the small, inline bucket buffer, and the 922dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // 'storage.buffer' static type is 'char *'. 923dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return reinterpret_cast<const BucketT *>(storage.buffer); 924dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 925dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth BucketT *getInlineBuckets() { 926dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return const_cast<BucketT *>( 927dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const_cast<const SmallDenseMap *>(this)->getInlineBuckets()); 928dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 929dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const LargeRep *getLargeRep() const { 930dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth assert(!Small); 931dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // Note, same rule about aliasing as with getInlineBuckets. 932dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return reinterpret_cast<const LargeRep *>(storage.buffer); 933dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 934dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth LargeRep *getLargeRep() { 935dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return const_cast<LargeRep *>( 936dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const_cast<const SmallDenseMap *>(this)->getLargeRep()); 937dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 938dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 939dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const BucketT *getBuckets() const { 940dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return Small ? getInlineBuckets() : getLargeRep()->Buckets; 941dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 942dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth BucketT *getBuckets() { 943dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return const_cast<BucketT *>( 944dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const_cast<const SmallDenseMap *>(this)->getBuckets()); 945dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 946dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned getNumBuckets() const { 947dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return Small ? InlineBuckets : getLargeRep()->NumBuckets; 948dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 949dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 950dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth void deallocateBuckets() { 951dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (Small) 952dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return; 953dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 954dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth operator delete(getLargeRep()->Buckets); 955dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth getLargeRep()->~LargeRep(); 956dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 957dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 958dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth LargeRep allocateBuckets(unsigned Num) { 959dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth assert(Num > InlineBuckets && "Must allocate more buckets than are inline"); 960dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth LargeRep Rep = { 961dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth static_cast<BucketT*>(operator new(sizeof(BucketT) * Num)), Num 962dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth }; 963dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return Rep; 964dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 965dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth}; 966dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 967dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruthtemplate<typename KeyT, typename ValueT, 9684e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer typename KeyInfoT, bool IsConst> 96981cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskinclass DenseMapIterator { 97081cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef std::pair<KeyT, ValueT> Bucket; 97181cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef DenseMapIterator<KeyT, ValueT, 9724e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer KeyInfoT, true> ConstIterator; 9734e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, true>; 97481cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskinpublic: 97581cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef ptrdiff_t difference_type; 97681cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef typename conditional<IsConst, const Bucket, Bucket>::type value_type; 97781cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef value_type *pointer; 97881cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef value_type &reference; 97981cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef std::forward_iterator_tag iterator_category; 98081cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskinprivate: 98181cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin pointer Ptr, End; 982f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerpublic: 983a9ad04191cb56c42944b17980b8b2bb2afe11ab2Dan Gohman DenseMapIterator() : Ptr(0), End(0) {} 98413e781ebe7a39e008dd5e5de78983e095e8a1d02David Greene 985f0be7ca7e42915779175a9332c6baba18a2a840cBenjamin Kramer DenseMapIterator(pointer Pos, pointer E, bool NoAdvance = false) 986f0be7ca7e42915779175a9332c6baba18a2a840cBenjamin Kramer : Ptr(Pos), End(E) { 987f0be7ca7e42915779175a9332c6baba18a2a840cBenjamin Kramer if (!NoAdvance) AdvancePastEmptyBuckets(); 988f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 9893a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 99081cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin // If IsConst is true this is a converting constructor from iterator to 99181cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin // const_iterator and the default copy constructor is used. 99281cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin // Otherwise this is a copy constructor for iterator. 99381cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin DenseMapIterator(const DenseMapIterator<KeyT, ValueT, 9944e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer KeyInfoT, false>& I) 99581cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin : Ptr(I.Ptr), End(I.End) {} 99681cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin 99781cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin reference operator*() const { 99881cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin return *Ptr; 999f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 100081cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin pointer operator->() const { 100181cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin return Ptr; 1002f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 10033a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 100481cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin bool operator==(const ConstIterator &RHS) const { 100581cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin return Ptr == RHS.operator->(); 1006f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 100781cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin bool operator!=(const ConstIterator &RHS) const { 100881cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin return Ptr != RHS.operator->(); 1009f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 10103a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 10114ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin inline DenseMapIterator& operator++() { // Preincrement 1012f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner ++Ptr; 1013f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner AdvancePastEmptyBuckets(); 1014f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner return *this; 1015f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 10164ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin DenseMapIterator operator++(int) { // Postincrement 1017f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner DenseMapIterator tmp = *this; ++*this; return tmp; 1018f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 10193a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1020f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerprivate: 1021f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner void AdvancePastEmptyBuckets() { 1022a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner const KeyT Empty = KeyInfoT::getEmptyKey(); 1023a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner const KeyT Tombstone = KeyInfoT::getTombstoneKey(); 1024f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 10253a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman while (Ptr != End && 102676c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner (KeyInfoT::isEqual(Ptr->first, Empty) || 102776c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner KeyInfoT::isEqual(Ptr->first, Tombstone))) 1028f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner ++Ptr; 1029f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 1030f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner}; 103118dceba0bb5e38250535401ecc9d9737943d0657Ted Kremenek 10324e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramertemplate<typename KeyT, typename ValueT, typename KeyInfoT> 103318dceba0bb5e38250535401ecc9d9737943d0657Ted Kremenekstatic inline size_t 10344e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramercapacity_in_bytes(const DenseMap<KeyT, ValueT, KeyInfoT> &X) { 103518dceba0bb5e38250535401ecc9d9737943d0657Ted Kremenek return X.getMemorySize(); 103618dceba0bb5e38250535401ecc9d9737943d0657Ted Kremenek} 1037f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 10386e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner} // end namespace llvm 10396e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 10406e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner#endif 1041