Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code

Unified Diff: compiled/StringMap.h

Issue 29333474: Issue 4125 - [emscripten] Convert filter classes to C++ (Closed)
Patch Set: Rebased, addressed comments, changed StringMap::find() return value Created Feb. 18, 2016, 4:02 p.m.
Use n/p to move between diff chunks; N/P to move between comments.
Jump to:
View side-by-side diff with in-line comments
Download patch
Index: compiled/StringMap.h
===================================================================
new file mode 100644
--- /dev/null
+++ b/compiled/StringMap.h
@@ -0,0 +1,302 @@
+#pragma once
+
+#include <cstddef>
+#include <cmath>
+#include <initializer_list>
+#include <memory>
+
+#include "String.h"
+#include "debug.h"
+
+template<typename T>
+class StringMap;
+
+namespace StringMap_internal
+{
+ template<typename Entry>
+ 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);
+ }
+
+ 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<typename Entry>
+ struct HashContainerReference
+ {
+ typedef Entry entry_type;
+
+ const entry_type* mEntry;
+
+ explicit HashContainerReference(const 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;
+
+ 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;
+ std::unique_ptr<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.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())
+ {
+ *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++;
+ }
+ *existing = entry;
+ return existing;
+ }
+
+ public:
+ void insert(const entry_type& entry)
+ {
+ assign(find_bucket(entry.first), entry);
+ }
+
+ 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]);
+ }
+ };
+
+ struct StringSetEntry
+ {
+ StringSetEntry() {}
+ StringSetEntry(const String& key)
+ : first(key)
+ {
+ }
+
+ DependentString first;
+ };
+
+ template<typename T>
+ struct StringMapEntry
+ {
+ StringMapEntry() {}
+ StringMapEntry(const String& key)
+ : first(key)
+ {
+ }
+ 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)
+ : super(entry), mMap(map)
+ {
+ }
+
+ 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 rep
Wladimir Palant 2016/02/23 12:37:36 As explained under https://codereview.adblockplus.
+ {
+ 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->mEntr
sergei 2016/02/22 12:46:05 It's not necessary to use `const_cast` here. We ca
Wladimir Palant 2016/02/23 12:37:34 Done.
Wladimir Palant 2016/02/23 12:37:37 Done.
+ }
+ };
+}
+
+class StringSet
+ : public StringMap_internal::HashContainer<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 class StringMap_internal::StringMapEntryReference<T>;
+
+ 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_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, super::find_bucket(key));
+ }
+};

Powered by Google App Engine
This is Rietveld