OLD | NEW |
(Empty) | |
| 1 #pragma once |
| 2 |
| 3 #include <cstddef> |
| 4 #include <cmath> |
| 5 #include <initializer_list> |
| 6 #include <memory> |
| 7 |
| 8 #include "String.h" |
| 9 #include "debug.h" |
| 10 |
| 11 template<typename T> |
| 12 class StringMap; |
| 13 |
| 14 namespace StringMap_internal |
| 15 { |
| 16 template<typename Entry> |
| 17 struct HashContainerIterator |
| 18 { |
| 19 typedef Entry entry_type; |
| 20 typedef HashContainerIterator<Entry> iterator; |
| 21 |
| 22 const entry_type* mPos; |
| 23 const entry_type* mEnd; |
| 24 |
| 25 explicit HashContainerIterator(const entry_type* start, const entry_type* en
d) |
| 26 : mPos(start), mEnd(end) |
| 27 { |
| 28 if (mPos != mEnd && mPos->first.is_invalid()) |
| 29 ++(*this); |
| 30 } |
| 31 |
| 32 const entry_type& operator*() const |
| 33 { |
| 34 return *mPos; |
| 35 } |
| 36 |
| 37 const entry_type* operator->() const |
| 38 { |
| 39 return mPos; |
| 40 } |
| 41 |
| 42 iterator& operator++() |
| 43 { |
| 44 do { |
| 45 ++mPos; |
| 46 } while(mPos != mEnd && mPos->first.is_invalid()); |
| 47 return *this; |
| 48 } |
| 49 |
| 50 bool operator==(const iterator& it) const |
| 51 { |
| 52 return mPos == it.mPos; |
| 53 } |
| 54 |
| 55 bool operator!=(const iterator& it) const |
| 56 { |
| 57 return mPos != it.mPos; |
| 58 } |
| 59 }; |
| 60 |
| 61 template<typename Entry> |
| 62 struct HashContainerReference |
| 63 { |
| 64 typedef Entry entry_type; |
| 65 |
| 66 entry_type* mEntry; |
| 67 |
| 68 explicit HashContainerReference(entry_type* entry) |
| 69 : mEntry(entry) |
| 70 { |
| 71 } |
| 72 |
| 73 const entry_type* operator->() const |
| 74 { |
| 75 return mEntry; |
| 76 } |
| 77 |
| 78 operator bool() const |
| 79 { |
| 80 return !mEntry->first.is_invalid(); |
| 81 } |
| 82 }; |
| 83 |
| 84 template<typename Entry> |
| 85 class HashContainer |
| 86 { |
| 87 public: |
| 88 typedef Entry entry_type; |
| 89 typedef size_t size_type; |
| 90 typedef HashContainerIterator<Entry> const_iterator; |
| 91 typedef HashContainerReference<const Entry> const_reference; |
| 92 |
| 93 private: |
| 94 explicit HashContainer(const HashContainer& other); |
| 95 void operator=(const HashContainer& other); |
| 96 |
| 97 protected: |
| 98 static constexpr size_type MIN_BUCKETS = 1; |
| 99 static constexpr double LOAD_FACTOR = 0.8; |
| 100 std::unique_ptr<entry_type[]> mBuckets; |
| 101 size_type mBucketCount; |
| 102 size_type mEntryCount; |
| 103 |
| 104 #if defined(DEBUG) |
| 105 size_type mInsertCounter; |
| 106 #endif |
| 107 |
| 108 explicit HashContainer(size_type expectedEntries = 0) |
| 109 : mEntryCount(0) |
| 110 { |
| 111 expectedEntries = ceil(expectedEntries / LOAD_FACTOR); |
| 112 mBucketCount = MIN_BUCKETS; |
| 113 while (mBucketCount < expectedEntries) |
| 114 mBucketCount <<= 1; |
| 115 |
| 116 mBuckets.reset(new entry_type[mBucketCount]); |
| 117 // Working around https://github.com/waywardmonkeys/emscripten-trace-colle
ctor/issues/2 here |
| 118 annotate_address(reinterpret_cast<size_type*>(mBuckets.get()) - 1, "Hash t
able buffer"); |
| 119 } |
| 120 |
| 121 static size_type hash(const String& str) |
| 122 { |
| 123 // FNV-1a hash function |
| 124 size_type result = 2166136261; |
| 125 for (String::size_type i = 0; i < str.length(); i++) |
| 126 result = (result ^ str[i]) * 16777619; |
| 127 return result; |
| 128 } |
| 129 |
| 130 entry_type* find_bucket(const String& key) const |
| 131 { |
| 132 size_type h = hash(key); |
| 133 |
| 134 // This does quadratic probing, effectively the following formula is used: |
| 135 // pos = (hash + 1/2 i + 1/2 i ^ 2) mod bucketCount |
| 136 for (size_type i = 0; ; ++i) |
| 137 { |
| 138 // mBucketCount is 2^n so (h & mBucketCount - 1) is equivalent to |
| 139 // h % mBucketCount but significantly faster. |
| 140 entry_type* entry = &mBuckets[h & (mBucketCount - 1)]; |
| 141 if (entry->first.is_invalid() || entry->first.equals(key)) |
| 142 return entry; |
| 143 h += i; |
| 144 } |
| 145 } |
| 146 |
| 147 void resize(size_type bucketCount) |
| 148 { |
| 149 std::unique_ptr<entry_type[]> oldBuckets(std::move(mBuckets)); |
| 150 size_type oldCount = mBucketCount; |
| 151 |
| 152 mEntryCount = 0; |
| 153 mBucketCount = bucketCount; |
| 154 mBuckets.reset(new entry_type[mBucketCount]); |
| 155 // Working around https://github.com/waywardmonkeys/emscripten-trace-colle
ctor/issues/2 here |
| 156 annotate_address(reinterpret_cast<size_type*>(mBuckets.get()) - 1, "Hash t
able buffer"); |
| 157 |
| 158 // Copy old entries into the new buffer |
| 159 for (size_type i = 0; i < oldCount; i++) |
| 160 { |
| 161 entry_type& entry = oldBuckets[i]; |
| 162 if (!entry.first.is_invalid() && !entry.first.is_deleted()) |
| 163 { |
| 164 *find_bucket(entry.first) = entry; |
| 165 mEntryCount++; |
| 166 } |
| 167 } |
| 168 } |
| 169 |
| 170 entry_type* assign(entry_type* existing, const entry_type& entry) |
| 171 { |
| 172 if (existing->first.is_invalid()) |
| 173 { |
| 174 if (mEntryCount + 1 >= mBucketCount * LOAD_FACTOR) |
| 175 { |
| 176 resize(mBucketCount << 1); |
| 177 existing = find_bucket(entry.first); |
| 178 } |
| 179 mEntryCount++; |
| 180 #if defined(DEBUG) |
| 181 mInsertCounter++; |
| 182 #endif |
| 183 } |
| 184 *existing = entry; |
| 185 return existing; |
| 186 } |
| 187 |
| 188 public: |
| 189 void insert(const entry_type& entry) |
| 190 { |
| 191 assign(find_bucket(entry.first), entry); |
| 192 } |
| 193 |
| 194 bool erase(const String& key) |
| 195 { |
| 196 entry_type* entry = find_bucket(key); |
| 197 if (entry->first.is_invalid()) |
| 198 return false; |
| 199 |
| 200 entry->first.erase(); |
| 201 return true; |
| 202 } |
| 203 |
| 204 const_reference find(const String& key) const |
| 205 { |
| 206 return const_reference(find_bucket(key)); |
| 207 } |
| 208 |
| 209 const_iterator begin() const |
| 210 { |
| 211 return const_iterator(&mBuckets[0], &mBuckets[mBucketCount]); |
| 212 } |
| 213 |
| 214 const_iterator end() const |
| 215 { |
| 216 return const_iterator(&mBuckets[mBucketCount], &mBuckets[mBucketCount]); |
| 217 } |
| 218 }; |
| 219 |
| 220 struct StringSetEntry |
| 221 { |
| 222 StringSetEntry() {} |
| 223 StringSetEntry(const String& key) |
| 224 : first(key) |
| 225 { |
| 226 } |
| 227 |
| 228 DependentString first; |
| 229 }; |
| 230 |
| 231 template<typename T> |
| 232 struct StringMapEntry |
| 233 { |
| 234 StringMapEntry() {} |
| 235 StringMapEntry(const String& key) |
| 236 : first(key), second() |
| 237 { |
| 238 } |
| 239 StringMapEntry(const String& key, T value) |
| 240 : first(key), second(value) |
| 241 { |
| 242 } |
| 243 |
| 244 DependentString first; |
| 245 T second; |
| 246 }; |
| 247 |
| 248 template<typename T> |
| 249 struct StringMapEntryReference : public HashContainerReference<StringMapEntry<
T>> |
| 250 { |
| 251 typedef HashContainerReference<StringMapEntry<T>> super; |
| 252 typedef typename super::entry_type entry_type; |
| 253 typedef StringMap<T> map_type; |
| 254 |
| 255 map_type* mMap; |
| 256 |
| 257 #if defined(DEBUG) |
| 258 typename map_type::size_type mInsertCounter; |
| 259 typename map_type::size_type mHash; |
| 260 #endif |
| 261 |
| 262 StringMapEntryReference(map_type* map, const String& key, entry_type* entry) |
| 263 : super(entry), mMap(map) |
| 264 { |
| 265 #if defined(DEBUG) |
| 266 mInsertCounter = mMap->mInsertCounter; |
| 267 mHash = mMap->hash(key); |
| 268 #endif |
| 269 } |
| 270 |
| 271 void assign(const String& key, const T& value) |
| 272 { |
| 273 #if defined(DEBUG) |
| 274 assert(mInsertCounter == mMap->mInsertCounter, |
| 275 u"There should be no insert operations performed between map.find() an
d assign()"_str); |
| 276 assert(mHash == mMap->hash(key), |
| 277 u"The keys used in map.find() and assign() should be identical"_str); |
| 278 #endif |
| 279 |
| 280 mMap->assign(this->mEntry, entry_type(key, value)); |
| 281 } |
| 282 }; |
| 283 } |
| 284 |
| 285 class StringSet |
| 286 : public StringMap_internal::HashContainer<StringMap_internal::StringSetEntry> |
| 287 { |
| 288 }; |
| 289 |
| 290 template<typename T> |
| 291 class StringMap |
| 292 : public StringMap_internal::HashContainer<StringMap_internal::StringMapEntry<
T>> |
| 293 { |
| 294 public: |
| 295 typedef StringMap_internal::HashContainer<StringMap_internal::StringMapEntry<T
>> super; |
| 296 typedef typename super::size_type size_type; |
| 297 typedef typename super::entry_type entry_type; |
| 298 typedef typename super::const_reference const_reference; |
| 299 typedef StringMap_internal::StringMapEntryReference<T> reference; |
| 300 friend class StringMap_internal::StringMapEntryReference<T>; |
| 301 |
| 302 explicit StringMap(size_type expectedEntries = 0) |
| 303 : super(expectedEntries) |
| 304 { |
| 305 } |
| 306 |
| 307 StringMap(std::initializer_list<entry_type> list) |
| 308 : super(list.size()) |
| 309 { |
| 310 for (auto it = list.begin(); it != list.end(); ++it) |
| 311 super::insert(*it); |
| 312 } |
| 313 |
| 314 ~StringMap() |
| 315 { |
| 316 } |
| 317 |
| 318 T& operator[](const String& key) |
| 319 { |
| 320 entry_type* entry = super::find_bucket(key); |
| 321 if (entry->first.is_invalid()) |
| 322 entry = super::assign(entry, key); |
| 323 return entry->second; |
| 324 } |
| 325 |
| 326 const_reference find(const String& key) const |
| 327 { |
| 328 return super::find(key); |
| 329 } |
| 330 |
| 331 reference find(const String& key) |
| 332 { |
| 333 return reference(this, key, super::find_bucket(key)); |
| 334 } |
| 335 }; |
OLD | NEW |