Mercurial > hg > webserver / changeset

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/ucx/cx/kv_list.h	Mon Nov 10 21:06:55 2025 +0100
@@ -0,0 +1,260 @@
+/*
+ * 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.
+ */
+/**
+ * @file kv_list.h
+ * @brief Linked list implementation with key/value-lookup.
+ * @author Mike Becker
+ * @author Olaf Wintermann
+ * @copyright 2-Clause BSD License
+ */
+
+#ifndef UCX_KV_LIST_H
+#define UCX_KV_LIST_H
+
+#include "common.h"
+#include "list.h"
+#include "map.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/**
+ * Allocates a linked list with a lookup-map for storing elements with @p elem_size bytes each.
+ *
+ * If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of
+ * copies of the added elements, and the compare function will be automatically set
+ * to cx_cmp_ptr() if none is given.
+ *
+ * After creating the list, it can also be used as a map after converting the pointer
+ * to a CxMap pointer with cxKvListAsMap().
+ * When you want to use the list interface again, you can also convert the map pointer back
+ * with cxKvListAsList().
+ *
+ * @param allocator the allocator for allocating the list nodes
+ * (if @c NULL, the cxDefaultAllocator will be used)
+ * @param comparator the comparator for the elements
+ * (if @c NULL, and the list is not storing pointers, sort and find
+ * functions will not work)
+ * @param elem_size the size of each element in bytes
+ * @return the created list
+ * @see cxKvListAsMap()
+ * @see cxKvListAsList()
+ */
+cx_attr_nodiscard cx_attr_malloc cx_attr_dealloc(cxListFree, 1)
+CX_EXPORT CxList *cxKvListCreate(const CxAllocator *allocator,
+        cx_compare_func comparator, size_t elem_size);
+
+/**
+ * Allocates a linked list with a lookup-map for storing elements with @p elem_size bytes each.
+ *
+ * If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of
+ * copies of the added elements, and the compare function will be automatically set
+ * to cx_cmp_ptr() if none is given.
+ *
+ * This function creates the list with cxKvListCreate() and immediately applies
+ * cxKvListAsMap(). If you want to use the returned object as a list, you can call
+ * cxKvListAsList() later.
+ *
+ * @param allocator the allocator for allocating the list nodes
+ * (if @c NULL, the cxDefaultAllocator will be used)
+ * @param comparator the comparator for the elements
+ * (if @c NULL, and the list is not storing pointers, sort and find
+ * functions will not work)
+ * @param elem_size the size of each element in bytes
+ * @return the created list wrapped into the CxMap interface
+ * @see cxKvListAsMap()
+ * @see cxKvListAsList()
+ */
+cx_attr_nodiscard cx_attr_malloc cx_attr_dealloc(cxMapFree, 1)
+CX_EXPORT CxMap *cxKvListCreateAsMap(const CxAllocator *allocator,
+        cx_compare_func comparator, size_t elem_size);
+
+/**
+ * Allocates a linked list with a lookup-map for storing elements with @p elem_size bytes each.
+ *
+ * The list will use cxDefaultAllocator and no comparator function. If you want
+ * to call functions that need a comparator, you must either set one immediately
+ * after list creation or use cxKvListCreate().
+ *
+ * If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of
+ * copies of the added elements, and the compare function will be automatically set
+ * to cx_cmp_ptr().
+ *
+ * After creating the list, it can also be used as a map after converting the pointer
+ * to a CxMap pointer with cxKvListAsMap().
+ * When you want to use the list interface again, you can also convert the map pointer back
+ * with cxKvListAsList().
+ *
+ * @param elem_size (@c size_t) the size of each element in bytes
+ * @return (@c CxList*) the created list
+ * @see cxKvListAsMap()
+ * @see cxKvListAsList()
+ */
+#define cxKvListCreateSimple(elem_size) cxKvListCreate(NULL, NULL, elem_size)
+
+/**
+ * Allocates a linked list with a lookup-map for storing elements with @p elem_size bytes each.
+ *
+ * The list will use cxDefaultAllocator and no comparator function. If you want
+ * to call functions that need a comparator, you must either set one immediately
+ * after list creation or use cxKvListCreate().
+ *
+ * If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of
+ * copies of the added elements, and the compare function will be automatically set
+ * to cx_cmp_ptr().
+ *
+ * This macro behaves as if the list was created with cxKvListCreateSimple() and
+ * immediately followed up by cxKvListAsMap().
+ * If you want to use the returned object as a list, you can call cxKvListAsList() later.
+ *
+ * @param elem_size (@c size_t) the size of each element in bytes
+ * @return (@c CxMap*) the created list wrapped into the CxMap interface
+ * @see cxKvListAsMap()
+ * @see cxKvListAsList()
+ */
+#define cxKvListCreateAsMapSimple(elem_size) cxKvListCreateAsMap(NULL, NULL, elem_size)
+
+/**
+ * Converts a map pointer belonging to a key-value-List back to the original list pointer.
+ *
+ * @param map a map pointer that was returned by a call to cxKvListAsMap()
+ * @return the original list pointer
+ */
+cx_attr_nodiscard cx_attr_nonnull cx_attr_returns_nonnull
+CX_EXPORT CxList *cxKvListAsList(CxMap *map);
+
+/**
+ * Converts a map pointer belonging to a key-value-List back to the original list pointer.
+ *
+ * @param list a list created by cxKvListCreate() or cxKvListCreateSimple()
+ * @return a map pointer that lets you use the list as if it was a map
+ */
+cx_attr_nodiscard cx_attr_nonnull cx_attr_returns_nonnull
+CX_EXPORT CxMap *cxKvListAsMap(CxList *list);
+
+/**
+ * Sets or updates the key of a list item.
+ *
+ * This is, for example, useful when you have inserted an element using the CxList interface,
+ * and now you want to associate this element with a key.
+ *
+ * @param list the list
+ * @param index the index of the element in the list
+ * @param key the key
+ * @retval zero success
+ * @retval non-zero memory allocation failure or the index is out of bounds
+ * @see cxKvListSetKey()
+ */
+cx_attr_nonnull
+CX_EXPORT int cx_kv_list_set_key(CxList *list, size_t index, CxHashKey key);
+
+/**
+ * Inserts an item into the list at the specified index and associates it with the specified key.
+ *
+ * @param list the list
+ * @param index the index the inserted element shall have
+ * @param key the key
+ * @param value the value
+ * @retval zero success
+ * @retval non-zero memory allocation failure or the index is out of bounds
+ * @see cxKvListInsert()
+ */
+cx_attr_nonnull
+CX_EXPORT int cx_kv_list_insert(CxList *list, size_t index, CxHashKey key, void *value);
+
+/**
+ * Sets or updates the key of a list item.
+ *
+ * This is, for example, useful when you have inserted an element using the CxList interface,
+ * and now you want to associate this element with a key.
+ *
+ * @param list (@c CxList*) the list
+ * @param index (@c size_t) the index of the element in the list
+ * @param key (any supported key type) the key
+ * @retval zero success
+ * @retval non-zero memory allocation failure or the index is out of bounds
+ * @see CX_HASH_KEY()
+ */
+#define cxKvListSetKey(list, index, key) cx_kv_list_set_key(list, index, CX_HASH_KEY(key))
+
+/**
+ * Inserts an item into the list at the specified index and associates it with the specified key.
+ *
+ * @param list (@c CxList*) the list
+ * @param index (@c size_t) the index the inserted element shall have
+ * @param key (any supported key type) the key
+ * @param value (@c void*) the value
+ * @retval zero success
+ * @retval non-zero memory allocation failure or the index is out of bounds
+ * @see CX_HASH_KEY()
+ */
+#define cxKvListInsert(list, index, key, value) cx_kv_list_insert(list, index, CX_HASH_KEY(key), value)
+
+
+/**
+ * Removes the key of a list item.
+ *
+ * This can be useful if you want to explicitly remove an item from the lookup map.
+ *
+ * If no key is associated with the item, nothing happens, and this function returns zero.
+ *
+ * @param list the list
+ * @param index the index of the element in the list
+ * @retval zero success
+ * @retval non-zero the index is out of bounds
+ */
+cx_attr_nonnull
+CX_EXPORT int cxKvListRemoveKey(CxList *list, size_t index);
+
+/**
+ * Returns the key of a list item.
+ *
+ * @param list the list
+ * @param index the index of the element in the list
+ * @return a pointer to the key or @c NULL when the index is out of bounds or the item does not have a key
+ */
+cx_attr_nonnull
+CX_EXPORT const CxHashKey *cxKvListGetKey(CxList *list, size_t index);
+
+/**
+ * Adds an item into the list and associates it with the specified key.
+ *
+ * @param list (@c CxList*) the list
+ * @param key (@c CxHashKey, @c char*, @c cxstring, or @c cxmutstr) the key
+ * @param value (@c void*) the value
+ * @retval zero success
+ * @retval non-zero memory allocation failure
+ */
+#define cxKvListAdd(list, key, value) cxKvListInsert(list, (list)->collection.size, key, value)
+
+#ifdef __cplusplus
+} // extern "C"
+#endif
+
+#endif // UCX_KV_LIST_H

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/ucx/kv_list.c	Mon Nov 10 21:06:55 2025 +0100
@@ -0,0 +1,705 @@
+/*
+ * 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;
+}