--- a/ucx/kv_list.c Sun Dec 07 20:16:59 2025 +0100
+++ b/ucx/kv_list.c Fri Dec 19 17:53:18 2025 +0100
@@ -98,7 +98,7 @@
}
static CxHashKey *cx_kv_list_loc_key(cx_kv_list *list, void *node_data) {
- return (CxHashKey*)((char*)node_data + list->list.base.collection.elem_size);
+ return (CxHashKey*)((char*)node_data - list->list.loc_data + list->list.loc_extra);
}
static void cx_kvl_deallocate(struct cx_list_s *list) {
@@ -221,11 +221,12 @@
size_t index;
cx_linked_list *ll = &kv_list->list;
- char *node = cx_linked_list_find(
+ char *node = cx_linked_list_find_c(
ll->begin,
ll->loc_next, ll->loc_data,
- list->collection.cmpfunc, elem,
- &index
+ elem, &index,
+ cx_list_compare_wrapper,
+ list
);
if (node == NULL) {
return list->collection.size;
@@ -285,6 +286,7 @@
static void cx_kvl_map_deallocate(struct cx_map_s *map) {
cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
+ cx_kv_list_update_destructors(kv_list);
kv_list->map_methods->deallocate(map);
kv_list->list_methods->deallocate(&kv_list->list.base);
}
@@ -296,41 +298,7 @@
kv_list->map_methods->clear(map);
}
-static void *cx_kvl_map_put(CxMap *map, CxHashKey key, void *value) {
- cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
- // if the hash has not yet been computed, do it now
- if (key.hash == 0) {
- cx_hash_murmur(&key);
- }
-
- // reserve memory in the map first
- void **map_data = kv_list->map_methods->put(map, key, NULL);
- if (map_data == NULL) return NULL; // LCOV_EXCL_LINE
-
- // insert the data into the list (which most likely destroys the sorted property)
- kv_list->list.base.collection.sorted = false;
- void *node_data = kv_list->list_methods->insert_element(
- &kv_list->list.base, kv_list->list.base.collection.size,
- kv_list->list.base.collection.store_pointer ? &value : value);
- if (node_data == NULL) { // LCOV_EXCL_START
- // non-destructively remove the key again
- kv_list->map_methods->remove(&kv_list->map->map_base.base, key, &map_data);
- return NULL;
- } // LCOV_EXCL_STOP
-
- // write the node pointer to the map entry
- *map_data = node_data;
-
- // copy the key to the node data
- CxHashKey *key_ptr = cx_kv_list_loc_key(kv_list, node_data);
- *key_ptr = key;
-
- // we must return node_data here and not map_data,
- // because the node_data is the actual element of this collection
- return node_data;
-}
-
-void *cx_kvl_map_get(const CxMap *map, CxHashKey key) {
+static void *cx_kvl_map_get(const CxMap *map, CxHashKey key) {
cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
void *node_data = kv_list->map_methods->get(map, key);
if (node_data == NULL) return NULL; // LCOV_EXCL_LINE
@@ -338,7 +306,7 @@
return kv_list->list.base.collection.store_pointer ? *(void**)node_data : node_data;
}
-int cx_kvl_map_remove(CxMap *map, CxHashKey key, void *targetbuf) {
+static int cx_kvl_map_remove(CxMap *map, CxHashKey key, void *targetbuf) {
cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
void *node_data;
@@ -381,6 +349,43 @@
return 0;
}
+static CxMapEntry cx_kvl_map_put(CxMap *map, CxHashKey key, void *value) {
+ cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
+ // if the hash has not yet been computed, do it now
+ if (key.hash == 0) {
+ cx_hash_murmur(&key);
+ }
+
+ // remove any existing element first
+ cx_kvl_map_remove(map, key, NULL);
+
+ // now reserve new memory in the map
+ CxMapEntry map_entry = kv_list->map_methods->put(map, key, NULL);
+ if (map_entry.key == NULL) return (CxMapEntry){NULL, NULL}; // LCOV_EXCL_LINE
+
+ // insert the data into the list (which most likely destroys the sorted property)
+ kv_list->list.base.collection.sorted = false;
+ void *node_data = kv_list->list_methods->insert_element(
+ &kv_list->list.base, kv_list->list.base.collection.size,
+ kv_list->list.base.collection.store_pointer ? &value : value);
+ if (node_data == NULL) { // LCOV_EXCL_START
+ // non-destructively remove the key again
+ void *dummy;
+ kv_list->map_methods->remove(&kv_list->map->map_base.base, key, &dummy);
+ return (CxMapEntry){NULL, NULL};
+ } // LCOV_EXCL_STOP
+
+ // write the node pointer to the map entry
+ *(void**)map_entry.value = node_data;
+
+ // copy the key to the node data
+ CxHashKey *key_ptr = cx_kv_list_loc_key(kv_list, node_data);
+ *key_ptr = *map_entry.key;
+
+ // we must return an entry that points to the node data!
+ return (CxMapEntry ){key_ptr, node_data};
+}
+
static void *cx_kvl_iter_current_entry(const void *it) {
const CxMapIterator *iter = it;
return (void*)&iter->entry;
@@ -455,7 +460,7 @@
return iter->elem != NULL;
}
-CxMapIterator cx_kvl_map_iterator(const CxMap *map, enum cx_map_iterator_type type) {
+static CxMapIterator cx_kvl_map_iterator(const CxMap *map, enum cx_map_iterator_type type) {
CxMapIterator iter = {0};
iter.type = type;
@@ -509,6 +514,15 @@
return iter;
}
+static int cx_kvl_change_capacity(struct cx_list_s *list,
+ cx_attr_unused size_t cap) {
+ // since our backing list is a linked list, we don't need to do much here,
+ // but rehashing the map is quite useful
+ cx_kv_list *kv_list = (cx_kv_list*)list;
+ cxMapRehash(&kv_list->map->map_base.base);
+ return 0;
+}
+
static cx_list_class cx_kv_list_class = {
cx_kvl_deallocate,
cx_kvl_insert_element,
@@ -524,6 +538,7 @@
cx_kvl_sort,
NULL,
cx_kvl_reverse,
+ cx_kvl_change_capacity,
cx_kvl_iterator,
};
@@ -538,7 +553,6 @@
CxList *cxKvListCreate(
const CxAllocator *allocator,
- cx_compare_func comparator,
size_t elem_size
) {
if (allocator == NULL) {
@@ -546,10 +560,10 @@
}
// create a normal linked list and a normal hash map, first
- CxList *list = cxLinkedListCreate(allocator, comparator, elem_size);
+ CxList *list = cxLinkedListCreate(allocator, elem_size);
if (list == NULL) return NULL; // LCOV_EXCL_LINE
cx_linked_list *ll = (cx_linked_list*)list;
- ll->extra_data_len = sizeof(CxHashKey);
+ cx_linked_list_extra_data(ll, sizeof(CxHashKey));
CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0);
if (map == NULL) { // LCOV_EXCL_START
cxListFree(list);
@@ -586,23 +600,17 @@
// remember the base methods and override them
kv_list->map_methods = map->cl;
map->cl = &cx_kv_map_class;
- if (list->climpl == NULL) {
- kv_list->list_methods = list->cl;
- list->cl = &cx_kv_list_class;
- } else {
- kv_list->list_methods = list->climpl;
- list->climpl = &cx_kv_list_class;
- }
+ kv_list->list_methods = list->cl;
+ list->cl = &cx_kv_list_class;
return list;
}
CxMap *cxKvListCreateAsMap(
const CxAllocator *allocator,
- cx_compare_func comparator,
size_t elem_size
) {
- CxList *list = cxKvListCreate(allocator, comparator, elem_size);
+ CxList *list = cxKvListCreate(allocator, elem_size);
return list == NULL ? NULL : cxKvListAsMap(list);
}
@@ -635,14 +643,14 @@
return 1;
}
- // add the key to the map;
- if (NULL == kv_list->map_methods->put(&kv_list->map->map_base.base, key, node_data)) {
- return 1; // LCOV_EXCL_LINE
- }
+ // add the key to the map
+ const CxMapEntry entry = kv_list->map_methods->put(
+ &kv_list->map->map_base.base, key, node_data);
+ if (entry.key == NULL) return 1; // LCOV_EXCL_LINE
// write the key to the list's node
CxHashKey *loc_key = cx_kv_list_loc_key(kv_list, node_data);
- *loc_key = key;
+ *loc_key = *entry.key;
return 0;
}
@@ -684,22 +692,23 @@
cx_kv_list *kv_list = (cx_kv_list*)list;
// reserve memory in the map
- void **map_data = kv_list->map_methods->put(&kv_list->map->map_base.base, key, NULL);
- if (map_data == NULL) return 1; // LCOV_EXCL_LINE
+ CxMapEntry map_entry = kv_list->map_methods->put(&kv_list->map->map_base.base, key, NULL);
+ if (map_entry.key == NULL) return 1; // LCOV_EXCL_LINE
// insert the node
void *node_data = kv_list->list_methods->insert_element(&kv_list->list.base, index,
kv_list->list.base.collection.store_pointer ? &value : value);
if (node_data == NULL) { // LCOV_EXCL_START
// non-destructively remove the key again
- kv_list->map_methods->remove(&kv_list->map->map_base.base, key, &map_data);
+ void *dummy;
+ kv_list->map_methods->remove(&kv_list->map->map_base.base, key, &dummy);
return 1;
} // LCOV_EXCL_STOP
- *map_data = node_data;
+ *(void**)map_entry.value = node_data;
// write the key to the node
CxHashKey *loc_key = cx_kv_list_loc_key(kv_list, node_data);
- *loc_key = key;
+ *loc_key = *map_entry.key;
return 0;
}