--- a/src/kv_list.c Tue Aug 26 21:14:17 2025 +0200
+++ b/src/kv_list.c Tue Aug 26 21:55:19 2025 +0200
@@ -27,13 +27,219 @@
*/
#include "cx/kv_list.h"
+#include "cx/hash_map.h"
+#include "cx/linked_list.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;
+};
+
+/** The list aspect (must have the same layout as the normal linked list). */
+struct cx_kv_list_list_s {
+ struct cx_list_s list_base;
+ void *begin;
+ void *end;
+};
+
+struct cx_kv_list_s {
+ struct cx_kv_list_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;
+};
+
+static void cx_kvl_deallocate(struct cx_list_s *list) {
+ cx_kv_list *kv_list = (cx_kv_list*)list;
+ // free the map first
+ kv_list->map_methods->deallocate(&kv_list->map->map_base.base);
+ 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;
+ // TODO: trick the base method by adding the required space for the key to the elem_size
+ 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;
+ // TODO: trick the base method by adding the required space for the key to the elem_size
+ 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;
+ // TODO: trick the base method by adding the required space for the key to the elem_size
+ return kv_list->list_methods->insert_sorted(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 = (cx_kv_list*)iter->src_handle.m;
+ // TODO: trick the base method by adding the required space for the key to the elem_size
+ 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;
+ // TODO: always use the target buffer to get the element first,
+ // then obtain the key, remove it from the map,
+ // and finally call any destructors manually
+ 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;
+ kv_list->list_methods->clear(list);
+ // also clear all lookup entries
+ cxMapClear(&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;
+ // TODO: implement removal of the key in the map
+ return kv_list->list_methods->find_remove(list, elem, remove);
+}
+
+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 int cx_kvl_compare(
+ const struct cx_list_s *list,
+ const struct cx_list_s *other
+) {
+ // TODO: make it so that comparison with normal linked lists is also optimized
+ const cx_kv_list *kv_list = (const cx_kv_list*)list;
+ return kv_list->list_methods->compare(list, other);
+}
+
+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 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;
+ // TODO: cannot really forward, because mutating iterators must be able to remove the element
+ return kv_list->list_methods->iterator(list, index, backward);
+}
+
+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_iter,
+ cx_kvl_remove,
+ cx_kvl_clear,
+ cx_kvl_swap,
+ cx_kvl_at,
+ cx_kvl_find_remove,
+ cx_kvl_sort,
+ cx_kvl_compare,
+ cx_kvl_reverse,
+ cx_kvl_iterator,
+};
CxList *cxKvListCreate(
const CxAllocator *allocator,
cx_compare_func comparator,
size_t elem_size
) {
- return NULL;
+ 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
+ CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0);
+ if (map == NULL) { // LCOV_EXCL_START
+ cxListFree(list);
+ return NULL;
+ } // LCOV_EXCL_STOP
+
+ // 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(cx_kv_list));
+
+ // 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
+
+ // 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->list_methods = list->cl;
+ kv_list->map_methods = map->cl;
+ list->cl = &cx_kv_list_class;
+ // TODO: override all map members
+ // and remember to set the sorted flag of the list to false in the put/emplace methods!
+
+ return list;
}
CxMap *cxKvListCreateAsMap(
@@ -46,11 +252,11 @@
}
CxList *cxKvListAsList(CxMap *map) {
- return NULL;
+ return &((struct cx_kv_list_map_s*)map)->list->list.list_base;
}
CxMap *cxKvListAsMap(CxList *list) {
- return NULL;
+ return &((cx_kv_list*)list)->map->map_base.base;
}
int cx_kv_list_set_key(CxList *list, size_t index, CxHashKey key) {