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