[base] Template MatchFun in TemplateHashMapImpl

src/base/hashmap.h

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 // The reason we write our own hash map instead of using unordered_map in STL,
 // is that STL containers use a mutex pool on debug build, which will lead to
 // deadlock when we are using async signal handler.
 
 #ifndef V8_BASE_HASHMAP_H_
 #define V8_BASE_HASHMAP_H_
 
 #include <stdlib.h>
 
 #include "src/base/bits.h"
 #include "src/base/hashmap-entry.h"
 #include "src/base/logging.h"
 
 namespace v8 {
 namespace base {
 
 class DefaultAllocationPolicy {
  public:
   V8_INLINE void* New(size_t size) { return malloc(size); }
   V8_INLINE static void Delete(void* p) { free(p); }
 };
 
-// Metaprogramming helper to allow pointer keys to be passed by value and
-// non-pointer keys by const reference.
-template <typename Key>
-struct MatchFunHelper;
-
-template <typename Key, typename Value, class AllocationPolicy>
+template <typename Key, typename Value, class MatchFun, class AllocationPolicy>
 class TemplateHashMapImpl {
  public:
-  typedef typename MatchFunHelper<Key>::Fun MatchFun;
   typedef TemplateHashMapEntry<Key, Value> Entry;
 
   // The default capacity.  This is used by the call sites which want
   // to pass in a non-default AllocationPolicy but want to use the
   // default value of capacity specified by the implementation.
   static const uint32_t kDefaultHashMapCapacity = 8;
 
   // initial_capacity is the size of the initial hash map;
   // it must be a power of 2 (and thus must not be 0).
-  TemplateHashMapImpl(MatchFun match,
+  TemplateHashMapImpl(MatchFun match = MatchFun(),

[rmcilroy, 2016/09/19 17:21:35]

Does this need to be passed as a argument (and stored as a field) if it is being
templated? Could we just directly call the templated function instead (maybe
this is related to the code size thing you were discussing before)?

[Leszek Swirski, 2016/09/20 11:14:30]

Yes, because it could be stateful (not least, the function pointer instantiation
by PointerHashMap).

Regarding space, we could actually potentially shove this, the allocator, and
the Entry* map_ in a tuple, which would collapse any empty classes using the
empty-base-optimisation where possible (afaik it uses metaprogramming magic to
detect empty non-final types).

[rmcilroy, 2016/09/20 12:57:57]

Ok sounds good. No need to specialize for space, this seems fine.

[Leszek Swirski, 2016/09/20 15:04:20]

Acknowledged.

                       uint32_t capacity = kDefaultHashMapCapacity,
                       AllocationPolicy allocator = AllocationPolicy());
 
   ~TemplateHashMapImpl();
 
   // If an entry with matching key is found, returns that entry.
   // Otherwise, nullptr is returned.
   Entry* Lookup(const Key& key, uint32_t hash) const;
 
   // If an entry with matching key is found, returns that entry.
@@ skipping 23 matching lines @@
   //
   // for (Entry* p = map.Start(); p != nullptr; p = map.Next(p)) {
   //   ...
   // }
   //
   // If entries are inserted during iteration, the effect of
   // calling Next() is undefined.
   Entry* Start() const;
   Entry* Next(Entry* entry) const;
 
-  // Some match functions defined for convenience.
-  // TODO(leszeks): This isn't really matching pointers, so the name doesn't
-  // really make sense, but we should remove this entirely and template the map
-  // on the matching function.
-  static bool PointersMatch(typename MatchFunHelper<Key>::KeyRef key1,
-                            typename MatchFunHelper<Key>::KeyRef key2) {
-    return key1 == key2;
-  }
-
  private:
-  MatchFun match_;
   Entry* map_;
   uint32_t capacity_;
   uint32_t occupancy_;
+  MatchFun match_;
   AllocationPolicy allocator_;
 
   Entry* map_end() const { return map_ + capacity_; }
   Entry* Probe(const Key& key, uint32_t hash) const;
   Entry* FillEmptyEntry(Entry* entry, const Key& key, const Value& value,
                         uint32_t hash);
   void Initialize(uint32_t capacity);
   void Resize();
 };
 
-template <typename Key>
-struct MatchFunHelper {
-  typedef const Key& KeyRef;
-  typedef bool (*Fun)(KeyRef key1, KeyRef key2);
-};
-
-template <typename Key>
-struct MatchFunHelper<Key*> {
-  typedef Key* KeyRef;
-  typedef bool (*Fun)(KeyRef key1, KeyRef key2);
-};
-
-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)
-    : allocator_(allocator) {
-  match_ = match;
+template <typename Key, typename Value, typename MatchFun,
+          class AllocationPolicy>
+TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::
+    TemplateHashMapImpl(MatchFun match, uint32_t initial_capacity,
+                        AllocationPolicy allocator)
+    : match_(match), allocator_(allocator) {
   Initialize(initial_capacity);
 }
 
-template <typename Key, typename Value, class AllocationPolicy>
-TemplateHashMapImpl<Key, Value, AllocationPolicy>::~TemplateHashMapImpl() {
+template <typename Key, typename Value, typename MatchFun,
+          class AllocationPolicy>
+TemplateHashMapImpl<Key, Value, MatchFun,
+                    AllocationPolicy>::~TemplateHashMapImpl() {
   allocator_.Delete(map_);
 }
 
-template <typename Key, typename Value, class AllocationPolicy>
-typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry*
-TemplateHashMapImpl<Key, Value, AllocationPolicy>::Lookup(const Key& key,
-                                                          uint32_t hash) const {
+template <typename Key, typename Value, typename MatchFun,
+          class AllocationPolicy>
+typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
+TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Lookup(
+    const Key& key, uint32_t hash) const {
   Entry* entry = Probe(key, hash);
   return entry->exists() ? entry : nullptr;
 }
 
-template <typename Key, typename Value, class AllocationPolicy>
-typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry*
-TemplateHashMapImpl<Key, Value, AllocationPolicy>::LookupOrInsert(
+template <typename Key, typename Value, typename MatchFun,
+          class AllocationPolicy>
+typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
+TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::LookupOrInsert(
     const Key& key, uint32_t hash) {
   // Find a matching entry.
   Entry* entry = Probe(key, hash);
   if (entry->exists()) {
     return entry;
   }
 
   return FillEmptyEntry(entry, key, Value(), 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) {
+template <typename Key, typename Value, typename MatchFun,
+          class AllocationPolicy>
+typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
+TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::InsertNew(
+    const Key& key, uint32_t hash) {
   Entry* entry = Probe(key, hash);
   return FillEmptyEntry(entry, key, Value(), hash);
 }
 
-template <typename Key, typename Value, class AllocationPolicy>
-Value TemplateHashMapImpl<Key, Value, AllocationPolicy>::Remove(const Key& key,
-                                                                uint32_t hash) {
+template <typename Key, typename Value, typename MatchFun,
+          class AllocationPolicy>
+Value TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Remove(
+    const Key& key, uint32_t hash) {
   // Lookup the entry for the key to remove.
   Entry* p = Probe(key, hash);
   if (!p->exists()) {
     // Key not found nothing to remove.
     return nullptr;
   }
 
   Value value = p->value;
   // To remove an entry we need to ensure that it does not create an empty
   // entry that will cause the search for another entry to stop too soon. If all
@@ skipping 38 matching lines @@
       p = q;
     }
   }
 
   // Clear the entry which is allowed to en emptied.
   p->clear();
   occupancy_--;
   return value;
 }
 
-template <typename Key, typename Value, class AllocationPolicy>
-void TemplateHashMapImpl<Key, Value, AllocationPolicy>::Clear() {
+template <typename Key, typename Value, typename MatchFun,
+          class AllocationPolicy>
+void TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Clear() {
   // Mark all entries as empty.
   const Entry* end = map_end();
   for (Entry* entry = map_; entry < end; entry++) {
     entry->clear();
   }
   occupancy_ = 0;
 }
 
-template <typename Key, typename Value, class AllocationPolicy>
-typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry*
-TemplateHashMapImpl<Key, Value, AllocationPolicy>::Start() const {
+template <typename Key, typename Value, typename MatchFun,
+          class AllocationPolicy>
+typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
+TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Start() const {
   return Next(map_ - 1);
 }
 
-template <typename Key, typename Value, class AllocationPolicy>
-typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry*
-TemplateHashMapImpl<Key, Value, AllocationPolicy>::Next(Entry* entry) const {
+template <typename Key, typename Value, typename MatchFun,
+          class AllocationPolicy>
+typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
+TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Next(
+    Entry* entry) const {
   const Entry* end = map_end();
   DCHECK(map_ - 1 <= entry && entry < end);
   for (entry++; entry < end; entry++) {
     if (entry->exists()) {
       return entry;
     }
   }
   return nullptr;
 }
 
-template <typename Key, typename Value, class AllocationPolicy>
-typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry*
-TemplateHashMapImpl<Key, Value, AllocationPolicy>::Probe(const Key& key,
-                                                         uint32_t hash) const {
+template <typename Key, typename Value, typename MatchFun,
+          class AllocationPolicy>
+typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
+TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Probe(
+    const Key& key, uint32_t hash) const {
   DCHECK(base::bits::IsPowerOfTwo32(capacity_));
   Entry* entry = map_ + (hash & (capacity_ - 1));
   const Entry* end = map_end();
   DCHECK(map_ <= entry && entry < end);
 
   DCHECK(occupancy_ < capacity_);  // Guarantees loop termination.
   while (entry->exists() && (hash != entry->hash || !match_(key, entry->key))) {
     entry++;
     if (entry >= end) {
       entry = map_;
     }
   }
 
   return entry;
 }
 
-template <typename Key, typename Value, class AllocationPolicy>
-typename TemplateHashMapImpl<Key, Value, AllocationPolicy>::Entry*
-TemplateHashMapImpl<Key, Value, AllocationPolicy>::FillEmptyEntry(
+template <typename Key, typename Value, typename MatchFun,
+          class AllocationPolicy>
+typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry*
+TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::FillEmptyEntry(
     Entry* entry, const Key& key, const Value& value, uint32_t hash) {
   DCHECK(!entry->exists());
 
   new (entry) Entry(key, value, hash);
   occupancy_++;
 
   // Grow the map if we reached >= 80% occupancy.
   if (occupancy_ + occupancy_ / 4 >= capacity_) {
     Resize();
     entry = Probe(key, hash);
   }
 
   return entry;
 }
 
-template <typename Key, typename Value, class AllocationPolicy>
-void TemplateHashMapImpl<Key, Value, AllocationPolicy>::Initialize(
+template <typename Key, typename Value, typename MatchFun,
+          class AllocationPolicy>
+void TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Initialize(
     uint32_t capacity) {
   DCHECK(base::bits::IsPowerOfTwo32(capacity));
   map_ = reinterpret_cast<Entry*>(allocator_.New(capacity * sizeof(Entry)));
   if (map_ == nullptr) {
     FATAL("Out of memory: HashMap::Initialize");
     return;
   }
   capacity_ = capacity;
   Clear();
 }
 
-template <typename Key, typename Value, class AllocationPolicy>
-void TemplateHashMapImpl<Key, Value, AllocationPolicy>::Resize() {
+template <typename Key, typename Value, typename MatchFun,
+          class AllocationPolicy>
+void TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Resize() {
   Entry* map = map_;
   uint32_t n = occupancy_;
 
   // Allocate larger map.
   Initialize(capacity_ * 2);
 
   // Rehash all current entries.
   for (Entry* entry = map; n > 0; entry++) {
     if (entry->exists()) {
       Entry* new_entry = Probe(entry->key, entry->hash);
       new_entry =
           FillEmptyEntry(new_entry, entry->key, entry->value, entry->hash);
       n--;
     }
   }
 
   // Delete old map.
   allocator_.Delete(map);
 }
 
+template <typename AllocationPolicy>

[rmcilroy, 2016/09/19 17:21:35]

Any reason we need both this class and TemplateHashMap - could we just inline
this code into TemplateHashMap and then:
typedef TemplateHashMap<void*, void*, DefaultAllocationPolicy> HashMap;
?

[Leszek Swirski, 2016/09/20 11:14:30]

It's to have

a) a static PointersMatch method, and
b) a constructor which does not default initialise MatchFun.
c) a common base for HashMap, TemplateHashMap and ZoneHashMap

The last one could be achieved with a templated using directive I guess, e.g.

template <typename AllocationPolicy>
using PointerHashMap = TemplateHashMap<void*, void*, AllocationPolicy>

but I think the first two are valid.

[rmcilroy, 2016/09/20 12:57:57]

Ok makes sense. A couple of points though: 
 - This CL adds the default MatchFunc initialization to the constructor above -
is there any reason you did this if you are adding this class to avoid it?
 - Most users of HashMap just want to default PointersMatch function - would it
make sense to just make that a default argument to the constructor here and
remove the extra arguments in all the callers? 
 - The name seems somehow more specific than TemplateHashMap, even although this
is the super class. Could we call it TemplatePointerHashMapImpl or similar (it
shouldn't be used except for to typedef HashMap and ZoneHashMap anyway I don't
think.

One other thought (not sure if it would work) - could we add this code to
TemplateHashMap, and then typedef HashMap to be TemplateHashMap<void*, void*,
DefaultAllocationPolicy> HashMap. This would save us the extra class, and all
HashMap's would get an iterator if they wanted it. WDYT?

[Leszek Swirski, 2016/09/20 15:04:20]

I was actually considering re-ordering the parameters in the TemplateHashMapImpl
to move MatchFun to the back, since it's likely to be default initialised, but
then I didn't and now this one makes less sense I guess. I could do that?
Done, which justifies the extra constructor a lot more ;)
Done.
This wouldn't work with TemplateHashMap as-is, because it uses private
inheritance to hide the base class. Honestly, I'd be more in favour of removing
it entirely (it's used in exactly one place), and replacing it with a partial
specialisation of TemplateHashMapImpl for pointers (with HashMap then maybe
being the void* typedef). But, again I'd want to do that in a separate CL to
keep changes fairly atomic.

[rmcilroy, 2016/09/20 16:06:03]

Yeah this probably makes sense - it does seem to be the least likely to be
default initialized looking through the code. Please reorder both
TemplateHashMapImpl and TemplatePointerHashMapImpl if doing this.
Right, hadn't noticed the private inheritance. Agreed - remove it entirely would
make more sense, but yeah, let's make this a separate CL.

+class PointerHashMap
+    : public TemplateHashMapImpl<void*, void*, bool (*)(void*, void*),
+                                 AllocationPolicy> {
+  typedef TemplateHashMapImpl<void*, void*, bool (*)(void*, void*),
+                              AllocationPolicy>
+      Base;
+
+ public:
+  typedef bool (*MatchFun)(void*, void*);
+
+  PointerHashMap(MatchFun match,
+                 uint32_t capacity = Base::kDefaultHashMapCapacity,
+                 AllocationPolicy allocator = AllocationPolicy())
+      : Base(match, capacity, allocator) {}
+
+  static bool PointersMatch(void* key1, void* key2) { return key1 == key2; }
+};
+
+typedef PointerHashMap<DefaultAllocationPolicy> HashMap;
+
 // A hash map for pointer keys and values with an STL-like interface.
 template <class Key, class Value, class AllocationPolicy>
-class TemplateHashMap
-    : private TemplateHashMapImpl<void*, void*, AllocationPolicy> {
+class TemplateHashMap : private PointerHashMap<AllocationPolicy> {
+  typedef PointerHashMap<AllocationPolicy> Base;
+
  public:
+  typedef bool (*MatchFun)(void*, void*);
+
   STATIC_ASSERT(sizeof(Key*) == sizeof(void*));    // NOLINT
   STATIC_ASSERT(sizeof(Value*) == sizeof(void*));  // NOLINT
   struct value_type {
     Key* first;
     Value* second;
   };
 
   class Iterator {
    public:
     Iterator& operator++() {
       entry_ = map_->Next(entry_);
       return *this;
     }
 
     value_type* operator->() { return reinterpret_cast<value_type*>(entry_); }
     bool operator!=(const Iterator& other) { return entry_ != other.entry_; }
 
    private:
-    Iterator(const TemplateHashMapImpl<void*, void*, AllocationPolicy>* map,
-             typename TemplateHashMapImpl<void*, void*,
-                                          AllocationPolicy>::Entry* entry)
+    Iterator(const Base* map, typename Base::Entry* entry)
         : map_(map), entry_(entry) {}
 
-    const TemplateHashMapImpl<void*, void*, AllocationPolicy>* map_;
-    typename TemplateHashMapImpl<void*, void*, AllocationPolicy>::Entry* entry_;
+    const Base* map_;
+    typename Base::Entry* entry_;
 
     friend class TemplateHashMap;
   };
 
-  TemplateHashMap(typename TemplateHashMapImpl<
-                      void*, void*, AllocationPolicy>::MatchFun match,
+  TemplateHashMap(MatchFun match,
                   AllocationPolicy allocator = AllocationPolicy())
-      : TemplateHashMapImpl<void*, void*, AllocationPolicy>(
-            match,
-            TemplateHashMapImpl<void*, void*,
-                                AllocationPolicy>::kDefaultHashMapCapacity,
-            allocator) {}
+      : Base(match, Base::kDefaultHashMapCapacity, allocator) {}
 
   Iterator begin() const { return Iterator(this, this->Start()); }
   Iterator end() const { return Iterator(this, nullptr); }
   Iterator find(Key* key, bool insert = false) {
     if (insert) {
       return Iterator(this, this->LookupOrInsert(key, key->Hash()));
     }
     return Iterator(this, this->Lookup(key, key->Hash()));
   }
 };
 
 }  // namespace base
 }  // namespace v8
 
 #endif  // V8_BASE_HASHMAP_H_