Issue 5141 - Generalize Map class to allow non-strings as keys

compiled/Map.h

 /*
  * This file is part of Adblock Plus <https://adblockplus.org/>,
  * Copyright (C) 2006-present eyeo GmbH
  *
  * Adblock Plus is free software: you can redistribute it and/or modify
  * it under the terms of the GNU General Public License version 3 as
  * published by the Free Software Foundation.
  *
  * Adblock Plus is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  * GNU General Public License for more details.
  *
  * You should have received a copy of the GNU General Public License
  * along with Adblock Plus.  If not, see <http://www.gnu.org/licenses/>.
  */
 
 #pragma once
 
 #include <cmath>
 #include <initializer_list>
 #include <memory>
 
 #include "debug.h"
-
-template<typename Entry, typename Value>
+#include "String.h"
+
+template<typename Entry>
 class Map;
 
 namespace Map_internal
 {
   template<typename Entry>
   struct HashContainerIterator
   {
     typedef Entry entry_type;
     typedef HashContainerIterator<Entry> iterator;
 
@@ skipping 57 matching lines @@
     {
       return !mEntry->is_invalid();
     }
   };
 
   template<typename Entry>
   class HashContainer
   {
   public:
     typedef Entry entry_type;
-    typedef typename Entry::key_type key_type;
+    typedef typename Entry::key_type_cref key_type_cref;
     typedef typename entry_type::size_type size_type;
     typedef HashContainerIterator<Entry> const_iterator;
     typedef HashContainerReference<const Entry> const_reference;
 
   private:
     explicit HashContainer(const HashContainer& other);
     void operator=(const HashContainer& other);
 
   protected:
     static constexpr size_type MIN_BUCKETS = 1;
     static constexpr double LOAD_FACTOR = 0.8;
     std::unique_ptr<entry_type[]> mBuckets;
     size_type mBucketCount;
     size_type mEntryCount;
 
 #if defined(DEBUG)
     size_type mInsertCounter;
 #endif
 
-    entry_type* find_bucket(const key_type& key) const
+    entry_type* find_bucket(key_type_cref key) const
     {
       size_type h = entry_type::hash(key);
 
       // This does quadratic probing, effectively the following formula is used:
       // pos = (hash + 1/2 i + 1/2 i ^ 2) mod bucketCount
       for (size_type i = 0; ; ++i)
       {
         // mBucketCount is 2^n so (h & mBucketCount - 1) is equivalent to
         // h % mBucketCount but significantly faster.
         entry_type* entry = &mBuckets[h & (mBucketCount - 1)];
@@ skipping 56 matching lines @@
       mBuckets.reset(new entry_type[mBucketCount]);
       // Working around https://github.com/waywardmonkeys/emscripten-trace-collector/issues/2 here
       annotate_address(reinterpret_cast<size_type*>(mBuckets.get()) - 1, "Hash table buffer");
     }
 
     void insert(const entry_type& entry)
     {
       assign(find_bucket(entry.first), entry);
     }
 
-    bool erase(const key_type& key)
+    bool erase(key_type_cref key)
     {
       entry_type* entry = find_bucket(key);
       if (entry->is_invalid())
         return false;
 
       entry->erase();
       return true;
     }
 
-    const_reference find(const key_type& key) const
+    const_reference find(key_type_cref key) const
     {
       return const_reference(find_bucket(key));
     }
 
     const_iterator begin() const
     {
       return const_iterator(&mBuckets[0], &mBuckets[mBucketCount]);
     }
 
     const_iterator end() const
     {
       return const_iterator(&mBuckets[mBucketCount], &mBuckets[mBucketCount]);
     }
 
     size_type size() const
     {
       return mEntryCount;
     }
   };
 
-  template<typename Entry, typename Value>
+  template<typename Entry>
   struct MapReference : public HashContainerReference<Entry>

[sergei, 2017/10/11 10:03:22]

I would remove Value template parameter because it's already present in the
Entry.

[Wladimir Palant, 2017/10/11 18:28:31]

Done.

   {
     typedef HashContainerReference<Entry> super;
     typedef typename super::entry_type entry_type;

[sergei, 2017/10/11 10:03:21]

entry_type is already defined in the public base class.

[Wladimir Palant, 2017/10/11 18:28:31]

Yes. However, using it in this class will produce compile errors if we don't
redeclare it.

[sergei, 2017/10/17 12:58:06]

Acknowledged. Interesting whether there is a difference between
typedef typename super::entry_type entry_type;
and
using typename super::entry_type.

-    typedef typename entry_type::key_type key_type;
-    typedef Value value_type;
-    typedef Map<Entry, Value> map_type;
+    typedef typename entry_type::key_type_cref key_type_cref;
+    typedef typename entry_type::value_type value_type;
+    typedef Map<entry_type> map_type;
 
     map_type* mMap;
 
 #if defined(DEBUG)
     typename map_type::size_type mInsertCounter;
     typename map_type::size_type mHash;
 #endif
 
-    MapReference(map_type* map, const key_type& key, entry_type* entry)
+    MapReference(map_type* map, key_type_cref key, entry_type* entry)
         : super(entry), mMap(map)
     {
 #if defined(DEBUG)
       mInsertCounter = mMap->mInsertCounter;
       mHash = entry_type::hash(key);
 #endif
     }
 
-    void assign(const key_type& key, const value_type& value)
+    void assign(key_type_cref key, const value_type& value)
     {
 #if defined(DEBUG)
       assert2(mInsertCounter == mMap->mInsertCounter,
           u"There should be no insert operations performed between map.find() and assign()"_str);
       assert2(mHash == entry_type::hash(key),
           u"The keys used in map.find() and assign() should be identical"_str);
 #endif
 
       mMap->assign(this->mEntry, entry_type(key, value));
     }
   };
 }
 
 template<typename Entry>
-class Set : public Map_internal::HashContainer<Entry>
-{
-public:
-  typedef Map_internal::HashContainer<Entry> super;
-  typedef typename super::size_type size_type;
-  typedef typename super::entry_type entry_type;
-  typedef typename super::key_type key_type;

[sergei, 2017/10/11 10:03:22]

Why is it required to define again size_type, entry_type and key_type which are
already defined in the publicly base class?
The same for Map class.

[Wladimir Palant, 2017/10/11 18:28:31]

Done here. For Map class they are actually required, we'll get compile errors
otherswise.

-
-  using super::super;
-};
-
-template<typename Entry, typename Value>
+using Set = Map_internal::HashContainer<Entry>;
+
+template<typename Entry>
 class Map : public Map_internal::HashContainer<Entry>
 {
 public:
   typedef Map_internal::HashContainer<Entry> super;
   typedef typename super::size_type size_type;
   typedef typename super::entry_type entry_type;
-  typedef typename super::key_type key_type;
-  typedef Value value_type;
+  typedef typename super::key_type_cref key_type_cref;
+  typedef typename entry_type::value_type value_type;
   typedef typename super::const_reference const_reference;

[sergei, 2017/10/11 10:03:22]

const_reference is already defined in the publicly base class.

[Wladimir Palant, 2017/10/11 18:28:31]

It's used in this class, we'll get compile error unless we redeclare it.

-  typedef Map_internal::MapReference<entry_type, value_type> reference;
-  friend struct Map_internal::MapReference<entry_type, value_type>;
+  typedef Map_internal::MapReference<entry_type> reference;
+  friend struct Map_internal::MapReference<entry_type>;
 
   using super::super;
 
   Map(std::initializer_list<entry_type> list)
       : super(list.size())
   {
     for (const auto& item : list)
       super::insert(item);
   }
 
-  value_type& operator[](const key_type& key)
+  value_type& operator[](key_type_cref key)
   {
     entry_type* entry = super::find_bucket(key);
     if (entry->is_invalid())
       entry = super::assign(entry, key);
     return entry->second;
   }
 
-  const_reference find(const key_type& key) const

[sergei, 2017/10/11 10:03:22]

It seems this method is not needed because it's available in the base class.

[Wladimir Palant, 2017/10/11 18:28:31]

We declare a non-const variant of this method below. If we don't redeclare the
const variant, it won't be exposed any more.

[sergei, 2017/10/17 12:58:06]

What about `using super::find;`, though it should be not in this commit.

+  const_reference find(key_type_cref key) const
   {
     return super::find(key);
   }
 
-  reference find(const key_type& key)
+  reference find(key_type_cref key)
   {
     return reference(this, key, super::find_bucket(key));
   }
 };