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 file. 6 Authors: Sönke Ludwig 7 */ 8 module memutils.hashmap; 9 10 import std.conv : emplace, to; 11 import std.traits; 12 import std.algorithm : countUntil; 13 import memutils.refcounted; 14 import memutils.constants; 15 import memutils.helpers; 16 import memutils.allocators; 17 import memutils.utils; 18 19 20 alias HashMapRef(Key, Value, ALLOC = ThreadMem) = RefCounted!(HashMap!(Key, Value, ALLOC), ALLOC); 21 22 struct HashMap(Key, Value, ALLOC = ThreadMem) 23 { 24 @disable this(this); 25 26 alias Traits = DefaultHashMapTraits!Key; 27 struct TableEntry { 28 UnConst!Key key; 29 Value value; 30 31 this(Key key, Value value) { this.key = cast(UnConst!Key)key; this.value = value; } 32 } 33 private { 34 TableEntry[] m_table; // NOTE: capacity is always POT 35 size_t m_length; 36 hash_t delegate(Key) m_hasher; 37 bool m_resizing; 38 } 39 40 nothrow ~this() 41 { 42 try { 43 clear(); 44 if (m_table) freeArray!(TableEntry, ALLOC)(m_table); 45 } catch(Throwable e) { assert(false, e.toString()); } 46 } 47 48 @property bool empty() const { return length == 0; } 49 @property size_t length() const { return m_length; } 50 51 void remove(Key key) 52 { 53 //static if (Key.stringof.countUntil("OIDImpl") != -1) logError("Removing: ", key.toString()); 54 auto idx = findIndex(key); 55 assert (idx != size_t.max, "Removing non-existent element."); 56 auto i = idx; 57 while (true) { 58 m_table[i].key = Traits.clearValue; 59 m_table[i].value = Value.init; 60 size_t j = i, r; 61 do { 62 if (++i >= m_table.length) i -= m_table.length; 63 if (Traits.equals(m_table[i].key, Traits.clearValue)) { 64 m_length--; 65 return; 66 } 67 r = m_hasher(m_table[i].key) & (m_table.length-1); 68 69 } while ((j<r && r<=i) || (i<j && j<r) || (r<=i && i<j)); 70 m_table[j] = m_table[i]; 71 } 72 } 73 74 Value get(in Key key, lazy Value default_value = Value.init) const 75 { 76 auto idx = this.findIndex(key); 77 if (idx == size_t.max) return default_value; 78 const Value ret = m_table[idx].value; 79 return *cast(Value*)&ret; 80 } 81 /* 82 static if (!is(typeof({ Value v; const(Value) vc; v = vc; }))) { 83 const(Value) get(Key key, lazy const(Value) default_value = Value.init) 84 { 85 auto idx = findIndex(key); 86 if (idx == size_t.max) return default_value; 87 return m_table[idx].value; 88 } 89 }*/ 90 91 void clear() 92 { 93 foreach (i; 0 .. m_table.length) 94 if (!Traits.equals(m_table[i].key, Traits.clearValue)) { 95 m_table[i].key = Traits.clearValue; 96 m_table[i].value = Value.init; 97 } 98 m_length = 0; 99 } 100 101 void set(Key key, Value value) { 102 opIndexAssign(value, key); 103 } 104 105 106 void opIndexAssign(inout Value value, in Key key) 107 { 108 //assert(!Traits.equals(key, Traits.clearValue), "Inserting clear value into hash map."); 109 grow(1); 110 auto i = findInsertIndex(key); 111 if (!Traits.equals(m_table[i].key, key)) m_length++; 112 m_table[i] = TableEntry(*cast(Key*) &key, *cast(Value*) &value); 113 } 114 115 ref inout(Value) opIndex(Key key) inout { 116 auto idx = findIndex(key); 117 assert (idx != size_t.max, "Accessing non-existent key type: " ~ Key.stringof ~ " value: " ~ key.to!string); 118 return m_table[idx].value; 119 } 120 121 Value opIndex(Key key) const { 122 auto idx = findIndex(key); 123 assert (idx != size_t.max, "Accessing non-existent key type: " ~ Key.stringof ~ " value: " ~ key.to!string); 124 const Value ret = m_table[idx].value; 125 return *cast(Value*) &ret; 126 } 127 128 inout(Value)* opBinaryRight(string op)(Key key) 129 inout if (op == "in") { 130 auto idx = findIndex(key); 131 if (idx == size_t.max) return null; 132 return &m_table[idx].value; 133 } 134 135 int opApply(int delegate(ref Value) del) 136 { 137 foreach (i; 0 .. m_table.length) 138 if (!Traits.equals(m_table[i].key, Traits.clearValue)) 139 if (auto ret = del(m_table[i].value)) 140 return ret; 141 return 0; 142 } 143 144 int opApply(int delegate(in ref Value) del) 145 const { 146 foreach (i; 0 .. m_table.length) 147 if (!Traits.equals(m_table[i].key, Traits.clearValue)) 148 if (auto ret = del(m_table[i].value)) 149 return ret; 150 return 0; 151 } 152 153 int opApply(int delegate(const ref Key, ref Value) del) 154 { 155 foreach (i; 0 .. m_table.length) 156 if (!Traits.equals(m_table[i].key, Traits.clearValue)) 157 if (auto ret = del(m_table[i].key, m_table[i].value)) 158 return ret; 159 return 0; 160 } 161 162 int opApply(int delegate(in ref Key, in ref Value) del) 163 const { 164 foreach (i; 0 .. m_table.length) 165 if (!Traits.equals(m_table[i].key, Traits.clearValue)) 166 if (auto ret = del(m_table[i].key, m_table[i].value)) 167 return ret; 168 return 0; 169 } 170 171 private size_t findIndex(in Key key) 172 const { 173 if (m_length == 0) return size_t.max; 174 size_t start = m_hasher(*cast(Key*) &key) & (m_table.length-1); 175 auto i = start; 176 while (!Traits.equals(m_table[i].key, key)) { 177 if (Traits.equals(m_table[i].key, Traits.clearValue)) return size_t.max; 178 if (++i >= m_table.length) i -= m_table.length; 179 if (i == start) return size_t.max; 180 } 181 return i; 182 } 183 184 private size_t findInsertIndex(in Key key) 185 const { 186 auto hash = m_hasher(*cast(Key*) &key); 187 size_t target = hash & (m_table.length-1); 188 auto i = target; 189 while (!Traits.equals(m_table[i].key, Traits.clearValue) && !Traits.equals(m_table[i].key, key)) { 190 if (++i >= m_table.length) i -= m_table.length; 191 assert (i != target, "No free bucket found, HashMap full!?"); 192 } 193 return i; 194 } 195 196 private void grow(size_t amount) 197 { 198 auto newsize = m_length + amount; 199 if (newsize < (m_table.length*2)/3) return; 200 auto newcap = m_table.length ? m_table.length : 16; 201 while (newsize >= (newcap*2)/3) newcap *= 2; 202 resize(newcap); 203 } 204 205 private void resize(size_t new_size) 206 { 207 assert(!m_resizing); 208 m_resizing = true; 209 scope(exit) m_resizing = false; 210 211 if (!m_hasher) { 212 setupHasher(); 213 } 214 215 // logTrace("Resizing ", Key.stringof, " : ", Value.stringof, " : ", cast(void*)&this, " from ", m_table.length, " to: ", new_size); 216 217 uint pot = 0; 218 while (new_size > 1) pot++, new_size /= 2; 219 new_size = 1 << pot; 220 auto old_size = m_table.length; 221 assert(new_size > old_size); // TODO: Allow hashmap to become smaller? 222 auto oldtable = m_table; 223 m_table = allocArray!(TableEntry, ALLOC)(new_size); 224 225 /// fixme: Use initializeAll ? 226 /// 227 foreach (ref el; m_table) { 228 static if (is(Key == struct)) { 229 emplace(cast(UnConst!Key*)&el.key); 230 static if (Traits.clearValue !is Key.init) 231 el.key = cast(UnConst!Key)Traits.clearValue; 232 } else el.key = cast(UnConst!Key)Traits.clearValue; 233 emplace(&el.value); 234 } 235 foreach (ref el; oldtable) 236 if (!Traits.equals(el.key, Traits.clearValue)) { 237 auto idx = findInsertIndex(el.key); 238 (cast(ubyte[])(&m_table[idx])[0 .. 1])[] = (cast(ubyte[])(&el)[0 .. 1])[]; 239 } 240 241 if (oldtable) freeArray!(TableEntry, ALLOC)(oldtable, 0); 242 logTrace("Now have ", m_table.length); 243 } 244 245 void setupHasher() { 246 247 248 static if ((__traits(hasMember, Key, "isRefCounted") && __traits(hasMember, typeof(*(Key())), "toArray") ) || 249 __traits(hasMember, Key, "toArray")) 250 { 251 m_hasher = (Key k) { 252 import std.typecons : scoped; 253 import memutils.vector : Array; 254 Array!ubyte s = k.toArray(); 255 size_t hash = hashOf(s[], 0); 256 return hash; 257 }; 258 } 259 else static if ((__traits(hasMember, Key, "isRefCounted") && __traits(hasMember, typeof(*(Key())), "toVector") ) || 260 __traits(hasMember, Key, "toVector")) 261 { 262 m_hasher = (Key k) { 263 import std.typecons : scoped; 264 import memutils.vector : Vector; 265 Vector!char s = k.toVector(); 266 size_t hash = hashOf(s[], 0); 267 return hash; 268 }; 269 } 270 else static if (( __traits(hasMember, Key, "isRefCounted") && __traits(hasMember, typeof(*(Key())), "toString") ) || 271 __traits(hasMember, Key, "toString")) 272 { 273 m_hasher = (Key k) { 274 string s = k.toString(); 275 size_t hash = typeid(string).getHash(&s); 276 // logTrace("string ", s, " hash:" , hash); 277 return hash; 278 }; 279 } 280 281 else static if (__traits(compiles, (){ Key t; size_t hash = t.toHash(); }())) { 282 static if (isPointer!Key || is(Unqual!Key == class)) m_hasher = k => k ? k.toHash() : 0; 283 else m_hasher = k => k.toHash(); 284 } else static if (__traits(compiles, (){ Key t; size_t hash = t.toHashShared(); }())) { 285 static if (isPointer!Key || is(Unqual!Key == class)) m_hasher = k => k ? k.toHashShared() : 0; 286 else m_hasher = k => k.toHashShared(); 287 } 288 else static if (__traits(hasMember, Key, "isRefCounted")) { 289 m_hasher = (k) { return typeid(typeof(*(Key()))).getHash(&k); }; 290 } 291 else { 292 m_hasher = (k) { return typeid(Key).getHash(&k); }; 293 } 294 } 295 } 296 297 298 struct DefaultHashMapTraits(Key) { 299 enum clearValue = Key.init; 300 static bool equals(in Key a, in Key b) 301 { 302 static if (__traits(hasMember, Key, "isRefCounted") && 303 is (typeof(*(Key())) == class) && 304 __traits(compiles, "bool c = a.opEquals(*b);")) 305 { 306 if (!a && b) { 307 return b.opEquals(*a); 308 } 309 else if (a && !b) { 310 return a.opEquals(*b); 311 } 312 else if (a && b) 313 { 314 return a.opEquals(*b); 315 } 316 else { 317 return true; 318 } 319 } 320 else static if (__traits(hasMember, Key, "isRefCounted") && is (typeof(*(Key())) == class)) { 321 return *a is *b; 322 } 323 else static if (isPointer!Key) { 324 return a is b; 325 } 326 else { 327 return a == b; 328 } 329 } 330 }