Fri, 27 May 2022 12:59:41 +0200
remove unused header
1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 *
4 * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
29 #include <string.h>
30 #include "cx/hash_map.h"
31 #include "cx/utils.h"
33 /**
34 * Computes a murmur hash-2.
35 *
36 * @param data the data to hash
37 * @param len the length of the data
38 * @return the murmur hash-2 of the data
39 */
40 static unsigned cx_hash_map_murmur(
41 unsigned char const *data,
42 size_t len
43 ) {
44 unsigned m = 0x5bd1e995;
45 unsigned r = 24;
46 unsigned h = 25 ^ len;
47 unsigned i = 0;
48 while (len >= 4) {
49 unsigned k = data[i + 0] & 0xFF;
50 k |= (data[i + 1] & 0xFF) << 8;
51 k |= (data[i + 2] & 0xFF) << 16;
52 k |= (data[i + 3] & 0xFF) << 24;
54 k *= m;
55 k ^= k >> r;
56 k *= m;
58 h *= m;
59 h ^= k;
61 i += 4;
62 len -= 4;
63 }
65 switch (len) {
66 case 3:
67 h ^= (data[i + 2] & 0xFF) << 16;
68 __attribute__((__fallthrough__));
69 case 2:
70 h ^= (data[i + 1] & 0xFF) << 8;
71 __attribute__((__fallthrough__));
72 case 1:
73 h ^= (data[i + 0] & 0xFF);
74 h *= m;
75 __attribute__((__fallthrough__));
76 default:
77 /* do nothing */;
78 }
80 h ^= h >> 13;
81 h *= m;
82 h ^= h >> 15;
84 return h;
85 }
87 static void cx_hash_map_clear(struct cx_map_s *map) {
88 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
89 cx_for_n(i, hash_map->bucket_count) {
90 struct cx_hash_map_element_s *elem = hash_map->buckets[i];
91 if (elem != NULL) {
92 do {
93 struct cx_hash_map_element_s *next = elem->next;
94 // free the key data
95 cxFree(map->allocator, elem->key.data);
96 // free the node
97 cxFree(map->allocator, elem);
98 // proceed
99 elem = next;
100 } while (elem != NULL);
102 // do not leave a dangling pointer
103 hash_map->buckets[i] = NULL;
104 }
105 }
106 map->size = 0;
107 }
109 static void cx_hash_map_destructor(struct cx_map_s *map) {
110 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
112 // free the buckets
113 cx_hash_map_clear(map);
114 cxFree(map->allocator, hash_map->buckets);
116 // free the map structure
117 cxFree(map->allocator, map);
118 }
120 static int cx_hash_map_put(
121 CxMap *map,
122 CxDataPtr key,
123 void *value
124 ) {
125 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
126 CxAllocator *allocator = map->allocator;
128 unsigned hash = cx_hash_map_murmur(key.data, key.len);
130 size_t slot = hash % hash_map->bucket_count;
131 struct cx_hash_map_element_s *elm = hash_map->buckets[slot];
132 struct cx_hash_map_element_s *prev = NULL;
134 while (elm != NULL && elm->key.hash < hash) {
135 prev = elm;
136 elm = elm->next;
137 }
139 if (elm == NULL || elm->key.hash != hash) {
140 struct cx_hash_map_element_s *e = cxMalloc(allocator, sizeof(struct cx_hash_map_element_s));
141 if (e == NULL) {
142 return -1;
143 }
145 // write the value
146 // TODO: depending on future map features, we may want to copy here
147 e->data = value;
149 // copy the key
150 void *kd = cxMalloc(allocator, key.len);
151 if (kd == NULL) {
152 return -1;
153 }
154 memcpy(kd, key.data, key.len);
155 e->key.data = kd;
156 e->key.len = key.len;
157 e->key.hash = hash;
159 // insert the element into the linked list
160 if (prev == NULL) {
161 hash_map->buckets[slot] = e;
162 } else {
163 prev->next = e;
164 }
165 e->next = elm;
167 // increase the size
168 map->size++;
169 } else {
170 // (elem != NULL && elem->key.hash == hash) - overwrite value of existing element
171 elm->data = value;
172 }
174 return 0;
175 }
177 static void cx_hash_map_unlink(
178 struct cx_hash_map_s *hash_map,
179 size_t slot,
180 struct cx_hash_map_element_s *prev,
181 struct cx_hash_map_element_s *elm
182 ) {
183 // unlink
184 if (prev == NULL) {
185 hash_map->buckets[slot] = elm->next;
186 } else {
187 prev->next = elm->next;
188 }
189 // free element
190 cxFree(hash_map->base.allocator, elm->key.data);
191 cxFree(hash_map->base.allocator, elm);
192 // decrease size
193 hash_map->base.size--;
194 }
196 /**
197 * Helper function to avoid code duplication.
198 *
199 * @param map the map
200 * @param key the key to look up
201 * @param remove flag indicating whether the looked up entry shall be removed
202 * @return the value corresponding to the key or \c NULL
203 */
204 static void *cx_hash_map_get_remove(
205 CxMap *map,
206 CxDataPtr key,
207 bool remove
208 ) {
209 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
211 unsigned hash = cx_hash_map_murmur(key.data, key.len);
213 size_t slot = hash % hash_map->bucket_count;
214 struct cx_hash_map_element_s *elm = hash_map->buckets[slot];
215 struct cx_hash_map_element_s *prev = NULL;
216 while (elm && elm->key.hash <= hash) {
217 if (elm->key.hash == hash && elm->key.len == key.len) {
218 if (memcmp(elm->key.data, key.data, key.len) == 0) {
219 void *data = elm->data;
220 if (remove) {
221 cx_hash_map_unlink(hash_map, slot, prev, elm);
222 }
223 return data;
224 }
225 }
226 prev = elm;
227 elm = prev->next;
228 }
230 return NULL;
231 }
233 static void *cx_hash_map_get(
234 CxMap const *map,
235 CxDataPtr key
236 ) {
237 // we can safely cast, because we know when remove=false, the map stays untouched
238 return cx_hash_map_get_remove((CxMap *) map, key, false);
239 }
241 static void *cx_hash_map_remove(
242 CxMap *map,
243 CxDataPtr key
244 ) {
245 return cx_hash_map_get_remove(map, key, true);
246 }
248 static void *cx_hash_map_iter_current_entry(CxIterator const *iter) {
249 // struct has to have a compatible signature
250 struct cx_map_entry_s *entry = (struct cx_map_entry_s *) &(iter->kv_data);
251 return entry;
252 }
254 static void *cx_hash_map_iter_current_key(CxIterator const *iter) {
255 struct cx_hash_map_element_s *elm = iter->elem_handle;
256 return &elm->key;
257 }
259 static void *cx_hash_map_iter_current_value(CxIterator const *iter) {
260 struct cx_hash_map_element_s *elm = iter->elem_handle;
261 // TODO: return a pointer to data if this map is storing copies
262 return elm->data;
263 }
265 static bool cx_hash_map_iter_valid(CxIterator const *iter) {
266 return iter->elem_handle != NULL;
267 }
269 static void cx_hash_map_iter_next(CxIterator *iter) {
270 struct cx_hash_map_s *map = iter->src_handle;
271 struct cx_hash_map_element_s *elm = iter->elem_handle;
273 // remove current element, if asked
274 if (iter->remove) {
275 // clear the flag
276 iter->remove = false;
278 // determine the next element
279 struct cx_hash_map_element_s *next = elm->next;
281 // search the previous element
282 struct cx_hash_map_element_s *prev = NULL;
283 if (map->buckets[iter->slot] != elm) {
284 prev = map->buckets[iter->slot];
285 while (prev->next != elm) {
286 prev = prev->next;
287 }
288 }
290 // unlink
291 cx_hash_map_unlink(map, iter->slot, prev, elm);
293 // advance
294 elm = next;
295 } else {
296 // just advance
297 elm = elm->next;
298 }
300 // do we leave the bucket?
301 if (elm == NULL) {
302 // search the next bucket
303 for (; elm == NULL && iter->slot < map->bucket_count; iter->slot++) {
304 elm = map->buckets[iter->slot];
305 }
306 }
308 // advance the index in any case
309 iter->index++;
311 // fill the struct with the current element
312 iter->elem_handle = elm;
313 if (elm == NULL) {
314 iter->kv_data.key = NULL;
315 iter->kv_data.value = NULL;
316 } else {
317 iter->kv_data.key = &elm->key;
318 // TODO: pointer to data if this map is storing copies
319 iter->kv_data.value = elm->data;
320 }
321 }
323 static CxIterator cx_hash_map_iterator(CxMap *map) {
324 CxIterator iter;
326 iter.src_handle = map;
327 iter.valid = cx_hash_map_iter_valid;
328 iter.next = cx_hash_map_iter_next;
329 iter.current = cx_hash_map_iter_current_entry;
331 iter.slot = 0;
332 iter.index = 0;
333 iter.remove = false;
335 if (map->size > 0) {
336 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
337 struct cx_hash_map_element_s *elm = NULL;
338 for (; elm == NULL; iter.slot++) {
339 elm = hash_map->buckets[iter.slot];
340 }
341 iter.elem_handle = elm;
342 iter.kv_data.key = &elm->key;
343 // TODO: pointer to data if this map is storing copies
344 iter.kv_data.value = elm->data;
345 } else {
346 iter.elem_handle = NULL;
347 iter.kv_data.key = NULL;
348 iter.kv_data.value = NULL;
349 }
351 return iter;
352 }
354 static CxIterator cx_hash_map_iterator_keys(CxMap *map) {
355 CxIterator iter = cx_hash_map_iterator(map);
356 iter.current = cx_hash_map_iter_current_key;
357 return iter;
358 }
360 static CxIterator cx_hash_map_iterator_values(CxMap *map) {
361 CxIterator iter = cx_hash_map_iterator(map);
362 iter.current = cx_hash_map_iter_current_value;
363 return iter;
364 }
366 static cx_map_class cx_hash_map_class = {
367 cx_hash_map_destructor,
368 cx_hash_map_clear,
369 cx_hash_map_put,
370 cx_hash_map_get,
371 cx_hash_map_remove,
372 cx_hash_map_iterator,
373 cx_hash_map_iterator_keys,
374 cx_hash_map_iterator_values,
375 };
377 CxMap *cxHashMapCreate(
378 CxAllocator *allocator,
379 size_t buckets
380 ) {
381 if (buckets == 0) {
382 // implementation defined default
383 buckets = 16;
384 }
386 struct cx_hash_map_s *map = cxMalloc(allocator, sizeof(struct cx_hash_map_s));
387 if (map == NULL) return NULL;
389 // initialize hash map members
390 map->bucket_count = buckets;
391 map->buckets = cxCalloc(allocator, buckets, sizeof(struct cx_hash_map_element_s *));
392 if (map->buckets == NULL) {
393 cxFree(allocator, map);
394 return NULL;
395 }
397 // initialize base members
398 map->base.cl = &cx_hash_map_class;
399 map->base.allocator = allocator;
400 map->base.size = 0;
402 return (CxMap *) map;
403 }