DenseMap.h revision ce9a04132d1bf85967d6ad062d45dd75f148eef1
16e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner//===- llvm/ADT/DenseMap.h - Dense probed hash table ------------*- C++ -*-===// 26e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner// 36e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner// The LLVM Compiler Infrastructure 46e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 76e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner// 86e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner//===----------------------------------------------------------------------===// 96e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner// 106e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner// This file defines the DenseMap class. 116e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner// 126e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner//===----------------------------------------------------------------------===// 136e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 146e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner#ifndef LLVM_ADT_DENSEMAP_H 156e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner#define LLVM_ADT_DENSEMAP_H 166e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 17ac5802bca0285eee49c1c372846552823d819181Benjamin Kramer#include "llvm/Support/Compiler.h" 18dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth#include "llvm/Support/AlignOf.h" 19398b40671b13018f88371b74822fa8ee2638577eOwen Anderson#include "llvm/Support/MathExtras.h" 2081cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin#include "llvm/Support/PointerLikeTypeTraits.h" 2181cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin#include "llvm/Support/type_traits.h" 22fb3af88ba75898896714d49c608b8daa4f106636Dan Gohman#include "llvm/ADT/DenseMapInfo.h" 23476b242fe7a61e5f9ac6214b0bc5c680d24f152eNick Lewycky#include <algorithm> 24724f6751442e2006856a9365ef3d3bc6f1b31c98Chris Lattner#include <iterator> 25724f6751442e2006856a9365ef3d3bc6f1b31c98Chris Lattner#include <new> 26724f6751442e2006856a9365ef3d3bc6f1b31c98Chris Lattner#include <utility> 276e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner#include <cassert> 28dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth#include <climits> 29345b378309eabd74a7a43f095dca9a4894bc371eDuncan Sands#include <cstddef> 30d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#include <cstring> 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 201aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer#if LLVM_USE_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 386aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer#if LLVM_USE_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) { 423dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->grow(NumBuckets); 424414fdbdb0104fdc8c570287f94df8bb697e7b7c1Jakob Stoklund Olesen LookupBucketFor(Key, TheBucket); 425414fdbdb0104fdc8c570287f94df8bb697e7b7c1Jakob Stoklund Olesen } 4263a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4277f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth // Only update the state after we've grown our bucket space appropriately 4287f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth // so that when growing buckets we have self-consistent entry count. 42948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth incrementNumEntries(); 4307f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 43104a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner // If we are writing over a tombstone, remember this. 43205831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner if (!KeyInfoT::isEqual(TheBucket->first, getEmptyKey())) 43348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth decrementNumTombstones(); 4343a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 43528f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner return TheBucket; 4366e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 43728f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner 4386e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in 4396e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// FoundBucket. If the bucket contains the key and a value, this returns 4406e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// true, otherwise it returns a bucket with an empty marker or tombstone and 4416e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner /// returns false. 442babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin template<typename LookupKeyT> 443dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth bool LookupBucketFor(const LookupKeyT &Val, 444dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const BucketT *&FoundBucket) const { 445dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const BucketT *BucketsPtr = getBuckets(); 446ce9a04132d1bf85967d6ad062d45dd75f148eef1Chandler Carruth const unsigned NumBuckets = getNumBuckets(); 4473a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 448ce9a04132d1bf85967d6ad062d45dd75f148eef1Chandler Carruth if (NumBuckets == 0) { 44949d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer FoundBucket = 0; 45049d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer return false; 45149d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer } 45249d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer 4536e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // FoundTombstone - Keep track of whether we find a tombstone while probing. 454dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const BucketT *FoundTombstone = 0; 4556e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT EmptyKey = getEmptyKey(); 4566e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner const KeyT TombstoneKey = getTombstoneKey(); 45705831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner assert(!KeyInfoT::isEqual(Val, EmptyKey) && 45805831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner !KeyInfoT::isEqual(Val, TombstoneKey) && 4596e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner "Empty/Tombstone value shouldn't be inserted into map!"); 4603a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 461ce9a04132d1bf85967d6ad062d45dd75f148eef1Chandler Carruth unsigned BucketNo = getHashValue(Val) & (NumBuckets-1); 462ce9a04132d1bf85967d6ad062d45dd75f148eef1Chandler Carruth unsigned ProbeAmt = 1; 4636e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner while (1) { 464ce9a04132d1bf85967d6ad062d45dd75f148eef1Chandler Carruth const BucketT *ThisBucket = BucketsPtr + BucketNo; 4656e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Found Val's bucket? If so, return it. 466babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin if (KeyInfoT::isEqual(Val, ThisBucket->first)) { 4676e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundBucket = ThisBucket; 4686e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return true; 4696e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 4703a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4716e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If we found an empty bucket, the key doesn't exist in the set. 4726e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Insert it and return the default value. 47376c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner if (KeyInfoT::isEqual(ThisBucket->first, EmptyKey)) { 4746e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If we've already seen a tombstone while probing, fill it in instead 4756e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // of the empty bucket we eventually probed to. 4766e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner if (FoundTombstone) ThisBucket = FoundTombstone; 4776e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket; 4786e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner return false; 4796e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 4803a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4816e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // If this is a tombstone, remember it. If Val ends up not in the map, we 4826e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // prefer to return it than something that would require more probing. 48376c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner if (KeyInfoT::isEqual(ThisBucket->first, TombstoneKey) && !FoundTombstone) 4846e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner FoundTombstone = ThisBucket; // Remember the first tombstone found. 4853a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 4866e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // Otherwise, it's a hash collision or a tombstone, continue quadratic 4876e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner // probing. 4886e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner BucketNo += ProbeAmt++; 489ce9a04132d1bf85967d6ad062d45dd75f148eef1Chandler Carruth BucketNo &= (NumBuckets-1); 4906e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 4916e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 4926e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 493dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth template <typename LookupKeyT> 494dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth bool LookupBucketFor(const LookupKeyT &Val, BucketT *&FoundBucket) { 49590420105964371571ccacdf47771c6ca05db2e67David Blaikie const BucketT *ConstFoundBucket; 496dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth bool Result = const_cast<const DenseMapBase *>(this) 497dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth ->LookupBucketFor(Val, ConstFoundBucket); 498dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth FoundBucket = const_cast<BucketT *>(ConstFoundBucket); 499dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return Result; 500dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 501dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 5027f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthpublic: 5037f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth /// Return the approximate size (in bytes) of the actual map. 5047f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth /// This is just the raw memory used by DenseMap. 5057f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth /// If entries are pointers to objects, the size of the referenced objects 5067f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth /// are not included. 5077f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth size_t getMemorySize() const { 5087f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return getNumBuckets() * sizeof(BucketT); 5097f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5107f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth}; 51149d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer 5127f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthtemplate<typename KeyT, typename ValueT, 5137f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth typename KeyInfoT = DenseMapInfo<KeyT> > 5147f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthclass DenseMap 5157f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT>, 5167f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth KeyT, ValueT, KeyInfoT> { 5177f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth // Lift some types from the dependent base class into this class for 5187f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth // simplicity of referring to them. 5197f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth typedef DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT> BaseT; 5207f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth typedef typename BaseT::BucketT BucketT; 5217f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth friend class DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT>; 52249d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer 5237f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth BucketT *Buckets; 52448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned NumEntries; 52548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned NumTombstones; 5267f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth unsigned NumBuckets; 5277f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 5287f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthpublic: 5297f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth explicit DenseMap(unsigned NumInitBuckets = 0) { 5307f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth init(NumInitBuckets); 5316e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 5323a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5337f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth DenseMap(const DenseMap &other) { 5347f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth init(0); 5357f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth copyFrom(other); 5367f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5373a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5387f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth#if LLVM_USE_RVALUE_REFERENCES 5397f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth DenseMap(DenseMap &&other) { 5407f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth init(0); 5417f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth swap(other); 5427f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5437f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth#endif 54449d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer 5457f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth template<typename InputIt> 5467f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth DenseMap(const InputIt &I, const InputIt &E) { 5477f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth init(NextPowerOf2(std::distance(I, E))); 5487f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->insert(I, E); 5497f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5506e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 5517f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth ~DenseMap() { 5527f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->destroyAll(); 5537f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth operator delete(Buckets); 5547f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5556e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 5567f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void swap(DenseMap& RHS) { 5577f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth std::swap(Buckets, RHS.Buckets); 55848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth std::swap(NumEntries, RHS.NumEntries); 55948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth std::swap(NumTombstones, RHS.NumTombstones); 56048f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth std::swap(NumBuckets, RHS.NumBuckets); 5617f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5623a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5637f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth DenseMap& operator=(const DenseMap& other) { 5647f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth copyFrom(other); 5657f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return *this; 5667f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5677f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 5687f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth#if LLVM_USE_RVALUE_REFERENCES 5697f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth DenseMap& operator=(DenseMap &&other) { 5707f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->destroyAll(); 5717f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth operator delete(Buckets); 5727f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth init(0); 5737f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth swap(other); 5747f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return *this; 5757f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 576d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#endif 5777f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 5787f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void copyFrom(const DenseMap& other) { 5797f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->destroyAll(); 5807f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth operator delete(Buckets); 58148f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth if (allocateBuckets(other.NumBuckets)) { 5827f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->BaseT::copyFrom(other); 58348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } else { 58448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth NumEntries = 0; 58548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth NumTombstones = 0; 58648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 5876e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner } 5883a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 5897f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void init(unsigned InitBuckets) { 59048f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth if (allocateBuckets(InitBuckets)) { 5917f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->BaseT::initEmpty(); 59248f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } else { 59348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth NumEntries = 0; 59448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth NumTombstones = 0; 59548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 5967f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 5977f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 5987f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void grow(unsigned AtLeast) { 5996ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson unsigned OldNumBuckets = NumBuckets; 6006ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson BucketT *OldBuckets = Buckets; 6013a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 6027f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth allocateBuckets(std::max<unsigned>(64, NextPowerOf2(AtLeast))); 6037f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth assert(Buckets); 6047f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth if (!OldBuckets) { 6057f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->BaseT::initEmpty(); 6067f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return; 6076ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 6083a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 6097f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->moveFromOldBuckets(OldBuckets, OldBuckets+OldNumBuckets); 6107f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 6116ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson // Free the old table. 61208c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman operator delete(OldBuckets); 6137f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 6143a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 6157f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth void shrink_and_clear() { 61648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned OldNumEntries = NumEntries; 6177f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->destroyAll(); 6187f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 6197f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth // Reduce the number of buckets. 6207f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth unsigned NewNumBuckets 62148f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth = std::max(64, 1 << (Log2_32_Ceil(OldNumEntries) + 1)); 6227f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth if (NewNumBuckets == NumBuckets) { 6237f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth this->BaseT::initEmpty(); 6247f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return; 6257f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 6267f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 6277f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth operator delete(Buckets); 6287f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth init(NewNumBuckets); 6296ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson } 6307f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 6317f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthprivate: 63248f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned getNumEntries() const { 63348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth return NumEntries; 63448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 63548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth void setNumEntries(unsigned Num) { 63648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth NumEntries = Num; 63748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 63848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth 63948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth unsigned getNumTombstones() const { 64048f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth return NumTombstones; 64148f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 64248f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth void setNumTombstones(unsigned Num) { 64348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth NumTombstones = Num; 64448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth } 64548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth 6467f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth BucketT *getBuckets() const { 6477f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return Buckets; 6487f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 6497f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 6507f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth unsigned getNumBuckets() const { 6517f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return NumBuckets; 6527f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 6537f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 6547f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth bool allocateBuckets(unsigned Num) { 6557f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth NumBuckets = Num; 6567f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth if (NumBuckets == 0) { 6577f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth Buckets = 0; 6587f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return false; 6597f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth } 6607f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth 6617f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT) * NumBuckets)); 6627f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth return true; 663e6b693db8cc07be91229bef0d8577ce8b5caf34bTed Kremenek } 6646e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner}; 6656e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 66681cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskintemplate<typename KeyT, typename ValueT, 667dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned InlineBuckets = 4, 668dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth typename KeyInfoT = DenseMapInfo<KeyT> > 669dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruthclass SmallDenseMap 670dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth : public DenseMapBase<SmallDenseMap<KeyT, ValueT, InlineBuckets, KeyInfoT>, 671dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth KeyT, ValueT, KeyInfoT> { 672dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // Lift some types from the dependent base class into this class for 673dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // simplicity of referring to them. 674dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth typedef DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT> BaseT; 675dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth typedef typename BaseT::BucketT BucketT; 676dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth friend class DenseMapBase<SmallDenseMap, KeyT, ValueT, KeyInfoT>; 677dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 678dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned Small : 1; 679dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned NumEntries : 31; 680dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned NumTombstones; 681dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 682dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth struct LargeRep { 683dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth BucketT *Buckets; 684dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned NumBuckets; 685dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth }; 686dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 687dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth /// A "union" of an inline bucket array and the struct representing 688dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth /// a large bucket. This union will be discriminated by the 'Small' bit. 689dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth typename AlignedCharArray<BucketT[InlineBuckets], LargeRep>::union_type 690dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth storage; 691dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 692dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruthpublic: 693dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth explicit SmallDenseMap(unsigned NumInitBuckets = 0) { 694dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth init(NumInitBuckets); 695dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 696dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 697dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth SmallDenseMap(const SmallDenseMap &other) { 698dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth init(0); 699dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth copyFrom(other); 700dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 701dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 702dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth#if LLVM_USE_RVALUE_REFERENCES 703dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth SmallDenseMap(SmallDenseMap &&other) { 704dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth init(0); 705dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth swap(other); 706dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 707dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth#endif 708dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 709dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth template<typename InputIt> 710dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth SmallDenseMap(const InputIt &I, const InputIt &E) { 711dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth init(NextPowerOf2(std::distance(I, E))); 712dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->insert(I, E); 713dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 714dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 715dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth ~SmallDenseMap() { 716dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->destroyAll(); 717dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth deallocateBuckets(); 718dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 719dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 720dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth void swap(SmallDenseMap& RHS) { 7218dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth unsigned TmpNumEntries = RHS.NumEntries; 7228dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth RHS.NumEntries = NumEntries; 7238dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth NumEntries = TmpNumEntries; 724dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth std::swap(NumTombstones, RHS.NumTombstones); 7258dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth 7268dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth const KeyT EmptyKey = this->getEmptyKey(); 7278dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth const KeyT TombstoneKey = this->getTombstoneKey(); 728dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (Small && RHS.Small) { 7298dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth // If we're swapping inline bucket arrays, we have to cope with some of 7308dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth // the tricky bits of DenseMap's storage system: the buckets are not 7318dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth // fully initialized. Thus we swap every key, but we may have 7328dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth // a one-directional move of the value. 7338dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth for (unsigned i = 0, e = InlineBuckets; i != e; ++i) { 7348dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth BucketT *LHSB = &getInlineBuckets()[i], 7358dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth *RHSB = &RHS.getInlineBuckets()[i]; 7368dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth bool hasLHSValue = (!KeyInfoT::isEqual(LHSB->first, EmptyKey) && 7378dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth !KeyInfoT::isEqual(LHSB->first, TombstoneKey)); 7388dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth bool hasRHSValue = (!KeyInfoT::isEqual(RHSB->first, EmptyKey) && 7398dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth !KeyInfoT::isEqual(RHSB->first, TombstoneKey)); 7408dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth if (hasLHSValue && hasRHSValue) { 7418dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth // Swap together if we can... 7428dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth std::swap(*LHSB, *RHSB); 7438dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth continue; 7448dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth } 7458dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth // Swap separately and handle any assymetry. 7468dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth std::swap(LHSB->first, RHSB->first); 7478dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth if (hasLHSValue) { 7488dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth new (&RHSB->second) ValueT(llvm_move(LHSB->second)); 7498dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth LHSB->second.~ValueT(); 7508dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth } else if (hasRHSValue) { 7518dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth new (&LHSB->second) ValueT(llvm_move(RHSB->second)); 7528dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth RHSB->second.~ValueT(); 7538dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth } 7548dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth } 755dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return; 756dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 757dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (!Small && !RHS.Small) { 758dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth std::swap(getLargeRep()->Buckets, RHS.getLargeRep()->Buckets); 759dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth std::swap(getLargeRep()->NumBuckets, RHS.getLargeRep()->NumBuckets); 760dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return; 761dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 762dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 763dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth SmallDenseMap &SmallSide = Small ? *this : RHS; 764dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth SmallDenseMap &LargeSide = Small ? RHS : *this; 765dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 766dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // First stash the large side's rep and move the small side across. 767dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth LargeRep TmpRep = llvm_move(*LargeSide.getLargeRep()); 768dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth LargeSide.getLargeRep()->~LargeRep(); 769dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth LargeSide.Small = true; 770dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // This is similar to the standard move-from-old-buckets, but the bucket 7718dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth // count hasn't actually rotated in this case. So we have to carefully 772dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // move construct the keys and values into their new locations, but there 773dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // is no need to re-hash things. 774dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth for (unsigned i = 0, e = InlineBuckets; i != e; ++i) { 775dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth BucketT *NewB = &LargeSide.getInlineBuckets()[i], 776dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth *OldB = &SmallSide.getInlineBuckets()[i]; 777dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth new (&NewB->first) KeyT(llvm_move(OldB->first)); 7788dffa4a106b52d893388c94c24e365e14c468b7cChandler Carruth OldB->first.~KeyT(); 779dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (!KeyInfoT::isEqual(NewB->first, EmptyKey) && 780dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth !KeyInfoT::isEqual(NewB->first, TombstoneKey)) { 781dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth new (&NewB->second) ValueT(llvm_move(OldB->second)); 782dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth OldB->second.~ValueT(); 783dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 784dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 785dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 786dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // The hard part of moving the small buckets across is done, just move 787dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // the TmpRep into its new home. 788dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth SmallSide.Small = false; 789dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth new (SmallSide.getLargeRep()) LargeRep(llvm_move(TmpRep)); 790dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 791dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 792dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth SmallDenseMap& operator=(const SmallDenseMap& other) { 793dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth copyFrom(other); 794dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return *this; 795dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 796dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 797dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth#if LLVM_USE_RVALUE_REFERENCES 798dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth SmallDenseMap& operator=(SmallDenseMap &&other) { 799dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->destroyAll(); 800dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth deallocateBuckets(); 801dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth init(0); 802dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth swap(other); 803dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return *this; 804dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 805dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth#endif 806dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 807dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth void copyFrom(const SmallDenseMap& other) { 808dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->destroyAll(); 809dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth deallocateBuckets(); 810dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth Small = true; 811dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (other.getNumBuckets() > InlineBuckets) { 812dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth Small = false; 813dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth allocateBuckets(other.getNumBuckets()); 814dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 815dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->BaseT::copyFrom(other); 816dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 817dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 818dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth void init(unsigned InitBuckets) { 819dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth Small = true; 820dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (InitBuckets > InlineBuckets) { 821dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth Small = false; 822dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth new (getLargeRep()) LargeRep(allocateBuckets(InitBuckets)); 823dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 824dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->BaseT::initEmpty(); 825dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 826dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 827dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth void grow(unsigned AtLeast) { 828dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (AtLeast > InlineBuckets) 829dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth AtLeast = std::max<unsigned>(64, NextPowerOf2(AtLeast)); 830dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 831dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (Small) { 832dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (AtLeast <= InlineBuckets) 833dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return; // Nothing to do. 834dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 8356446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth // First move the inline buckets into a temporary storage. 8366446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth typename AlignedCharArray<BucketT[InlineBuckets]>::union_type 8376446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth TmpStorage; 8386446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth BucketT *TmpBegin = reinterpret_cast<BucketT *>(TmpStorage.buffer); 8396446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth BucketT *TmpEnd = TmpBegin; 8406446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth 8416446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth // Loop over the buckets, moving non-empty, non-tombstones into the 8426446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth // temporary storage. Have the loop move the TmpEnd forward as it goes. 8436446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth const KeyT EmptyKey = this->getEmptyKey(); 8446446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth const KeyT TombstoneKey = this->getTombstoneKey(); 8456446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth for (BucketT *P = getBuckets(), *E = P + InlineBuckets; P != E; ++P) { 8466446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth if (!KeyInfoT::isEqual(P->first, EmptyKey) && 8476446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth !KeyInfoT::isEqual(P->first, TombstoneKey)) { 848ac24e251014de60a16558fc0a1f2340c334d2aa8Benjamin Kramer assert(size_t(TmpEnd - TmpBegin) < InlineBuckets && 8496446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth "Too many inline buckets!"); 8506446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth new (&TmpEnd->first) KeyT(llvm_move(P->first)); 8516446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth new (&TmpEnd->second) ValueT(llvm_move(P->second)); 8526446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth ++TmpEnd; 8536446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth P->second.~ValueT(); 8546446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth } 8556446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth P->first.~KeyT(); 8566446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth } 8576446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth 8586446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth // Now make this map use the large rep, and move all the entries back 8596446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth // into it. 860dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth Small = false; 8616446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth new (getLargeRep()) LargeRep(allocateBuckets(AtLeast)); 8626446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruth this->moveFromOldBuckets(TmpBegin, TmpEnd); 863dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return; 864dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 865dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 866dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth LargeRep OldRep = llvm_move(*getLargeRep()); 867dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth getLargeRep()->~LargeRep(); 868dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (AtLeast <= InlineBuckets) { 869dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth Small = true; 870dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } else { 871dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth new (getLargeRep()) LargeRep(allocateBuckets(AtLeast)); 872dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 873dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 874dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->moveFromOldBuckets(OldRep.Buckets, OldRep.Buckets+OldRep.NumBuckets); 875dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 876dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // Free the old table. 877dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth operator delete(OldRep.Buckets); 878dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 879dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 880dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth void shrink_and_clear() { 881dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned OldSize = this->size(); 882dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->destroyAll(); 883dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 884dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // Reduce the number of buckets. 885dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned NewNumBuckets = 0; 886dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (OldSize) { 887dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth NewNumBuckets = 1 << (Log2_32_Ceil(OldSize) + 1); 888dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (NewNumBuckets > InlineBuckets && NewNumBuckets < 64u) 889dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth NewNumBuckets = 64; 890dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 891dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if ((Small && NewNumBuckets <= InlineBuckets) || 892dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth (!Small && NewNumBuckets == getLargeRep()->NumBuckets)) { 893dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth this->BaseT::initEmpty(); 894dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return; 895dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 896dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 897dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth deallocateBuckets(); 898dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth init(NewNumBuckets); 899dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 900dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 901dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruthprivate: 902dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned getNumEntries() const { 903dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return NumEntries; 904dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 905dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth void setNumEntries(unsigned Num) { 906dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth assert(Num < INT_MAX && "Cannot support more than INT_MAX entries"); 907dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth NumEntries = Num; 908dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 909dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 910dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned getNumTombstones() const { 911dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return NumTombstones; 912dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 913dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth void setNumTombstones(unsigned Num) { 914dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth NumTombstones = Num; 915dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 916dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 917dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const BucketT *getInlineBuckets() const { 918dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth assert(Small); 919dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // Note that this cast does not violate aliasing rules as we assert that 920dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // the memory's dynamic type is the small, inline bucket buffer, and the 921dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // 'storage.buffer' static type is 'char *'. 922dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return reinterpret_cast<const BucketT *>(storage.buffer); 923dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 924dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth BucketT *getInlineBuckets() { 925dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return const_cast<BucketT *>( 926dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const_cast<const SmallDenseMap *>(this)->getInlineBuckets()); 927dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 928dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const LargeRep *getLargeRep() const { 929dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth assert(!Small); 930dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth // Note, same rule about aliasing as with getInlineBuckets. 931dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return reinterpret_cast<const LargeRep *>(storage.buffer); 932dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 933dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth LargeRep *getLargeRep() { 934dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return const_cast<LargeRep *>( 935dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const_cast<const SmallDenseMap *>(this)->getLargeRep()); 936dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 937dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 938dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const BucketT *getBuckets() const { 939dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return Small ? getInlineBuckets() : getLargeRep()->Buckets; 940dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 941dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth BucketT *getBuckets() { 942dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return const_cast<BucketT *>( 943dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth const_cast<const SmallDenseMap *>(this)->getBuckets()); 944dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 945dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth unsigned getNumBuckets() const { 946dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return Small ? InlineBuckets : getLargeRep()->NumBuckets; 947dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 948dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 949dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth void deallocateBuckets() { 950dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth if (Small) 951dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return; 952dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 953dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth operator delete(getLargeRep()->Buckets); 954dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth getLargeRep()->~LargeRep(); 955dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 956dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 957dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth LargeRep allocateBuckets(unsigned Num) { 958dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth assert(Num > InlineBuckets && "Must allocate more buckets than are inline"); 959dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth LargeRep Rep = { 960dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth static_cast<BucketT*>(operator new(sizeof(BucketT) * Num)), Num 961dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth }; 962dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth return Rep; 963dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth } 964dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth}; 965dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth 966dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruthtemplate<typename KeyT, typename ValueT, 9674e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer typename KeyInfoT, bool IsConst> 96881cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskinclass DenseMapIterator { 96981cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef std::pair<KeyT, ValueT> Bucket; 97081cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef DenseMapIterator<KeyT, ValueT, 9714e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer KeyInfoT, true> ConstIterator; 9724e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, true>; 97381cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskinpublic: 97481cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef ptrdiff_t difference_type; 97581cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef typename conditional<IsConst, const Bucket, Bucket>::type value_type; 97681cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef value_type *pointer; 97781cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef value_type &reference; 97881cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin typedef std::forward_iterator_tag iterator_category; 97981cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskinprivate: 98081cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin pointer Ptr, End; 981f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerpublic: 982a9ad04191cb56c42944b17980b8b2bb2afe11ab2Dan Gohman DenseMapIterator() : Ptr(0), End(0) {} 98313e781ebe7a39e008dd5e5de78983e095e8a1d02David Greene 984f0be7ca7e42915779175a9332c6baba18a2a840cBenjamin Kramer DenseMapIterator(pointer Pos, pointer E, bool NoAdvance = false) 985f0be7ca7e42915779175a9332c6baba18a2a840cBenjamin Kramer : Ptr(Pos), End(E) { 986f0be7ca7e42915779175a9332c6baba18a2a840cBenjamin Kramer if (!NoAdvance) AdvancePastEmptyBuckets(); 987f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 9883a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 98981cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin // If IsConst is true this is a converting constructor from iterator to 99081cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin // const_iterator and the default copy constructor is used. 99181cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin // Otherwise this is a copy constructor for iterator. 99281cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin DenseMapIterator(const DenseMapIterator<KeyT, ValueT, 9934e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer KeyInfoT, false>& I) 99481cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin : Ptr(I.Ptr), End(I.End) {} 99581cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin 99681cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin reference operator*() const { 99781cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin return *Ptr; 998f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 99981cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin pointer operator->() const { 100081cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin return Ptr; 1001f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 10023a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 100381cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin bool operator==(const ConstIterator &RHS) const { 100481cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin return Ptr == RHS.operator->(); 1005f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 100681cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin bool operator!=(const ConstIterator &RHS) const { 100781cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin return Ptr != RHS.operator->(); 1008f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 10093a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 10104ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin inline DenseMapIterator& operator++() { // Preincrement 1011f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner ++Ptr; 1012f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner AdvancePastEmptyBuckets(); 1013f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner return *this; 1014f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 10154ab74cdc124af6b4f57c2d2d09548e01d64a1f34Jeffrey Yasskin DenseMapIterator operator++(int) { // Postincrement 1016f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner DenseMapIterator tmp = *this; ++*this; return tmp; 1017f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 10183a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1019f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattnerprivate: 1020f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner void AdvancePastEmptyBuckets() { 1021a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner const KeyT Empty = KeyInfoT::getEmptyKey(); 1022a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner const KeyT Tombstone = KeyInfoT::getTombstoneKey(); 1023f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 10243a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman while (Ptr != End && 102576c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner (KeyInfoT::isEqual(Ptr->first, Empty) || 102676c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner KeyInfoT::isEqual(Ptr->first, Tombstone))) 1027f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner ++Ptr; 1028f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner } 1029f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner}; 103018dceba0bb5e38250535401ecc9d9737943d0657Ted Kremenek 10314e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramertemplate<typename KeyT, typename ValueT, typename KeyInfoT> 103218dceba0bb5e38250535401ecc9d9737943d0657Ted Kremenekstatic inline size_t 10334e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramercapacity_in_bytes(const DenseMap<KeyT, ValueT, KeyInfoT> &X) { 103418dceba0bb5e38250535401ecc9d9737943d0657Ted Kremenek return X.getMemorySize(); 103518dceba0bb5e38250535401ecc9d9737943d0657Ted Kremenek} 1036f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner 10376e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner} // end namespace llvm 10386e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner 10396e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner#endif 1040