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 73 matching lines @@
   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:
-    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)
@@ skipping 25 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);

[sergei, 2016/06/16 21:16:42]

For the future: We need to take a look at the actual size of the container it
could be useful to grow faster at the beginning and slower starting from a
certain size.

[Wladimir Palant, 2016/12/06 10:47:35]

I already chose a fairly good initial size but this can always be optimized of
course.

           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()
     {

[sergei, 2016/06/16 21:16:43]

I have read again about default and value initialization, it looks a bit vague
how "second" member is initialized when it is a scalar, e.g. bool (see
ActiveFilter::mDomains), so I would recommend to add ", second{}" here to be
sure that it's always false.

[Wladimir Palant, 2016/12/06 10:47:37]

Done.

     }
     StringMapEntry(const String& key, T value)
         : first(key), second(value)
     {
     }
 
     DependentString first;
     T second;
   };
 
@@ skipping 78 matching lines @@
   const_reference find(const String& key) const
   {
     return super::find(key);
   }
 
   reference find(const String& key)
   {
     return reference(this, key, super::find_bucket(key));
   }
 };