/*
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
*
* Copyright 2025 Mike Becker, Olaf Wintermann All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*/
#include "cx/kv_list.h"
#include "cx/hash_map.h"
#include "cx/linked_list.h"
#include <string.h>
#include <assert.h>
typedef struct cx_kv_list_s cx_kv_list;
struct cx_kv_list_map_s {
struct cx_hash_map_s map_base;
/** Back-reference to the list. */
cx_kv_list *list;
};
struct cx_kv_list_s {
struct cx_linked_list_s list;
/** The lookup map - stores pointers to the nodes. */
struct cx_kv_list_map_s *map;
const cx_list_class *list_methods;
const cx_map_class *map_methods;
cx_destructor_func list_destr;
cx_destructor_func2 list_destr2;
void *list_destr_data;
cx_destructor_func map_destr;
cx_destructor_func2 map_destr2;
void *map_destr_data;
};
static void cx_kv_list_destructor_wrapper(void *list_ptr, void *elem) {
const cx_kv_list *kv_list = list_ptr;
// list destructor is already called with proper deref of the elem
if (kv_list->list_destr) {
kv_list->list_destr(elem);
}
if (kv_list->list_destr2) {
kv_list->list_destr2(kv_list->list_destr_data, elem);
}
if (kv_list->map_destr) {
kv_list->map_destr(elem);
}
if (kv_list->map_destr2) {
kv_list->map_destr2(kv_list->map_destr_data, elem);
}
}
static void cx_kv_list_update_destructors(cx_kv_list *list) {
// we copy the destructors to our custom fields and register
// an own destructor function which invokes all these
if (list->list.base.collection.simple_destructor != NULL) {
list->list_destr = list->list.base.collection.simple_destructor;
list->list.base.collection.simple_destructor = NULL;
}
if (list->list.base.collection.advanced_destructor != cx_kv_list_destructor_wrapper) {
list->list_destr2 = list->list.base.collection.advanced_destructor;
list->list_destr_data = list->list.base.collection.destructor_data;
list->list.base.collection.advanced_destructor = cx_kv_list_destructor_wrapper;
list->list.base.collection.destructor_data = list;
}
if (list->map->map_base.base.collection.simple_destructor != NULL) {
list->map_destr = list->map->map_base.base.collection.simple_destructor;
list->map->map_base.base.collection.simple_destructor = NULL;
}
if (list->map->map_base.base.collection.advanced_destructor != NULL) {
list->map_destr2 = list->map->map_base.base.collection.advanced_destructor;
list->map_destr_data = list->map->map_base.base.collection.destructor_data;
list->map->map_base.base.collection.advanced_destructor = NULL;
list->map->map_base.base.collection.destructor_data = NULL;
}
}
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);
}
static void cx_kvl_deallocate(struct cx_list_s *list) {
cx_kv_list *kv_list = (cx_kv_list*)list;
// patch the destructors
cx_kv_list_update_destructors(kv_list);
kv_list->map_methods->deallocate(&kv_list->map->map_base.base);
// then free the list, now the destructors may be called
kv_list->list_methods->deallocate(list);
}
static void *cx_kvl_insert_element(
struct cx_list_s *list,
size_t index,
const void *data
) {
cx_kv_list *kv_list = (cx_kv_list*)list;
return kv_list->list_methods->insert_element(list, index, data);
}
static size_t cx_kvl_insert_array(
struct cx_list_s *list,
size_t index,
const void *data,
size_t n
) {
cx_kv_list *kv_list = (cx_kv_list*)list;
return kv_list->list_methods->insert_array(list, index, data, n);
}
static size_t cx_kvl_insert_sorted(
struct cx_list_s *list,
const void *sorted_data,
size_t n
) {
cx_kv_list *kv_list = (cx_kv_list*)list;
return kv_list->list_methods->insert_sorted(list, sorted_data, n);
}
static size_t cx_kvl_insert_unique(
struct cx_list_s *list,
const void *sorted_data,
size_t n
) {
cx_kv_list *kv_list = (cx_kv_list*)list;
return kv_list->list_methods->insert_unique(list, sorted_data, n);
}
static int cx_kvl_insert_iter(
struct cx_iterator_s *iter,
const void *elem,
int prepend
) {
cx_kv_list *kv_list = iter->src_handle;
return kv_list->list_methods->insert_iter(iter, elem, prepend);
}
static size_t cx_kvl_remove(
struct cx_list_s *list,
size_t index,
size_t num,
void *targetbuf
) {
cx_kv_list *kv_list = (cx_kv_list*)list;
// patch the destructors
// we also have to do that when targetbuf is NULL,
// because we do not want wrong destructors to be called when we remove keys from the map
cx_kv_list_update_destructors(kv_list);
// iterate through the elements first and remove their keys from the map
CxIterator iter = kv_list->list_methods->iterator(list, index, false);
for (size_t i = 0; i < num && cxIteratorValid(iter); i++) {
void *node_data = cxIteratorCurrent(iter);
CxHashKey *key = cx_kv_list_loc_key(kv_list, node_data);
// when the hash is zero, there is no key assigned to that element
if (key->hash != 0) {
kv_list->map_methods->remove(&kv_list->map->map_base.base, *key, NULL);
}
cxIteratorNext(iter);
}
return kv_list->list_methods->remove(list, index, num, targetbuf);
}
static void cx_kvl_clear(struct cx_list_s *list) {
cx_kv_list *kv_list = (cx_kv_list*)list;
// patch the destructors
cx_kv_list_update_destructors(kv_list);
// clear the list
kv_list->list_methods->clear(list);
// then clear the map
kv_list->map_methods->clear(&kv_list->map->map_base.base);
}
static int cx_kvl_swap(
struct cx_list_s *list,
size_t i,
size_t j
) {
cx_kv_list *kv_list = (cx_kv_list*)list;
return kv_list->list_methods->swap(list, i, j);
}
static void *cx_kvl_at(
const struct cx_list_s *list,
size_t index
) {
const cx_kv_list *kv_list = (const cx_kv_list*)list;
return kv_list->list_methods->at(list, index);
}
static size_t cx_kvl_find_remove(
struct cx_list_s *list,
const void *elem,
bool remove
) {
cx_kv_list *kv_list = (cx_kv_list*)list;
// we do not use the original list methods,
// because that would need two passes for removal
// (the first to find the index, the second to get a pointer)
if (list->collection.size == 0) return 0;
size_t index;
cx_linked_list *ll = &kv_list->list;
char *node = cx_linked_list_find(
ll->begin,
ll->loc_next, ll->loc_data,
list->collection.cmpfunc, elem,
&index
);
if (node == NULL) {
return list->collection.size;
}
if (remove) {
cx_kv_list_update_destructors(kv_list);
cx_invoke_advanced_destructor(list, node + ll->loc_data);
cx_linked_list_remove(&ll->begin, &ll->end,
ll->loc_prev, ll->loc_next, node);
CxHashKey *key = cx_kv_list_loc_key(kv_list, node + ll->loc_data);
if (key->hash != 0) {
kv_list->map_methods->remove(&kv_list->map->map_base.base, *key, NULL);
}
list->collection.size--;
cxFree(list->collection.allocator, node);
}
return index;
}
static void cx_kvl_sort(struct cx_list_s *list) {
cx_kv_list *kv_list = (cx_kv_list*)list;
kv_list->list_methods->sort(list);
}
static void cx_kvl_reverse(struct cx_list_s *list) {
cx_kv_list *kv_list = (cx_kv_list*)list;
kv_list->list_methods->reverse(list);
}
static void cx_kvl_list_iter_next(void *it) {
struct cx_iterator_s *iter = it;
if (iter->base.remove) {
// remove the assigned key from the map before calling the actual function
cx_kv_list *kv_list = iter->src_handle;
cx_kv_list_update_destructors(kv_list);
char *node = iter->elem_handle;
CxHashKey *key = cx_kv_list_loc_key(kv_list, node + kv_list->list.loc_data);
if (key->hash != 0) {
kv_list->map_methods->remove(&kv_list->map->map_base.base, *key, NULL);
}
}
// note that we do not clear the remove flag, because the next_impl will do that
iter->base.next_impl(it);
}
static struct cx_iterator_s cx_kvl_iterator(
const struct cx_list_s *list,
size_t index,
bool backward
) {
const cx_kv_list *kv_list = (const cx_kv_list*)list;
struct cx_iterator_s iter = kv_list->list_methods->iterator(list, index, backward);
iter.base.next_impl = iter.base.next;
iter.base.next = cx_kvl_list_iter_next;
return iter;
}
static void cx_kvl_map_deallocate(struct cx_map_s *map) {
cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
kv_list->map_methods->deallocate(map);
kv_list->list_methods->deallocate(&kv_list->list.base);
}
static void cx_kvl_map_clear(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->list_methods->clear(&kv_list->list.base);
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) {
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
// return the node data
return kv_list->list.base.collection.store_pointer ? *(void**)node_data : node_data;
}
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;
if (kv_list->map_methods->remove(map, key, &node_data)) {
return 1;
}
// we cannot just call a list method (because we don't have the index)
// and tbh. we also don't want to (because it's not performant when we
// can have the node ptr directly instead)
// therefore, we re-implement the logic ourselves
// check if the outside caller want's us to return or to destroy the element
if (targetbuf == NULL) {
// patch the destructors and invoke them through the wrapper
cx_kv_list_update_destructors(kv_list);
cx_invoke_advanced_destructor(&kv_list->list.base, node_data);
} else {
// copy the element to the target buffer
memcpy(targetbuf, node_data, kv_list->list.base.collection.elem_size);
}
// calculate the address of the node
void *node_ptr = (char*)node_data - kv_list->list.loc_data;
// unlink the node
cx_linked_list_remove(
&kv_list->list.begin,
&kv_list->list.end,
kv_list->list.loc_prev,
kv_list->list.loc_next,
node_ptr
);
// decrement the list's size
kv_list->list.base.collection.size--;
// deallocate the node
cxFree(kv_list->list.base.collection.allocator, node_ptr);
return 0;
}
static void *cx_kvl_iter_current_entry(const void *it) {
const CxMapIterator *iter = it;
return (void*)&iter->entry;
}
static void *cx_kvl_iter_current_key(const void *it) {
const CxMapEntry *entry = cx_kvl_iter_current_entry(it);
return (void*)entry->key;
}
static void *cx_kvl_iter_current_value(const void *it) {
const CxMapEntry *entry = cx_kvl_iter_current_entry(it);
return entry->value;
}
static void cx_kvl_iter_next(void *it) {
CxMapIterator *iter = it;
cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)iter->map)->list;
// find the next list entry that has a key assigned
CxHashKey *key = NULL;
char *next = iter->elem;
while (true) {
next = *(char**)(next + kv_list->list.loc_next);
if (next == NULL) break;
key = cx_kv_list_loc_key(kv_list, next + kv_list->list.loc_data);
if (key->hash != 0) break;
}
// remove previous element if requested
if (iter->base.remove) {
iter->base.remove = false;
cx_kv_list_update_destructors(kv_list);
char *elem = iter->elem;
char *elem_data = elem + kv_list->list.loc_data;
CxHashKey *elem_key = cx_kv_list_loc_key(kv_list, elem_data);
// key is guaranteed to exist because iterator only iterates over elems with a key
kv_list->map_methods->remove(&kv_list->map->map_base.base, *elem_key, NULL);
cx_invoke_advanced_destructor(&kv_list->list.base, elem_data);
cx_linked_list_remove(
&kv_list->list.begin,
&kv_list->list.end,
kv_list->list.loc_prev,
kv_list->list.loc_next,
elem
);
cxFree(kv_list->list.base.collection.allocator, elem);
kv_list->list.base.collection.size--;
iter->index--;
iter->elem_count--;
}
// advance to the next element, if any
if (next == NULL) {
iter->index = kv_list->list.base.collection.size;
iter->elem = NULL;
iter->entry = (CxMapEntry){NULL, NULL};
return;
}
iter->index++;
iter->elem = next;
iter->entry.key = key;
if (kv_list->list.base.collection.store_pointer) {
iter->entry.value = *(void**)(next + kv_list->list.loc_data);
} else {
iter->entry.value = (void*)(next + kv_list->list.loc_data);
}
}
static bool cx_kvl_iter_valid(const void *it) {
const CxMapIterator *iter = it;
return iter->elem != NULL;
}
CxMapIterator cx_kvl_map_iterator(const CxMap *map, enum cx_map_iterator_type type) {
CxMapIterator iter = {0};
iter.type = type;
iter.map = (CxMap*)map;
// although we iterate over the list, we only report that many elements that have a key in the map
iter.elem_count = map->collection.size;
switch (type) {
case CX_MAP_ITERATOR_PAIRS:
iter.elem_size = sizeof(CxMapEntry);
iter.base.current = cx_kvl_iter_current_entry;
break;
case CX_MAP_ITERATOR_KEYS:
iter.elem_size = sizeof(CxHashKey);
iter.base.current = cx_kvl_iter_current_key;
break;
case CX_MAP_ITERATOR_VALUES:
iter.elem_size = map->collection.elem_size;
iter.base.current = cx_kvl_iter_current_value;
break;
default:
assert(false); // LCOV_EXCL_LINE
}
iter.base.allow_remove = true;
iter.base.next = cx_kvl_iter_next;
iter.base.valid = cx_kvl_iter_valid;
// find the first list entry that has a key assigned
cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
CxHashKey *key = NULL;
char *next = kv_list->list.begin;
while (next != NULL) {
key = cx_kv_list_loc_key(kv_list, next + kv_list->list.loc_data);
if (key->hash != 0) break;
next = *(char**)(next + kv_list->list.loc_next);
}
if (next == NULL) {
iter.elem = NULL;
iter.entry = (CxMapEntry){NULL, NULL};
} else {
iter.elem = next;
iter.entry.key = key;
if (kv_list->list.base.collection.store_pointer) {
iter.entry.value = *(void**)(next + kv_list->list.loc_data);
} else {
iter.entry.value = (void*)(next + kv_list->list.loc_data);
}
}
return iter;
}
static cx_list_class cx_kv_list_class = {
cx_kvl_deallocate,
cx_kvl_insert_element,
cx_kvl_insert_array,
cx_kvl_insert_sorted,
cx_kvl_insert_unique,
cx_kvl_insert_iter,
cx_kvl_remove,
cx_kvl_clear,
cx_kvl_swap,
cx_kvl_at,
cx_kvl_find_remove,
cx_kvl_sort,
NULL,
cx_kvl_reverse,
cx_kvl_iterator,
};
static cx_map_class cx_kv_map_class = {
cx_kvl_map_deallocate,
cx_kvl_map_clear,
cx_kvl_map_put,
cx_kvl_map_get,
cx_kvl_map_remove,
cx_kvl_map_iterator,
};
CxList *cxKvListCreate(
const CxAllocator *allocator,
cx_compare_func comparator,
size_t elem_size
) {
if (allocator == NULL) {
allocator = cxDefaultAllocator;
}
// create a normal linked list and a normal hash map, first
CxList *list = cxLinkedListCreate(allocator, comparator, elem_size);
if (list == NULL) return NULL; // LCOV_EXCL_LINE
cx_linked_list *ll = (cx_linked_list*)list;
ll->extra_data_len = sizeof(CxHashKey);
CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0);
if (map == NULL) { // LCOV_EXCL_START
cxListFree(list);
return NULL;
} // LCOV_EXCL_STOP
// patch the kv-list class with the compare function of the linked list
// this allows cxListCompare() to optimize comparisons between linked lists and kv-list
cx_kv_list_class.compare = list->cl->compare;
// reallocate the map to add memory for the list back-reference
struct cx_kv_list_map_s *kv_map = cxRealloc(allocator, map, sizeof(struct cx_kv_list_map_s));
// reallocate the list to add memory for storing the metadata
cx_kv_list *kv_list = cxRealloc(allocator, list, sizeof(struct cx_kv_list_s));
// if any of the reallocations failed, we bail out
if (kv_map != NULL && kv_list != NULL) {
map = (CxMap*) kv_map;
list = (CxList*) kv_list;
} else { // LCOV_EXCL_START
cxListFree(list);
cxMapFree(map);
return NULL;
} // LCOV_EXCL_STOP
// zero the custom destructor information
memset((char*)kv_list + offsetof(cx_kv_list, list_destr), 0, sizeof(void*)*6);
// combine the list and the map aspect
kv_list->map = kv_map;
kv_map->list = kv_list;
// 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;
}
return list;
}
CxMap *cxKvListCreateAsMap(
const CxAllocator *allocator,
cx_compare_func comparator,
size_t elem_size
) {
CxList *list = cxKvListCreate(allocator, comparator, elem_size);
return list == NULL ? NULL : cxKvListAsMap(list);
}
CxList *cxKvListAsList(CxMap *map) {
return &((struct cx_kv_list_map_s*)map)->list->list.base;
}
CxMap *cxKvListAsMap(CxList *list) {
return &((cx_kv_list*)list)->map->map_base.base;
}
int cx_kv_list_set_key(CxList *list, size_t index, CxHashKey key) {
cx_kv_list *kv_list = (cx_kv_list*)list;
void *node_data = kv_list->list_methods->at(list, index);
if (node_data == NULL) {
return 1;
}
// if the hash has not yet been computed, do it now
if (key.hash == 0) {
cx_hash_murmur(&key);
}
// check if the key is already assigned
void *existing = kv_list->map_methods->get(&kv_list->map->map_base.base, key);
if (existing == node_data) {
return 0; // nothing to do
}
if (existing != NULL) {
// the key is already assigned to another node, we disallow re-assignment
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
}
// write the key to the list's node
CxHashKey *loc_key = cx_kv_list_loc_key(kv_list, node_data);
*loc_key = key;
return 0;
}
int cxKvListRemoveKey(CxList *list, size_t index) {
cx_kv_list *kv_list = (cx_kv_list*)list;
void *node_data = kv_list->list_methods->at(list, index);
if (node_data == NULL) {
return 1;
}
CxHashKey *loc_key = cx_kv_list_loc_key(kv_list, node_data);
if (loc_key->hash == 0) {
return 0;
}
kv_list->map_methods->remove(&kv_list->map->map_base.base, *loc_key, NULL);
// also zero the memory in the list node,
// but don't free the key data (that was done by the map remove)
memset(loc_key, 0, sizeof(CxHashKey));
return 0;
}
const CxHashKey *cxKvListGetKey(CxList *list, size_t index) {
cx_kv_list *kv_list = (cx_kv_list*)list;
void *node_data = kv_list->list_methods->at(list, index);
if (node_data == NULL) {
return NULL;
}
CxHashKey *key = cx_kv_list_loc_key(kv_list, node_data);
if (key->hash == 0) {
return NULL;
}
return key;
}
int cx_kv_list_insert(CxList *list, size_t index, CxHashKey key, void *value) {
// assume we are losing the sorted property
list->collection.sorted = false;
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
// 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);
return 1;
} // LCOV_EXCL_STOP
*map_data = node_data;
// write the key to the node
CxHashKey *loc_key = cx_kv_list_loc_key(kv_list, node_data);
*loc_key = key;
return 0;
}