Issue 4125 - [emscripten] Convert filter classes to C++

compiled/StringMap.h

 #pragma once
 
 #include <cstddef>
 #include <cmath>
 #include <initializer_list>
 #include <memory>
 
 #include "String.h"
 #include "debug.h"
 
@@ skipping 45 matching lines @@
     {
       return mPos != it.mPos;
     }
   };
 
   template<typename Entry>
   struct HashContainerReference
   {
     typedef Entry entry_type;
 
-    const entry_type* mEntry;
-
-    explicit HashContainerReference(const entry_type* entry)
+    entry_type* mEntry;
+
+    explicit HashContainerReference(entry_type* entry)
         : mEntry(entry)
     {
     }
 
     const entry_type* operator->() const
     {
       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<Entry> const_reference;
+    typedef HashContainerReference<const Entry> const_reference;
 
   private:
-    HashContainer(const HashContainer& other);
+    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
@@ skipping 12 matching lines @@
     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];
+        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())
+        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]);
     }
 
@@ skipping 12 matching lines @@
     }
 
     DependentString first;
   };
 
   template<typename T>
   struct StringMapEntry
   {
     StringMapEntry() {}
     StringMapEntry(const String& key)
-        : first(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;
 
-    StringMapEntryReference(map_type* map, const entry_type* entry)
+#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)

[sergei, 2016/02/22 12:46:03]

I have noticed a couple of asserts here in the repository, what about removing
`key` argument and use only `value`?

[Wladimir Palant, 2016/02/23 12:37:36]

As explained under https://codereview.adblockplus.org/29333474/#msg21, this
approach is quite a hack. However, I don't see a better way - the key passed
into find() and the one here aren't the same. The former refers to a temporary
buffer which will go away, the latter to an actual OwnedString that we can store
a reference to (it's only created if the lookup via find() doesn't yield a
result). The asserts I added verify that both actually have the same value which
makes this somewhat safer.

     {
-      mMap->assign(const_cast<entry_type*>(super::mEntry), entry_type(key, value));

[sergei, 2016/02/22 12:46:02]

`super::mEntry` is also accessible by `this->mEntry`.

[sergei, 2016/02/22 12:46:05]

It's not necessary to use `const_cast` here. We can remove `const` modifier for
`HashContainerReference::mEntry` and use `typedef HashContainerReference<const
Entry> const_reference;` inside `HashContainer`.

[Wladimir Palant, 2016/02/23 12:37:34]

Done.

[Wladimir Palant, 2016/02/23 12:37:37]

Done.

+#if defined(DEBUG)
+      assert(mInsertCounter == mMap->mInsertCounter,
+          u"There should be no insert operations performed between map.find() and assign()"_str);
+      assert(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));
     }
   };
 }
 
 class StringSet
   : public StringMap_internal::HashContainer<StringMap_internal::StringSetEntry>
 {
 };
 
 template<typename T>
@@ skipping 32 matching lines @@
     return entry->second;
   }
 
   const_reference find(const String& key) const
   {
     return super::find(key);
   }
 
   reference find(const String& key)
   {
-    return reference(this, super::find_bucket(key));
+    return reference(this, key, super::find_bucket(key));
   }
 };