1 /** 2 Internal hash map implementation. 3 4 Copyright: © 2013 RejectedSoftware e.K. 5 License: Subject to the terms of the MIT license, as written in the included LICENSE.txt file. 6 Authors: Sönke Ludwig 7 */ 8 module vibe.utils.hashmap; 9 10 import vibe.internal.utilallocator; 11 12 import std.conv : emplace; 13 import std.traits; 14 15 16 struct DefaultHashMapTraits(Key) { 17 enum clearValue = Key.init; 18 static bool equals(in Key a, in Key b) 19 { 20 static if (is(Key == class)) return a is b; 21 else return a == b; 22 } 23 static size_t hashOf(in ref Key k) 24 @safe { 25 static if (is(Key == class) && &Unqual!Key.init.toHash is &Object.init.toHash) 26 return () @trusted { return cast(size_t)cast(void*)k; } (); 27 else static if (__traits(compiles, Key.init.toHash())) 28 return () @trusted { return (cast(Key)k).toHash(); } (); 29 else static if (__traits(compiles, Key.init.toHashShared())) 30 return k.toHashShared(); 31 else { 32 // evil casts to be able to get the most basic operations of 33 // HashMap nothrow and @nogc 34 static size_t hashWrapper(in ref Key k) { 35 static typeinfo = typeid(Key); 36 return typeinfo.getHash(&k); 37 } 38 static @nogc nothrow size_t properlyTypedWrapper(in ref Key k) { return 0; } 39 return () @trusted { return (cast(typeof(&properlyTypedWrapper))&hashWrapper)(k); } (); 40 } 41 } 42 } 43 44 struct HashMap(TKey, TValue, Traits = DefaultHashMapTraits!TKey) 45 { 46 import core.memory : GC; 47 import vibe.internal.meta.traits : isOpApplyDg; 48 import std.algorithm.iteration : filter, map; 49 50 alias Key = TKey; 51 alias Value = TValue; 52 53 static if (__VERSION__ < 2074) { 54 struct AW { // work around AffixAllocator limitations 55 import std.algorithm.comparison : max; 56 IAllocator alloc; 57 alias alloc this; 58 enum alignment = max(Key.alignof, int.alignof); 59 void[] resolveInternalPointer(void* p) { void[] ret; alloc.resolveInternalPointer(p, ret); return ret; } 60 } 61 alias AllocatorType = AffixAllocator!(AW, int); 62 } else { 63 IAllocator AW(IAllocator a) { return a; } 64 alias AllocatorType = AffixAllocator!(IAllocator, int); 65 } 66 67 struct TableEntry { 68 UnConst!Key key = Traits.clearValue; 69 Value value; 70 71 this(ref Key key, ref Value value) 72 { 73 import std.algorithm.mutation : move; 74 this.key = cast(UnConst!Key)key; 75 this.value = value.move; 76 } 77 } 78 private { 79 TableEntry[] m_table; // NOTE: capacity is always POT 80 size_t m_length; 81 AllocatorType m_allocator; 82 bool m_resizing; 83 } 84 85 this(IAllocator allocator) 86 { 87 m_allocator = typeof(m_allocator)(AW(allocator)); 88 } 89 90 ~this() 91 { 92 int rc; 93 try rc = m_table is null ? 1 : () @trusted { return --m_allocator.prefix(m_table); } (); 94 catch (Exception e) assert(false, e.msg); 95 96 if (rc == 0) { 97 clear(); 98 if (m_table.ptr !is null) () @trusted { 99 static if (hasIndirections!TableEntry) GC.removeRange(m_table.ptr); 100 try m_allocator.dispose(m_table); 101 catch (Exception e) assert(false, e.msg); 102 } (); 103 } 104 } 105 106 this(this) 107 @trusted { 108 if (m_table.ptr) { 109 try m_allocator.prefix(m_table)++; 110 catch (Exception e) assert(false, e.msg); 111 } 112 } 113 114 @property size_t length() const { return m_length; } 115 116 void remove(Key key) 117 { 118 import std.algorithm.mutation : move; 119 120 auto idx = findIndex(key); 121 assert (idx != size_t.max, "Removing non-existent element."); 122 auto i = idx; 123 while (true) { 124 m_table[i].key = Traits.clearValue; 125 m_table[i].value = Value.init; 126 127 size_t j = i, r; 128 do { 129 if (++i >= m_table.length) i -= m_table.length; 130 if (Traits.equals(m_table[i].key, Traits.clearValue)) { 131 m_length--; 132 return; 133 } 134 r = Traits.hashOf(m_table[i].key) & (m_table.length-1); 135 } while ((j<r && r<=i) || (i<j && j<r) || (r<=i && i<j)); 136 m_table[j] = m_table[i].move; 137 } 138 } 139 140 Value get(Key key, lazy Value default_value = Value.init) 141 { 142 auto idx = findIndex(key); 143 if (idx == size_t.max) return default_value; 144 return m_table[idx].value; 145 } 146 147 /// Workaround #12647 148 package(vibe) Value getNothrow(Key key, Value default_value = Value.init) 149 { 150 auto idx = findIndex(key); 151 if (idx == size_t.max) return default_value; 152 return m_table[idx].value; 153 } 154 155 static if (!is(typeof({ Value v; const(Value) vc; v = vc; }))) { 156 const(Value) get(Key key, lazy const(Value) default_value = Value.init) 157 { 158 auto idx = findIndex(key); 159 if (idx == size_t.max) return default_value; 160 return m_table[idx].value; 161 } 162 } 163 164 void clear() 165 { 166 foreach (i; 0 .. m_table.length) 167 if (!Traits.equals(m_table[i].key, Traits.clearValue)) { 168 m_table[i].key = Traits.clearValue; 169 m_table[i].value = Value.init; 170 } 171 m_length = 0; 172 } 173 174 void opIndexAssign(T)(T value, Key key) 175 { 176 import std.algorithm.mutation : move; 177 178 assert(!Traits.equals(key, Traits.clearValue), "Inserting clear value into hash map."); 179 grow(1); 180 auto i = findInsertIndex(key); 181 if (!Traits.equals(m_table[i].key, key)) m_length++; 182 m_table[i].key = () @trusted { return cast(UnConst!Key)key; } (); 183 m_table[i].value = value; 184 } 185 186 ref inout(Value) opIndex(Key key) 187 inout { 188 auto idx = findIndex(key); 189 assert (idx != size_t.max, "Accessing non-existent key."); 190 return m_table[idx].value; 191 } 192 193 inout(Value)* opBinaryRight(string op)(Key key) 194 inout if (op == "in") { 195 auto idx = findIndex(key); 196 if (idx == size_t.max) return null; 197 return &m_table[idx].value; 198 } 199 200 int opApply(DG)(scope DG del) if (isOpApplyDg!(DG, Key, Value)) 201 { 202 import std.traits : arity; 203 foreach (i; 0 .. m_table.length) 204 if (!Traits.equals(m_table[i].key, Traits.clearValue)) { 205 static assert(arity!del >= 1 && arity!del <= 2, 206 "isOpApplyDg should have prevented this"); 207 static if (arity!del == 1) { 208 if (int ret = del(m_table[i].value)) 209 return ret; 210 } else 211 if (int ret = del(m_table[i].key, m_table[i].value)) 212 return ret; 213 } 214 return 0; 215 } 216 217 auto byKey() { return bySlot.map!(e => e.key); } 218 auto byKey() const { return bySlot.map!(e => e.key); } 219 auto byValue() { return bySlot.map!(e => e.value); } 220 auto byValue() const { return bySlot.map!(e => e.value); } 221 auto byKeyValue() { import std.typecons : Tuple; return bySlot.map!(e => Tuple!(Key, "key", Value, "value")(e.key, e.value)); } 222 auto byKeyValue() const { import std.typecons : Tuple; return bySlot.map!(e => Tuple!(const(Key), "key", const(Value), "value")(e.key, e.value)); } 223 224 private auto bySlot() { return m_table[].filter!(e => !Traits.equals(e.key, Traits.clearValue)); } 225 private auto bySlot() const { return m_table[].filter!(e => !Traits.equals(e.key, Traits.clearValue)); } 226 227 private size_t findIndex(Key key) 228 const { 229 if (m_length == 0) return size_t.max; 230 size_t start = Traits.hashOf(key) & (m_table.length-1); 231 auto i = start; 232 while (!Traits.equals(m_table[i].key, key)) { 233 if (Traits.equals(m_table[i].key, Traits.clearValue)) return size_t.max; 234 if (++i >= m_table.length) i -= m_table.length; 235 if (i == start) return size_t.max; 236 } 237 return i; 238 } 239 240 private size_t findInsertIndex(Key key) 241 const { 242 auto hash = Traits.hashOf(key); 243 size_t target = hash & (m_table.length-1); 244 auto i = target; 245 while (!Traits.equals(m_table[i].key, Traits.clearValue) && !Traits.equals(m_table[i].key, key)) { 246 if (++i >= m_table.length) i -= m_table.length; 247 assert (i != target, "No free bucket found, HashMap full!?"); 248 } 249 return i; 250 } 251 252 private void grow(size_t amount) 253 @trusted { 254 try { 255 static if (__VERSION__ < 2074) auto palloc = m_allocator.parent; 256 else auto palloc = m_allocator._parent; 257 if (!palloc) { 258 try m_allocator = typeof(m_allocator)(AW(vibeThreadAllocator())); 259 catch (Exception e) assert(false, e.msg); 260 } 261 } catch (Exception e) { 262 assert(false, e.msg); 263 } 264 265 auto newsize = m_length + amount; 266 if (newsize < (m_table.length*2)/3) { 267 int rc; 268 try rc = m_allocator.prefix(m_table); 269 catch (Exception e) assert(false, e.msg); 270 if (rc > 1) { 271 // enforce copy-on-write 272 auto oldtable = m_table; 273 try { 274 m_table = m_allocator.makeArray!TableEntry(m_table.length); 275 m_table[] = oldtable; 276 m_allocator.prefix(oldtable)--; 277 m_allocator.prefix(m_table) = 1; 278 } catch (Exception e) { 279 assert(false, e.msg); 280 } 281 } 282 return; 283 } 284 auto newcap = m_table.length ? m_table.length : 16; 285 while (newsize >= (newcap*2)/3) newcap *= 2; 286 resize(newcap); 287 } 288 289 private void resize(size_t new_size) 290 @trusted { 291 assert(!m_resizing); 292 m_resizing = true; 293 scope(exit) m_resizing = false; 294 295 uint pot = 0; 296 while (new_size > 1) { 297 pot++; 298 new_size /= 2; 299 } 300 new_size = 1 << pot; 301 302 auto oldtable = m_table; 303 304 // allocate the new array, automatically initializes with empty entries (Traits.clearValue) 305 try { 306 m_table = m_allocator.makeArray!TableEntry(new_size); 307 m_allocator.prefix(m_table) = 1; 308 } catch (Exception e) assert(false, e.msg); 309 static if (hasIndirections!TableEntry) GC.addRange(m_table.ptr, m_table.length * TableEntry.sizeof); 310 // perform a move operation of all non-empty elements from the old array to the new one 311 foreach (ref el; oldtable) 312 if (!Traits.equals(el.key, Traits.clearValue)) { 313 auto idx = findInsertIndex(el.key); 314 (cast(ubyte[])(&m_table[idx])[0 .. 1])[] = (cast(ubyte[])(&el)[0 .. 1])[]; 315 } 316 317 // all elements have been moved to the new array, so free the old one without calling destructors 318 int rc; 319 try rc = oldtable is null ? 1 : --m_allocator.prefix(oldtable); 320 catch (Exception e) assert(false, e.msg); 321 if (rc == 0) { 322 static if (hasIndirections!TableEntry) GC.removeRange(oldtable.ptr); 323 try m_allocator.deallocate(oldtable); 324 catch (Exception e) assert(false, e.msg); 325 } 326 } 327 } 328 329 unittest { 330 import std.conv; 331 332 HashMap!(string, string) map; 333 334 foreach (i; 0 .. 100) { 335 map[to!string(i)] = to!string(i) ~ "+"; 336 assert(map.length == i+1); 337 } 338 339 foreach (i; 0 .. 100) { 340 auto str = to!string(i); 341 auto pe = str in map; 342 assert(pe !is null && *pe == str ~ "+"); 343 assert(map[str] == str ~ "+"); 344 } 345 346 foreach (i; 0 .. 50) { 347 map.remove(to!string(i)); 348 assert(map.length == 100-i-1); 349 } 350 351 foreach (i; 50 .. 100) { 352 auto str = to!string(i); 353 auto pe = str in map; 354 assert(pe !is null && *pe == str ~ "+"); 355 assert(map[str] == str ~ "+"); 356 } 357 } 358 359 // test for nothrow/@nogc compliance 360 nothrow unittest { 361 HashMap!(int, int) map1; 362 HashMap!(string, string) map2; 363 map1[1] = 2; 364 map2["1"] = "2"; 365 366 @nogc nothrow void performNoGCOps() 367 { 368 foreach (int v; map1) {} 369 foreach (int k, int v; map1) {} 370 assert(1 in map1); 371 assert(map1.length == 1); 372 assert(map1[1] == 2); 373 assert(map1.getNothrow(1, -1) == 2); 374 375 foreach (string v; map2) {} 376 foreach (string k, string v; map2) {} 377 assert("1" in map2); 378 assert(map2.length == 1); 379 assert(map2["1"] == "2"); 380 assert(map2.getNothrow("1", "") == "2"); 381 } 382 383 performNoGCOps(); 384 } 385 386 unittest { // test for proper use of constructor/post-blit/destructor 387 static struct Test { 388 static size_t constructedCounter = 0; 389 bool constructed = false; 390 this(int) { constructed = true; constructedCounter++; } 391 this(this) nothrow { if (constructed) constructedCounter++; } 392 ~this() nothrow { if (constructed) constructedCounter--; } 393 } 394 395 assert(Test.constructedCounter == 0); 396 397 { // sanity check 398 Test t; 399 assert(Test.constructedCounter == 0); 400 t = Test(1); 401 assert(Test.constructedCounter == 1); 402 auto u = t; 403 assert(Test.constructedCounter == 2); 404 t = Test.init; 405 assert(Test.constructedCounter == 1); 406 } 407 assert(Test.constructedCounter == 0); 408 409 { // basic insertion and hash map resizing 410 HashMap!(int, Test) map; 411 foreach (i; 1 .. 67) { 412 map[i] = Test(1); 413 assert(Test.constructedCounter == i); 414 } 415 } 416 417 assert(Test.constructedCounter == 0); 418 419 { // test clear() and overwriting existing entries 420 HashMap!(int, Test) map; 421 foreach (i; 1 .. 67) { 422 map[i] = Test(1); 423 assert(Test.constructedCounter == i); 424 } 425 map.clear(); 426 foreach (i; 1 .. 67) { 427 map[i] = Test(1); 428 assert(Test.constructedCounter == i); 429 } 430 foreach (i; 1 .. 67) { 431 map[i] = Test(1); 432 assert(Test.constructedCounter == 66); 433 } 434 } 435 436 assert(Test.constructedCounter == 0); 437 438 { // test removing entries and adding entries after remove 439 HashMap!(int, Test) map; 440 foreach (i; 1 .. 67) { 441 map[i] = Test(1); 442 assert(Test.constructedCounter == i); 443 } 444 foreach (i; 1 .. 33) { 445 map.remove(i); 446 assert(Test.constructedCounter == 66 - i); 447 } 448 foreach (i; 67 .. 130) { 449 map[i] = Test(1); 450 assert(Test.constructedCounter == i - 32); 451 } 452 } 453 454 assert(Test.constructedCounter == 0); 455 } 456 457 private template UnConst(T) { 458 static if (is(T U == const(U))) { 459 alias UnConst = U; 460 } else static if (is(T V == immutable(V))) { 461 alias UnConst = V; 462 } else alias UnConst = T; 463 }