Factor DenseMap into a base class that implements the hashtable logic,

and a derived class that provides the allocation and growth strategy.

This is the first (and biggest) step toward building a SmallDenseMap
that actually behaves exactly the same as DenseMap, and supports all the
same types and interface points with the same semantics.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158585 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 249 insertions, 195 deletions

diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h
index 17131a2140..31bbba9e78 100644
--- a/include/llvm/ADT/DenseMap.h
+++ b/include/llvm/ADT/DenseMap.h
@@ -34,61 +34,34 @@ template<typename KeyT, typename ValueT,
          bool IsConst = false>
 class DenseMapIterator;
 
-template<typename KeyT, typename ValueT,
-         typename KeyInfoT = DenseMapInfo<KeyT> >
-class DenseMap {
+template<typename DerivedT,
+         typename KeyT, typename ValueT, typename KeyInfoT>
+class DenseMapBase {
+protected:
   typedef std::pair<KeyT, ValueT> BucketT;
-  BucketT *Buckets;
-
-  unsigned NumBuckets;
   unsigned NumEntries;
   unsigned NumTombstones;
+
 public:
   typedef KeyT key_type;
   typedef ValueT mapped_type;
   typedef BucketT value_type;
 
-  DenseMap(const DenseMap &other) {
-    NumBuckets = 0;
-    CopyFrom(other);
-  }
-
-#if LLVM_USE_RVALUE_REFERENCES
-  DenseMap(DenseMap &&other) {
-    init(0);
-    swap(other);
-  }
-#endif
-
-  explicit DenseMap(unsigned NumInitBuckets = 0) {
-    init(NumInitBuckets);
-  }
-
-  template<typename InputIt>
-  DenseMap(const InputIt &I, const InputIt &E) {
-    init(NextPowerOf2(std::distance(I, E)));
-    insert(I, E);
-  }
-
-  ~DenseMap() {
-    DestroyAll();
-  }
-
   typedef DenseMapIterator<KeyT, ValueT, KeyInfoT> iterator;
   typedef DenseMapIterator<KeyT, ValueT,
                            KeyInfoT, true> const_iterator;
   inline iterator begin() {
     // When the map is empty, avoid the overhead of AdvancePastEmptyBuckets().
-    return empty() ? end() : iterator(Buckets, Buckets+NumBuckets);
+    return empty() ? end() : iterator(getBuckets(), getBucketsEnd());
   }
   inline iterator end() {
-    return iterator(Buckets+NumBuckets, Buckets+NumBuckets, true);
+    return iterator(getBucketsEnd(), getBucketsEnd(), true);
   }
   inline const_iterator begin() const {
-    return empty() ? end() : const_iterator(Buckets, Buckets+NumBuckets);
+    return empty() ? end() : const_iterator(getBuckets(), getBucketsEnd());
   }
   inline const_iterator end() const {
-    return const_iterator(Buckets+NumBuckets, Buckets+NumBuckets, true);
+    return const_iterator(getBucketsEnd(), getBucketsEnd(), true);
   }
 
   bool empty() const { return NumEntries == 0; }
@@ -96,7 +69,7 @@ public:
 
   /// Grow the densemap so that it has at least Size buckets. Does not shrink
   void resize(size_t Size) {
-    if (Size > NumBuckets)
+    if (Size > getNumBuckets())
       grow(Size);
   }
 
@@ -105,13 +78,13 @@ public:
     
     // If the capacity of the array is huge, and the # elements used is small,
     // shrink the array.
-    if (NumEntries * 4 < NumBuckets && NumBuckets > 64) {
+    if (NumEntries * 4 < getNumBuckets() && getNumBuckets() > 64) {
       shrink_and_clear();
       return;
     }
 
     const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
-    for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) {
+    for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) {
       if (!KeyInfoT::isEqual(P->first, EmptyKey)) {
         if (!KeyInfoT::isEqual(P->first, TombstoneKey)) {
           P->second.~ValueT();
@@ -133,13 +106,13 @@ public:
   iterator find(const KeyT &Val) {
     BucketT *TheBucket;
     if (LookupBucketFor(Val, TheBucket))
-      return iterator(TheBucket, Buckets+NumBuckets, true);
+      return iterator(TheBucket, getBucketsEnd(), true);
     return end();
   }
   const_iterator find(const KeyT &Val) const {
     BucketT *TheBucket;
     if (LookupBucketFor(Val, TheBucket))
-      return const_iterator(TheBucket, Buckets+NumBuckets, true);
+      return const_iterator(TheBucket, getBucketsEnd(), true);
     return end();
   }
 
@@ -152,14 +125,14 @@ public:
   iterator find_as(const LookupKeyT &Val) {
     BucketT *TheBucket;
     if (LookupBucketFor(Val, TheBucket))
-      return iterator(TheBucket, Buckets+NumBuckets, true);
+      return iterator(TheBucket, getBucketsEnd(), true);
     return end();
   }
   template<class LookupKeyT>
   const_iterator find_as(const LookupKeyT &Val) const {
     BucketT *TheBucket;
     if (LookupBucketFor(Val, TheBucket))
-      return const_iterator(TheBucket, Buckets+NumBuckets, true);
+      return const_iterator(TheBucket, getBucketsEnd(), true);
     return end();
   }
 
@@ -178,12 +151,12 @@ public:
   std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
     BucketT *TheBucket;
     if (LookupBucketFor(KV.first, TheBucket))
-      return std::make_pair(iterator(TheBucket, Buckets+NumBuckets, true),
+      return std::make_pair(iterator(TheBucket, getBucketsEnd(), true),
                             false); // Already in map.
 
     // Otherwise, insert the new element.
     TheBucket = InsertIntoBucket(KV.first, KV.second, TheBucket);
-    return std::make_pair(iterator(TheBucket, Buckets+NumBuckets, true), true);
+    return std::make_pair(iterator(TheBucket, getBucketsEnd(), true), true);
   }
 
   /// insert - Range insertion of pairs.
@@ -213,13 +186,6 @@ public:
     ++NumTombstones;
   }
 
-  void swap(DenseMap& RHS) {
-    std::swap(NumBuckets, RHS.NumBuckets);
-    std::swap(Buckets, RHS.Buckets);
-    std::swap(NumEntries, RHS.NumEntries);
-    std::swap(NumTombstones, RHS.NumTombstones);
-  }
-
   value_type& FindAndConstruct(const KeyT &Key) {
     BucketT *TheBucket;
     if (LookupBucketFor(Key, TheBucket))
@@ -246,39 +212,27 @@ public:
   }
 #endif
 
-  DenseMap& operator=(const DenseMap& other) {
-    CopyFrom(other);
-    return *this;
-  }
-
-#if LLVM_USE_RVALUE_REFERENCES
-  DenseMap& operator=(DenseMap &&other) {
-    DestroyAll();
-    init(0);
-    swap(other);
-    return *this;
-  }
-#endif
-
   /// isPointerIntoBucketsArray - Return true if the specified pointer points
   /// somewhere into the DenseMap's array of buckets (i.e. either to a key or
   /// value in the DenseMap).
   bool isPointerIntoBucketsArray(const void *Ptr) const {
-    return Ptr >= Buckets && Ptr < Buckets+NumBuckets;
+    return Ptr >= getBuckets() && Ptr < getBucketsEnd();
   }
 
   /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets
   /// array.  In conjunction with the previous method, this can be used to
   /// determine whether an insertion caused the DenseMap to reallocate.
-  const void *getPointerIntoBucketsArray() const { return Buckets; }
+  const void *getPointerIntoBucketsArray() const { return getBuckets(); }
 
-private:
-  void DestroyAll() {
-    if (NumBuckets == 0) // Nothing to do.
+protected:
+  DenseMapBase() : NumEntries(), NumTombstones() {}
+
+  void destroyAll() {
+    if (getNumBuckets() == 0) // Nothing to do.
       return;
 
     const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
-    for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) {
+    for (BucketT *P = getBuckets(), *E = getBucketsEnd(); P != E; ++P) {
       if (!KeyInfoT::isEqual(P->first, EmptyKey) &&
           !KeyInfoT::isEqual(P->first, TombstoneKey))
         P->second.~ValueT();
@@ -286,36 +240,114 @@ private:
     }
 
 #ifndef NDEBUG
-    memset((void*)Buckets, 0x5a, sizeof(BucketT)*NumBuckets);
+    memset((void*)getBuckets(), 0x5a, sizeof(BucketT)*getNumBuckets());
 #endif
-    operator delete(Buckets);
   }
 
-  void CopyFrom(const DenseMap& other) {
-    DestroyAll();
+  void initEmpty() {
+    NumEntries = 0;
+    NumTombstones = 0;
+
+    assert((getNumBuckets() & (getNumBuckets()-1)) == 0 &&
+           "# initial buckets must be a power of two!");
+    const KeyT EmptyKey = getEmptyKey();
+    for (BucketT *B = getBuckets(), *E = getBucketsEnd(); B != E; ++B)
+      new (&B->first) KeyT(EmptyKey);
+  }
 
-    NumEntries = other.NumEntries;
-    NumTombstones = other.NumTombstones;
-    NumBuckets = other.NumBuckets;
+  void moveFromOldBuckets(BucketT *OldBucketsBegin, BucketT *OldBucketsEnd) {
+    initEmpty();
 
-    if (NumBuckets == 0) {
-      Buckets = 0;
-      return;
+    // Insert all the old elements.
+    const KeyT EmptyKey = getEmptyKey();
+    const KeyT TombstoneKey = getTombstoneKey();
+    for (BucketT *B = OldBucketsBegin, *E = OldBucketsEnd; B != E; ++B) {
+      if (!KeyInfoT::isEqual(B->first, EmptyKey) &&
+          !KeyInfoT::isEqual(B->first, TombstoneKey)) {
+        // Insert the key/value into the new table.
+        BucketT *DestBucket;
+        bool FoundVal = LookupBucketFor(B->first, DestBucket);
+        (void)FoundVal; // silence warning.
+        assert(!FoundVal && "Key already in new map?");
+        DestBucket->first = llvm_move(B->first);
+        new (&DestBucket->second) ValueT(llvm_move(B->second));
+        ++NumEntries;
+
+        // Free the value.
+        B->second.~ValueT();
+      }
+      B->first.~KeyT();
     }
 
-    Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT) * NumBuckets));
+#ifndef NDEBUG
+    if (OldBucketsBegin != OldBucketsEnd)
+      memset((void*)OldBucketsBegin, 0x5a,
+             sizeof(BucketT) * (OldBucketsEnd - OldBucketsBegin));
+#endif
+  }
+
+  template <typename OtherBaseT>
+  void copyFrom(const DenseMapBase<OtherBaseT, KeyT, ValueT, KeyInfoT>& other) {
+    assert(getNumBuckets() == other.getNumBuckets());
+
+    NumEntries = other.NumEntries;
+    NumTombstones = other.NumTombstones;
 
     if (isPodLike<KeyT>::value && isPodLike<ValueT>::value)
-      memcpy(Buckets, other.Buckets, NumBuckets * sizeof(BucketT));
+      memcpy(getBuckets(), other.getBuckets(),
+             getNumBuckets() * sizeof(BucketT));
     else
-      for (size_t i = 0; i < NumBuckets; ++i) {
-        new (&Buckets[i].first) KeyT(other.Buckets[i].first);
-        if (!KeyInfoT::isEqual(Buckets[i].first, getEmptyKey()) &&
-            !KeyInfoT::isEqual(Buckets[i].first, getTombstoneKey()))
-          new (&Buckets[i].second) ValueT(other.Buckets[i].second);
+      for (size_t i = 0; i < getNumBuckets(); ++i) {
+        new (&getBuckets()[i].first) KeyT(other.getBuckets()[i].first);
+        if (!KeyInfoT::isEqual(getBuckets()[i].first, getEmptyKey()) &&
+            !KeyInfoT::isEqual(getBuckets()[i].first, getTombstoneKey()))
+          new (&getBuckets()[i].second) ValueT(other.getBuckets()[i].second);
       }
   }
 
+  void swap(DenseMapBase& RHS) {
+    std::swap(NumEntries, RHS.NumEntries);
+    std::swap(NumTombstones, RHS.NumTombstones);
+  }
+
+private:
+  static unsigned getHashValue(const KeyT &Val) {
+    return KeyInfoT::getHashValue(Val);
+  }
+  template<typename LookupKeyT>
+  static unsigned getHashValue(const LookupKeyT &Val) {
+    return KeyInfoT::getHashValue(Val);
+  }
+  static const KeyT getEmptyKey() {
+    return KeyInfoT::getEmptyKey();
+  }
+  static const KeyT getTombstoneKey() {
+    return KeyInfoT::getTombstoneKey();
+  }
+
+  BucketT *getBuckets() const {
+    return static_cast<const DerivedT *>(this)->getBuckets();
+  }
+
+  unsigned getNumBuckets() const {
+    return static_cast<const DerivedT *>(this)->getNumBuckets();
+  }
+
+  BucketT *getBucketsEnd() const {
+    return getBuckets() + getNumBuckets();
+  }
+
+  void grow(unsigned AtLeast) {
+    static_cast<DerivedT *>(this)->grow(AtLeast);
+  }
+
+  void shrink_and_clear() {
+    static_cast<DerivedT *>(this)->shrink_and_clear();
+    NumTombstones = 0;
+    NumEntries = 0;
+  }
+
+
   BucketT *InsertIntoBucket(const KeyT &Key, const ValueT &Value,
                             BucketT *TheBucket) {
     TheBucket = InsertIntoBucketImpl(Key, TheBucket);
@@ -354,16 +386,20 @@ private:
     // probe almost the entire table until it found the empty bucket.  If the
     // table completely filled with tombstones, no lookup would ever succeed,
     // causing infinite loops in lookup.
-    ++NumEntries;
-    if (NumEntries*4 >= NumBuckets*3) {
-      this->grow(NumBuckets * 2);
+    unsigned NewNumEntries = NumEntries + 1;
+    if (NewNumEntries*4 >= getNumBuckets()*3) {
+      this->grow(getNumBuckets() * 2);
       LookupBucketFor(Key, TheBucket);
     }
-    if (NumBuckets-(NumEntries+NumTombstones) < NumBuckets/8) {
-      this->grow(NumBuckets);
+    if (getNumBuckets()-(NewNumEntries+NumTombstones) < getNumBuckets()/8) {
+      this->grow(getNumBuckets());
       LookupBucketFor(Key, TheBucket);
     }
 
+    // Only update the state after we've grown our bucket space appropriately
+    // so that when growing buckets we have self-consistent entry count.
+    ++NumEntries;
+
     // If we are writing over a tombstone, remember this.
     if (!KeyInfoT::isEqual(TheBucket->first, getEmptyKey()))
       --NumTombstones;
@@ -371,20 +407,6 @@ private:
     return TheBucket;
   }
 
-  static unsigned getHashValue(const KeyT &Val) {
-    return KeyInfoT::getHashValue(Val);
-  }
-  template<typename LookupKeyT>
-  static unsigned getHashValue(const LookupKeyT &Val) {
-    return KeyInfoT::getHashValue(Val);
-  }
-  static const KeyT getEmptyKey() {
-    return KeyInfoT::getEmptyKey();
-  }
-  static const KeyT getTombstoneKey() {
-    return KeyInfoT::getTombstoneKey();
-  }
-
   /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in
   /// FoundBucket.  If the bucket contains the key and a value, this returns
   /// true, otherwise it returns a bucket with an empty marker or tombstone and
@@ -393,9 +415,9 @@ private:
   bool LookupBucketFor(const LookupKeyT &Val, BucketT *&FoundBucket) const {
     unsigned BucketNo = getHashValue(Val);
     unsigned ProbeAmt = 1;
-    BucketT *BucketsPtr = Buckets;
+    BucketT *BucketsPtr = getBuckets();
 
-    if (NumBuckets == 0) {
+    if (getNumBuckets() == 0) {
       FoundBucket = 0;
       return false;
     }
@@ -409,7 +431,7 @@ private:
            "Empty/Tombstone value shouldn't be inserted into map!");
 
     while (1) {
-      BucketT *ThisBucket = BucketsPtr + (BucketNo & (NumBuckets-1));
+      BucketT *ThisBucket = BucketsPtr + (BucketNo & (getNumBuckets()-1));
       // Found Val's bucket?  If so, return it.
       if (KeyInfoT::isEqual(Val, ThisBucket->first)) {
         FoundBucket = ThisBucket;
@@ -437,112 +459,144 @@ private:
     }
   }
 
-  void init(unsigned InitBuckets) {
-    NumEntries = 0;
-    NumTombstones = 0;
-    NumBuckets = InitBuckets;
+public:
+  /// Return the approximate size (in bytes) of the actual map.
+  /// This is just the raw memory used by DenseMap.
+  /// If entries are pointers to objects, the size of the referenced objects
+  /// are not included.
+  size_t getMemorySize() const {
+    return getNumBuckets() * sizeof(BucketT);
+  }
+};
 
-    if (InitBuckets == 0) {
-      Buckets = 0;
-      return;
-    }
+template<typename KeyT, typename ValueT,
+         typename KeyInfoT = DenseMapInfo<KeyT> >
+class DenseMap
+    : public DenseMapBase<DenseMap<KeyT, ValueT, KeyInfoT>,
+                          KeyT, ValueT, KeyInfoT> {
+  // Lift some types from the dependent base class into this class for
+  // simplicity of referring to them.
+  typedef DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT> BaseT;
+  typedef typename BaseT::BucketT BucketT;
+  friend class DenseMapBase<DenseMap, KeyT, ValueT, KeyInfoT>;
 
-    assert(InitBuckets && (InitBuckets & (InitBuckets-1)) == 0 &&
-           "# initial buckets must be a power of two!");
-    Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*InitBuckets));
-    // Initialize all the keys to EmptyKey.
-    const KeyT EmptyKey = getEmptyKey();
-    for (unsigned i = 0; i != InitBuckets; ++i)
-      new (&Buckets[i].first) KeyT(EmptyKey);
+  BucketT *Buckets;
+  unsigned NumBuckets;
+
+public:
+  explicit DenseMap(unsigned NumInitBuckets = 0) {
+    init(NumInitBuckets);
   }
 
-  void grow(unsigned AtLeast) {
-    unsigned OldNumBuckets = NumBuckets;
-    BucketT *OldBuckets = Buckets;
+  DenseMap(const DenseMap &other) {
+    init(0);
+    copyFrom(other);
+  }
 
-    if (NumBuckets < 64)
-      NumBuckets = 64;
+#if LLVM_USE_RVALUE_REFERENCES
+  DenseMap(DenseMap &&other) {
+    init(0);
+    swap(other);
+  }
+#endif
 
-    // Double the number of buckets.
-    while (NumBuckets < AtLeast)
-      NumBuckets <<= 1;
-    NumTombstones = 0;
-    Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*NumBuckets));
+  template<typename InputIt>
+  DenseMap(const InputIt &I, const InputIt &E) {
+    init(NextPowerOf2(std::distance(I, E)));
+    this->insert(I, E);
+  }
 
-    // Initialize all the keys to EmptyKey.
-    const KeyT EmptyKey = getEmptyKey();
-    for (unsigned i = 0, e = NumBuckets; i != e; ++i)
-      new (&Buckets[i].first) KeyT(EmptyKey);
+  ~DenseMap() {
+    this->destroyAll();
+    operator delete(Buckets);
+  }
 
-    // Insert all the old elements.
-    const KeyT TombstoneKey = getTombstoneKey();
-    for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) {
-      if (!KeyInfoT::isEqual(B->first, EmptyKey) &&
-          !KeyInfoT::isEqual(B->first, TombstoneKey)) {
-        // Insert the key/value into the new table.
-        BucketT *DestBucket;
-        bool FoundVal = LookupBucketFor(B->first, DestBucket);
-        (void)FoundVal; // silence warning.
-        assert(!FoundVal && "Key already in new map?");
-        DestBucket->first = llvm_move(B->first);
-        new (&DestBucket->second) ValueT(llvm_move(B->second));
+  void swap(DenseMap& RHS) {
+    std::swap(NumBuckets, RHS.NumBuckets);
+    std::swap(Buckets, RHS.Buckets);
 
-        // Free the value.
-        B->second.~ValueT();
-      }
-      B->first.~KeyT();
-    }
+    this->BaseT::swap(RHS);
+  }
 
-#ifndef NDEBUG
-    if (OldNumBuckets)
-      memset((void*)OldBuckets, 0x5a, sizeof(BucketT)*OldNumBuckets);
+  DenseMap& operator=(const DenseMap& other) {
+    copyFrom(other);
+    return *this;
+  }
+
+#if LLVM_USE_RVALUE_REFERENCES
+  DenseMap& operator=(DenseMap &&other) {
+    this->destroyAll();
+    operator delete(Buckets);
+    init(0);
+    swap(other);
+    return *this;
+  }
 #endif
-    // Free the old table.
-    operator delete(OldBuckets);
+
+  void copyFrom(const DenseMap& other) {
+    this->destroyAll();
+    operator delete(Buckets);
+
+    if (allocateBuckets(other.NumBuckets))
+      this->BaseT::copyFrom(other);
   }
 
-  void shrink_and_clear() {
+  void init(unsigned InitBuckets) {
+    if (allocateBuckets(InitBuckets))
+      this->BaseT::initEmpty();
+  }
+
+  void grow(unsigned AtLeast) {
     unsigned OldNumBuckets = NumBuckets;
     BucketT *OldBuckets = Buckets;
 
-    // Reduce the number of buckets.
-    NumBuckets = NumEntries > 32 ? 1 << (Log2_32_Ceil(NumEntries) + 1)
-                                 : 64;
-    NumTombstones = 0;
-    Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*NumBuckets));
-
-    // Initialize all the keys to EmptyKey.
-    const KeyT EmptyKey = getEmptyKey();
-    for (unsigned i = 0, e = NumBuckets; i != e; ++i)
-      new (&Buckets[i].first) KeyT(EmptyKey);
-
-    // Free the old buckets.
-    const KeyT TombstoneKey = getTombstoneKey();
-    for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) {
-      if (!KeyInfoT::isEqual(B->first, EmptyKey) &&
-          !KeyInfoT::isEqual(B->first, TombstoneKey)) {
-        // Free the value.
-        B->second.~ValueT();
-      }
-      B->first.~KeyT();
+    allocateBuckets(std::max<unsigned>(64, NextPowerOf2(AtLeast)));
+    assert(Buckets);
+    if (!OldBuckets) {
+      this->BaseT::initEmpty();
+      return;
     }
 
-#ifndef NDEBUG
-    memset((void*)OldBuckets, 0x5a, sizeof(BucketT)*OldNumBuckets);
-#endif
+    this->moveFromOldBuckets(OldBuckets, OldBuckets+OldNumBuckets);
+
     // Free the old table.
     operator delete(OldBuckets);
+  }
 
-    NumEntries = 0;
+  void shrink_and_clear() {
+    unsigned OldSize = this->size();
+    this->destroyAll();
+
+    // Reduce the number of buckets.
+    unsigned NewNumBuckets
+      = std::max(64, 1 << (Log2_32_Ceil(OldSize) + 1));
+    if (NewNumBuckets == NumBuckets) {
+      this->BaseT::initEmpty();
+      return;
+    }
+
+    operator delete(Buckets);
+    init(NewNumBuckets);
   }
-  
-public:
-  /// Return the approximate size (in bytes) of the actual map.
-  /// This is just the raw memory used by DenseMap.
-  /// If entries are pointers to objects, the size of the referenced objects
-  /// are not included.
-  size_t getMemorySize() const {
-    return NumBuckets * sizeof(BucketT);
+
+private:
+  BucketT *getBuckets() const {
+    return Buckets;
+  }
+
+  unsigned getNumBuckets() const {
+    return NumBuckets;
+  }
+
+  bool allocateBuckets(unsigned Num) {
+    NumBuckets = Num;
+    if (NumBuckets == 0) {
+      Buckets = 0;
+      return false;
+    }
+
+    Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT) * NumBuckets));
+    return true;
   }
 };