[base] Template MatchFun in TemplateHashMapImpl

src/base/hashmap.h

Index: src/base/hashmap.h
diff --git a/src/base/hashmap.h b/src/base/hashmap.h
index 6bef83ed4d8c7cbb2d25c55625fd65ade6b58b00..6cb52484f9409a3715d315c34ae870e50e848101 100644
--- a/src/base/hashmap.h
+++ b/src/base/hashmap.h
@@ -24,15 +24,9 @@ class DefaultAllocationPolicy {
   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
@@ -42,7 +36,7 @@ class TemplateHashMapImpl {
 
   // 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());
 
@@ -86,20 +80,11 @@ class TemplateHashMapImpl {
   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_; }
@@ -110,44 +95,35 @@ class TemplateHashMapImpl {
   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);
@@ -158,17 +134,19 @@ TemplateHashMapImpl<Key, Value, AllocationPolicy>::LookupOrInsert(
   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()) {
@@ -227,8 +205,9 @@ Value TemplateHashMapImpl<Key, Value, AllocationPolicy>::Remove(const Key& key,
   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++) {
@@ -237,15 +216,18 @@ void TemplateHashMapImpl<Key, Value, AllocationPolicy>::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++) {
@@ -256,10 +238,11 @@ TemplateHashMapImpl<Key, Value, AllocationPolicy>::Next(Entry* entry) const {
   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();
@@ -276,9 +259,10 @@ TemplateHashMapImpl<Key, Value, AllocationPolicy>::Probe(const Key& key,
   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());
 
@@ -294,8 +278,9 @@ TemplateHashMapImpl<Key, Value, AllocationPolicy>::FillEmptyEntry(
   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)));
@@ -307,8 +292,9 @@ void TemplateHashMapImpl<Key, Value, AllocationPolicy>::Initialize(
   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_;
 
@@ -329,11 +315,35 @@ void TemplateHashMapImpl<Key, Value, AllocationPolicy>::Resize() {
   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 {
@@ -352,25 +362,18 @@ class TemplateHashMap
     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); }