Mercurial > hg > ucx / changeset

--- a/src/Makefile	Tue Aug 26 21:14:17 2025 +0200
+++ b/src/Makefile	Tue Aug 26 21:55:19 2025 +0200
@@ -111,7 +111,7 @@
 
 $(build_dir)/kv_list$(OBJ_EXT): kv_list.c cx/kv_list.h cx/common.h \
  cx/list.h cx/collection.h cx/allocator.h cx/iterator.h cx/compare.h \
- cx/map.h cx/string.h cx/hash_key.h
+ cx/map.h cx/string.h cx/hash_key.h cx/hash_map.h cx/linked_list.h
 	@echo "Compiling $<"
 	$(CC) -o $@ $(CFLAGS)  -c $<
 

--- 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) {

--- a/tests/Makefile	Tue Aug 26 21:14:17 2025 +0200
+++ b/tests/Makefile	Tue Aug 26 21:55:19 2025 +0200
@@ -31,6 +31,7 @@
 	test_string.c test_buffer.c \
 	test_hash_key.c test_hash_map.c \
 	test_iterator.c test_list.c test_tree.c \
+	test_kv_list.c \
 	test_properties.c test_json.c \
 	test_printf.c test_streams.c \
 	test_mempool.c \
@@ -96,11 +97,20 @@
 	@echo "Compiling $<"
 	$(CC) -o $@ $(CFLAGS) -I../src -c $<
 
+$(TEST_DIR)/test_kv_list$(OBJ_EXT): test_kv_list.c ../src/cx/test.h \
+ ../src/cx/common.h util_allocator.h ../src/cx/allocator.h \
+ ../src/cx/kv_list.h ../src/cx/list.h ../src/cx/collection.h \
+ ../src/cx/allocator.h ../src/cx/iterator.h ../src/cx/compare.h \
+ ../src/cx/map.h ../src/cx/string.h ../src/cx/hash_key.h
+	@echo "Compiling $<"
+	$(CC) -o $@ $(CFLAGS) -I../src -c $<
+
 $(TEST_DIR)/test_list$(OBJ_EXT): test_list.c ../src/cx/test.h \
  ../src/cx/common.h util_allocator.h ../src/cx/allocator.h \
  ../src/cx/compare.h ../src/cx/array_list.h ../src/cx/list.h \
  ../src/cx/collection.h ../src/cx/allocator.h ../src/cx/iterator.h \
- ../src/cx/compare.h ../src/cx/linked_list.h
+ ../src/cx/compare.h ../src/cx/linked_list.h ../src/cx/kv_list.h \
+ ../src/cx/map.h ../src/cx/string.h ../src/cx/hash_key.h
 	@echo "Compiling $<"
 	$(CC) -o $@ $(CFLAGS) -I../src -c $<
 

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/test_kv_list.c	Tue Aug 26 21:55:19 2025 +0200
@@ -0,0 +1,51 @@
+/*
+ * 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/test.h"
+#include "util_allocator.h"
+
+#include "cx/kv_list.h"
+
+CX_TEST(test_kv_list_map_as_list) {
+    CxList *list = cxKvListCreateSimple(sizeof(int));
+    CX_TEST_DO {
+        CxMap *map = cxKvListAsMap(list);
+        CX_TEST_ASSERT(map != NULL);
+        CxList *list_from_map = cxKvListAsList(map);
+        CX_TEST_ASSERT(list_from_map == list);
+    }
+    cxListFree(list);
+}
+
+CxTestSuite *cx_test_suite_kv_list_specifics(void) {
+    CxTestSuite *suite = cx_test_suite_new("kv_list specifics");
+
+    cx_test_register(suite, test_kv_list_map_as_list);
+
+    return suite;
+}

--- a/tests/test_list.c	Tue Aug 26 21:14:17 2025 +0200
+++ b/tests/test_list.c	Tue Aug 26 21:55:19 2025 +0200
@@ -32,6 +32,7 @@
 
 #include "cx/array_list.h"
 #include "cx/linked_list.h"
+#include "cx/kv_list.h"
 
 #include <stdarg.h>
 #include <errno.h>
@@ -1242,6 +1243,12 @@
         CX_TEST_CALL_SUBROUTINE(test_list_verify_##name, list, false); \
     tear_down_combo \
 } \
+CX_TEST(test_list_kvl_##name) { \
+    set_up_combo \
+        CxList *list = cxKvListCreate(alloc, cx_cmp_int, sizeof(int)); \
+        CX_TEST_CALL_SUBROUTINE(test_list_verify_##name, list, false); \
+    tear_down_combo \
+} \
 CX_TEST(test_list_pll_##name) { \
     set_up_combo \
         CxList *list = cxLinkedListCreate(alloc, cx_cmp_int, CX_STORE_POINTERS); \
@@ -1253,6 +1260,12 @@
         CxList *list = cxArrayListCreate(alloc, cx_cmp_int, CX_STORE_POINTERS, 8); \
         CX_TEST_CALL_SUBROUTINE(test_list_verify_##name, list, true); \
     tear_down_combo \
+} \
+CX_TEST(test_list_pkvl_##name) { \
+    set_up_combo \
+        CxList *list = cxKvListCreate(alloc, cx_cmp_int, CX_STORE_POINTERS); \
+        CX_TEST_CALL_SUBROUTINE(test_list_verify_##name, list, true); \
+    tear_down_combo \
 }
 #define roll_out_test_combos(name, body) \
 static CX_TEST_SUBROUTINE(test_list_verify_##name, CxList *list, \
@@ -2326,6 +2339,65 @@
     return suite;
 }
 
+CxTestSuite *cx_test_suite_kv_list(void) {
+    CxTestSuite *suite = cx_test_suite_new("kv_list");
+
+    cx_test_register(suite, test_list_kvl_add);
+    cx_test_register(suite, test_list_pkvl_add);
+    cx_test_register(suite, test_list_kvl_insert);
+    cx_test_register(suite, test_list_pkvl_insert);
+    cx_test_register(suite, test_list_kvl_emplace);
+    cx_test_register(suite, test_list_pkvl_emplace);
+    cx_test_register(suite, test_list_kvl_insert_array);
+    cx_test_register(suite, test_list_pkvl_insert_array);
+    cx_test_register(suite, test_list_kvl_insert_sorted);
+    cx_test_register(suite, test_list_pkvl_insert_sorted);
+    cx_test_register(suite, test_list_kvl_remove);
+    cx_test_register(suite, test_list_pkvl_remove);
+    cx_test_register(suite, test_list_kvl_remove_and_get);
+    cx_test_register(suite, test_list_pkvl_remove_and_get);
+    cx_test_register(suite, test_list_kvl_remove_array);
+    cx_test_register(suite, test_list_pkvl_remove_array);
+    cx_test_register(suite, test_list_kvl_find_remove);
+    cx_test_register(suite, test_list_pkvl_find_remove);
+    cx_test_register(suite, test_list_kvl_find_remove_sorted);
+    cx_test_register(suite, test_list_pkvl_find_remove_sorted);
+    cx_test_register(suite, test_list_kvl_contains);
+    cx_test_register(suite, test_list_pkvl_contains);
+    cx_test_register(suite, test_list_kvl_clear);
+    cx_test_register(suite, test_list_pkvl_clear);
+    cx_test_register(suite, test_list_kvl_at);
+    cx_test_register(suite, test_list_pkvl_at);
+    cx_test_register(suite, test_list_kvl_set);
+    cx_test_register(suite, test_list_pkvl_set);
+    cx_test_register(suite, test_list_kvl_swap);
+    cx_test_register(suite, test_list_pkvl_swap);
+    cx_test_register(suite, test_list_kvl_find);
+    cx_test_register(suite, test_list_pkvl_find);
+    cx_test_register(suite, test_list_kvl_sort);
+    cx_test_register(suite, test_list_pkvl_sort);
+    cx_test_register(suite, test_list_kvl_reverse);
+    cx_test_register(suite, test_list_pkvl_reverse);
+    cx_test_register(suite, test_list_kvl_iterator);
+    cx_test_register(suite, test_list_pkvl_iterator);
+    cx_test_register(suite, test_list_kvl_insert_with_iterator);
+    cx_test_register(suite, test_list_pkvl_insert_with_iterator);
+    cx_test_register(suite, test_list_kvl_compare_ll);
+    cx_test_register(suite, test_list_kvl_compare_arl);
+    cx_test_register(suite, test_list_kvl_compare_pll);
+    cx_test_register(suite, test_list_kvl_compare_parl);
+    cx_test_register(suite, test_list_pkvl_compare_ll);
+    cx_test_register(suite, test_list_pkvl_compare_arl);
+    cx_test_register(suite, test_list_pkvl_compare_pll);
+    cx_test_register(suite, test_list_pkvl_compare_parl);
+    cx_test_register(suite, test_list_kvl_simple_destr);
+    cx_test_register(suite, test_list_pkvl_simple_destr);
+    cx_test_register(suite, test_list_kvl_advanced_destr);
+    cx_test_register(suite, test_list_pkvl_advanced_destr);
+
+    return suite;
+}
+
 CxTestSuite *cx_test_suite_empty_list(void) {
     CxTestSuite *suite = cx_test_suite_new("empty list dummy");
 

--- a/tests/ucxtest.c	Tue Aug 26 21:14:17 2025 +0200
+++ b/tests/ucxtest.c	Tue Aug 26 21:55:19 2025 +0200
@@ -46,6 +46,7 @@
 CxTestSuite *cx_test_suite_array_list_defaulted_funcs(void);
 CxTestSuite *cx_test_suite_linked_list(void);
 CxTestSuite *cx_test_suite_linked_list_defaulted_funcs(void);
+CxTestSuite *cx_test_suite_kv_list(void);
 CxTestSuite *cx_test_suite_tree_low_level(void);
 CxTestSuite *cx_test_suite_tree_high_level(void);
 CxTestSuite *cx_test_suite_properties(void);
@@ -97,6 +98,7 @@
             cx_test_suite_array_list_defaulted_funcs(),
             cx_test_suite_linked_list(),
             cx_test_suite_linked_list_defaulted_funcs(),
+            cx_test_suite_kv_list(),
             cx_test_suite_tree_low_level(),
             cx_test_suite_tree_high_level(),
             cx_test_suite_properties(),