OLD | NEW |
(Empty) | |
| 1 #pragma once |
| 2 |
| 3 #include <cstddef> |
| 4 #include <cmath> |
| 5 #include <initializer_list> |
| 6 |
| 7 #include "String.h" |
| 8 #include "debug.h" |
| 9 |
| 10 template<typename Entry> |
| 11 struct _HashContainerIterator |
| 12 { |
| 13 typedef Entry entry_type; |
| 14 typedef _HashContainerIterator<Entry> iterator; |
| 15 |
| 16 const entry_type* mPos; |
| 17 const entry_type* mEnd; |
| 18 |
| 19 explicit _HashContainerIterator(const entry_type* start, const entry_type* end
) |
| 20 : mPos(start), mEnd(end) |
| 21 { |
| 22 if (mPos != mEnd && mPos->first.is_invalid()) |
| 23 ++(*this); |
| 24 } |
| 25 |
| 26 _HashContainerIterator() |
| 27 { |
| 28 } |
| 29 |
| 30 const entry_type& operator*() const |
| 31 { |
| 32 return *mPos; |
| 33 } |
| 34 |
| 35 const entry_type* operator->() const |
| 36 { |
| 37 return mPos; |
| 38 } |
| 39 |
| 40 iterator& operator++() |
| 41 { |
| 42 do { |
| 43 ++mPos; |
| 44 } while(mPos != mEnd && mPos->first.is_invalid()); |
| 45 return *this; |
| 46 } |
| 47 |
| 48 bool operator==(const iterator& it) const |
| 49 { |
| 50 return mPos == it.mPos; |
| 51 } |
| 52 |
| 53 bool operator!=(const iterator& it) const |
| 54 { |
| 55 return mPos != it.mPos; |
| 56 } |
| 57 }; |
| 58 |
| 59 template<typename Entry> |
| 60 class _HashContainer |
| 61 { |
| 62 public: |
| 63 typedef Entry entry_type; |
| 64 typedef size_t size_type; |
| 65 typedef _HashContainerIterator<Entry> iterator; |
| 66 |
| 67 private: |
| 68 _HashContainer(const _HashContainer& other) {} |
| 69 void operator=(const _HashContainer& other) {} |
| 70 |
| 71 protected: |
| 72 static constexpr size_type MIN_BUCKETS = 1; |
| 73 static constexpr double LOAD_FACTOR = 0.8; |
| 74 entry_type* mBuckets; |
| 75 size_type mBucketCount; |
| 76 size_type mEntryCount; |
| 77 |
| 78 explicit _HashContainer(size_type expectedEntries = 0) |
| 79 : mEntryCount(0) |
| 80 { |
| 81 expectedEntries = ceil(expectedEntries / LOAD_FACTOR); |
| 82 mBucketCount = MIN_BUCKETS; |
| 83 while (mBucketCount < expectedEntries) |
| 84 mBucketCount <<= 1; |
| 85 |
| 86 mBuckets = new entry_type[mBucketCount]; |
| 87 // Working around https://github.com/waywardmonkeys/emscripten-trace-collect
or/issues/2 here |
| 88 annotate_address(reinterpret_cast<size_type*>(mBuckets) - 1, "Hash table buf
fer"); |
| 89 } |
| 90 |
| 91 ~_HashContainer() |
| 92 { |
| 93 delete[] mBuckets; |
| 94 } |
| 95 |
| 96 static size_type hash(const String& str) |
| 97 { |
| 98 // FNV-1a hash function |
| 99 size_type result = 2166136261; |
| 100 for (String::size_type i = 0; i < str.length(); i++) |
| 101 result = (result ^ str[i]) * 16777619; |
| 102 return result; |
| 103 } |
| 104 |
| 105 entry_type* find_entry(const String& key) const |
| 106 { |
| 107 size_type h = hash(key); |
| 108 |
| 109 // This does quadratic probing, effectively the following formula is used: |
| 110 // pos = (hash + 1/2 i + 1/2 i ^ 2) mod bucketCount |
| 111 for (size_type i = 0; ; ++i) |
| 112 { |
| 113 entry_type* entry = mBuckets + h % mBucketCount; |
| 114 if (entry->first.is_invalid() || entry->first.equals(key)) |
| 115 return entry; |
| 116 h += i; |
| 117 } |
| 118 } |
| 119 |
| 120 void resize(size_type bucketCount) |
| 121 { |
| 122 entry_type* oldBuckets = mBuckets; |
| 123 size_type oldCount = mBucketCount; |
| 124 |
| 125 mEntryCount = 0; |
| 126 mBucketCount = bucketCount; |
| 127 mBuckets = new entry_type[mBucketCount]; |
| 128 // Working around https://github.com/waywardmonkeys/emscripten-trace-collect
or/issues/2 here |
| 129 annotate_address(reinterpret_cast<size_type*>(mBuckets) - 1, "Hash table buf
fer"); |
| 130 |
| 131 for (size_type i = 0; i < oldCount; i++) |
| 132 { |
| 133 entry_type& entry = oldBuckets[i]; |
| 134 if (!entry.first.is_invalid()) |
| 135 { |
| 136 *find_entry(entry.first) = entry; |
| 137 mEntryCount++; |
| 138 } |
| 139 } |
| 140 |
| 141 delete[] oldBuckets; |
| 142 } |
| 143 |
| 144 entry_type* assign(entry_type* existing, const entry_type& entry) |
| 145 { |
| 146 bool added = existing->first.is_invalid(); |
| 147 *existing = entry; |
| 148 if (added) |
| 149 { |
| 150 mEntryCount++; |
| 151 if (mEntryCount >= mBucketCount * LOAD_FACTOR) |
| 152 { |
| 153 resize(mBucketCount << 1); |
| 154 existing = find_entry(entry.first); |
| 155 } |
| 156 } |
| 157 return existing; |
| 158 } |
| 159 |
| 160 public: |
| 161 void insert(const entry_type& entry) |
| 162 { |
| 163 assign(find_entry(entry.first), entry); |
| 164 } |
| 165 |
| 166 iterator find(const String& key) const |
| 167 { |
| 168 entry_type* entry = find_entry(key); |
| 169 if (entry->first.is_invalid()) |
| 170 return end(); |
| 171 else |
| 172 return iterator(entry, mBuckets + mBucketCount); |
| 173 } |
| 174 |
| 175 iterator begin() const |
| 176 { |
| 177 return iterator(mBuckets, mBuckets + mBucketCount); |
| 178 } |
| 179 |
| 180 iterator end() const |
| 181 { |
| 182 return iterator(mBuckets + mBucketCount, mBuckets + mBucketCount); |
| 183 } |
| 184 }; |
| 185 |
| 186 struct _StringSetEntry |
| 187 { |
| 188 _StringSetEntry() {} |
| 189 _StringSetEntry(const String& key) |
| 190 : first(key) |
| 191 { |
| 192 } |
| 193 |
| 194 DependentString first; |
| 195 }; |
| 196 |
| 197 class StringSet : public _HashContainer<_StringSetEntry> |
| 198 { |
| 199 }; |
| 200 |
| 201 template<typename T> |
| 202 struct _StringMapEntry |
| 203 { |
| 204 _StringMapEntry() {} |
| 205 _StringMapEntry(const String& key) |
| 206 : first(key) |
| 207 { |
| 208 } |
| 209 _StringMapEntry(const String& key, T value) |
| 210 : first(key), second(value) |
| 211 { |
| 212 } |
| 213 |
| 214 DependentString first; |
| 215 T second; |
| 216 }; |
| 217 |
| 218 template<typename T> |
| 219 class StringMap : public _HashContainer<_StringMapEntry<T>> |
| 220 { |
| 221 public: |
| 222 typedef _HashContainer<_StringMapEntry<T>> super; |
| 223 typedef typename super::size_type size_type; |
| 224 typedef typename super::entry_type entry_type; |
| 225 |
| 226 explicit StringMap(size_type expectedEntries = 0) |
| 227 : super(expectedEntries) |
| 228 { |
| 229 } |
| 230 |
| 231 StringMap(std::initializer_list<entry_type> list) |
| 232 : super(list.size()) |
| 233 { |
| 234 for (auto it = list.begin(); it != list.end(); ++it) |
| 235 super::insert(*it); |
| 236 } |
| 237 |
| 238 ~StringMap() |
| 239 { |
| 240 } |
| 241 |
| 242 T& operator[](const String& key) |
| 243 { |
| 244 entry_type* entry = super::find_entry(key); |
| 245 if (entry->first.is_invalid()) |
| 246 entry = super::assign(entry, key); |
| 247 return entry->second; |
| 248 } |
| 249 }; |
OLD | NEW |