Mercurial > hg > idav / file comparison

comparison: ucx/kv_list.c

ucx/kv_list.c

changeset 112
c3f2f16fa4b8
child 113
dde28a806552
equal deleted inserted replaced
111:81c4f73236a4 112:c3f2f16fa4b8
1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 *
4 * Copyright 2025 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 */
28
29 #include "cx/kv_list.h"
30 #include "cx/hash_map.h"
31 #include "cx/linked_list.h"
32
33 #include <string.h>
34 #include <assert.h>
35
36 typedef struct cx_kv_list_s cx_kv_list;
37
38 struct cx_kv_list_map_s {
39 struct cx_hash_map_s map_base;
40 /** Back-reference to the list. */
41 cx_kv_list *list;
42 };
43
44 struct cx_kv_list_s {
45 struct cx_linked_list_s list;
46 /** The lookup map - stores pointers to the nodes. */
47 struct cx_kv_list_map_s *map;
48 const cx_list_class *list_methods;
49 const cx_map_class *map_methods;
50 cx_destructor_func list_destr;
51 cx_destructor_func2 list_destr2;
52 void *list_destr_data;
53 cx_destructor_func map_destr;
54 cx_destructor_func2 map_destr2;
55 void *map_destr_data;
56 };
57
58 static void cx_kv_list_destructor_wrapper(void *list_ptr, void *elem) {
59 const cx_kv_list *kv_list = list_ptr;
60 // list destructor is already called with proper deref of the elem
61 if (kv_list->list_destr) {
62 kv_list->list_destr(elem);
63 }
64 if (kv_list->list_destr2) {
65 kv_list->list_destr2(kv_list->list_destr_data, elem);
66 }
67 if (kv_list->map_destr) {
68 kv_list->map_destr(elem);
69 }
70 if (kv_list->map_destr2) {
71 kv_list->map_destr2(kv_list->map_destr_data, elem);
72 }
73 }
74
75 static void cx_kv_list_update_destructors(cx_kv_list *list) {
76 // we copy the destructors to our custom fields and register
77 // an own destructor function which invokes all these
78 if (list->list.base.collection.simple_destructor != NULL) {
79 list->list_destr = list->list.base.collection.simple_destructor;
80 list->list.base.collection.simple_destructor = NULL;
81 }
82 if (list->list.base.collection.advanced_destructor != cx_kv_list_destructor_wrapper) {
83 list->list_destr2 = list->list.base.collection.advanced_destructor;
84 list->list_destr_data = list->list.base.collection.destructor_data;
85 list->list.base.collection.advanced_destructor = cx_kv_list_destructor_wrapper;
86 list->list.base.collection.destructor_data = list;
87 }
88 if (list->map->map_base.base.collection.simple_destructor != NULL) {
89 list->map_destr = list->map->map_base.base.collection.simple_destructor;
90 list->map->map_base.base.collection.simple_destructor = NULL;
91 }
92 if (list->map->map_base.base.collection.advanced_destructor != NULL) {
93 list->map_destr2 = list->map->map_base.base.collection.advanced_destructor;
94 list->map_destr_data = list->map->map_base.base.collection.destructor_data;
95 list->map->map_base.base.collection.advanced_destructor = NULL;
96 list->map->map_base.base.collection.destructor_data = NULL;
97 }
98 }
99
100 static CxHashKey *cx_kv_list_loc_key(cx_kv_list *list, void *node_data) {
101 return (CxHashKey*)((char*)node_data + list->list.base.collection.elem_size);
102 }
103
104 static void cx_kvl_deallocate(struct cx_list_s *list) {
105 cx_kv_list *kv_list = (cx_kv_list*)list;
106 // patch the destructors
107 cx_kv_list_update_destructors(kv_list);
108 kv_list->map_methods->deallocate(&kv_list->map->map_base.base);
109 // then free the list, now the destructors may be called
110 kv_list->list_methods->deallocate(list);
111 }
112
113 static void *cx_kvl_insert_element(
114 struct cx_list_s *list,
115 size_t index,
116 const void *data
117 ) {
118 cx_kv_list *kv_list = (cx_kv_list*)list;
119 return kv_list->list_methods->insert_element(list, index, data);
120 }
121
122 static size_t cx_kvl_insert_array(
123 struct cx_list_s *list,
124 size_t index,
125 const void *data,
126 size_t n
127 ) {
128 cx_kv_list *kv_list = (cx_kv_list*)list;
129 return kv_list->list_methods->insert_array(list, index, data, n);
130 }
131
132 static size_t cx_kvl_insert_sorted(
133 struct cx_list_s *list,
134 const void *sorted_data,
135 size_t n
136 ) {
137 cx_kv_list *kv_list = (cx_kv_list*)list;
138 return kv_list->list_methods->insert_sorted(list, sorted_data, n);
139 }
140
141 static size_t cx_kvl_insert_unique(
142 struct cx_list_s *list,
143 const void *sorted_data,
144 size_t n
145 ) {
146 cx_kv_list *kv_list = (cx_kv_list*)list;
147 return kv_list->list_methods->insert_unique(list, sorted_data, n);
148 }
149
150 static int cx_kvl_insert_iter(
151 struct cx_iterator_s *iter,
152 const void *elem,
153 int prepend
154 ) {
155 cx_kv_list *kv_list = iter->src_handle.m;
156 return kv_list->list_methods->insert_iter(iter, elem, prepend);
157 }
158
159 static size_t cx_kvl_remove(
160 struct cx_list_s *list,
161 size_t index,
162 size_t num,
163 void *targetbuf
164 ) {
165 cx_kv_list *kv_list = (cx_kv_list*)list;
166 // patch the destructors
167 // we also have to do that when targetbuf is NULL,
168 // because we do not want wrong destructors to be called when we remove keys from the map
169 cx_kv_list_update_destructors(kv_list);
170 // iterate through the elements first and remove their keys from the map
171 CxIterator iter = kv_list->list_methods->iterator(list, index, false);
172 for (size_t i = 0; i < num && cxIteratorValid(iter); i++) {
173 void *node_data = cxIteratorCurrent(iter);
174 CxHashKey *key = cx_kv_list_loc_key(kv_list, node_data);
175 // when the hash is zero, there is no key assigned to that element
176 if (key->hash != 0) {
177 kv_list->map_methods->remove(&kv_list->map->map_base.base, *key, NULL);
178 }
179 cxIteratorNext(iter);
180 }
181 return kv_list->list_methods->remove(list, index, num, targetbuf);
182 }
183
184 static void cx_kvl_clear(struct cx_list_s *list) {
185 cx_kv_list *kv_list = (cx_kv_list*)list;
186 // patch the destructors
187 cx_kv_list_update_destructors(kv_list);
188 // clear the list
189 kv_list->list_methods->clear(list);
190 // then clear the map
191 kv_list->map_methods->clear(&kv_list->map->map_base.base);
192 }
193
194 static int cx_kvl_swap(
195 struct cx_list_s *list,
196 size_t i,
197 size_t j
198 ) {
199 cx_kv_list *kv_list = (cx_kv_list*)list;
200 return kv_list->list_methods->swap(list, i, j);
201 }
202
203 static void *cx_kvl_at(
204 const struct cx_list_s *list,
205 size_t index
206 ) {
207 const cx_kv_list *kv_list = (const cx_kv_list*)list;
208 return kv_list->list_methods->at(list, index);
209 }
210
211 static size_t cx_kvl_find_remove(
212 struct cx_list_s *list,
213 const void *elem,
214 bool remove
215 ) {
216 cx_kv_list *kv_list = (cx_kv_list*)list;
217 // we do not use the original list methods,
218 // because that would need two passes for removal
219 // (the first to find the index, the second to get a pointer)
220 if (list->collection.size == 0) return 0;
221
222 size_t index;
223 cx_linked_list *ll = &kv_list->list;
224 char *node = cx_linked_list_find(
225 ll->begin,
226 ll->loc_next, ll->loc_data,
227 list->collection.cmpfunc, elem,
228 &index
229 );
230 if (node == NULL) {
231 return list->collection.size;
232 }
233 if (remove) {
234 cx_kv_list_update_destructors(kv_list);
235 cx_invoke_advanced_destructor(list, node + ll->loc_data);
236 cx_linked_list_remove(&ll->begin, &ll->end,
237 ll->loc_prev, ll->loc_next, node);
238 CxHashKey *key = cx_kv_list_loc_key(kv_list, node + ll->loc_data);
239 if (key->hash != 0) {
240 kv_list->map_methods->remove(&kv_list->map->map_base.base, *key, NULL);
241 }
242 list->collection.size--;
243 cxFree(list->collection.allocator, node);
244 }
245 return index;
246 }
247
248 static void cx_kvl_sort(struct cx_list_s *list) {
249 cx_kv_list *kv_list = (cx_kv_list*)list;
250 kv_list->list_methods->sort(list);
251 }
252
253 static void cx_kvl_reverse(struct cx_list_s *list) {
254 cx_kv_list *kv_list = (cx_kv_list*)list;
255 kv_list->list_methods->reverse(list);
256 }
257
258 static void cx_kvl_list_iter_next(void *it) {
259 struct cx_iterator_s *iter = it;
260 if (iter->base.remove) {
261 // remove the assigned key from the map before calling the actual function
262 cx_kv_list *kv_list = iter->src_handle.m;
263 cx_kv_list_update_destructors(kv_list);
264 char *node = iter->elem_handle;
265 CxHashKey *key = cx_kv_list_loc_key(kv_list, node + kv_list->list.loc_data);
266 if (key->hash != 0) {
267 kv_list->map_methods->remove(&kv_list->map->map_base.base, *key, NULL);
268 }
269 }
270 iter->base.next_impl(it);
271 }
272
273 static struct cx_iterator_s cx_kvl_iterator(
274 const struct cx_list_s *list,
275 size_t index,
276 bool backward
277 ) {
278 const cx_kv_list *kv_list = (const cx_kv_list*)list;
279 struct cx_iterator_s iter = kv_list->list_methods->iterator(list, index, backward);
280 iter.base.next_impl = iter.base.next;
281 iter.base.next = cx_kvl_list_iter_next;
282 return iter;
283 }
284
285 static void cx_kvl_map_deallocate(struct cx_map_s *map) {
286 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
287 kv_list->map_methods->deallocate(map);
288 kv_list->list_methods->deallocate(&kv_list->list.base);
289 }
290
291 static void cx_kvl_map_clear(struct cx_map_s *map) {
292 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
293 cx_kv_list_update_destructors(kv_list);
294 kv_list->list_methods->clear(&kv_list->list.base);
295 kv_list->map_methods->clear(map);
296 }
297
298 static void *cx_kvl_map_put(CxMap *map, CxHashKey key, void *value) {
299 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
300 // if the hash has not yet been computed, do it now
301 if (key.hash == 0) {
302 cx_hash_murmur(&key);
303 }
304
305 // reserve memory in the map first
306 void **map_data = kv_list->map_methods->put(map, key, NULL);
307 if (map_data == NULL) return NULL; // LCOV_EXCL_LINE
308
309 // insert the data into the list (which most likely destroys the sorted property)
310 kv_list->list.base.collection.sorted = false;
311 void *node_data = kv_list->list_methods->insert_element(
312 &kv_list->list.base, kv_list->list.base.collection.size,
313 kv_list->list.base.collection.store_pointer ? &value : value);
314 if (node_data == NULL) { // LCOV_EXCL_START
315 // non-destructively remove the key again
316 kv_list->map_methods->remove(&kv_list->map->map_base.base, key, &map_data);
317 return NULL;
318 } // LCOV_EXCL_STOP
319
320 // write the node pointer to the map entry
321 *map_data = node_data;
322
323 // copy the key to the node data
324 CxHashKey *key_ptr = cx_kv_list_loc_key(kv_list, node_data);
325 *key_ptr = key;
326
327 // we must return node_data here and not map_data,
328 // because the node_data is the actual element of this collection
329 return node_data;
330 }
331
332 void *cx_kvl_map_get(const CxMap *map, CxHashKey key) {
333 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
334 void *node_data = kv_list->map_methods->get(map, key);
335 if (node_data == NULL) return NULL; // LCOV_EXCL_LINE
336 // return the node data
337 return kv_list->list.base.collection.store_pointer ? *(void**)node_data : node_data;
338 }
339
340 int cx_kvl_map_remove(CxMap *map, CxHashKey key, void *targetbuf) {
341 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
342
343 void *node_data;
344 if (kv_list->map_methods->remove(map, key, &node_data)) {
345 return 1;
346 }
347 // we cannot just call a list method (because we don't have the index)
348 // and tbh. we also don't want to (because it's not performant when we
349 // can have the node ptr directly instead)
350 // therefore, we re-implement the logic ourselves
351
352 // check if the outside caller want's us to return or to destroy the element
353 if (targetbuf == NULL) {
354 // patch the destructors and invoke them through the wrapper
355 cx_kv_list_update_destructors(kv_list);
356 cx_invoke_advanced_destructor(&kv_list->list.base, node_data);
357 } else {
358 // copy the element to the target buffer
359 memcpy(targetbuf, node_data, kv_list->list.base.collection.elem_size);
360 }
361
362 // calculate the address of the node
363 void *node_ptr = (char*)node_data - kv_list->list.loc_data;
364
365 // unlink the node
366 cx_linked_list_remove(
367 &kv_list->list.begin,
368 &kv_list->list.end,
369 kv_list->list.loc_prev,
370 kv_list->list.loc_next,
371 node_ptr
372 );
373
374 // decrement the list's size
375 kv_list->list.base.collection.size--;
376
377 // deallocate the node
378 cxFree(kv_list->list.base.collection.allocator, node_ptr);
379
380 return 0;
381 }
382
383 static void *cx_kvl_iter_current_entry(const void *it) {
384 const CxMapIterator *iter = it;
385 return (void*)&iter->entry;
386 }
387
388 static void *cx_kvl_iter_current_key(const void *it) {
389 const CxMapEntry *entry = cx_kvl_iter_current_entry(it);
390 return (void*)entry->key;
391 }
392
393 static void *cx_kvl_iter_current_value(const void *it) {
394 const CxMapEntry *entry = cx_kvl_iter_current_entry(it);
395 return entry->value;
396 }
397
398 static void cx_kvl_iter_next(void *it) {
399 CxMapIterator *iter = it;
400 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)iter->map.m)->list;
401
402 // find the next list entry that has a key assigned
403 CxHashKey *key = NULL;
404 char *next = iter->elem;
405 while (true) {
406 next = *(char**)(next + kv_list->list.loc_next);
407 if (next == NULL) break;
408 key = cx_kv_list_loc_key(kv_list, next + kv_list->list.loc_data);
409 if (key->hash != 0) break;
410 }
411
412 // remove previous element if requested
413 if (iter->base.remove) {
414 iter->base.remove = false;
415 cx_kv_list_update_destructors(kv_list);
416 char *elem = iter->elem;
417 char *elem_data = elem + kv_list->list.loc_data;
418 CxHashKey *elem_key = cx_kv_list_loc_key(kv_list, elem_data);
419 // key is guaranteed to exist because iterator only iterates over elems with a key
420 kv_list->map_methods->remove(&kv_list->map->map_base.base, *elem_key, NULL);
421 cx_invoke_advanced_destructor(&kv_list->list.base, elem_data);
422 cx_linked_list_remove(
423 &kv_list->list.begin,
424 &kv_list->list.end,
425 kv_list->list.loc_prev,
426 kv_list->list.loc_next,
427 elem
428 );
429 cxFree(kv_list->list.base.collection.allocator, elem);
430 kv_list->list.base.collection.size--;
431 iter->index--;
432 iter->elem_count--;
433 }
434
435 // advance to the next element, if any
436 if (next == NULL) {
437 iter->index = kv_list->list.base.collection.size;
438 iter->elem = NULL;
439 iter->entry = (CxMapEntry){NULL, NULL};
440 return;
441 }
442 iter->index++;
443 iter->elem = next;
444 iter->entry.key = key;
445 if (kv_list->list.base.collection.store_pointer) {
446 iter->entry.value = *(void**)(next + kv_list->list.loc_data);
447 } else {
448 iter->entry.value = (void*)(next + kv_list->list.loc_data);
449 }
450 }
451
452 static bool cx_kvl_iter_valid(const void *it) {
453 const CxMapIterator *iter = it;
454 return iter->elem != NULL;
455 }
456
457 CxMapIterator cx_kvl_map_iterator(const CxMap *map, enum cx_map_iterator_type type) {
458 CxMapIterator iter = {0};
459
460 iter.type = type;
461 iter.map.c = map;
462 // although we iterate over the list, we only report that many elements that have a key in the map
463 iter.elem_count = map->collection.size;
464
465 switch (type) {
466 case CX_MAP_ITERATOR_PAIRS:
467 iter.elem_size = sizeof(CxMapEntry);
468 iter.base.current = cx_kvl_iter_current_entry;
469 break;
470 case CX_MAP_ITERATOR_KEYS:
471 iter.elem_size = sizeof(CxHashKey);
472 iter.base.current = cx_kvl_iter_current_key;
473 break;
474 case CX_MAP_ITERATOR_VALUES:
475 iter.elem_size = map->collection.elem_size;
476 iter.base.current = cx_kvl_iter_current_value;
477 break;
478 default:
479 assert(false); // LCOV_EXCL_LINE
480 }
481
482 iter.base.next = cx_kvl_iter_next;
483 iter.base.valid = cx_kvl_iter_valid;
484
485 // find the first list entry that has a key assigned
486 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
487 CxHashKey *key = NULL;
488 char *next = kv_list->list.begin;
489 while (next != NULL) {
490 key = cx_kv_list_loc_key(kv_list, next + kv_list->list.loc_data);
491 if (key->hash != 0) break;
492 next = *(char**)(next + kv_list->list.loc_next);
493 }
494 if (next == NULL) {
495 iter.elem = NULL;
496 iter.entry = (CxMapEntry){NULL, NULL};
497 } else {
498 iter.elem = next;
499 iter.entry.key = key;
500 if (kv_list->list.base.collection.store_pointer) {
501 iter.entry.value = *(void**)(next + kv_list->list.loc_data);
502 } else {
503 iter.entry.value = (void*)(next + kv_list->list.loc_data);
504 }
505 }
506
507 return iter;
508 }
509
510 static cx_list_class cx_kv_list_class = {
511 cx_kvl_deallocate,
512 cx_kvl_insert_element,
513 cx_kvl_insert_array,
514 cx_kvl_insert_sorted,
515 cx_kvl_insert_unique,
516 cx_kvl_insert_iter,
517 cx_kvl_remove,
518 cx_kvl_clear,
519 cx_kvl_swap,
520 cx_kvl_at,
521 cx_kvl_find_remove,
522 cx_kvl_sort,
523 NULL,
524 cx_kvl_reverse,
525 cx_kvl_iterator,
526 };
527
528 static cx_map_class cx_kv_map_class = {
529 cx_kvl_map_deallocate,
530 cx_kvl_map_clear,
531 cx_kvl_map_put,
532 cx_kvl_map_get,
533 cx_kvl_map_remove,
534 cx_kvl_map_iterator,
535 };
536
537 CxList *cxKvListCreate(
538 const CxAllocator *allocator,
539 cx_compare_func comparator,
540 size_t elem_size
541 ) {
542 if (allocator == NULL) {
543 allocator = cxDefaultAllocator;
544 }
545
546 // create a normal linked list and a normal hash map, first
547 CxList *list = cxLinkedListCreate(allocator, comparator, elem_size);
548 if (list == NULL) return NULL; // LCOV_EXCL_LINE
549 cx_linked_list *ll = (cx_linked_list*)list;
550 ll->extra_data_len = sizeof(CxHashKey);
551 CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0);
552 if (map == NULL) { // LCOV_EXCL_START
553 cxListFree(list);
554 return NULL;
555 } // LCOV_EXCL_STOP
556
557 // patch the kv-list class with the compare function of the linked list
558 // this allows cxListCompare() to optimize comparisons between linked lists and kv-list
559 cx_kv_list_class.compare = list->cl->compare;
560
561 // reallocate the map to add memory for the list back-reference
562 struct cx_kv_list_map_s *kv_map = cxRealloc(allocator, map, sizeof(struct cx_kv_list_map_s));
563
564 // reallocate the list to add memory for storing the metadata
565 cx_kv_list *kv_list = cxRealloc(allocator, list, sizeof(struct cx_kv_list_s));
566
567 // if any of the reallocations failed, we bail out
568 if (kv_map != NULL && kv_list != NULL) {
569 map = (CxMap*) kv_map;
570 list = (CxList*) kv_list;
571 } else { // LCOV_EXCL_START
572 cxListFree(list);
573 cxMapFree(map);
574 return NULL;
575 } // LCOV_EXCL_STOP
576
577 // zero the custom destructor information
578 memset((char*)kv_list + offsetof(cx_kv_list, list_destr), 0, sizeof(void*)*6);
579
580 // combine the list and the map aspect
581 kv_list->map = kv_map;
582 kv_map->list = kv_list;
583
584 // remember the base methods and override them
585 kv_list->map_methods = map->cl;
586 map->cl = &cx_kv_map_class;
587 if (list->climpl == NULL) {
588 kv_list->list_methods = list->cl;
589 list->cl = &cx_kv_list_class;
590 } else {
591 kv_list->list_methods = list->climpl;
592 list->climpl = &cx_kv_list_class;
593 }
594
595 return list;
596 }
597
598 CxMap *cxKvListCreateAsMap(
599 const CxAllocator *allocator,
600 cx_compare_func comparator,
601 size_t elem_size
602 ) {
603 CxList *list = cxKvListCreate(allocator, comparator, elem_size);
604 return list == NULL ? NULL : cxKvListAsMap(list);
605 }
606
607 CxList *cxKvListAsList(CxMap *map) {
608 return &((struct cx_kv_list_map_s*)map)->list->list.base;
609 }
610
611 CxMap *cxKvListAsMap(CxList *list) {
612 return &((cx_kv_list*)list)->map->map_base.base;
613 }
614
615 int cx_kv_list_set_key(CxList *list, size_t index, CxHashKey key) {
616 cx_kv_list *kv_list = (cx_kv_list*)list;
617 void *node_data = kv_list->list_methods->at(list, index);
618 if (node_data == NULL) {
619 return 1;
620 }
621 // if the hash has not yet been computed, do it now
622 if (key.hash == 0) {
623 cx_hash_murmur(&key);
624 }
625
626 // check if the key is already assigned
627 void *existing = kv_list->map_methods->get(&kv_list->map->map_base.base, key);
628 if (existing == node_data) {
629 return 0; // nothing to do
630 }
631 if (existing != NULL) {
632 // the key is already assigned to another node, we disallow re-assignment
633 return 1;
634 }
635
636 // add the key to the map;
637 if (NULL == kv_list->map_methods->put(&kv_list->map->map_base.base, key, node_data)) {
638 return 1; // LCOV_EXCL_LINE
639 }
640
641 // write the key to the list's node
642 CxHashKey *loc_key = cx_kv_list_loc_key(kv_list, node_data);
643 *loc_key = key;
644
645 return 0;
646 }
647
648 int cxKvListRemoveKey(CxList *list, size_t index) {
649 cx_kv_list *kv_list = (cx_kv_list*)list;
650 void *node_data = kv_list->list_methods->at(list, index);
651 if (node_data == NULL) {
652 return 1;
653 }
654 CxHashKey *loc_key = cx_kv_list_loc_key(kv_list, node_data);
655 if (loc_key->hash == 0) {
656 return 0;
657 }
658 kv_list->map_methods->remove(&kv_list->map->map_base.base, *loc_key, NULL);
659 // also zero the memory in the list node,
660 // but don't free the key data (that was done by the map remove)
661 memset(loc_key, 0, sizeof(CxHashKey));
662 return 0;
663 }
664
665 const CxHashKey *cxKvListGetKey(CxList *list, size_t index) {
666 cx_kv_list *kv_list = (cx_kv_list*)list;
667 void *node_data = kv_list->list_methods->at(list, index);
668 if (node_data == NULL) {
669 return NULL;
670 }
671 CxHashKey *key = cx_kv_list_loc_key(kv_list, node_data);
672 if (key->hash == 0) {
673 return NULL;
674 }
675 return key;
676 }
677
678 int cx_kv_list_insert(CxList *list, size_t index, CxHashKey key, void *value) {
679 // assume we are losing the sorted property
680 list->collection.sorted = false;
681
682 cx_kv_list *kv_list = (cx_kv_list*)list;
683
684 // reserve memory in the map
685 void **map_data = kv_list->map_methods->put(&kv_list->map->map_base.base, key, NULL);
686 if (map_data == NULL) return 1; // LCOV_EXCL_LINE
687
688 // insert the node
689 void *node_data = kv_list->list_methods->insert_element(&kv_list->list.base, index,
690 kv_list->list.base.collection.store_pointer ? &value : value);
691 if (node_data == NULL) { // LCOV_EXCL_START
692 // non-destructively remove the key again
693 kv_list->map_methods->remove(&kv_list->map->map_base.base, key, &map_data);
694 return 1;
695 } // LCOV_EXCL_STOP
696 *map_data = node_data;
697
698 // write the key to the node
699 CxHashKey *loc_key = cx_kv_list_loc_key(kv_list, node_data);
700 *loc_key = key;
701
702 return 0;
703 }

Mercurial Repository: idav

mercurial