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 libasync.internals.hashmap; 9 import libasync.internals.memory; 10 11 import std.conv : emplace; 12 import std.traits; 13 14 15 struct DefaultHashMapTraits(Key) { 16 enum clearValue = Key.init; 17 static bool equals(in Key a, in Key b) 18 { 19 static if (is(Key == class)) return a is b; 20 else return a == b; 21 } 22 } 23 24 struct HashMap(Key, Value, Traits = DefaultHashMapTraits!Key) 25 { 26 struct TableEntry { 27 UnConst!Key key; 28 Value value; 29 30 this(Key key, Value value) { this.key = cast(UnConst!Key)key; this.value = value; } 31 } 32 private { 33 TableEntry[] m_table; // NOTE: capacity is always POT 34 size_t m_length; 35 Allocator m_allocator; 36 hash_t delegate(Key) m_hasher; 37 bool m_resizing; 38 } 39 40 this(Allocator allocator) 41 { 42 m_allocator = allocator; 43 } 44 45 ~this() 46 { 47 if (m_table) freeArray(m_allocator, m_table); 48 } 49 50 @disable this(this); 51 52 @property size_t length() const { return m_length; } 53 54 void remove(Key key) 55 { 56 auto idx = findIndex(key); 57 assert (idx != size_t.max, "Removing non-existent element."); 58 auto i = idx; 59 while (true) { 60 m_table[i].key = Traits.clearValue; 61 m_table[i].value = Value.init; 62 63 size_t j = i, r; 64 do { 65 if (++i >= m_table.length) i -= m_table.length; 66 if (Traits.equals(m_table[i].key, Traits.clearValue)) { 67 m_length--; 68 return; 69 } 70 r = m_hasher(m_table[i].key) & (m_table.length-1); 71 } while ((j<r && r<=i) || (i<j && j<r) || (r<=i && i<j)); 72 m_table[j] = m_table[i]; 73 } 74 } 75 76 Value get(Key key, lazy Value default_value = Value.init) 77 { 78 auto idx = findIndex(key); 79 if (idx == size_t.max) return default_value; 80 return m_table[idx].value; 81 } 82 83 static if (!is(typeof({ Value v; const(Value) vc; v = vc; }))) { 84 const(Value) get(Key key, lazy const(Value) default_value = Value.init) 85 { 86 auto idx = findIndex(key); 87 if (idx == size_t.max) return default_value; 88 return m_table[idx].value; 89 } 90 } 91 92 void clear() 93 { 94 foreach (i; 0 .. m_table.length) 95 if (!Traits.equals(m_table[i].key, Traits.clearValue)) { 96 m_table[i].key = Traits.clearValue; 97 m_table[i].value = Value.init; 98 } 99 m_length = 0; 100 } 101 102 void opIndexAssign(Value value, Key key) 103 { 104 assert(!Traits.equals(key, Traits.clearValue), "Inserting clear value into hash map."); 105 grow(1); 106 auto i = findInsertIndex(key); 107 if (!Traits.equals(m_table[i].key, key)) m_length++; 108 m_table[i] = TableEntry(key, value); 109 } 110 111 ref inout(Value) opIndex(Key key) 112 inout { 113 auto idx = findIndex(key); 114 assert (idx != size_t.max, "Accessing non-existent key."); 115 return m_table[idx].value; 116 } 117 118 inout(Value)* opBinaryRight(string op)(Key key) 119 inout if (op == "in") { 120 auto idx = findIndex(key); 121 if (idx == size_t.max) return null; 122 return &m_table[idx].value; 123 } 124 125 int opApply(int delegate(ref Value) del) 126 { 127 foreach (i; 0 .. m_table.length) 128 if (!Traits.equals(m_table[i].key, Traits.clearValue)) 129 if (auto ret = del(m_table[i].value)) 130 return ret; 131 return 0; 132 } 133 134 int opApply(int delegate(in ref Value) del) 135 const { 136 foreach (i; 0 .. m_table.length) 137 if (!Traits.equals(m_table[i].key, Traits.clearValue)) 138 if (auto ret = del(m_table[i].value)) 139 return ret; 140 return 0; 141 } 142 143 int opApply(int delegate(in ref Key, ref Value) del) 144 { 145 foreach (i; 0 .. m_table.length) 146 if (!Traits.equals(m_table[i].key, Traits.clearValue)) 147 if (auto ret = del(m_table[i].key, m_table[i].value)) 148 return ret; 149 return 0; 150 } 151 152 int opApply(int delegate(in ref Key, in ref Value) del) 153 const { 154 foreach (i; 0 .. m_table.length) 155 if (!Traits.equals(m_table[i].key, Traits.clearValue)) 156 if (auto ret = del(m_table[i].key, m_table[i].value)) 157 return ret; 158 return 0; 159 } 160 161 private size_t findIndex(Key key) 162 const { 163 if (m_length == 0) return size_t.max; 164 size_t start = m_hasher(key) & (m_table.length-1); 165 auto i = start; 166 while (!Traits.equals(m_table[i].key, key)) { 167 if (Traits.equals(m_table[i].key, Traits.clearValue)) return size_t.max; 168 if (++i >= m_table.length) i -= m_table.length; 169 if (i == start) return size_t.max; 170 } 171 return i; 172 } 173 174 private size_t findInsertIndex(Key key) 175 const { 176 auto hash = m_hasher(key); 177 size_t target = hash & (m_table.length-1); 178 auto i = target; 179 while (!Traits.equals(m_table[i].key, Traits.clearValue) && !Traits.equals(m_table[i].key, key)) { 180 if (++i >= m_table.length) i -= m_table.length; 181 assert (i != target, "No free bucket found, HashMap full!?"); 182 } 183 return i; 184 } 185 186 private void grow(size_t amount) 187 { 188 auto newsize = m_length + amount; 189 if (newsize < (m_table.length*2)/3) return; 190 auto newcap = m_table.length ? m_table.length : 16; 191 while (newsize >= (newcap*2)/3) newcap *= 2; 192 resize(newcap); 193 } 194 195 private void resize(size_t new_size) 196 { 197 assert(!m_resizing); 198 m_resizing = true; 199 scope(exit) m_resizing = false; 200 201 if (!m_allocator) m_allocator = defaultAllocator(); 202 if (!m_hasher) { 203 static if (__traits(compiles, (){ Key t; size_t hash = t.toHash(); }())) { 204 static if (isPointer!Key || is(Unqual!Key == class)) m_hasher = k => k ? k.toHash() : 0; 205 else m_hasher = k => k.toHash(); 206 } else static if (__traits(compiles, (){ Key t; size_t hash = t.toHashShared(); }())) { 207 static if (isPointer!Key || is(Unqual!Key == class)) m_hasher = k => k ? k.toHashShared() : 0; 208 else m_hasher = k => k.toHashShared(); 209 } else { 210 auto typeinfo = typeid(Key); 211 m_hasher = k => typeinfo.getHash(&k); 212 } 213 } 214 215 uint pot = 0; 216 while (new_size > 1) pot++, new_size /= 2; 217 new_size = 1 << pot; 218 219 auto oldtable = m_table; 220 m_table = allocArray!TableEntry(m_allocator, new_size); 221 foreach (ref el; m_table) { 222 static if (is(Key == struct)) { 223 emplace(cast(UnConst!Key*)&el.key); 224 static if (Traits.clearValue !is Key.init) 225 el.key = cast(UnConst!Key)Traits.clearValue; 226 } else el.key = cast(UnConst!Key)Traits.clearValue; 227 emplace(&el.value); 228 } 229 foreach (ref el; oldtable) 230 if (!Traits.equals(el.key, Traits.clearValue)) { 231 auto idx = findInsertIndex(el.key); 232 (cast(ubyte[])(&m_table[idx])[0 .. 1])[] = (cast(ubyte[])(&el)[0 .. 1])[]; 233 } 234 if (oldtable) freeArray(m_allocator, oldtable); 235 } 236 } 237 238 unittest { 239 import std.conv; 240 241 HashMap!(string, string) map; 242 243 foreach (i; 0 .. 100) { 244 map[to!string(i)] = to!string(i) ~ "+"; 245 assert(map.length == i+1); 246 } 247 248 foreach (i; 0 .. 100) { 249 auto str = to!string(i); 250 auto pe = str in map; 251 assert(pe !is null && *pe == str ~ "+"); 252 assert(map[str] == str ~ "+"); 253 } 254 255 foreach (i; 0 .. 50) { 256 map.remove(to!string(i)); 257 assert(map.length == 100-i-1); 258 } 259 260 foreach (i; 50 .. 100) { 261 auto str = to!string(i); 262 auto pe = str in map; 263 assert(pe !is null && *pe == str ~ "+"); 264 assert(map[str] == str ~ "+"); 265 } 266 } 267 268 private template UnConst(T) { 269 static if (is(T U == const(U))) { 270 alias UnConst = U; 271 } else static if (is(T V == immutable(V))) { 272 alias UnConst = V; 273 } else alias UnConst = T; 274 }