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:
46cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines  typedef unsigned size_type;
4713e781ebe7a39e008dd5e5de78983e095e8a1d02David Greene  typedef KeyT key_type;
4813e781ebe7a39e008dd5e5de78983e095e8a1d02David Greene  typedef ValueT mapped_type;
49aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek  typedef BucketT value_type;
503a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman
51a76b1febd4fd258e8054395adedcbd477668d956Chris Lattner  typedef DenseMapIterator<KeyT, ValueT, KeyInfoT> iterator;
5281cf4325698b48b02eddab921ac333c7f25005c3Jeffrey Yasskin  typedef DenseMapIterator<KeyT, ValueT,
534e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer                           KeyInfoT, true> const_iterator;
5470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner  inline iterator begin() {
55b843d9f833aa474ae700363a445b7409665c4a6eJakob Stoklund Olesen    // When the map is empty, avoid the overhead of AdvancePastEmptyBuckets().
567f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    return empty() ? end() : iterator(getBuckets(), getBucketsEnd());
5770a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner  }
5870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner  inline iterator end() {
597f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    return iterator(getBucketsEnd(), getBucketsEnd(), true);
6070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner  }
6170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner  inline const_iterator begin() const {
627f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    return empty() ? end() : const_iterator(getBuckets(), getBucketsEnd());
6370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner  }
6470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner  inline const_iterator end() const {
657f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    return const_iterator(getBucketsEnd(), getBucketsEnd(), true);
6670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner  }
673a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman
68cbe40cfe96a6bb3f2da56445269c2c71e55e0e56Benjamin Kramer  bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const {
69cbe40cfe96a6bb3f2da56445269c2c71e55e0e56Benjamin Kramer    return getNumEntries() == 0;
70cbe40cfe96a6bb3f2da56445269c2c71e55e0e56Benjamin Kramer  }
7148f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth  unsigned size() const { return getNumEntries(); }
72d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin
73d81ccc2806b2c8a498d16f1a547d0cc9c00d602dDaniel Berlin  /// Grow the densemap so that it has at least Size buckets. Does not shrink
74cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines  void resize(size_type Size) {
757f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    if (Size > getNumBuckets())
7649d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer      grow(Size);
7749d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer  }
783a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman
796e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner  void clear() {
8048f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth    if (getNumEntries() == 0 && getNumTombstones() == 0) return;
81255cd6f317f3a0bad6e7939ca5ce49b33c6676f9NAKAMURA Takumi
8242e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner    // If the capacity of the array is huge, and the # elements used is small,
8342e4bdf2577946380ce1529d5716e48b33d4186dChris Lattner    // shrink the array.
8448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth    if (getNumEntries() * 4 < getNumBuckets() && getNumBuckets() > 64) {
856ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson      shrink_and_clear();
866ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson      return;
876ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson    }
883a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman
896e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner    const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
907f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) {
9105831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner      if (!KeyInfoT::isEqual(P->first, EmptyKey)) {
9205831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner        if (!KeyInfoT::isEqual(P->first, TombstoneKey)) {
937b54452c84e478ab4d49ac08759ca4ec1badf2b2Chris Lattner          P->second.~ValueT();
9448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth          decrementNumEntries();
957b54452c84e478ab4d49ac08759ca4ec1badf2b2Chris Lattner        }
96f6390f48e6324b0221d10a9c75ab625357d8a43aChris Lattner        P->first = EmptyKey;
976e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner      }
986e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner    }
9948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth    assert(getNumEntries() == 0 && "Node count imbalance!");
10048f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth    setNumTombstones(0);
1016e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner  }
1026ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson
103cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines  /// Return 1 if the specified key is in the map, 0 otherwise.
104cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines  size_type count(const KeyT &Val) const {
105dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth    const BucketT *TheBucket;
106cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines    return LookupBucketFor(Val, TheBucket) ? 1 : 0;
1076e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner  }
1083a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman
109569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner  iterator find(const KeyT &Val) {
11070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner    BucketT *TheBucket;
11170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner    if (LookupBucketFor(Val, TheBucket))
1127f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth      return iterator(TheBucket, getBucketsEnd(), true);
11370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner    return end();
11470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner  }
115569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner  const_iterator find(const KeyT &Val) const {
116dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth    const BucketT *TheBucket;
117569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner    if (LookupBucketFor(Val, TheBucket))
1187f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth      return const_iterator(TheBucket, getBucketsEnd(), true);
119569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner    return end();
120569b935e6b23c4a0e4ebb2c96603974310ef0587Chris Lattner  }
1213a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman
122babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin  /// Alternate version of find() which allows a different, and possibly
123babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin  /// less expensive, key type.
124babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin  /// The DenseMapInfo is responsible for supplying methods
125babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin  /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key
126babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin  /// type used.
127babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin  template<class LookupKeyT>
128babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin  iterator find_as(const LookupKeyT &Val) {
129babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin    BucketT *TheBucket;
130babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin    if (LookupBucketFor(Val, TheBucket))
1317f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth      return iterator(TheBucket, getBucketsEnd(), true);
132babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin    return end();
133babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin  }
134babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin  template<class LookupKeyT>
135babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin  const_iterator find_as(const LookupKeyT &Val) const {
136dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth    const BucketT *TheBucket;
137babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin    if (LookupBucketFor(Val, TheBucket))
1387f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth      return const_iterator(TheBucket, getBucketsEnd(), true);
139babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin    return end();
140babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin  }
141babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin
1427b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar  /// lookup - Return the entry for the specified key, or a default
1437b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar  /// constructed value if no such entry exists.
1447b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar  ValueT lookup(const KeyT &Val) const {
145dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth    const BucketT *TheBucket;
1467b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar    if (LookupBucketFor(Val, TheBucket))
1477b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar      return TheBucket->second;
1487b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar    return ValueT();
1497b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar  }
1507b75fbf224c0a2d181c35708a27c514ae798c904Daniel Dunbar
151127445818efd810b138dd5362129ab3c7f8b9963Torok Edwin  // Inserts key,value pair into the map if the key isn't already in the map.
152127445818efd810b138dd5362129ab3c7f8b9963Torok Edwin  // If the key is already in the map, it returns false and doesn't update the
153127445818efd810b138dd5362129ab3c7f8b9963Torok Edwin  // value.
1546b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman  std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
15528f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner    BucketT *TheBucket;
15628f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner    if (LookupBucketFor(KV.first, TheBucket))
1577f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth      return std::make_pair(iterator(TheBucket, getBucketsEnd(), true),
1586b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman                            false); // Already in map.
1593a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman
16028f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner    // Otherwise, insert the new element.
1616b345ee9b2833cf1b2f79dc16d06d4060bec36efDan Gohman    TheBucket = InsertIntoBucket(KV.first, KV.second, TheBucket);
1627f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), true);
16328f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner  }
1643a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman
165a662a9862501fc86904e90054f7c1519101d9126Joe Groff  // Inserts key,value pair into the map if the key isn't already in the map.
166a662a9862501fc86904e90054f7c1519101d9126Joe Groff  // If the key is already in the map, it returns false and doesn't update the
167a662a9862501fc86904e90054f7c1519101d9126Joe Groff  // value.
168a662a9862501fc86904e90054f7c1519101d9126Joe Groff  std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) {
169a662a9862501fc86904e90054f7c1519101d9126Joe Groff    BucketT *TheBucket;
170a662a9862501fc86904e90054f7c1519101d9126Joe Groff    if (LookupBucketFor(KV.first, TheBucket))
171a662a9862501fc86904e90054f7c1519101d9126Joe Groff      return std::make_pair(iterator(TheBucket, getBucketsEnd(), true),
172a662a9862501fc86904e90054f7c1519101d9126Joe Groff                            false); // Already in map.
173a662a9862501fc86904e90054f7c1519101d9126Joe Groff
174a662a9862501fc86904e90054f7c1519101d9126Joe Groff    // Otherwise, insert the new element.
175a662a9862501fc86904e90054f7c1519101d9126Joe Groff    TheBucket = InsertIntoBucket(std::move(KV.first),
176a662a9862501fc86904e90054f7c1519101d9126Joe Groff                                 std::move(KV.second),
177a662a9862501fc86904e90054f7c1519101d9126Joe Groff                                 TheBucket);
178a662a9862501fc86904e90054f7c1519101d9126Joe Groff    return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), true);
179a662a9862501fc86904e90054f7c1519101d9126Joe Groff  }
18036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines
181b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner  /// insert - Range insertion of pairs.
182b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner  template<typename InputIt>
183b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner  void insert(InputIt I, InputIt E) {
184b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner    for (; I != E; ++I)
185b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner      insert(*I);
186b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner  }
187b6bbe6320b4a60b7399eea08426aec834701d514Chris Lattner
1883a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman
18970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner  bool erase(const KeyT &Val) {
19070a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner    BucketT *TheBucket;
19170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner    if (!LookupBucketFor(Val, TheBucket))
19270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner      return false; // not in map.
19370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner
19470a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner    TheBucket->second.~ValueT();
19570a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner    TheBucket->first = getTombstoneKey();
19648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth    decrementNumEntries();
19748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth    incrementNumTombstones();
19870a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner    return true;
19970a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner  }
200e3955df639ff9aff990f628ef6a219ff5efdbc81Dan Gohman  void erase(iterator I) {
20170a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner    BucketT *TheBucket = &*I;
20270a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner    TheBucket->second.~ValueT();
20370a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner    TheBucket->first = getTombstoneKey();
20448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth    decrementNumEntries();
20548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth    incrementNumTombstones();
20670a76a633ed5101dbe472404efd989f4f1b3669cChris Lattner  }
207aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek
208aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek  value_type& FindAndConstruct(const KeyT &Key) {
2096e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner    BucketT *TheBucket;
21028f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner    if (LookupBucketFor(Key, TheBucket))
211aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek      return *TheBucket;
2123a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman
213aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek    return *InsertIntoBucket(Key, ValueT(), TheBucket);
214aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek  }
2153a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman
216aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek  ValueT &operator[](const KeyT &Key) {
217aef806e9cb021919be8f3a988af0478f3da75758Ted Kremenek    return FindAndConstruct(Key).second;
21828f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner  }
2193a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman
220aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer  value_type& FindAndConstruct(KeyT &&Key) {
221aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer    BucketT *TheBucket;
222aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer    if (LookupBucketFor(Key, TheBucket))
223aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer      return *TheBucket;
224aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer
225da8b91a0731e34b97aadb0241ba6cefa4481cffaBenjamin Kramer    return *InsertIntoBucket(std::move(Key), ValueT(), TheBucket);
226aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer  }
227aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer
228aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer  ValueT &operator[](KeyT &&Key) {
229da8b91a0731e34b97aadb0241ba6cefa4481cffaBenjamin Kramer    return FindAndConstruct(std::move(Key)).second;
230aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer  }
231aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer
232bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner  /// isPointerIntoBucketsArray - Return true if the specified pointer points
233bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner  /// somewhere into the DenseMap's array of buckets (i.e. either to a key or
234bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner  /// value in the DenseMap).
235bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner  bool isPointerIntoBucketsArray(const void *Ptr) const {
2367f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    return Ptr >= getBuckets() && Ptr < getBucketsEnd();
237bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner  }
238bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner
239bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner  /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets
240bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner  /// array.  In conjunction with the previous method, this can be used to
241bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner  /// determine whether an insertion caused the DenseMap to reallocate.
2427f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  const void *getPointerIntoBucketsArray() const { return getBuckets(); }
243bdd376ccb25f251e115fff24b526b4e65e03a1d3Chris Lattner
2447f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthprotected:
24548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth  DenseMapBase() {}
2467f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth
2477f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  void destroyAll() {
2487f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    if (getNumBuckets() == 0) // Nothing to do.
2498e337120133c746640246feb9383556d383a94beBenjamin Kramer      return;
2508e337120133c746640246feb9383556d383a94beBenjamin Kramer
251295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer    const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
2527f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) {
253295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer      if (!KeyInfoT::isEqual(P->first, EmptyKey) &&
254295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer          !KeyInfoT::isEqual(P->first, TombstoneKey))
255295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer        P->second.~ValueT();
256295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer      P->first.~KeyT();
25767280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson    }
2583a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman
259d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#ifndef NDEBUG
2607f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    memset((void*)getBuckets(), 0x5a, sizeof(BucketT)*getNumBuckets());
261d06c59821a1ca0191ea8a326a18509808a02ed03Torok Edwin#endif
262295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer  }
26388b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer
2647f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  void initEmpty() {
26548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth    setNumEntries(0);
26648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth    setNumTombstones(0);
2677f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth
2687f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    assert((getNumBuckets() & (getNumBuckets()-1)) == 0 &&
2697f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth           "# initial buckets must be a power of two!");
2707f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    const KeyT EmptyKey = getEmptyKey();
2717f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    for (BucketT *B = getBuckets(), *E = getBucketsEnd(); B != E; ++B)
2727f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth      new (&B->first) KeyT(EmptyKey);
2737f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  }
274295d8ff007ef2c36a91141d7f7aa218f43c4c4b5Benjamin Kramer
2757f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  void moveFromOldBuckets(BucketT *OldBucketsBegin, BucketT *OldBucketsEnd) {
2767f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    initEmpty();
27788b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer
2787f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    // Insert all the old elements.
2797f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    const KeyT EmptyKey = getEmptyKey();
2807f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    const KeyT TombstoneKey = getTombstoneKey();
2817f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    for (BucketT *B = OldBucketsBegin, *E = OldBucketsEnd; B != E; ++B) {
2827f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth      if (!KeyInfoT::isEqual(B->first, EmptyKey) &&
2837f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth          !KeyInfoT::isEqual(B->first, TombstoneKey)) {
2847f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth        // Insert the key/value into the new table.
2857f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth        BucketT *DestBucket;
2867f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth        bool FoundVal = LookupBucketFor(B->first, DestBucket);
2877f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth        (void)FoundVal; // silence warning.
2887f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth        assert(!FoundVal && "Key already in new map?");
28936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines        DestBucket->first = std::move(B->first);
29036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines        new (&DestBucket->second) ValueT(std::move(B->second));
29148f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth        incrementNumEntries();
2927f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth
2937f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth        // Free the value.
2947f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth        B->second.~ValueT();
2957f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth      }
2967f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth      B->first.~KeyT();
29788b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer    }
29888b0c6a59a54a2d7b3763dfabb595ce0e09e658aBenjamin Kramer
2997f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth#ifndef NDEBUG
3007f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    if (OldBucketsBegin != OldBucketsEnd)
3017f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth      memset((void*)OldBucketsBegin, 0x5a,
3027f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth             sizeof(BucketT) * (OldBucketsEnd - OldBucketsBegin));
3037f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth#endif
3047f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  }
3057f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth
3067f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  template <typename OtherBaseT>
3077f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  void copyFrom(const DenseMapBase<OtherBaseT, KeyT, ValueT, KeyInfoT>& other) {
3087f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    assert(getNumBuckets() == other.getNumBuckets());
3097f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth
31048f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth    setNumEntries(other.getNumEntries());
31148f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth    setNumTombstones(other.getNumTombstones());
3123a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman
3134e58263459d7f9ae862b52adafe585b66411272fBenjamin Kramer    if (isPodLike<KeyT>::value && isPodLike<ValueT>::value)
3147f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth      memcpy(getBuckets(), other.getBuckets(),
3157f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth             getNumBuckets() * sizeof(BucketT));
3169544dc294f63ce116fbab398a8874ebf834cf41eOwen Anderson    else
3177f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth      for (size_t i = 0; i < getNumBuckets(); ++i) {
3187f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth        new (&getBuckets()[i].first) KeyT(other.getBuckets()[i].first);
3197f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth        if (!KeyInfoT::isEqual(getBuckets()[i].first, getEmptyKey()) &&
3207f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth            !KeyInfoT::isEqual(getBuckets()[i].first, getTombstoneKey()))
3217f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth          new (&getBuckets()[i].second) ValueT(other.getBuckets()[i].second);
3229544dc294f63ce116fbab398a8874ebf834cf41eOwen Anderson      }
32367280e1dd22cf9fa452c335d1e2328d13f158da1Owen Anderson  }
3243a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman
3257f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  void swap(DenseMapBase& RHS) {
32648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth    std::swap(getNumEntries(), RHS.getNumEntries());
32748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth    std::swap(getNumTombstones(), RHS.getNumTombstones());
3287f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  }
3297f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth
3307f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  static unsigned getHashValue(const KeyT &Val) {
3317f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    return KeyInfoT::getHashValue(Val);
3327f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  }
3337f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  template<typename LookupKeyT>
3347f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  static unsigned getHashValue(const LookupKeyT &Val) {
3357f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    return KeyInfoT::getHashValue(Val);
3367f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  }
3377f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  static const KeyT getEmptyKey() {
3387f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    return KeyInfoT::getEmptyKey();
3397f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  }
3407f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  static const KeyT getTombstoneKey() {
3417f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    return KeyInfoT::getTombstoneKey();
3427f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  }
3437f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth
3446446d7e6d641135bdf9dc315ed69d0b10067fbd6Chandler Carruthprivate:
34548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth  unsigned getNumEntries() const {
34648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth    return static_cast<const DerivedT *>(this)->getNumEntries();
34748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth  }
34848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth  void setNumEntries(unsigned Num) {
34948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth    static_cast<DerivedT *>(this)->setNumEntries(Num);
35048f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth  }
35148f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth  void incrementNumEntries() {
35248f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth    setNumEntries(getNumEntries() + 1);
35348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth  }
35448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth  void decrementNumEntries() {
35548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth    setNumEntries(getNumEntries() - 1);
35648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth  }
35748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth  unsigned getNumTombstones() const {
35848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth    return static_cast<const DerivedT *>(this)->getNumTombstones();
35948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth  }
36048f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth  void setNumTombstones(unsigned Num) {
36148f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth    static_cast<DerivedT *>(this)->setNumTombstones(Num);
36248f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth  }
36348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth  void incrementNumTombstones() {
36448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth    setNumTombstones(getNumTombstones() + 1);
36548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth  }
36648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth  void decrementNumTombstones() {
36748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth    setNumTombstones(getNumTombstones() - 1);
36848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth  }
369dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth  const BucketT *getBuckets() const {
3707f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    return static_cast<const DerivedT *>(this)->getBuckets();
3717f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  }
372dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth  BucketT *getBuckets() {
373dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth    return static_cast<DerivedT *>(this)->getBuckets();
374dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth  }
3757f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  unsigned getNumBuckets() const {
3767f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    return static_cast<const DerivedT *>(this)->getNumBuckets();
3777f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  }
378dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth  BucketT *getBucketsEnd() {
379dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth    return getBuckets() + getNumBuckets();
380dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth  }
381dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth  const BucketT *getBucketsEnd() const {
3827f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    return getBuckets() + getNumBuckets();
3837f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  }
3847f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth
3857f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  void grow(unsigned AtLeast) {
3867f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    static_cast<DerivedT *>(this)->grow(AtLeast);
3877f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  }
3887f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth
3897f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  void shrink_and_clear() {
3907f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    static_cast<DerivedT *>(this)->shrink_and_clear();
3917f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  }
3927f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth
3937f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth
39428f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner  BucketT *InsertIntoBucket(const KeyT &Key, const ValueT &Value,
39528f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner                            BucketT *TheBucket) {
396aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer    TheBucket = InsertIntoBucketImpl(Key, TheBucket);
397aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer
398aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer    TheBucket->first = Key;
399aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer    new (&TheBucket->second) ValueT(Value);
400aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer    return TheBucket;
401aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer  }
402aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer
403aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer  BucketT *InsertIntoBucket(const KeyT &Key, ValueT &&Value,
404aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer                            BucketT *TheBucket) {
405aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer    TheBucket = InsertIntoBucketImpl(Key, TheBucket);
406aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer
407aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer    TheBucket->first = Key;
408aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer    new (&TheBucket->second) ValueT(std::move(Value));
409aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer    return TheBucket;
410aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer  }
411aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer
412aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer  BucketT *InsertIntoBucket(KeyT &&Key, ValueT &&Value, BucketT *TheBucket) {
413aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer    TheBucket = InsertIntoBucketImpl(Key, TheBucket);
414aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer
415aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer    TheBucket->first = std::move(Key);
416aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer    new (&TheBucket->second) ValueT(std::move(Value));
417aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer    return TheBucket;
418aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer  }
419aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer
420aee60d4d42b913bd3e4958f32ec9e7f2cf28b0ffBenjamin Kramer  BucketT *InsertIntoBucketImpl(const KeyT &Key, BucketT *TheBucket) {
42104a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner    // If the load of the hash table is more than 3/4, or if fewer than 1/8 of
42204a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner    // the buckets are empty (meaning that many are filled with tombstones),
42304a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner    // grow the table.
42404a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner    //
42504a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner    // The later case is tricky.  For example, if we had one empty bucket with
42604a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner    // tons of tombstones, failing lookups (e.g. for insertion) would have to
42704a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner    // probe almost the entire table until it found the empty bucket.  If the
42804a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner    // table completely filled with tombstones, no lookup would ever succeed,
42904a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner    // causing infinite loops in lookup.
43048f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth    unsigned NewNumEntries = getNumEntries() + 1;
431dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth    unsigned NumBuckets = getNumBuckets();
432dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth    if (NewNumEntries*4 >= NumBuckets*3) {
433dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth      this->grow(NumBuckets * 2);
43428f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner      LookupBucketFor(Key, TheBucket);
435dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth      NumBuckets = getNumBuckets();
4362aaa47f396f185d28aa7855d345f7385681098e2Howard Hinnant    } else if (NumBuckets-(NewNumEntries+getNumTombstones()) <= NumBuckets/8) {
4372aaa47f396f185d28aa7855d345f7385681098e2Howard Hinnant      this->grow(NumBuckets);
438414fdbdb0104fdc8c570287f94df8bb697e7b7c1Jakob Stoklund Olesen      LookupBucketFor(Key, TheBucket);
439414fdbdb0104fdc8c570287f94df8bb697e7b7c1Jakob Stoklund Olesen    }
4403bbdddf527c762085802544665d6e77471ea035bJordan Rose    assert(TheBucket);
4413a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman
4427f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    // Only update the state after we've grown our bucket space appropriately
4437f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    // so that when growing buckets we have self-consistent entry count.
44448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth    incrementNumEntries();
4457f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth
44604a3115e619740245cbe34c8c7428b4bde7868f7Chris Lattner    // If we are writing over a tombstone, remember this.
4475d295b41a3f4194778b6bc01a828b2115bd3a3f1NAKAMURA Takumi    const KeyT EmptyKey = getEmptyKey();
4485d295b41a3f4194778b6bc01a828b2115bd3a3f1NAKAMURA Takumi    if (!KeyInfoT::isEqual(TheBucket->first, EmptyKey))
44948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth      decrementNumTombstones();
4503a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman
45128f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner    return TheBucket;
4526e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner  }
45328f72279f5aaf34ba62ae00ca3b8bb94d8b91f70Chris Lattner
4546e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner  /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in
4556e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner  /// FoundBucket.  If the bucket contains the key and a value, this returns
4566e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner  /// true, otherwise it returns a bucket with an empty marker or tombstone and
4576e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner  /// returns false.
458babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin  template<typename LookupKeyT>
459dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth  bool LookupBucketFor(const LookupKeyT &Val,
460dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth                       const BucketT *&FoundBucket) const {
461dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth    const BucketT *BucketsPtr = getBuckets();
462ce9a04132d1bf85967d6ad062d45dd75f148eef1Chandler Carruth    const unsigned NumBuckets = getNumBuckets();
4633a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman
464ce9a04132d1bf85967d6ad062d45dd75f148eef1Chandler Carruth    if (NumBuckets == 0) {
465dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines      FoundBucket = nullptr;
46649d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer      return false;
46749d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer    }
46849d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer
4696e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner    // FoundTombstone - Keep track of whether we find a tombstone while probing.
470dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines    const BucketT *FoundTombstone = nullptr;
4716e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner    const KeyT EmptyKey = getEmptyKey();
4726e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner    const KeyT TombstoneKey = getTombstoneKey();
47305831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner    assert(!KeyInfoT::isEqual(Val, EmptyKey) &&
47405831c073abbaacbf2fc21ef5ef160872056e075Chris Lattner           !KeyInfoT::isEqual(Val, TombstoneKey) &&
4756e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner           "Empty/Tombstone value shouldn't be inserted into map!");
4763a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman
477ce9a04132d1bf85967d6ad062d45dd75f148eef1Chandler Carruth    unsigned BucketNo = getHashValue(Val) & (NumBuckets-1);
478ce9a04132d1bf85967d6ad062d45dd75f148eef1Chandler Carruth    unsigned ProbeAmt = 1;
4796e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner    while (1) {
480ce9a04132d1bf85967d6ad062d45dd75f148eef1Chandler Carruth      const BucketT *ThisBucket = BucketsPtr + BucketNo;
4816e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner      // Found Val's bucket?  If so, return it.
482babd5980d8a8b4aad9814212a269f6197ebf1f2eTalin      if (KeyInfoT::isEqual(Val, ThisBucket->first)) {
4836e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner        FoundBucket = ThisBucket;
4846e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner        return true;
4856e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner      }
4863a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman
4876e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner      // If we found an empty bucket, the key doesn't exist in the set.
4886e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner      // Insert it and return the default value.
48976c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner      if (KeyInfoT::isEqual(ThisBucket->first, EmptyKey)) {
4906e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner        // If we've already seen a tombstone while probing, fill it in instead
4916e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner        // of the empty bucket we eventually probed to.
4926e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner        FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket;
4936e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner        return false;
4946e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner      }
4953a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman
4966e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner      // If this is a tombstone, remember it.  If Val ends up not in the map, we
4976e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner      // prefer to return it than something that would require more probing.
49876c1b97e4020faace8c95a127f1eab66c278fb58Chris Lattner      if (KeyInfoT::isEqual(ThisBucket->first, TombstoneKey) && !FoundTombstone)
4996e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner        FoundTombstone = ThisBucket;  // Remember the first tombstone found.
5003a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman
5016e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner      // Otherwise, it's a hash collision or a tombstone, continue quadratic
5026e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner      // probing.
5036e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner      BucketNo += ProbeAmt++;
504ce9a04132d1bf85967d6ad062d45dd75f148eef1Chandler Carruth      BucketNo &= (NumBuckets-1);
5056e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner    }
5066e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner  }
5076e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner
508dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth  template <typename LookupKeyT>
509dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth  bool LookupBucketFor(const LookupKeyT &Val, BucketT *&FoundBucket) {
51090420105964371571ccacdf47771c6ca05db2e67David Blaikie    const BucketT *ConstFoundBucket;
511dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth    bool Result = const_cast<const DenseMapBase *>(this)
512dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth      ->LookupBucketFor(Val, ConstFoundBucket);
513dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth    FoundBucket = const_cast<BucketT *>(ConstFoundBucket);
514dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth    return Result;
515dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth  }
516dd9d38d57bbd2161e04af90a9e03011afb039b16Chandler Carruth
5177f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthpublic:
5187f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  /// Return the approximate size (in bytes) of the actual map.
5197f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  /// This is just the raw memory used by DenseMap.
5207f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  /// If entries are pointers to objects, the size of the referenced objects
5217f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  /// are not included.
5227f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  size_t getMemorySize() const {
5237f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    return getNumBuckets() * sizeof(BucketT);
5247f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  }
5257f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth};
52649d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer
5277f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthtemplate<typename KeyT, typename ValueT,
5287f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth         typename KeyInfoT = DenseMapInfo<KeyT> >
5297f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthclass DenseMap
5307f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT>,
5317f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth                          KeyT, ValueT, KeyInfoT> {
5327f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  // Lift some types from the dependent base class into this class for
5337f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  // simplicity of referring to them.
5347f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  typedef DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT> BaseT;
5357f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  typedef typename BaseT::BucketT BucketT;
5367f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  friend class DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT>;
53749d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer
5387f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  BucketT *Buckets;
53948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth  unsigned NumEntries;
54048f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth  unsigned NumTombstones;
5417f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  unsigned NumBuckets;
5427f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth
5437f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthpublic:
5447f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  explicit DenseMap(unsigned NumInitBuckets = 0) {
5457f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    init(NumInitBuckets);
5466e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner  }
5473a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman
548319120f6229dcf37f288be2719bc095a2f454d55Alex Rosenberg  DenseMap(const DenseMap &other) : BaseT() {
5497f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    init(0);
5507f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    copyFrom(other);
5517f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  }
5523a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman
553319120f6229dcf37f288be2719bc095a2f454d55Alex Rosenberg  DenseMap(DenseMap &&other) : BaseT() {
5547f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    init(0);
5557f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    swap(other);
5567f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  }
55749d443053bf6565f2420692b54f96abffa76f236Benjamin Kramer
5587f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  template<typename InputIt>
5597f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  DenseMap(const InputIt &I, const InputIt &E) {
5607f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    init(NextPowerOf2(std::distance(I, E)));
5617f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    this->insert(I, E);
5627f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  }
5636e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner
5647f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  ~DenseMap() {
5657f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    this->destroyAll();
5667f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    operator delete(Buckets);
5677f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  }
5686e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner
5697f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  void swap(DenseMap& RHS) {
5707f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    std::swap(Buckets, RHS.Buckets);
57148f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth    std::swap(NumEntries, RHS.NumEntries);
57248f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth    std::swap(NumTombstones, RHS.NumTombstones);
57348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth    std::swap(NumBuckets, RHS.NumBuckets);
5747f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  }
5753a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman
5767f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  DenseMap& operator=(const DenseMap& other) {
5777f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    copyFrom(other);
5787f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    return *this;
5797f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  }
5807f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth
5817f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  DenseMap& operator=(DenseMap &&other) {
5827f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    this->destroyAll();
5837f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    operator delete(Buckets);
5847f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    init(0);
5857f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    swap(other);
5867f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    return *this;
5877f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  }
5887f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth
5897f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  void copyFrom(const DenseMap& other) {
5907f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    this->destroyAll();
5917f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    operator delete(Buckets);
59248f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth    if (allocateBuckets(other.NumBuckets)) {
5937f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth      this->BaseT::copyFrom(other);
59448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth    } else {
59548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth      NumEntries = 0;
59648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth      NumTombstones = 0;
59748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth    }
5986e94c00ab29e654125e845f3bce692a3764c1c11Chris Lattner  }
5993a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman
6007f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  void init(unsigned InitBuckets) {
60148f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth    if (allocateBuckets(InitBuckets)) {
6027f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth      this->BaseT::initEmpty();
60348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth    } else {
60448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth      NumEntries = 0;
60548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth      NumTombstones = 0;
60648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth    }
6077f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  }
6087f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth
6097f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  void grow(unsigned AtLeast) {
6106ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson    unsigned OldNumBuckets = NumBuckets;
6116ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson    BucketT *OldBuckets = Buckets;
6123a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman
613711d324d50e5b335e98e576ce6725b056427e3f3Peng Cheng    allocateBuckets(std::max<unsigned>(64, static_cast<unsigned>(NextPowerOf2(AtLeast-1))));
6147f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    assert(Buckets);
6157f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    if (!OldBuckets) {
6167f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth      this->BaseT::initEmpty();
6177f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth      return;
6186ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson    }
6193a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman
6207f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    this->moveFromOldBuckets(OldBuckets, OldBuckets+OldNumBuckets);
6217f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth
6226ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson    // Free the old table.
62308c09496c2fa7c1da027a52d8c410c2ae98481e1Dan Gohman    operator delete(OldBuckets);
6247f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  }
6253a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman
6267f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth  void shrink_and_clear() {
62748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth    unsigned OldNumEntries = NumEntries;
6287f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    this->destroyAll();
6297f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth
6307f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    // Reduce the number of buckets.
631b8ea08ca8c43016f5bc35e1a3b6557d414448faeRichard Smith    unsigned NewNumBuckets = 0;
632b8ea08ca8c43016f5bc35e1a3b6557d414448faeRichard Smith    if (OldNumEntries)
633b8ea08ca8c43016f5bc35e1a3b6557d414448faeRichard Smith      NewNumBuckets = std::max(64, 1 << (Log2_32_Ceil(OldNumEntries) + 1));
6347f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    if (NewNumBuckets == NumBuckets) {
6357f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth      this->BaseT::initEmpty();
6367f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth      return;
6377f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    }
6387f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth
6397f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    operator delete(Buckets);
6407f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth    init(NewNumBuckets);
6416ad5fde5d01e0c8c23b928583d2fb9489b1b5a36Owen Anderson  }
6427f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruth
6437f6c82a7e0fbf8ed012bc76471576c8cc42370a3Chandler Carruthprivate:
64448f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth  unsigned getNumEntries() const {
64548f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth    return NumEntries;
64648f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth  }
64748f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth  void setNumEntries(unsigned Num) {
64848f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth    NumEntries = Num;
64948f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth  }
65048f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth
65148f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth  unsigned getNumTombstones() const {
65248f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth    return NumTombstones;
65348f4dcf0f7fd64df00839018d633944bc2464501Chandler Carruth  }
654<