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

compiled/StringMap.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 <cstddef>
-#include <cmath>
-#include <initializer_list>
-#include <memory>
 
+#include "Map.h"
 #include "String.h"
-#include "debug.h"
-
-template<typename T>
-class StringMap;
 
 namespace StringMap_internal
 {
-  template<typename Entry>
-  struct HashContainerIterator
+  struct StringSetEntry
   {
-    typedef Entry entry_type;
-    typedef HashContainerIterator<Entry> iterator;
+    typedef String key_type;
+    typedef size_t size_type;
 
-    const entry_type* mPos;
-    const entry_type* mEnd;
+    DependentString first;

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

Actually, the type of `first` should be key_type, thus key_type should be
DependentString. What do you think about having
typedef const String& key_type_cref;
and using it everywhere as the argument type? It seems it also solves
https://codereview.adblockplus.org/29572731/diff/29572868/compiled/IntMap.h#n....

[Wladimir Palant, 2017/12/04 13:44:15]

Done.

 
-    explicit HashContainerIterator(const entry_type* start, const entry_type* end)
-        : mPos(start), mEnd(end)
+    StringSetEntry(const key_type& key = DependentString())
     {
-      if (mPos != mEnd && mPos->first.is_invalid())
-        ++(*this);
+      if (!key.is_invalid())
+        first.reset(key);

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

Why is this trick required and `:first(key)` cannot be used?
I have actually tried it with the current key_type and the compiler hangs up.

[Wladimir Palant, 2017/12/04 13:44:15]

That's because DepedentString() constructor will create a valid empty string if
constructed from an invalid DependentString() instance. Having DependentString()
constructor copy flags isn't entirely trivial however.

[sergei, 2017/12/04 14:26:09]

I have added a ticket for that because it seems a serious issue which has been
already observed in several places. https://issues.adblockplus.org/ticket/6138.

     }
 
-    const entry_type& operator*() const
+    bool equals(const key_type& other) const
     {
-      return *mPos;
+      return first.equals(other);
     }
 
-    const entry_type* operator->() const
+    bool is_invalid() const
     {
-      return mPos;
+      return first.is_invalid();
     }
 
-    iterator& operator++()
+    bool is_deleted() const
     {
-      do {
-        ++mPos;
-      } while(mPos != mEnd && mPos->first.is_invalid());
-      return *this;
+      return first.is_deleted();
     }
 
-    bool operator==(const iterator& it) const
+    void erase()
     {
-      return mPos == it.mPos;
+      first.erase();
     }
 
-    bool operator!=(const iterator& it) const
+    static size_type hash(const key_type& key)
     {
-      return mPos != it.mPos;
+      // FNV-1a hash function
+      size_type result = 2166136261;
+      for (String::size_type i = 0; i < key.length(); i++)
+        result = (result ^ key[i]) * 16777619;
+      return result;
     }
   };
 
-  template<typename Entry>
-  struct HashContainerReference
+  template<typename Value>
+  struct StringMapEntry : StringSetEntry
   {
-    typedef Entry entry_type;
+    typedef StringSetEntry super;
+    typedef Value value_type;
 
-    entry_type* mEntry;
+    Value second;
 
-    explicit HashContainerReference(entry_type* entry)
-        : mEntry(entry)
+    StringMapEntry(const key_type& key = DependentString(),
+                   value_type value = value_type())
+        : super(key), second(value)
     {
     }
 
-    const entry_type* operator->() const
+    void erase()
     {
-      return mEntry;
-    }
-
-    operator bool() const
-    {
-      return !mEntry->first.is_invalid();
-    }
-  };
-
-  template<typename Entry>
-  class HashContainer
-  {
-  public:
-    typedef Entry entry_type;
-    typedef size_t 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
-
-    explicit HashContainer(size_type expectedEntries = 0)
-        : mEntryCount(0)
-    {
-      expectedEntries = ceil(expectedEntries / LOAD_FACTOR);
-      mBucketCount = MIN_BUCKETS;
-      while (mBucketCount < expectedEntries)
-        mBucketCount <<= 1;
-
-      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");
-    }
-
-    static size_type hash(const String& str)
-    {
-      // FNV-1a hash function
-      size_type result = 2166136261;
-      for (String::size_type i = 0; i < str.length(); i++)
-        result = (result ^ str[i]) * 16777619;
-      return result;
-    }
-
-    entry_type* find_bucket(const String& key) const
-    {
-      size_type h = 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)];
-        if (entry->first.is_invalid() || entry->first.equals(key))
-          return entry;
-        h += i;
-      }
-    }
-
-    void resize(size_type bucketCount)
-    {
-      std::unique_ptr<entry_type[]> oldBuckets(std::move(mBuckets));
-      size_type oldCount = mBucketCount;
-
-      mEntryCount = 0;
-      mBucketCount = bucketCount;
-      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");
-
-      // Copy old entries into the new buffer
-      for (size_type i = 0; i < oldCount; i++)
-      {
-        entry_type& entry = oldBuckets[i];
-        if (!entry.first.is_invalid() && !entry.first.is_deleted())
-        {
-          *find_bucket(entry.first) = entry;
-          mEntryCount++;
-        }
-      }
-    }
-
-    entry_type* assign(entry_type* existing, const entry_type& entry)
-    {
-      if (existing->first.is_invalid())
-      {
-        if (mEntryCount + 1 >= mBucketCount * LOAD_FACTOR)
-        {
-          resize(mBucketCount << 1);
-          existing = find_bucket(entry.first);
-        }
-        mEntryCount++;
-#if defined(DEBUG)
-        mInsertCounter++;
-#endif
-      }
-      *existing = entry;
-      return existing;
-    }
-
-  public:
-    void insert(const entry_type& entry)
-    {
-      assign(find_bucket(entry.first), entry);
-    }
-
-    bool erase(const String& key)
-    {
-      entry_type* entry = find_bucket(key);
-      if (entry->first.is_invalid())
-        return false;
-
-      entry->first.erase();
-      return true;
-    }
-
-    const_reference find(const String& 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;
-    }
-  };
-
-  struct StringSetEntry
-  {
-    StringSetEntry() {}
-    StringSetEntry(const String& key)
-        : first(key)
-    {
-    }
-
-    DependentString first;
-  };
-
-  template<typename T>
-  struct StringMapEntry
-  {
-    StringMapEntry() {}
-    StringMapEntry(const String& key)
-        : first(key), second()
-    {
-    }
-    StringMapEntry(const String& key, T value)
-        : first(key), second(value)
-    {
-    }
-
-    DependentString first;
-    T second;
-  };
-
-  template<typename T>
-  struct StringMapEntryReference : public HashContainerReference<StringMapEntry<T>>
-  {
-    typedef HashContainerReference<StringMapEntry<T>> super;
-    typedef typename super::entry_type entry_type;
-    typedef StringMap<T> map_type;
-
-    map_type* mMap;
-
-#if defined(DEBUG)
-    typename map_type::size_type mInsertCounter;
-    typename map_type::size_type mHash;
-#endif
-
-    StringMapEntryReference(map_type* map, const String& key, entry_type* entry)
-        : super(entry), mMap(map)
-    {
-#if defined(DEBUG)
-      mInsertCounter = mMap->mInsertCounter;
-      mHash = mMap->hash(key);
-#endif
-    }
-
-    void assign(const String& key, const T& value)
-    {
-#if defined(DEBUG)
-      assert2(mInsertCounter == mMap->mInsertCounter,
-          u"There should be no insert operations performed between map.find() and assign()"_str);
-      assert2(mHash == mMap->hash(key),
-          u"The keys used in map.find() and assign() should be identical"_str);
-#endif
-
-      mMap->assign(this->mEntry, entry_type(key, value));
+      super::erase();
+      second = value_type();
     }
   };
 }
 
-class StringSet
-  : public StringMap_internal::HashContainer<StringMap_internal::StringSetEntry>
-{
-};
+using StringSet = Set<StringMap_internal::StringSetEntry>;
 
-template<typename T>
-class StringMap
-  : public StringMap_internal::HashContainer<StringMap_internal::StringMapEntry<T>>
-{
-public:
-  typedef StringMap_internal::HashContainer<StringMap_internal::StringMapEntry<T>> super;
-  typedef typename super::size_type size_type;
-  typedef typename super::entry_type entry_type;
-  typedef typename super::const_reference const_reference;
-  typedef StringMap_internal::StringMapEntryReference<T> reference;
-  friend struct StringMap_internal::StringMapEntryReference<T>;
-
-  explicit StringMap(size_type expectedEntries = 0)
-      : super(expectedEntries)
-  {
-  }
-
-  StringMap(std::initializer_list<entry_type> list)
-      : super(list.size())
-  {
-    for (const auto& item : list)
-      super::insert(item);
-  }
-
-  ~StringMap()
-  {
-  }
-
-  T& operator[](const String& key)
-  {
-    entry_type* entry = super::find_bucket(key);
-    if (entry->first.is_invalid())
-      entry = super::assign(entry, key);
-    return entry->second;
-  }
-
-  const_reference find(const String& key) const
-  {
-    return super::find(key);
-  }
-
-  reference find(const String& key)
-  {
-    return reference(this, key, super::find_bucket(key));
-  }
-};
+template<typename Value>
+using StringMap = Map<StringMap_internal::StringMapEntry<Value>>;