Mercurial > hg > webserver / file comparison

comparison: src/ucx/hash_map.c

src/ucx/hash_map.c

changeset 490
d218607f5a7e
parent 484
c036a8b242a8
child 504
c094afcdfb27
equal deleted inserted replaced
489:921f83a8943f 490:d218607f5a7e
28 28
29 #include <string.h> 29 #include <string.h>
30 #include "cx/hash_map.h" 30 #include "cx/hash_map.h"
31 #include "cx/utils.h" 31 #include "cx/utils.h"
32 32
33 struct cx_hash_map_element_s {
34 /** A pointer to the next element in the current bucket. */
35 struct cx_hash_map_element_s *next;
36
37 /** The corresponding key. */
38 CxHashKey key;
39
40 /** The value data. */
41 char data[];
42 };
43
33 static void cx_hash_map_clear(struct cx_map_s *map) { 44 static void cx_hash_map_clear(struct cx_map_s *map) {
34 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; 45 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
35 cx_for_n(i, hash_map->bucket_count) { 46 cx_for_n(i, hash_map->bucket_count) {
36 struct cx_hash_map_element_s *elem = hash_map->buckets[i]; 47 struct cx_hash_map_element_s *elem = hash_map->buckets[i];
37 if (elem != NULL) { 48 if (elem != NULL) {
38 do { 49 do {
39 struct cx_hash_map_element_s *next = elem->next; 50 struct cx_hash_map_element_s *next = elem->next;
51 // invoke the destructor
52 cx_invoke_destructor(map, elem->data);
40 // free the key data 53 // free the key data
41 cxFree(map->allocator, elem->key.data.obj); 54 cxFree(map->allocator, (void *) elem->key.data);
42 // free the node 55 // free the node
43 cxFree(map->allocator, elem); 56 cxFree(map->allocator, elem);
44 // proceed 57 // proceed
45 elem = next; 58 elem = next;
46 } while (elem != NULL); 59 } while (elem != NULL);
67 CxMap *map, 80 CxMap *map,
68 CxHashKey key, 81 CxHashKey key,
69 void *value 82 void *value
70 ) { 83 ) {
71 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; 84 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
72 CxAllocator *allocator = map->allocator; 85 CxAllocator const *allocator = map->allocator;
73 86
74 unsigned hash = key.hash; 87 unsigned hash = key.hash;
75 if (hash == 0) { 88 if (hash == 0) {
76 cx_hash_murmur(&key); 89 cx_hash_murmur(&key);
77 hash = key.hash; 90 hash = key.hash;
85 prev = elm; 98 prev = elm;
86 elm = elm->next; 99 elm = elm->next;
87 } 100 }
88 101
89 if (elm != NULL && elm->key.hash == hash && elm->key.len == key.len && 102 if (elm != NULL && elm->key.hash == hash && elm->key.len == key.len &&
90 memcmp(elm->key.data.obj, key.data.obj, key.len) == 0) { 103 memcmp(elm->key.data, key.data, key.len) == 0) {
91 // overwrite existing element 104 // overwrite existing element
92 elm->data = value; 105 if (map->store_pointer) {
106 memcpy(elm->data, &value, sizeof(void *));
107 } else {
108 memcpy(elm->data, value, map->item_size);
109 }
93 } else { 110 } else {
94 // allocate new element 111 // allocate new element
95 struct cx_hash_map_element_s *e = cxMalloc(allocator, sizeof(struct cx_hash_map_element_s)); 112 struct cx_hash_map_element_s *e = cxMalloc(
113 allocator,
114 sizeof(struct cx_hash_map_element_s) + map->item_size
115 );
96 if (e == NULL) { 116 if (e == NULL) {
97 return -1; 117 return -1;
98 } 118 }
99 119
100 // write the value 120 // write the value
101 // TODO: depending on future map features, we may want to copy here 121 if (map->store_pointer) {
102 e->data = value; 122 memcpy(e->data, &value, sizeof(void *));
123 } else {
124 memcpy(e->data, value, map->item_size);
125 }
103 126
104 // copy the key 127 // copy the key
105 void *kd = cxMalloc(allocator, key.len); 128 void *kd = cxMalloc(allocator, key.len);
106 if (kd == NULL) { 129 if (kd == NULL) {
107 return -1; 130 return -1;
108 } 131 }
109 memcpy(kd, key.data.obj, key.len); 132 memcpy(kd, key.data, key.len);
110 e->key.data.obj = kd; 133 e->key.data = kd;
111 e->key.len = key.len; 134 e->key.len = key.len;
112 e->key.hash = hash; 135 e->key.hash = hash;
113 136
114 // insert the element into the linked list 137 // insert the element into the linked list
115 if (prev == NULL) { 138 if (prev == NULL) {
137 hash_map->buckets[slot] = elm->next; 160 hash_map->buckets[slot] = elm->next;
138 } else { 161 } else {
139 prev->next = elm->next; 162 prev->next = elm->next;
140 } 163 }
141 // free element 164 // free element
142 cxFree(hash_map->base.allocator, elm->key.data.obj); 165 cxFree(hash_map->base.allocator, (void *) elm->key.data);
143 cxFree(hash_map->base.allocator, elm); 166 cxFree(hash_map->base.allocator, elm);
144 // decrease size 167 // decrease size
145 hash_map->base.size--; 168 hash_map->base.size--;
146 } 169 }
147 170
149 * Helper function to avoid code duplication. 172 * Helper function to avoid code duplication.
150 * 173 *
151 * @param map the map 174 * @param map the map
152 * @param key the key to look up 175 * @param key the key to look up
153 * @param remove flag indicating whether the looked up entry shall be removed 176 * @param remove flag indicating whether the looked up entry shall be removed
154 * @return the value corresponding to the key or \c NULL 177 * @param destroy flag indicating whether the destructor shall be invoked
178 * @return a pointer to the value corresponding to the key or \c NULL
155 */ 179 */
156 static void *cx_hash_map_get_remove( 180 static void *cx_hash_map_get_remove(
157 CxMap *map, 181 CxMap *map,
158 CxHashKey key, 182 CxHashKey key,
159 bool remove 183 bool remove,
184 bool destroy
160 ) { 185 ) {
161 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; 186 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
162 187
163 unsigned hash = key.hash; 188 unsigned hash = key.hash;
164 if (hash == 0) { 189 if (hash == 0) {
169 size_t slot = hash % hash_map->bucket_count; 194 size_t slot = hash % hash_map->bucket_count;
170 struct cx_hash_map_element_s *elm = hash_map->buckets[slot]; 195 struct cx_hash_map_element_s *elm = hash_map->buckets[slot];
171 struct cx_hash_map_element_s *prev = NULL; 196 struct cx_hash_map_element_s *prev = NULL;
172 while (elm && elm->key.hash <= hash) { 197 while (elm && elm->key.hash <= hash) {
173 if (elm->key.hash == hash && elm->key.len == key.len) { 198 if (elm->key.hash == hash && elm->key.len == key.len) {
174 if (memcmp(elm->key.data.obj, key.data.obj, key.len) == 0) { 199 if (memcmp(elm->key.data, key.data, key.len) == 0) {
175 void *data = elm->data; 200 void *data = NULL;
201 if (destroy) {
202 cx_invoke_destructor(map, elm->data);
203 } else {
204 if (map->store_pointer) {
205 data = *(void **) elm->data;
206 } else {
207 data = elm->data;
208 }
209 }
176 if (remove) { 210 if (remove) {
177 cx_hash_map_unlink(hash_map, slot, prev, elm); 211 cx_hash_map_unlink(hash_map, slot, prev, elm);
178 } 212 }
179 return data; 213 return data;
180 } 214 }
188 222
189 static void *cx_hash_map_get( 223 static void *cx_hash_map_get(
190 CxMap const *map, 224 CxMap const *map,
191 CxHashKey key 225 CxHashKey key
192 ) { 226 ) {
193 // we can safely cast, because we know when remove=false, the map stays untouched 227 // we can safely cast, because we know the map stays untouched
194 return cx_hash_map_get_remove((CxMap *) map, key, false); 228 return cx_hash_map_get_remove((CxMap *) map, key, false, false);
195 } 229 }
196 230
197 static void *cx_hash_map_remove( 231 static void *cx_hash_map_remove(
198 CxMap *map, 232 CxMap *map,
199 CxHashKey key 233 CxHashKey key,
234 bool destroy
200 ) { 235 ) {
201 return cx_hash_map_get_remove(map, key, true); 236 return cx_hash_map_get_remove(map, key, true, destroy);
202 } 237 }
203 238
204 static void *cx_hash_map_iter_current_entry(void const *it) { 239 static void *cx_hash_map_iter_current_entry(void const *it) {
205 struct cx_iterator_s const *iter = it; 240 struct cx_iterator_s const *iter = it;
206 // struct has to have a compatible signature 241 // struct has to have a compatible signature
213 return &elm->key; 248 return &elm->key;
214 } 249 }
215 250
216 static void *cx_hash_map_iter_current_value(void const *it) { 251 static void *cx_hash_map_iter_current_value(void const *it) {
217 struct cx_iterator_s const *iter = it; 252 struct cx_iterator_s const *iter = it;
253 struct cx_hash_map_s const *map = iter->src_handle;
218 struct cx_hash_map_element_s *elm = iter->elem_handle; 254 struct cx_hash_map_element_s *elm = iter->elem_handle;
219 // TODO: return a pointer to data if this map is storing copies 255 if (map->base.store_pointer) {
220 return elm->data; 256 return *(void **) elm->data;
257 } else {
258 return elm->data;
259 }
221 } 260 }
222 261
223 static bool cx_hash_map_iter_valid(void const *it) { 262 static bool cx_hash_map_iter_valid(void const *it) {
224 struct cx_iterator_s const *iter = it; 263 struct cx_iterator_s const *iter = it;
225 return iter->elem_handle != NULL; 264 return iter->elem_handle != NULL;
248 while (prev->next != elm) { 287 while (prev->next != elm) {
249 prev = prev->next; 288 prev = prev->next;
250 } 289 }
251 } 290 }
252 291
292 // destroy
293 cx_invoke_destructor((struct cx_map_s *) map, elm->data);
294
253 // unlink 295 // unlink
254 cx_hash_map_unlink(map, iter->slot, prev, elm); 296 cx_hash_map_unlink(map, iter->slot, prev, elm);
255 297
256 // advance 298 // advance
257 elm = next; 299 elm = next;
272 if (elm == NULL) { 314 if (elm == NULL) {
273 iter->kv_data.key = NULL; 315 iter->kv_data.key = NULL;
274 iter->kv_data.value = NULL; 316 iter->kv_data.value = NULL;
275 } else { 317 } else {
276 iter->kv_data.key = &elm->key; 318 iter->kv_data.key = &elm->key;
277 // TODO: pointer to data if this map is storing copies 319 if (map->base.store_pointer) {
278 iter->kv_data.value = elm->data; 320 iter->kv_data.value = *(void **) elm->data;
321 } else {
322 iter->kv_data.value = elm->data;
323 }
279 } 324 }
280 } 325 }
281 326
282 static bool cx_hash_map_iter_flag_rm(void *it) { 327 static bool cx_hash_map_iter_flag_rm(void *it) {
283 struct cx_iterator_base_s *iter = it; 328 struct cx_iterator_base_s *iter = it;
300 iter.base.remove = false; 345 iter.base.remove = false;
301 iter.base.mutating = false; 346 iter.base.mutating = false;
302 347
303 iter.slot = 0; 348 iter.slot = 0;
304 iter.index = 0; 349 iter.index = 0;
305 350
306 if (map->size > 0) { 351 if (map->size > 0) {
307 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; 352 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
308 struct cx_hash_map_element_s *elm = hash_map->buckets[0]; 353 struct cx_hash_map_element_s *elm = hash_map->buckets[0];
309 while (elm == NULL) { 354 while (elm == NULL) {
310 elm = hash_map->buckets[++iter.slot]; 355 elm = hash_map->buckets[++iter.slot];
311 } 356 }
312 iter.elem_handle = elm; 357 iter.elem_handle = elm;
313 iter.kv_data.key = &elm->key; 358 iter.kv_data.key = &elm->key;
314 // TODO: pointer to data if this map is storing copies 359 if (map->store_pointer) {
315 iter.kv_data.value = elm->data; 360 iter.kv_data.value = *(void **) elm->data;
361 } else {
362 iter.kv_data.value = elm->data;
363 }
316 } else { 364 } else {
317 iter.elem_handle = NULL; 365 iter.elem_handle = NULL;
318 iter.kv_data.key = NULL; 366 iter.kv_data.key = NULL;
319 iter.kv_data.value = NULL; 367 iter.kv_data.value = NULL;
320 } 368 }
369 cx_hash_map_mut_iterator_keys, 417 cx_hash_map_mut_iterator_keys,
370 cx_hash_map_mut_iterator_values, 418 cx_hash_map_mut_iterator_values,
371 }; 419 };
372 420
373 CxMap *cxHashMapCreate( 421 CxMap *cxHashMapCreate(
374 CxAllocator *allocator, 422 CxAllocator const *allocator,
423 size_t itemsize,
375 size_t buckets 424 size_t buckets
376 ) { 425 ) {
377 if (buckets == 0) { 426 if (buckets == 0) {
378 // implementation defined default 427 // implementation defined default
379 buckets = 16; 428 buckets = 16;
380 } 429 }
381 430
382 struct cx_hash_map_s *map = cxMalloc(allocator, sizeof(struct cx_hash_map_s)); 431 struct cx_hash_map_s *map = cxCalloc(allocator, 1,
432 sizeof(struct cx_hash_map_s));
383 if (map == NULL) return NULL; 433 if (map == NULL) return NULL;
384 434
385 // initialize hash map members 435 // initialize hash map members
386 map->bucket_count = buckets; 436 map->bucket_count = buckets;
387 map->buckets = cxCalloc(allocator, buckets, sizeof(struct cx_hash_map_element_s *)); 437 map->buckets = cxCalloc(allocator, buckets,
438 sizeof(struct cx_hash_map_element_s *));
388 if (map->buckets == NULL) { 439 if (map->buckets == NULL) {
389 cxFree(allocator, map); 440 cxFree(allocator, map);
390 return NULL; 441 return NULL;
391 } 442 }
392 443
393 // initialize base members 444 // initialize base members
394 map->base.cl = &cx_hash_map_class; 445 map->base.cl = &cx_hash_map_class;
395 map->base.allocator = allocator; 446 map->base.allocator = allocator;
396 map->base.size = 0; 447
448 if (itemsize > 0) {
449 map->base.store_pointer = false;
450 map->base.item_size = itemsize;
451 } else {
452 map->base.store_pointer = true;
453 map->base.item_size = sizeof(void *);
454 }
397 455
398 return (CxMap *) map; 456 return (CxMap *) map;
399 } 457 }
400 458
401 int cxMapRehash(CxMap *map) { 459 int cxMapRehash(CxMap *map) {
402 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; 460 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
403 if (map->size > ((hash_map->bucket_count * 3) >> 2)) { 461 if (map->size > ((hash_map->bucket_count * 3) >> 2)) {
404 462
405 size_t new_bucket_count = (map->size * 5) >> 1; 463 size_t new_bucket_count = (map->size * 5) >> 1;
406 struct cx_hash_map_element_s **new_buckets = cxCalloc(map->allocator, 464 struct cx_hash_map_element_s **new_buckets = cxCalloc(
407 new_bucket_count, sizeof(struct cx_hash_map_element_s *)); 465 map->allocator,
466 new_bucket_count, sizeof(struct cx_hash_map_element_s *)
467 );
408 468
409 if (new_buckets == NULL) { 469 if (new_buckets == NULL) {
410 return 1; 470 return 1;
411 } 471 }
412 472
418 size_t new_slot = elm->key.hash % new_bucket_count; 478 size_t new_slot = elm->key.hash % new_bucket_count;
419 479
420 // find position where to insert 480 // find position where to insert
421 struct cx_hash_map_element_s *bucket_next = new_buckets[new_slot]; 481 struct cx_hash_map_element_s *bucket_next = new_buckets[new_slot];
422 struct cx_hash_map_element_s *bucket_prev = NULL; 482 struct cx_hash_map_element_s *bucket_prev = NULL;
423 while (bucket_next != NULL && bucket_next->key.hash < elm->key.hash) { 483 while (bucket_next != NULL &&
484 bucket_next->key.hash < elm->key.hash) {
424 bucket_prev = bucket_next; 485 bucket_prev = bucket_next;
425 bucket_next = bucket_next->next; 486 bucket_next = bucket_next->next;
426 } 487 }
427 488
428 // insert 489 // insert

Mercurial Repository: webserver

mercurial