1 /**
2  * ae.utils.container.hashtable
3  *
4  * License:
5  *   This Source Code Form is subject to the terms of
6  *   the Mozilla Public License, v. 2.0. If a copy of
7  *   the MPL was not distributed with this file, You
8  *   can obtain one at http://mozilla.org/MPL/2.0/.
9  *
10  * Authors:
11  *   Vladimir Panteleev <vladimir@thecybershadow.net>
12  */
13 
14 module ae.utils.container.hashtable;
15 
16 struct HashTableItem(K, V)
17 {
18 	K k;
19 	HashTableItem* next;
20 	V v;
21 }
22 
23 /// A hash table with a static size.
24 struct HashTable(K, V, uint SIZE, alias ALLOCATOR, alias HASHFUNC="k")
25 {
26 	alias K KEY;
27 	alias V VALUE;
28 
29 	import std.functional;
30 	import std.exception;
31 
32 	alias unaryFun!(HASHFUNC, "k") hashFunc;
33 
34 	// hashFunc returns a hash, get its type
35 	alias typeof(hashFunc(K.init)) H;
36 	static assert(is(H : ulong), "Numeric hash type expected");
37 
38 	alias HashTableItem!(K, V) Item;
39 
40 	struct Data
41 	{
42 		Item*[SIZE] items;
43 	}
44 
45 	static template Impl(alias data)
46 	{
47 		V* get(in K k)
48 		{
49 			auto h = hashFunc(k) % SIZE;
50 			auto item = data.items[h];
51 			while (item)
52 			{
53 				if (item.k == k)
54 					return &item.v;
55 				item = item.next;
56 			}
57 			return null;
58 		}
59 
60 		V* opBinaryRight(string op)(in K k)
61 		if (op == "in")
62 		{
63 			return get(k); // Issue 11842
64 		}
65 
66 		V get(in K k, V def)
67 		{
68 			auto pv = get(k);
69 			return pv ? *pv : def;
70 		}
71 
72 		/// Returns a pointer to the value storage space for a new value.
73 		/// Assumes the key does not yet exist in the table.
74 		V* add(in K k)
75 		{
76 			auto h = hashFunc(k) % SIZE;
77 			auto newItem = ALLOCATOR.allocate!Item();
78 			newItem.k = k;
79 			newItem.next = data.items[h];
80 			data.items[h] = newItem;
81 			return &newItem.v;
82 		}
83 
84 		/// Returns a pointer to the value storage space for a new
85 		/// or existing value.
86 		V* getOrAdd(in K k)
87 		{
88 			auto h = hashFunc(k) % SIZE;
89 			auto item = data.items[h];
90 			while (item)
91 			{
92 				if (item.k == k)
93 					return &item.v;
94 				item = item.next;
95 			}
96 
97 			auto newItem = ALLOCATOR.allocate!Item();
98 			newItem.k = k;
99 			newItem.next = data.items[h];
100 			data.items[h] = newItem;
101 			return &newItem.v;
102 		}
103 
104 		void set(in K k, ref V v) { *getOrAdd(k) = v; }
105 
106 		int opApply(int delegate(ref K, ref V) dg)
107 		{
108 			int result = 0;
109 
110 			outerLoop:
111 			for (uint h=0; h<SIZE; h++)
112 			{
113 				auto item = data.items[h];
114 				while (item)
115 				{
116 					result = dg(item.k, item.v);
117 					if (result)
118 						break outerLoop;
119 					item = item.next;
120 				}
121 			}
122 			return result;
123 		}
124 
125 		ref V opIndex(in K k)
126 		{
127 			auto pv = get(k);
128 			enforce(pv, "Key not in HashTable");
129 			return *pv;
130 		}
131 
132 		void opIndexAssign(ref V v, in K k) { set(k, v); }
133 
134 		size_t getLength()
135 		{
136 			size_t count = 0;
137 			for (uint h=0; h<SIZE; h++)
138 			{
139 				auto item = data.items[h];
140 				while (item)
141 				{
142 					count++;
143 					item = item.next;
144 				}
145 			}
146 			return count;
147 		}
148 
149 		void clear()
150 		{
151 			data.items[] = null;
152 		}
153 
154 		void freeAll()
155 		{
156 			static if (is(typeof(ALLOCATOR.freeAll())))
157 				ALLOCATOR.freeAll();
158 		}
159 	}
160 }
161 
162 unittest
163 {
164 	import ae.utils.alloc;
165 
166 	static struct Test
167 	{
168 		WrapParts!(RegionAllocator!()) allocator;
169 		alias HashTable!(int, string, 16, allocator) HT;
170 		HT.Data htData;
171 		alias ht = HT.Impl!htData;
172 
173 		mixin(mixAliasForward!(ht, q{ht}));
174 	}
175 	Test ht;
176 
177 	assert(5 !in ht);
178 	auto s = "five";
179 	ht[5] = s;
180 	assert(5 in ht);
181 	assert(ht[5] == "five");
182 }