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 CxMapEntry 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 CxMapEntry map_entry = kv_list->map_methods->put(map, key, NULL);
363 if (map_entry.key == NULL) return (CxMapEntry){NULL, 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 void *dummy;
373 kv_list->map_methods->remove(&kv_list->map->map_base.base, key, &dummy);
374 return (CxMapEntry){NULL, NULL};
375 } // LCOV_EXCL_STOP
376
377 // write the node pointer to the map entry
378 *(void**)map_entry.value = node_data;
379
380 // copy the key to the node data
381 CxHashKey *key_ptr = cx_kv_list_loc_key(kv_list, node_data);
382 *key_ptr = *map_entry.key;
383
384 // we must return an entry that points to the node data!
385 return (CxMapEntry ){key_ptr, 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 size_t elem_size
556 ) {
557 if (allocator == NULL) {
558 allocator = cxDefaultAllocator;
559 }
560
561 // create a normal linked list and a normal hash map, first
562 CxList *list = cxLinkedListCreate(allocator, elem_size);
563 if (list == NULL) return NULL; // LCOV_EXCL_LINE
564 cx_linked_list *ll = (cx_linked_list*)list;
565 cx_linked_list_extra_data(ll, sizeof(CxHashKey));
566 CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0);
567 if (map == NULL) { // LCOV_EXCL_START
568 cxListFree(list);
569 return NULL;
570 } // LCOV_EXCL_STOP
571
572 // patch the kv-list class with the compare function of the linked list
573 // this allows cxListCompare() to optimize comparisons between linked lists and kv-list
574 cx_kv_list_class.compare = list->cl->compare;
575
576 // reallocate the map to add memory for the list back-reference
577 struct cx_kv_list_map_s *kv_map = cxRealloc(allocator, map, sizeof(struct cx_kv_list_map_s));
578
579 // reallocate the list to add memory for storing the metadata
580 cx_kv_list *kv_list = cxRealloc(allocator, list, sizeof(struct cx_kv_list_s));
581
582 // if any of the reallocations failed, we bail out
583 if (kv_map != NULL && kv_list != NULL) {
584 map = (CxMap*) kv_map;
585 list = (CxList*) kv_list;
586 } else { // LCOV_EXCL_START
587 cxListFree(list);
588 cxMapFree(map);
589 return NULL;
590 } // LCOV_EXCL_STOP
591
592 // zero the custom destructor information
593 memset((char*)kv_list + offsetof(cx_kv_list, list_destr), 0, sizeof(void*)*6);
594
595 // combine the list and the map aspect
596 kv_list->map = kv_map;
597 kv_map->list = kv_list;
598
599 // remember the base methods and override them
600 kv_list->map_methods = map->cl;
601 map->cl = &cx_kv_map_class;
602 if (list->climpl == NULL) {
603 kv_list->list_methods = list->cl;
604 list->cl = &cx_kv_list_class;
605 } else {
606 kv_list->list_methods = list->climpl;
607 list->climpl = &cx_kv_list_class;
608 }
609
610 return list;
611 }
612
613 CxMap *cxKvListCreateAsMap(
614 const CxAllocator *allocator,
615 size_t elem_size
616 ) {
617 CxList *list = cxKvListCreate(allocator, elem_size);
618 return list == NULL ? NULL : cxKvListAsMap(list);
619 }
620
621 CxList *cxKvListAsList(CxMap *map) {
622 return &((struct cx_kv_list_map_s*)map)->list->list.base;
623 }
624
625 CxMap *cxKvListAsMap(CxList *list) {
626 return &((cx_kv_list*)list)->map->map_base.base;
627 }
628
629 int cx_kv_list_set_key(CxList *list, size_t index, CxHashKey key) {
630 cx_kv_list *kv_list = (cx_kv_list*)list;
631 void *node_data = kv_list->list_methods->at(list, index);
632 if (node_data == NULL) {
633 return 1;
634 }
635 // if the hash has not yet been computed, do it now
636 if (key.hash == 0) {
637 cx_hash_murmur(&key);
638 }
639
640 // check if the key is already assigned
641 void *existing = kv_list->map_methods->get(&kv_list->map->map_base.base, key);
642 if (existing == node_data) {
643 return 0; // nothing to do
644 }
645 if (existing != NULL) {
646 // the key is already assigned to another node, we disallow re-assignment
647 return 1;
648 }
649
650 // add the key to the map
651 const CxMapEntry entry = kv_list->map_methods->put(
652 &kv_list->map->map_base.base, key, node_data);
653 if (entry.key == NULL) return 1; // LCOV_EXCL_LINE
654
655 // write the key to the list's node
656 CxHashKey *loc_key = cx_kv_list_loc_key(kv_list, node_data);
657 *loc_key = *entry.key;
658
659 return 0;
660 }
661
662 int cxKvListRemoveKey(CxList *list, size_t index) {
663 cx_kv_list *kv_list = (cx_kv_list*)list;
664 void *node_data = kv_list->list_methods->at(list, index);
665 if (node_data == NULL) {
666 return 1;
667 }
668 CxHashKey *loc_key = cx_kv_list_loc_key(kv_list, node_data);
669 if (loc_key->hash == 0) {
670 return 0;
671 }
672 kv_list->map_methods->remove(&kv_list->map->map_base.base, *loc_key, NULL);
673 // also zero the memory in the list node,
674 // but don't free the key data (that was done by the map remove)
675 memset(loc_key, 0, sizeof(CxHashKey));
676 return 0;
677 }
678
679 const CxHashKey *cxKvListGetKey(CxList *list, size_t index) {
680 cx_kv_list *kv_list = (cx_kv_list*)list;
681 void *node_data = kv_list->list_methods->at(list, index);
682 if (node_data == NULL) {
683 return NULL;
684 }
685 CxHashKey *key = cx_kv_list_loc_key(kv_list, node_data);
686 if (key->hash == 0) {
687 return NULL;
688 }
689 return key;
690 }
691
692 int cx_kv_list_insert(CxList *list, size_t index, CxHashKey key, void *value) {
693 // assume we are losing the sorted property
694 list->collection.sorted = false;
695
696 cx_kv_list *kv_list = (cx_kv_list*)list;
697
698 // reserve memory in the map
699 CxMapEntry map_entry = kv_list->map_methods->put(&kv_list->map->map_base.base, key, NULL);
700 if (map_entry.key == NULL) return 1; // LCOV_EXCL_LINE
701
702 // insert the node
703 void *node_data = kv_list->list_methods->insert_element(&kv_list->list.base, index,
704 kv_list->list.base.collection.store_pointer ? &value : value);
705 if (node_data == NULL) { // LCOV_EXCL_START
706 // non-destructively remove the key again
707 void *dummy;
708 kv_list->map_methods->remove(&kv_list->map->map_base.base, key, &dummy);
709 return 1;
710 } // LCOV_EXCL_STOP
711 *(void**)map_entry.value = node_data;
712
713 // write the key to the node
714 CxHashKey *loc_key = cx_kv_list_loc_key(kv_list, node_data);
715 *loc_key = *map_entry.key;
716
717 return 0;
718 }
719