kv-list: add documentation

Wed, 24 Sep 2025 23:50:15 +0200

author
Mike Becker <universe@uap-core.de>
date
Wed, 24 Sep 2025 23:50:15 +0200
changeset 1390
ff077f793c5d
parent 1389
bbdc4aee8534
child 1391
4ec83232975f

kv-list: add documentation

relates to #461

docs/Writerside/topics/about.md file | annotate | diff | comparison | revisions
docs/Writerside/topics/array_list.h.md file | annotate | diff | comparison | revisions
docs/Writerside/topics/collections.md file | annotate | diff | comparison | revisions
docs/Writerside/topics/kv_list.h.md file | annotate | diff | comparison | revisions
docs/Writerside/topics/linked_list.h.md file | annotate | diff | comparison | revisions
docs/Writerside/topics/map.h.md file | annotate | diff | comparison | revisions
docs/Writerside/ucx.tree file | annotate | diff | comparison | revisions
--- a/docs/Writerside/topics/about.md	Tue Sep 23 20:31:50 2025 +0200
+++ b/docs/Writerside/topics/about.md	Wed Sep 24 23:50:15 2025 +0200
@@ -30,16 +30,18 @@
 
 * adds cxMempoolTransfer() and cxMempoolTransferObject()
 * adds support for different destruction strategies in CxMempool
+* adds new key-value-based list implementation
 * adds cxListSet()
 * adds cxListContains()
 * adds cxListFirst() and cxListLast()
 * adds cxListRemoveAndGetFirst() and cxListRemoveAndGetLast(),
   and corresponding macro aliases cxListPopFront() and cxListPop()
-* adds cxListEmplace() and cxListEmplaceAt()
+* adds cxListEmplace(), cxListEmplaceAt(), and cxMapEmplace()
 * adds cxBufferShrink()
 * adds cxTreeSize()
 * adds CX_PRIstr and CX_SFMT macros for formatting UCX strings
 * adds cx_strcpy() and cx_strcpy_a()
+* adds cxJsonArrRemove() and cxJsonObjRemove()
 * adds cxStdlibAllocator and allows changes of cxDefaultAllocator
 * improves performance of the CxList array list implementation
 * changes cx_str() and cx_mutstr() to allow NULL strings
@@ -47,11 +49,12 @@
 * changes grow strategy for the memory pool to reduce reallocations
 * changes grow strategy for CxBuffer, which does now take the page size into account
 * changes the implementation of cx_strreplacen() for improved efficiency
-* changes all cxListIterator() without index to also accept NULL as list argument
+* changes all cxListIterator() and cxMapIterator() family of functions to also accept NULL as argument
 * changes insert_element member function of CxList to accept NULL source and return a pointer to the inserted element
 * fixes critical memory overflow in the stack-based array reallocator (this unfortunately breaks the function signature)
 * fixes mempool implementation not supporting NULL as argument for realloc
 * fixes mempool implementation not supporting zero as size for realloc
+* fixes that the elem_count member of an iterator was not updated after removing an element flagged by cxIteratorFlagRemoval()
 * fixes that starting an iteration in a non-root node incorrectly continues iteration with the siblings of that node
 * fixes unnecessary allocations in cx_strcat() family of functions
 * fixes errno value after failing cxBufferSeek() to be consistently EINVAL
--- a/docs/Writerside/topics/array_list.h.md	Tue Sep 23 20:31:50 2025 +0200
+++ b/docs/Writerside/topics/array_list.h.md	Wed Sep 24 23:50:15 2025 +0200
@@ -3,7 +3,7 @@
 Next to an array list implementation of the list interface,
 UCX offers several functions to work with plain C arrays equipped with a size and a capacity.
 
-The high level [list interface](list.h.md) is documented on a separate page and explains how lists are used
+The high-level [list interface](list.h.md) is documented on a separate page and explains how lists are used
 that are created by one of the following functions.
 
 ```C
--- a/docs/Writerside/topics/collections.md	Tue Sep 23 20:31:50 2025 +0200
+++ b/docs/Writerside/topics/collections.md	Wed Sep 24 23:50:15 2025 +0200
@@ -3,10 +3,12 @@
 UCX provides a [linked list](linked_list.h.md) and [array list](array_list.h.md) implementation over a common [list](list.h.md) interface,
 as well as a [hash nap](hash_map.h.md) implementation over a [map](map.h.md) interface, and a basic [tree](tree.h.md) implementation.
 
+Another special collection is the [key/value-list](kv_list.h.md) that combines both the list and the map interfaces.
+
 Additionally, UCX provides an abstraction for [iterators](iterator.h.md) that work with all collection types, and
 plain C arrays.
 
-The design goal of this API was to provide high level abstractions (functions in lowerCamelCase) and low level
+The design goal of this API was to provide high-level abstractions (functions in lowerCamelCase) and low-level 
 implementations (functions in snake_case).
-This way you can freely choose whether to use the predefined implementations for the various collection types,
-or to implement your own collections using the low level API.
+This way you can freely choose whether to use the predefined implementations for the various collection types
+or to implement your own collections using the low-level API.
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/docs/Writerside/topics/kv_list.h.md	Wed Sep 24 23:50:15 2025 +0200
@@ -0,0 +1,81 @@
+# Key/Value List
+
+The key/value list is a linked list of key/value pairs.
+It implements both the `CxList` and `CxMap` interfaces.
+
+```C
+#include <cx/kv_list.h>
+
+CxList *cxKvListCreate(const CxAllocator *allocator,
+        cx_compare_func comparator, size_t elem_size);
+        
+CxList *cxKvListCreateSimple(size_t elem_size);
+
+CxMap *cxKvListCreateAsMap(const CxAllocator *allocator,
+        cx_compare_func comparator, size_t elem_size);
+        
+CxMap *cxKvListCreateAsMapSimple(size_t elem_size);
+```
+
+The lists are created as usual linked lists with an additional map to look up items by key.
+The map is created with the same allocator as the list.
+You can use either interface to access the list.
+Also, defining destructors on either interface will work as if you defined them on the list.
+Using the list interface to insert items will insert them without an assigned key,
+but you can always set a key later using the `cxKvListSetKey()` function (see [](#special-functions) below).
+
+> The special thing about key/value lists when used with the map interface is,
+> that when you iterate over the map, the elements are returned in the order they appear in the list.
+> In contrast, a normal hash map will return the elements in arbitrary order.
+> This way you can use a key/value list as an ordered map.
+> {style="note"}
+
+## Converting between the Interfaces
+
+To easily convert between the `CxList` and `CxMap` interfaces, we provide the following functions.
+
+```C
+#include <cx/kv_list.h>
+
+CxMap *cxKvListAsMap(CxList *list);
+
+CxList *cxKvListAsList(CxMap *map);
+```
+
+They must only be used on lists that have been created as key/value lists.
+Using them with other lists will result in undefined behavior.
+
+## Special Functions
+
+The key/value list has some special functions that are not part of the `CxList` or `CxMap` interface.
+They also may only be used with lists that have been created as key/value lists.
+Using them with other lists will result in undefined behavior.
+
+```C
+#include <cx/kv_list.h>
+
+int cxKvListSetKey(CxList *list, size_t index, KeyType key);
+
+int cxKvListRemoveKey(CxList *list, size_t index);
+
+int cxKvListAdd(CxList *list, KeyType key, void *value);
+
+int cxKvListInsert(CxList *list, size_t index,
+        KeyType key, void *value);
+```
+
+> All functions working with keys are implemented as generics, so that the following types are supported:
+> `CxHashKey`, `cxstring`, `cxmutstr`, `const char*`, and `char*`.
+> When we write `KeyType`, we mean any of these types.
+> {style="note"}
+
+The `cxKvListSetKey()` and `cxKvListRemoveKey()` functions are used to set or remove the key of an element.
+They return zero on success and non-zero on failure.
+A failure can happen when the index is out of bounds or when a memory allocation failed.
+The `cxKvListSetKey()` function also returns non-zero if the key already exists for _another_ element.
+
+With the `cxKvListAdd()` and `cxKvListInsert()` functions, you can add a new element to the list and immediately assign a key to it.
+The `cxKvListAdd()` function will add the element at the end of the list,
+while the `cxKvListInsert()` function will insert the element at the specified index.
+
+> The effect of `cxKvListAdd()` using the list interface and `cxMapPut()` using the map interface is the same.
--- a/docs/Writerside/topics/linked_list.h.md	Tue Sep 23 20:31:50 2025 +0200
+++ b/docs/Writerside/topics/linked_list.h.md	Wed Sep 24 23:50:15 2025 +0200
@@ -3,7 +3,7 @@
 On top of implementing the list interface, this header also defines several low-level functions that
 work with arbitrary structures.
 
-The high level [list interface](list.h.md) is documented on a separate page and explains how lists are used
+The high-level [list interface](list.h.md) is documented on a separate page and explains how lists are used
 that are created by one of the following functions.
 
 ```C
--- a/docs/Writerside/topics/map.h.md	Tue Sep 23 20:31:50 2025 +0200
+++ b/docs/Writerside/topics/map.h.md	Wed Sep 24 23:50:15 2025 +0200
@@ -29,9 +29,9 @@
 > This allows you to write clean code without checking for `NULL`-pointer everywhere.
 > You still need to make sure that the placeholder is replaced with an actual map before inserting elements.
 
-> In the Sections below, the type for the key is denoted `KeyType`.
-> All functions are implemented as generics, so that the following types are supported:
+> All functions working with keys are implemented as generics, so that the following types are supported:
 > `CxHashKey`, `cxstring`, `cxmutstr`, `const char*`, and `char*`.
+> When we write `KeyType`, we mean any of these types.
 > {style="note"}
 
 ## Examples
--- a/docs/Writerside/ucx.tree	Tue Sep 23 20:31:50 2025 +0200
+++ b/docs/Writerside/ucx.tree	Wed Sep 24 23:50:15 2025 +0200
@@ -17,6 +17,7 @@
             <toc-element topic="list.h.md"/>
             <toc-element topic="array_list.h.md"/>
             <toc-element topic="linked_list.h.md"/>
+            <toc-element topic="kv_list.h.md"/>
             <toc-element topic="map.h.md"/>
             <toc-element topic="hash_map.h.md"/>
             <toc-element topic="tree.h.md"/>

mercurial