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())
@@ skipping 11 matching lines @@
       *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;
   };
@@ skipping 19 matching lines @@
       mInsertCounter = mMap->mInsertCounter;
       mHash = mMap->hash(key);
 #endif
     }
 
     void assign(const String& key, const T& value)
     {
 #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),

[sergei, 2016/02/23 15:07:36]

It might be better to compare keys instead of hashes.

[Wladimir Palant, 2016/02/23 21:35:00]

a) We cannot really keep a reference to the key since it might be referring to a
temporary buffer which is subject to change - this code is meant to protect
against this very scenario.

b) If it is a different key with the same hash - we don't really care. The
important thing is that its hash matches the bucket it is in so that it can be
found there.

           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>
@@ skipping 39 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));
   }
 };