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

compiled/StringMap.h

Index: compiled/StringMap.h
===================================================================
new file mode 100644
--- /dev/null
+++ b/compiled/StringMap.h
@@ -0,0 +1,252 @@
+#ifndef ADBLOCK_PLUS_STRING_MAP_H
+#define ADBLOCK_PLUS_STRING_MAP_H
+
+#include <cstddef>
+#include <cmath>
+#include <initializer_list>
+
+#include "String.h"
+#include "debug.h"
+
+template<class Entry>

[René Jeschke, 2016/02/02 11:11:22]

Nit: The usage of `class` for declaring template parameters is discouraged,
`typename` should be used instead. There are only very few special cases where
`class` should/must be used.
See: http://blogs.msdn.com/b/slippman/archive/2004/08/11/212768.aspx

[Wladimir Palant, 2016/02/02 17:55:18]

Done.

+struct _HashContainerIterator
+{
+  typedef Entry entry_type;
+  typedef _HashContainerIterator<Entry> iterator;
+
+  const entry_type* mPos;
+  const entry_type* mEnd;
+
+  explicit _HashContainerIterator(const entry_type* start, const entry_type* end)
+      : mPos(start), mEnd(end)
+  {
+    if (mPos != mEnd && mPos->first.is_invalid())
+      ++(*this);
+  }
+
+  _HashContainerIterator()
+  {
+  }
+
+  const entry_type& operator*() const
+  {
+    return *mPos;
+  }
+
+  const entry_type* operator->() const
+  {
+    return mPos;
+  }
+
+  iterator& operator++()
+  {
+    do {
+      ++mPos;
+    } while(mPos != mEnd && mPos->first.is_invalid());
+    return *this;
+  }
+
+  bool operator==(const iterator& it) const
+  {
+    return mPos == it.mPos;
+  }
+
+  bool operator!=(const iterator& it) const
+  {
+    return mPos != it.mPos;
+  }
+};
+
+template<class Entry>
+class _HashContainer
+{
+public:
+  typedef Entry entry_type;
+  typedef size_t size_type;
+  typedef _HashContainerIterator<Entry> iterator;
+
+private:
+  _HashContainer(const _HashContainer& other) {}
+  void operator=(const _HashContainer& other) {}
+
+protected:
+  static constexpr size_type MIN_BUCKETS = 1;
+  static constexpr double LOAD_FACTOR = 0.8;
+  entry_type* mBuckets;
+  size_type mBucketCount;
+  size_type mEntryCount;
+
+  explicit _HashContainer(size_type expectedEntries = 0)
+      : mEntryCount(0)
+  {
+    expectedEntries = ceil(expectedEntries / LOAD_FACTOR);
+    mBucketCount = MIN_BUCKETS;
+    while (mBucketCount < expectedEntries)
+      mBucketCount <<= 1;
+
+    mBuckets = new entry_type[mBucketCount];
+    // Working around https://github.com/waywardmonkeys/emscripten-trace-collector/issues/2 here
+    annotate_address(reinterpret_cast<size_type*>(mBuckets) - 1, "Hash table buffer");
+  }
+
+  ~_HashContainer()
+  {
+    delete[] mBuckets;
+  }
+
+  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_entry(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)
+    {
+      entry_type* entry = mBuckets + h % mBucketCount;
+      if (entry->first.is_invalid() || entry->first.equals(key))
+        return entry;
+      h += i;
+    }
+  }
+
+  void resize(size_type bucketCount)
+  {
+    entry_type* oldBuckets = mBuckets;
+    size_type oldCount = mBucketCount;
+
+    mEntryCount = 0;
+    mBucketCount = bucketCount;
+    mBuckets = new entry_type[mBucketCount];
+    // Working around https://github.com/waywardmonkeys/emscripten-trace-collector/issues/2 here
+    annotate_address(reinterpret_cast<size_type*>(mBuckets) - 1, "Hash table buffer");
+
+    for (size_type i = 0; i < oldCount; i++)
+    {
+      entry_type& entry = oldBuckets[i];
+      if (!entry.first.is_invalid())
+      {
+        *find_entry(entry.first) = entry;
+        mEntryCount++;
+      }
+    }
+
+    delete[] oldBuckets;
+  }
+
+  entry_type* assign(entry_type* existing, const entry_type& entry)
+  {
+    bool added = existing->first.is_invalid();
+    *existing = entry;
+    if (added)
+    {
+      mEntryCount++;
+      if (mEntryCount >= mBucketCount * LOAD_FACTOR)
+      {
+        resize(mBucketCount << 1);
+        existing = find_entry(entry.first);
+      }
+    }
+    return existing;
+  }
+
+public:
+  void insert(const entry_type& entry)
+  {
+    assign(find_entry(entry.first), entry);
+  }
+
+  iterator find(const String& key) const
+  {
+    entry_type* entry = find_entry(key);
+    if (entry->first.is_invalid())
+      return end();
+    else
+      return iterator(entry, mBuckets + mBucketCount);
+  }
+
+  iterator begin() const
+  {
+    return iterator(mBuckets, mBuckets + mBucketCount);
+  }
+
+  iterator end() const
+  {
+    return iterator(mBuckets + mBucketCount, mBuckets + mBucketCount);
+  }
+};
+
+struct _StringSetEntry
+{
+  _StringSetEntry() {}
+  _StringSetEntry(const String& key)
+      : first(key)
+  {
+  }
+
+  String first;
+};
+
+class StringSet : public _HashContainer<_StringSetEntry>
+{
+};
+
+template<class T>
+struct _StringMapEntry
+{
+  _StringMapEntry() {}
+  _StringMapEntry(const String& key)
+      : first(key)
+  {
+  }
+  _StringMapEntry(const String& key, T value)
+      : first(key), second(value)
+  {
+  }
+
+  String first;
+  T second;
+};
+
+template<class T>
+class StringMap : public _HashContainer<_StringMapEntry<T>>
+{
+public:
+  typedef _HashContainer<_StringMapEntry<T>> super;
+  typedef typename super::size_type size_type;
+  typedef typename super::entry_type entry_type;
+
+  explicit StringMap(size_type expectedEntries = 0)
+      : super(expectedEntries)
+  {
+  }
+
+  StringMap(std::initializer_list<entry_type> list)
+      : super(list.size())
+  {
+    for (auto it = list.begin(); it != list.end(); ++it)
+      super::insert(*it);
+  }
+
+  ~StringMap()
+  {
+  }
+
+  T& operator[](const String& key)
+  {
+    entry_type* entry = super::find_entry(key);
+    if (entry->first.is_invalid())
+      entry = super::assign(entry, key);
+    return entry->second;
+  }
+};
+
+#endif