1 module zua.vm.hashmap;
2 import zua.vm.engine;
3 import std.typecons;
4
5 private const double LOAD_FACTOR = 0.75;
6
7 private struct Bucket {
8 size_t hash;
9 Value key;
10 Value value;
11 }
12
13 pragma(inline) size_t getHash(T)(T obj) {
14 size_t res = hashOf(obj);
15 if (res == 0) return 1; // shim to allow us to use a hash of 0 to store an empty bucket
16 return res;
17 }
18
19 /** HashTable iterator */
20 struct HashTableIterator {
21
22 private HashTable table;
23 package size_t index;
24
25 private void skipNulls() {
26 Bucket* bucket = &table.buckets[index];
27 while (bucket.hash == 0 || bucket.value.isNil) {
28 index++;
29 if (index >= table.buckets.length) return;
30 bucket = &table.buckets[index];
31 }
32 }
33
34 /** Check if range is empty */
35 bool empty() {
36 return index >= table.buckets.length;
37 }
38
39 /** Get the front element of this range */
40 Tuple!(Value, Value) front() {
41 Bucket* bucket = &table.buckets[index];
42 return tuple(bucket.key, bucket.value);
43 }
44
45 /** Pop the front element of this range */
46 void popFront() {
47 index++;
48 if (index >= table.buckets.length) return;
49 skipNulls();
50 }
51
52 }
53
54 // package struct HashTable {
55
56 // Value[Value] table;
57
58 // void initObj() {
59
60 // }
61
62 // size_t length() {
63 // return table.length;
64 // }
65
66 // /** Insert a value at a given key */
67 // void insert(Value key, Value value) {
68 // table[key] = value;
69 // }
70
71 // /** Lookup a value from a key */
72 // Value* lookup(Value key) {
73 // return key in table;
74 // }
75
76 // }
77
78 /** HashMap implementation for Lua tables */
79 package class HashTable {
80
81 /** Get the number of key-value pairs in this map */
82 size_t length;
83
84 private Bucket[] buckets;
85
86 private size_t capacityMask;
87
88 /** Create a new hashmap */
89 this() {
90 buckets = newBuckets(16);
91 capacityMask = buckets.length - 1;
92 }
93
94 private pragma(inline) Bucket[] newBuckets(size_t numOfBuckets) {
95 return new Bucket[numOfBuckets];
96 }
97
98 private void resize() {
99 Bucket[] prevBuckets = buckets;
100 const numBuckets = buckets.length * 2;
101 capacityMask = numBuckets - 1;
102 buckets = newBuckets(numBuckets);
103
104 length = 0;
105
106 size_t newLength;
107 foreach (i; 0 .. numBuckets / 2) {
108 Bucket* bucket = &prevBuckets[i];
109 if (bucket.hash != 0 && !bucket.value.isNil) {
110 newLength++;
111 insert(bucket.key, bucket.value);
112 }
113 }
114
115 length = newLength;
116 }
117
118 private size_t probe(Value key, size_t hash = 0) {
119 if (hash == 0) hash = getHash(key);
120 size_t index = hash & capacityMask;
121 Nullable!size_t tombstone;
122 while (true) {
123 Bucket* bucket = &buckets[index];
124
125 if (bucket.hash == hash && bucket.key == key) return index;
126
127 if (bucket.hash == 0) {
128 if (!tombstone.isNull) return tombstone.get;
129 return index;
130 }
131
132 if (bucket.value.isNil) tombstone = index.nullable;
133
134 index = (index + 1) & capacityMask;
135 }
136 }
137
138 /** Insert a value at a given key */
139 void insert(Value key, Value value) {
140 if (length + 1 > LOAD_FACTOR * buckets.length) resize();
141
142 const size_t hash = getHash(key);
143 const size_t index = probe(key, hash);
144
145 Bucket newBucket;
146 newBucket.hash = hash;
147 newBucket.key = key;
148 newBucket.value = value;
149
150 if (buckets[index].hash == 0) {
151 length++;
152 }
153
154 buckets[index] = newBucket;
155 }
156
157 /** Lookup a value from a key */
158 Value* lookup(Value key) {
159 if (length == 0) return null;
160
161 const size_t index = probe(key);
162
163 if (buckets[index].hash == 0 || buckets[index].value.isNil) {
164 return null;
165 }
166 else {
167 return &buckets[index].value;
168 }
169 }
170
171 /** Return an iterator for this table */
172 HashTableIterator iterator() {
173 HashTableIterator res;
174 res.index = 0;
175 res.table = this;
176 res.skipNulls();
177 return res;
178 }
179
180 /** Return an iterator starting at, and including, a given key */
181 HashTableIterator find(Value key) {
182 const size_t index = probe(key);
183
184 HashTableIterator res;
185 res.index = index;
186 res.table = this;
187 return res;
188 }
189
190 }
191
192 unittest {
193 HashTable table = new HashTable;
194
195 assert(table.length == 0);
196 table.insert(Value(2), Value("hi"));
197
198 auto hi = table.lookup(Value(2));
199 assert(hi);
200 assert(*hi == Value("hi"));
201
202 foreach (d; 0 .. 100) {
203 table.insert(Value(d), Value(d * 2 + 3));
204 }
205
206 foreach (d; 0 .. 100) {
207 auto v = table.lookup(Value(d));
208 assert(v);
209 assert(*v == Value(d * 2 + 3));
210 }
211
212 HashTable table2 = new HashTable;
213
214 foreach (d; 0 .. 10_000) {
215 table2.insert(Value(d + 1.25), Value(d * 2 + 3));
216 }
217
218 foreach (d; 0 .. 10_000) {
219 auto v = table2.lookup(Value(d + 1.25));
220 assert(v);
221 assert(*v == Value(d * 2 + 3));
222 }
223
224 }