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: Minor improvements Created Feb. 6, 2016, 8:29 a.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
« no previous file with comments | « compiled/String.h ('k') | compiled/StringScanner.h » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: compiled/StringMap.h
===================================================================
new file mode 100644
--- /dev/null
+++ b/compiled/StringMap.h
@@ -0,0 +1,249 @@
+#pragma once
+
+#include <cstddef>
+#include <cmath>
+#include <initializer_list>
+
+#include "String.h"
+#include "debug.h"
+
+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);
+ }
+
+ _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<typename 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)
+ {
+ }
+
+ DependentString first;
+};
+
+class StringSet : public _HashContainer<_StringSetEntry>
+{
+};
+
+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>
+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;
+ }
+};
« no previous file with comments | « compiled/String.h ('k') | compiled/StringScanner.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld