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.loc_data + list->list.loc_extra);
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;
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;
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 // note that we do not clear the remove flag, because the next_impl will do that
271 iter->base.next_impl(it);
272 }
273
274 static struct cx_iterator_s cx_kvl_iterator(
275 const struct cx_list_s *list,
276 size_t index,
277 bool backward
278 ) {
279 const cx_kv_list *kv_list = (const cx_kv_list*)list;
280 struct cx_iterator_s iter = kv_list->list_methods->iterator(list, index, backward);
281 iter.base.next_impl = iter.base.next;
282 iter.base.next = cx_kvl_list_iter_next;
283 return iter;
284 }
285
286 static void cx_kvl_map_deallocate(struct cx_map_s *map) {
287 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
288 kv_list->map_methods->deallocate(map);
289 kv_list->list_methods->deallocate(&kv_list->list.base);
290 }
291
292 static void cx_kvl_map_clear(struct cx_map_s *map) {
293 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
294 cx_kv_list_update_destructors(kv_list);
295 kv_list->list_methods->clear(&kv_list->list.base);
296 kv_list->map_methods->clear(map);
297 }
298
299 static void *cx_kvl_map_put(CxMap *map, CxHashKey key, void *value) {
300 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
301 // if the hash has not yet been computed, do it now
302 if (key.hash == 0) {
303 cx_hash_murmur(&key);
304 }
305
306 // reserve memory in the map first
307 void **map_data = kv_list->map_methods->put(map, key, NULL);
308 if (map_data == NULL) return NULL; // LCOV_EXCL_LINE
309
310 // insert the data into the list (which most likely destroys the sorted property)
311 kv_list->list.base.collection.sorted = false;
312 void *node_data = kv_list->list_methods->insert_element(
313 &kv_list->list.base, kv_list->list.base.collection.size,
314 kv_list->list.base.collection.store_pointer ? &value : value);
315 if (node_data == NULL) { // LCOV_EXCL_START
316 // non-destructively remove the key again
317 kv_list->map_methods->remove(&kv_list->map->map_base.base, key, &map_data);
318 return NULL;
319 } // LCOV_EXCL_STOP
320
321 // write the node pointer to the map entry
322 *map_data = node_data;
323
324 // copy the key to the node data
325 CxHashKey *key_ptr = cx_kv_list_loc_key(kv_list, node_data);
326 *key_ptr = key;
327
328 // we must return node_data here and not map_data,
329 // because the node_data is the actual element of this collection
330 return node_data;
331 }
332
333 void *cx_kvl_map_get(const CxMap *map, CxHashKey key) {
334 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
335 void *node_data = kv_list->map_methods->get(map, key);
336 if (node_data == NULL) return NULL; // LCOV_EXCL_LINE
337 // return the node data
338 return kv_list->list.base.collection.store_pointer ? *(void**)node_data : node_data;
339 }
340
341 int cx_kvl_map_remove(CxMap *map, CxHashKey key, void *targetbuf) {
342 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
343
344 void *node_data;
345 if (kv_list->map_methods->remove(map, key, &node_data)) {
346 return 1;
347 }
348 // we cannot just call a list method (because we don't have the index)
349 // and tbh. we also don't want to (because it's not performant when we
350 // can have the node ptr directly instead)
351 // therefore, we re-implement the logic ourselves
352
353 // check if the outside caller want's us to return or to destroy the element
354 if (targetbuf == NULL) {
355 // patch the destructors and invoke them through the wrapper
356 cx_kv_list_update_destructors(kv_list);
357 cx_invoke_advanced_destructor(&kv_list->list.base, node_data);
358 } else {
359 // copy the element to the target buffer
360 memcpy(targetbuf, node_data, kv_list->list.base.collection.elem_size);
361 }
362
363 // calculate the address of the node
364 void *node_ptr = (char*)node_data - kv_list->list.loc_data;
365
366 // unlink the node
367 cx_linked_list_remove(
368 &kv_list->list.begin,
369 &kv_list->list.end,
370 kv_list->list.loc_prev,
371 kv_list->list.loc_next,
372 node_ptr
373 );
374
375 // decrement the list's size
376 kv_list->list.base.collection.size--;
377
378 // deallocate the node
379 cxFree(kv_list->list.base.collection.allocator, node_ptr);
380
381 return 0;
382 }
383
384 static void *cx_kvl_iter_current_entry(const void *it) {
385 const CxMapIterator *iter = it;
386 return (void*)&iter->entry;
387 }
388
389 static void *cx_kvl_iter_current_key(const void *it) {
390 const CxMapEntry *entry = cx_kvl_iter_current_entry(it);
391 return (void*)entry->key;
392 }
393
394 static void *cx_kvl_iter_current_value(const void *it) {
395 const CxMapEntry *entry = cx_kvl_iter_current_entry(it);
396 return entry->value;
397 }
398
399 static void cx_kvl_iter_next(void *it) {
400 CxMapIterator *iter = it;
401 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)iter->map)->list;
402
403 // find the next list entry that has a key assigned
404 CxHashKey *key = NULL;
405 char *next = iter->elem;
406 while (true) {
407 next = *(char**)(next + kv_list->list.loc_next);
408 if (next == NULL) break;
409 key = cx_kv_list_loc_key(kv_list, next + kv_list->list.loc_data);
410 if (key->hash != 0) break;
411 }
412
413 // remove previous element if requested
414 if (iter->base.remove) {
415 iter->base.remove = false;
416 cx_kv_list_update_destructors(kv_list);
417 char *elem = iter->elem;
418 char *elem_data = elem + kv_list->list.loc_data;
419 CxHashKey *elem_key = cx_kv_list_loc_key(kv_list, elem_data);
420 // key is guaranteed to exist because iterator only iterates over elems with a key
421 kv_list->map_methods->remove(&kv_list->map->map_base.base, *elem_key, NULL);
422 cx_invoke_advanced_destructor(&kv_list->list.base, elem_data);
423 cx_linked_list_remove(
424 &kv_list->list.begin,
425 &kv_list->list.end,
426 kv_list->list.loc_prev,
427 kv_list->list.loc_next,
428 elem
429 );
430 cxFree(kv_list->list.base.collection.allocator, elem);
431 kv_list->list.base.collection.size--;
432 iter->index--;
433 iter->elem_count--;
434 }
435
436 // advance to the next element, if any
437 if (next == NULL) {
438 iter->index = kv_list->list.base.collection.size;
439 iter->elem = NULL;
440 iter->entry = (CxMapEntry){NULL, NULL};
441 return;
442 }
443 iter->index++;
444 iter->elem = next;
445 iter->entry.key = key;
446 if (kv_list->list.base.collection.store_pointer) {
447 iter->entry.value = *(void**)(next + kv_list->list.loc_data);
448 } else {
449 iter->entry.value = (void*)(next + kv_list->list.loc_data);
450 }
451 }
452
453 static bool cx_kvl_iter_valid(const void *it) {
454 const CxMapIterator *iter = it;
455 return iter->elem != NULL;
456 }
457
458 CxMapIterator cx_kvl_map_iterator(const CxMap *map, enum cx_map_iterator_type type) {
459 CxMapIterator iter = {0};
460
461 iter.type = type;
462 iter.map = (CxMap*)map;
463 // although we iterate over the list, we only report that many elements that have a key in the map
464 iter.elem_count = map->collection.size;
465
466 switch (type) {
467 case CX_MAP_ITERATOR_PAIRS:
468 iter.elem_size = sizeof(CxMapEntry);
469 iter.base.current = cx_kvl_iter_current_entry;
470 break;
471 case CX_MAP_ITERATOR_KEYS:
472 iter.elem_size = sizeof(CxHashKey);
473 iter.base.current = cx_kvl_iter_current_key;
474 break;
475 case CX_MAP_ITERATOR_VALUES:
476 iter.elem_size = map->collection.elem_size;
477 iter.base.current = cx_kvl_iter_current_value;
478 break;
479 default:
480 assert(false); // LCOV_EXCL_LINE
481 }
482
483 iter.base.allow_remove = true;
484 iter.base.next = cx_kvl_iter_next;
485 iter.base.valid = cx_kvl_iter_valid;
486
487 // find the first list entry that has a key assigned
488 cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
489 CxHashKey *key = NULL;
490 char *next = kv_list->list.begin;
491 while (next != NULL) {
492 key = cx_kv_list_loc_key(kv_list, next + kv_list->list.loc_data);
493 if (key->hash != 0) break;
494 next = *(char**)(next + kv_list->list.loc_next);
495 }
496 if (next == NULL) {
497 iter.elem = NULL;
498 iter.entry = (CxMapEntry){NULL, NULL};
499 } else {
500 iter.elem = next;
501 iter.entry.key = key;
502 if (kv_list->list.base.collection.store_pointer) {
503 iter.entry.value = *(void**)(next + kv_list->list.loc_data);
504 } else {
505 iter.entry.value = (void*)(next + kv_list->list.loc_data);
506 }
507 }
508
509 return iter;
510 }
511
512 static int cx_kvl_change_capacity(struct cx_list_s *list,
513 cx_attr_unused size_t cap) {
514 // since our backing list is a linked list, we don't need to do much here,
515 // but rehashing the map is quite useful
516 cx_kv_list *kv_list = (cx_kv_list*)list;
517 cxMapRehash(&kv_list->map->map_base.base);
518 return 0;
519 }
520
521 static cx_list_class cx_kv_list_class = {
522 cx_kvl_deallocate,
523 cx_kvl_insert_element,
524 cx_kvl_insert_array,
525 cx_kvl_insert_sorted,
526 cx_kvl_insert_unique,
527 cx_kvl_insert_iter,
528 cx_kvl_remove,
529 cx_kvl_clear,
530 cx_kvl_swap,
531 cx_kvl_at,
532 cx_kvl_find_remove,
533 cx_kvl_sort,
534 NULL,
535 cx_kvl_reverse,
536 cx_kvl_change_capacity,
537 cx_kvl_iterator,
538 };
539
540 static cx_map_class cx_kv_map_class = {
541 cx_kvl_map_deallocate,
542 cx_kvl_map_clear,
543 cx_kvl_map_put,
544 cx_kvl_map_get,
545 cx_kvl_map_remove,
546 cx_kvl_map_iterator,
547 };
548
549 CxList *cxKvListCreate(
550 const CxAllocator *allocator,
551 cx_compare_func comparator,
552 size_t elem_size
553 ) {
554 if (allocator == NULL) {
555 allocator = cxDefaultAllocator;
556 }
557
558 // create a normal linked list and a normal hash map, first
559 CxList *list = cxLinkedListCreate(allocator, comparator, elem_size);
560 if (list == NULL) return NULL; // LCOV_EXCL_LINE
561 cx_linked_list *ll = (cx_linked_list*)list;
562 cx_linked_list_extra_data(ll, sizeof(CxHashKey));
563 CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0);
564 if (map == NULL) { // LCOV_EXCL_START
565 cxListFree(list);
566 return NULL;
567 } // LCOV_EXCL_STOP
568
569 // patch the kv-list class with the compare function of the linked list
570 // this allows cxListCompare() to optimize comparisons between linked lists and kv-list
571 cx_kv_list_class.compare = list->cl->compare;
572
573 // reallocate the map to add memory for the list back-reference
574 struct cx_kv_list_map_s *kv_map = cxRealloc(allocator, map, sizeof(struct cx_kv_list_map_s));
575
576 // reallocate the list to add memory for storing the metadata
577 cx_kv_list *kv_list = cxRealloc(allocator, list, sizeof(struct cx_kv_list_s));
578
579 // if any of the reallocations failed, we bail out
580 if (kv_map != NULL && kv_list != NULL) {
581 map = (CxMap*) kv_map;
582 list = (CxList*) kv_list;
583 } else { // LCOV_EXCL_START
584 cxListFree(list);
585 cxMapFree(map);
586 return NULL;
587 } // LCOV_EXCL_STOP
588
589 // zero the custom destructor information
590 memset((char*)kv_list + offsetof(cx_kv_list, list_destr), 0, sizeof(void*)*6);
591
592 // combine the list and the map aspect
593 kv_list->map = kv_map;
594 kv_map->list = kv_list;
595
596 // remember the base methods and override them
597 kv_list->map_methods = map->cl;
598 map->cl = &cx_kv_map_class;
599 if (list->climpl == NULL) {
600 kv_list->list_methods = list->cl;
601 list->cl = &cx_kv_list_class;
602 } else {
603 kv_list->list_methods = list->climpl;
604 list->climpl = &cx_kv_list_class;
605 }
606
607 return list;
608 }
609
610 CxMap *cxKvListCreateAsMap(
611 const CxAllocator *allocator,
612 cx_compare_func comparator,
613 size_t elem_size
614 ) {
615 CxList *list = cxKvListCreate(allocator, comparator, elem_size);
616 return list == NULL ? NULL : cxKvListAsMap(list);
617 }
618
619 CxList *cxKvListAsList(CxMap *map) {
620 return &((struct cx_kv_list_map_s*)map)->list->list.base;
621 }
622
623 CxMap *cxKvListAsMap(CxList *list) {
624 return &((cx_kv_list*)list)->map->map_base.base;
625 }
626
627 int cx_kv_list_set_key(CxList *list, size_t index, CxHashKey key) {
628 cx_kv_list *kv_list = (cx_kv_list*)list;
629 void *node_data = kv_list->list_methods->at(list, index);
630 if (node_data == NULL) {
631 return 1;
632 }
633 // if the hash has not yet been computed, do it now
634 if (key.hash == 0) {
635 cx_hash_murmur(&key);
636 }
637
638 // check if the key is already assigned
639 void *existing = kv_list->map_methods->get(&kv_list->map->map_base.base, key);
640 if (existing == node_data) {
641 return 0; // nothing to do
642 }
643 if (existing != NULL) {
644 // the key is already assigned to another node, we disallow re-assignment
645 return 1;
646 }
647
648 // add the key to the map;
649 if (NULL == kv_list->map_methods->put(&kv_list->map->map_base.base, key, node_data)) {
650 return 1; // LCOV_EXCL_LINE
651 }
652
653 // write the key to the list's node
654 CxHashKey *loc_key = cx_kv_list_loc_key(kv_list, node_data);
655 *loc_key = key;
656
657 return 0;
658 }
659
660 int cxKvListRemoveKey(CxList *list, size_t index) {
661 cx_kv_list *kv_list = (cx_kv_list*)list;
662 void *node_data = kv_list->list_methods->at(list, index);
663 if (node_data == NULL) {
664 return 1;
665 }
666 CxHashKey *loc_key = cx_kv_list_loc_key(kv_list, node_data);
667 if (loc_key->hash == 0) {
668 return 0;
669 }
670 kv_list->map_methods->remove(&kv_list->map->map_base.base, *loc_key, NULL);
671 // also zero the memory in the list node,
672 // but don't free the key data (that was done by the map remove)
673 memset(loc_key, 0, sizeof(CxHashKey));
674 return 0;
675 }
676
677 const CxHashKey *cxKvListGetKey(CxList *list, size_t index) {
678 cx_kv_list *kv_list = (cx_kv_list*)list;
679 void *node_data = kv_list->list_methods->at(list, index);
680 if (node_data == NULL) {
681 return NULL;
682 }
683 CxHashKey *key = cx_kv_list_loc_key(kv_list, node_data);
684 if (key->hash == 0) {
685 return NULL;
686 }
687 return key;
688 }
689
690 int cx_kv_list_insert(CxList *list, size_t index, CxHashKey key, void *value) {
691 // assume we are losing the sorted property
692 list->collection.sorted = false;
693
694 cx_kv_list *kv_list = (cx_kv_list*)list;
695
696 // reserve memory in the map
697 void **map_data = kv_list->map_methods->put(&kv_list->map->map_base.base, key, NULL);
698 if (map_data == NULL) return 1; // LCOV_EXCL_LINE
699
700 // insert the node
701 void *node_data = kv_list->list_methods->insert_element(&kv_list->list.base, index,
702 kv_list->list.base.collection.store_pointer ? &value : value);
703 if (node_data == NULL) { // LCOV_EXCL_START
704 // non-destructively remove the key again
705 kv_list->map_methods->remove(&kv_list->map->map_base.base, key, &map_data);
706 return 1;
707 } // LCOV_EXCL_STOP
708 *map_data = node_data;
709
710 // write the key to the node
711 CxHashKey *loc_key = cx_kv_list_loc_key(kv_list, node_data);
712 *loc_key = key;
713
714 return 0;
715 }
716