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; |
+ } |
+}; |