Thu, 19 May 2022 14:30:20 +0200
#189 basic map implementation
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 <errno.h>
30 #include <string.h>
31 #include "cx/hash_map.h"
32 #include "cx/utils.h"
34 /**
35 * Computes a murmur hash-2.
36 *
37 * @param data the data to hash
38 * @param len the length of the data
39 * @return the murmur hash-2 of the data
40 */
41 static unsigned cx_hash_map_murmur(
42 unsigned char const *data,
43 size_t len
44 ) {
45 unsigned m = 0x5bd1e995;
46 unsigned r = 24;
47 unsigned h = 25 ^ len;
48 unsigned i = 0;
49 while (len >= 4) {
50 unsigned k = data[i + 0] & 0xFF;
51 k |= (data[i + 1] & 0xFF) << 8;
52 k |= (data[i + 2] & 0xFF) << 16;
53 k |= (data[i + 3] & 0xFF) << 24;
55 k *= m;
56 k ^= k >> r;
57 k *= m;
59 h *= m;
60 h ^= k;
62 i += 4;
63 len -= 4;
64 }
66 switch (len) {
67 case 3:
68 h ^= (data[i + 2] & 0xFF) << 16;
69 __attribute__((__fallthrough__));
70 case 2:
71 h ^= (data[i + 1] & 0xFF) << 8;
72 __attribute__((__fallthrough__));
73 case 1:
74 h ^= (data[i + 0] & 0xFF);
75 h *= m;
76 __attribute__((__fallthrough__));
77 default:
78 /* do nothing */;
79 }
81 h ^= h >> 13;
82 h *= m;
83 h ^= h >> 15;
85 return h;
86 }
88 static void cx_hash_map_clear(struct cx_map_s *map) {
89 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
90 cx_for_n(i, hash_map->bucket_count) {
91 struct cx_hash_map_element_s *elem = hash_map->buckets[i];
92 if (elem != NULL) {
93 do {
94 struct cx_hash_map_element_s *next = elem->next;
95 // free the key data
96 cxFree(map->allocator, elem->key.data);
97 // free the node
98 cxFree(map->allocator, elem);
99 // proceed
100 elem = next;
101 } while (elem != NULL);
103 // do not leave a dangling pointer
104 hash_map->buckets[i] = NULL;
105 }
106 }
107 map->size = 0;
108 }
110 static void cx_hash_map_destructor(struct cx_map_s *map) {
111 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
113 // free the buckets
114 cx_hash_map_clear(map);
115 cxFree(map->allocator, hash_map->buckets);
117 // free the map structure
118 cxFree(map->allocator, map);
119 }
121 static int cx_hash_map_put(
122 CxMap *map,
123 CxDataPtr key,
124 void *value
125 ) {
126 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
127 CxAllocator *allocator = map->allocator;
129 unsigned hash = cx_hash_map_murmur(key.data, key.len);
131 size_t slot = hash % hash_map->bucket_count;
132 struct cx_hash_map_element_s *elm = hash_map->buckets[slot];
133 struct cx_hash_map_element_s *prev = NULL;
135 while (elm != NULL && elm->key.hash < hash) {
136 prev = elm;
137 elm = elm->next;
138 }
140 if (elm == NULL || elm->key.hash != hash) {
141 struct cx_hash_map_element_s *e = cxMalloc(allocator, sizeof(struct cx_hash_map_element_s));
142 if (e == NULL) {
143 return -1;
144 }
146 // write the value
147 // TODO: depending on future map features, we may want to copy here
148 e->data = value;
150 // copy the key
151 void *kd = cxMalloc(allocator, key.len);
152 if (kd == NULL) {
153 return -1;
154 }
155 memcpy(kd, key.data, key.len);
156 e->key.data = kd;
157 e->key.len = key.len;
158 e->key.hash = hash;
160 // insert the element into the linked list
161 if (prev == NULL) {
162 hash_map->buckets[slot] = e;
163 } else {
164 prev->next = e;
165 }
166 e->next = elm;
168 // increase the size
169 map->size++;
170 } else {
171 // (elem != NULL && elem->key.hash == hash) - overwrite value of existing element
172 elm->data = value;
173 }
175 return 0;
176 }
178 /**
179 * Helper function to avoid code duplication.
180 *
181 * @param map the map
182 * @param key the key to look up
183 * @param remove flag indicating whether the looked up entry shall be removed
184 * @return the value corresponding to the key or \c NULL
185 */
186 static void *cx_hash_map_get_remove(
187 CxMap *map,
188 CxDataPtr key,
189 bool remove
190 ) {
191 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
193 unsigned hash = cx_hash_map_murmur(key.data, key.len);
195 size_t slot = hash % hash_map->bucket_count;
196 struct cx_hash_map_element_s *elm = hash_map->buckets[slot];
197 struct cx_hash_map_element_s *prev = NULL;
198 while (elm && elm->key.hash <= hash) {
199 if (elm->key.hash == hash && elm->key.len == key.len) {
200 if (memcmp(elm->key.data, key.data, key.len) == 0) {
201 void *data = elm->data;
202 if (remove) {
203 // unlink
204 if (prev) {
205 prev->next = elm->next;
206 } else {
207 hash_map->buckets[slot] = elm->next;
208 }
209 // free element
210 cxFree(map->allocator, elm->key.data);
211 cxFree(map->allocator, elm);
212 // decrease size
213 map->size--;
214 }
215 return data;
216 }
217 }
218 prev = elm;
219 elm = prev->next;
220 }
222 return NULL;
223 }
225 static void *cx_hash_map_get(
226 CxMap const *map,
227 CxDataPtr key
228 ) {
229 // we can safely cast, because we know when remove=false, the map stays untouched
230 return cx_hash_map_get_remove((CxMap *) map, key, false);
231 }
233 static void *cx_hash_map_remove(
234 CxMap *map,
235 CxDataPtr key
236 ) {
237 return cx_hash_map_get_remove(map, key, true);
238 }
240 static CxIterator cx_hash_map_iterator(CxMap const *map) {
241 CxIterator iter;
242 // TODO: initialize iter
243 return iter;
244 }
246 static CxIterator cx_hash_map_iterator_keys(CxMap const *map) {
247 CxIterator iter;
248 // TODO: initialize iter
249 return iter;
250 }
252 static CxIterator cx_hash_map_iterator_values(CxMap const *map) {
253 CxIterator iter;
254 // TODO: initialize iter
255 return iter;
256 }
258 static cx_map_class cx_hash_map_class = {
259 cx_hash_map_destructor,
260 cx_hash_map_clear,
261 cx_hash_map_put,
262 cx_hash_map_get,
263 cx_hash_map_remove,
264 cx_hash_map_iterator,
265 cx_hash_map_iterator_keys,
266 cx_hash_map_iterator_values,
267 };
269 CxMap *cxHashMapCreate(
270 CxAllocator *allocator,
271 size_t buckets
272 ) {
273 if (buckets == 0) {
274 // implementation defined default
275 buckets = 16;
276 }
278 struct cx_hash_map_s *map = cxMalloc(allocator, sizeof(struct cx_hash_map_s));
279 if (map == NULL) return NULL;
281 // initialize hash map members
282 map->bucket_count = buckets;
283 map->buckets = cxCalloc(allocator, buckets, sizeof(struct cx_hash_map_element_s *));
284 if (map->buckets == NULL) {
285 cxFree(allocator, map);
286 return NULL;
287 }
289 // initialize base members
290 map->base.cl = &cx_hash_map_class;
291 map->base.allocator = allocator;
292 map->base.size = 0;
294 return (CxMap *) map;
295 }