[base] Move hashmap allocator to a field

src/base/hashmap.h

Index: src/base/hashmap.h
diff --git a/src/base/hashmap.h b/src/base/hashmap.h
index bca35d41b1167678e5b9b025ffc2ddf912a22aad..2dcf8429261711d53c2a0d5e59271f00a2df710c 100644
--- a/src/base/hashmap.h
+++ b/src/base/hashmap.h
@@ -55,11 +55,9 @@ class TemplateHashMapImpl {
   // If an entry with matching key is found, returns that entry.
   // If no matching entry is found, a new entry is inserted with
   // corresponding key, key hash, and default initialized value.
-  Entry* LookupOrInsert(const Key& key, uint32_t hash,
-                        AllocationPolicy allocator = AllocationPolicy());
+  Entry* LookupOrInsert(const Key& key, uint32_t hash);
 
-  Entry* InsertNew(const Key& key, uint32_t hash,
-                   AllocationPolicy allocator = AllocationPolicy());
+  Entry* InsertNew(const Key& key, uint32_t hash);
 
   // Removes the entry with matching key.
   // It returns the value of the deleted entry
@@ -95,15 +93,25 @@ class TemplateHashMapImpl {
   }
 
  private:
+  // Helper which holds the entry array as well as the allocation policy.
+  // AllocationPolicy is a base class rather than a field to take advantage of
+  // the empty base optimisation for state-free allocators, such as the
+  // DefaultAllocationPolicy above.

[rmcilroy, 2016/09/19 10:55:11]

Let's make this a field instead of using the empty base optimization. I'd prefer
to keep ZoneAllocationPolicy final.

[Leszek Swirski, 2016/09/19 12:20:56]

Fair enough, done.

+  struct AllocatedEntryHolder : public AllocationPolicy {
+    Entry* values;
+    explicit AllocatedEntryHolder(AllocationPolicy allocator)
+        : AllocationPolicy(allocator) {}
+  };
+
   MatchFun match_;
-  Entry* map_;
+  AllocatedEntryHolder map_;
   uint32_t capacity_;
   uint32_t occupancy_;
 
-  Entry* map_end() const { return map_ + capacity_; }
+  Entry* map_end() const { return map_.values + capacity_; }
   Entry* Probe(const Key& key, uint32_t hash) const;
-  void Initialize(uint32_t capacity, AllocationPolicy allocator);
-  void Resize(AllocationPolicy allocator);
+  void Initialize(uint32_t capacity);
+  void Resize();
 };
 
 template <typename Key>
@@ -122,14 +130,15 @@ typedef TemplateHashMapImpl<void*, void*, DefaultAllocationPolicy> HashMap;
 
 template <typename Key, typename Value, class AllocationPolicy>
 TemplateHashMapImpl<Key, Value, AllocationPolicy>::TemplateHashMapImpl(
-    MatchFun match, uint32_t initial_capacity, AllocationPolicy allocator) {
+    MatchFun match, uint32_t initial_capacity, AllocationPolicy allocator)
+    : map_(allocator) {
   match_ = match;
-  Initialize(initial_capacity, allocator);
+  Initialize(initial_capacity);
 }
 
 template <typename Key, typename Value, class AllocationPolicy>
 TemplateHashMapImpl<Key, Value, AllocationPolicy>::~TemplateHashMapImpl() {
-  AllocationPolicy::Delete(map_);
+  map_.AllocationPolicy::Delete(map_.values);
 }
 
 template <typename Key, typename Value, class AllocationPolicy>
@@ -143,20 +152,20 @@ TemplateHashMapImpl<Key, Value, AllocationPolicy>::Lookup(const Key& key,
 template <typename Key, typename Value, class AllocationPolicy>
 typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry*
 TemplateHashMapImpl<Key, Value, AllocationPolicy>::LookupOrInsert(
-    const Key& key, uint32_t hash, AllocationPolicy allocator) {
+    const Key& key, uint32_t hash) {
   // Find a matching entry.
   Entry* p = Probe(key, hash);
   if (p->exists()) {
     return p;
   }
 
-  return InsertNew(key, hash, allocator);
+  return InsertNew(key, hash);
 }
 
 template <typename Key, typename Value, class AllocationPolicy>
 typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry*
-TemplateHashMapImpl<Key, Value, AllocationPolicy>::InsertNew(
-    const Key& key, uint32_t hash, AllocationPolicy allocator) {
+TemplateHashMapImpl<Key, Value, AllocationPolicy>::InsertNew(const Key& key,
+                                                             uint32_t hash) {
   // Find a matching entry.
   Entry* p = Probe(key, hash);
   DCHECK(!p->exists());
@@ -167,7 +176,7 @@ TemplateHashMapImpl<Key, Value, AllocationPolicy>::InsertNew(
 
   // Grow the map if we reached >= 80% occupancy.
   if (occupancy_ + occupancy_ / 4 >= capacity_) {
-    Resize(allocator);
+    Resize();
     p = Probe(key, hash);
   }
 
@@ -207,7 +216,7 @@ Value TemplateHashMapImpl<Key, Value, AllocationPolicy>::Remove(const Key& key,
     // Move q to the next entry.
     q = q + 1;
     if (q == map_end()) {
-      q = map_;
+      q = map_.values;
     }
 
     // All entries between p and q have their initial position between p and q
@@ -218,7 +227,7 @@ Value TemplateHashMapImpl<Key, Value, AllocationPolicy>::Remove(const Key& key,
     }
 
     // Find the initial position for the entry at position q.
-    Entry* r = map_ + (q->hash & (capacity_ - 1));
+    Entry* r = map_.values + (q->hash & (capacity_ - 1));
 
     // If the entry at position q has its initial position outside the range
     // between p and q it can be moved forward to position p and will still be
@@ -239,7 +248,7 @@ template <typename Key, typename Value, class AllocationPolicy>
 void TemplateHashMapImpl<Key, Value, AllocationPolicy>::Clear() {
   // Mark all entries as empty.
   const Entry* end = map_end();
-  for (Entry* p = map_; p < end; p++) {
+  for (Entry* p = map_.values; p < end; p++) {
     p->clear();
   }
   occupancy_ = 0;
@@ -248,14 +257,14 @@ void TemplateHashMapImpl<Key, Value, AllocationPolicy>::Clear() {
 template <typename Key, typename Value, class AllocationPolicy>
 typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry*
 TemplateHashMapImpl<Key, Value, AllocationPolicy>::Start() const {
-  return Next(map_ - 1);
+  return Next(map_.values - 1);
 }
 
 template <typename Key, typename Value, class AllocationPolicy>
 typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry*
 TemplateHashMapImpl<Key, Value, AllocationPolicy>::Next(Entry* p) const {
   const Entry* end = map_end();
-  DCHECK(map_ - 1 <= p && p < end);
+  DCHECK(map_.values - 1 <= p && p < end);
   for (p++; p < end; p++) {
     if (p->exists()) {
       return p;
@@ -269,15 +278,15 @@ typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry*
 TemplateHashMapImpl<Key, Value, AllocationPolicy>::Probe(const Key& key,
                                                          uint32_t hash) const {
   DCHECK(base::bits::IsPowerOfTwo32(capacity_));
-  Entry* p = map_ + (hash & (capacity_ - 1));
+  Entry* p = map_.values + (hash & (capacity_ - 1));
   const Entry* end = map_end();
-  DCHECK(map_ <= p && p < end);
+  DCHECK(map_.values <= p && p < end);
 
   DCHECK(occupancy_ < capacity_);  // Guarantees loop termination.
   while (p->exists() && (hash != p->hash || !match_(key, p->key))) {
     p++;
     if (p >= end) {
-      p = map_;
+      p = map_.values;
     }
   }
 
@@ -286,10 +295,11 @@ TemplateHashMapImpl<Key, Value, AllocationPolicy>::Probe(const Key& key,
 
 template <typename Key, typename Value, class AllocationPolicy>
 void TemplateHashMapImpl<Key, Value, AllocationPolicy>::Initialize(
-    uint32_t capacity, AllocationPolicy allocator) {
+    uint32_t capacity) {
   DCHECK(base::bits::IsPowerOfTwo32(capacity));
-  map_ = reinterpret_cast<Entry*>(allocator.New(capacity * sizeof(Entry)));
-  if (map_ == nullptr) {
+  map_.values = reinterpret_cast<Entry*>(
+      map_.AllocationPolicy::New(capacity * sizeof(Entry)));
+  if (map_.values == nullptr) {
     FATAL("Out of memory: HashMap::Initialize");
     return;
   }
@@ -298,18 +308,17 @@ void TemplateHashMapImpl<Key, Value, AllocationPolicy>::Initialize(
 }
 
 template <typename Key, typename Value, class AllocationPolicy>
-void TemplateHashMapImpl<Key, Value, AllocationPolicy>::Resize(
-    AllocationPolicy allocator) {
-  Entry* map = map_;
+void TemplateHashMapImpl<Key, Value, AllocationPolicy>::Resize() {
+  Entry* map = map_.values;
   uint32_t n = occupancy_;
 
   // Allocate larger map.
-  Initialize(capacity_ * 2, allocator);
+  Initialize(capacity_ * 2);
 
   // Rehash all current entries.
   for (Entry* p = map; n > 0; p++) {
     if (p->exists()) {
-      Entry* entry = LookupOrInsert(p->key, p->hash, allocator);
+      Entry* entry = LookupOrInsert(p->key, p->hash);
       entry->value = p->value;
       n--;
     }
@@ -364,10 +373,9 @@ class TemplateHashMap
 
   Iterator begin() const { return Iterator(this, this->Start()); }
   Iterator end() const { return Iterator(this, nullptr); }
-  Iterator find(Key* key, bool insert = false,
-                AllocationPolicy allocator = AllocationPolicy()) {
+  Iterator find(Key* key, bool insert = false) {
     if (insert) {
-      return Iterator(this, this->LookupOrInsert(key, key->Hash(), allocator));
+      return Iterator(this, this->LookupOrInsert(key, key->Hash()));
     }
     return Iterator(this, this->Lookup(key, key->Hash()));
   }