1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 *
4 * Copyright 2025 Mike Becker, Olaf Wintermann All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28 /**
29 * @file kv_list.h
30 * @brief Linked list implementation with key/value-lookup.
31 * @author Mike Becker
32 * @author Olaf Wintermann
33 * @copyright 2-Clause BSD License
34 */
35
36 #ifndef UCX_KV_LIST_H
37 #define UCX_KV_LIST_H
38
39 #include "common.h"
40 #include "list.h"
41 #include "map.h"
42
43 #ifdef __cplusplus
44 extern "C" {
45 #endif
46
47 /**
48 * Allocates a linked list with a lookup-map for storing elements with @p elem_size bytes each.
49 *
50 * If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of
51 * copies of the added elements, and the compare function will be automatically set
52 * to cx_cmp_ptr() if none is given.
53 *
54 * After creating the list, it can also be used as a map after converting the pointer
55 * to a CxMap pointer with cxKvListAsMap().
56 * When you want to use the list interface again, you can also convert the map pointer back
57 * with cxKvListAsList().
58 *
59 * @param allocator the allocator for allocating the list nodes
60 * (if @c NULL, the cxDefaultAllocator will be used)
61 * @param comparator the comparator for the elements
62 * (if @c NULL, and the list is not storing pointers, sort and find
63 * functions will not work)
64 * @param elem_size the size of each element in bytes
65 * @return the created list
66 * @see cxKvListAsMap()
67 * @see cxKvListAsList()
68 */
69 cx_attr_nodiscard cx_attr_malloc cx_attr_dealloc(cxListFree, 1)
70 CX_EXPORT CxList *cxKvListCreate(const CxAllocator *allocator,
71 cx_compare_func comparator, size_t elem_size);
72
73 /**
74 * Allocates a linked list with a lookup-map for storing elements with @p elem_size bytes each.
75 *
76 * If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of
77 * copies of the added elements, and the compare function will be automatically set
78 * to cx_cmp_ptr() if none is given.
79 *
80 * This function creates the list with cxKvListCreate() and immediately applies
81 * cxKvListAsMap(). If you want to use the returned object as a list, you can call
82 * cxKvListAsList() later.
83 *
84 * @param allocator the allocator for allocating the list nodes
85 * (if @c NULL, the cxDefaultAllocator will be used)
86 * @param comparator the comparator for the elements
87 * (if @c NULL, and the list is not storing pointers, sort and find
88 * functions will not work)
89 * @param elem_size the size of each element in bytes
90 * @return the created list wrapped into the CxMap interface
91 * @see cxKvListAsMap()
92 * @see cxKvListAsList()
93 */
94 cx_attr_nodiscard cx_attr_malloc cx_attr_dealloc(cxMapFree, 1)
95 CX_EXPORT CxMap *cxKvListCreateAsMap(const CxAllocator *allocator,
96 cx_compare_func comparator, size_t elem_size);
97
98 /**
99 * Allocates a linked list with a lookup-map for storing elements with @p elem_size bytes each.
100 *
101 * The list will use cxDefaultAllocator and no comparator function. If you want
102 * to call functions that need a comparator, you must either set one immediately
103 * after list creation or use cxKvListCreate().
104 *
105 * If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of
106 * copies of the added elements, and the compare function will be automatically set
107 * to cx_cmp_ptr().
108 *
109 * After creating the list, it can also be used as a map after converting the pointer
110 * to a CxMap pointer with cxKvListAsMap().
111 * When you want to use the list interface again, you can also convert the map pointer back
112 * with cxKvListAsList().
113 *
114 * @param elem_size (@c size_t) the size of each element in bytes
115 * @return (@c CxList*) the created list
116 * @see cxKvListAsMap()
117 * @see cxKvListAsList()
118 */
119 #define cxKvListCreateSimple(elem_size) cxKvListCreate(NULL, NULL, elem_size)
120
121 /**
122 * Allocates a linked list with a lookup-map for storing elements with @p elem_size bytes each.
123 *
124 * The list will use cxDefaultAllocator and no comparator function. If you want
125 * to call functions that need a comparator, you must either set one immediately
126 * after list creation or use cxKvListCreate().
127 *
128 * If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of
129 * copies of the added elements, and the compare function will be automatically set
130 * to cx_cmp_ptr().
131 *
132 * This macro behaves as if the list was created with cxKvListCreateSimple() and
133 * immediately followed up by cxKvListAsMap().
134 * If you want to use the returned object as a list, you can call cxKvListAsList() later.
135 *
136 * @param elem_size (@c size_t) the size of each element in bytes
137 * @return (@c CxMap*) the created list wrapped into the CxMap interface
138 * @see cxKvListAsMap()
139 * @see cxKvListAsList()
140 */
141 #define cxKvListCreateAsMapSimple(elem_size) cxKvListCreateAsMap(NULL, NULL, elem_size)
142
143 /**
144 * Converts a map pointer belonging to a key-value-List back to the original list pointer.
145 *
146 * @param map a map pointer that was returned by a call to cxKvListAsMap()
147 * @return the original list pointer
148 */
149 cx_attr_nodiscard cx_attr_nonnull cx_attr_returns_nonnull
150 CX_EXPORT CxList *cxKvListAsList(CxMap *map);
151
152 /**
153 * Converts a map pointer belonging to a key-value-List back to the original list pointer.
154 *
155 * @param list a list created by cxKvListCreate() or cxKvListCreateSimple()
156 * @return a map pointer that lets you use the list as if it was a map
157 */
158 cx_attr_nodiscard cx_attr_nonnull cx_attr_returns_nonnull
159 CX_EXPORT CxMap *cxKvListAsMap(CxList *list);
160
161 /**
162 * Sets or updates the key of a list item.
163 *
164 * This is, for example, useful when you have inserted an element using the CxList interface,
165 * and now you want to associate this element with a key.
166 *
167 * @param list the list
168 * @param index the index of the element in the list
169 * @param key the key
170 * @retval zero success
171 * @retval non-zero memory allocation failure or the index is out of bounds
172 * @see cxKvListSetKey()
173 */
174 cx_attr_nonnull
175 CX_EXPORT int cx_kv_list_set_key(CxList *list, size_t index, CxHashKey key);
176
177 /**
178 * Inserts an item into the list at the specified index and associates it with the specified key.
179 *
180 * @param list the list
181 * @param index the index the inserted element shall have
182 * @param key the key
183 * @param value the value
184 * @retval zero success
185 * @retval non-zero memory allocation failure or the index is out of bounds
186 * @see cxKvListInsert()
187 */
188 cx_attr_nonnull
189 CX_EXPORT int cx_kv_list_insert(CxList *list, size_t index, CxHashKey key, void *value);
190
191 /**
192 * Sets or updates the key of a list item.
193 *
194 * This is, for example, useful when you have inserted an element using the CxList interface,
195 * and now you want to associate this element with a key.
196 *
197 * @param list (@c CxList*) the list
198 * @param index (@c size_t) the index of the element in the list
199 * @param key (any supported key type) the key
200 * @retval zero success
201 * @retval non-zero memory allocation failure or the index is out of bounds
202 * @see CX_HASH_KEY()
203 */
204 #define cxKvListSetKey(list, index, key) cx_kv_list_set_key(list, index, CX_HASH_KEY(key))
205
206 /**
207 * Inserts an item into the list at the specified index and associates it with the specified key.
208 *
209 * @param list (@c CxList*) the list
210 * @param index (@c size_t) the index the inserted element shall have
211 * @param key (any supported key type) the key
212 * @param value (@c void*) the value
213 * @retval zero success
214 * @retval non-zero memory allocation failure or the index is out of bounds
215 * @see CX_HASH_KEY()
216 */
217 #define cxKvListInsert(list, index, key, value) cx_kv_list_insert(list, index, CX_HASH_KEY(key), value)
218
219
220 /**
221 * Removes the key of a list item.
222 *
223 * This can be useful if you want to explicitly remove an item from the lookup map.
224 *
225 * If no key is associated with the item, nothing happens, and this function returns zero.
226 *
227 * @param list the list
228 * @param index the index of the element in the list
229 * @retval zero success
230 * @retval non-zero the index is out of bounds
231 */
232 cx_attr_nonnull
233 CX_EXPORT int cxKvListRemoveKey(CxList *list, size_t index);
234
235 /**
236 * Returns the key of a list item.
237 *
238 * @param list the list
239 * @param index the index of the element in the list
240 * @return a pointer to the key or @c NULL when the index is out of bounds or the item does not have a key
241 */
242 cx_attr_nonnull
243 CX_EXPORT const CxHashKey *cxKvListGetKey(CxList *list, size_t index);
244
245 /**
246 * Adds an item into the list and associates it with the specified key.
247 *
248 * @param list (@c CxList*) the list
249 * @param key (@c CxHashKey, @c char*, @c cxstring, or @c cxmutstr) the key
250 * @param value (@c void*) the value
251 * @retval zero success
252 * @retval non-zero memory allocation failure
253 */
254 #define cxKvListAdd(list, key, value) cxKvListInsert(list, (list)->collection.size, key, value)
255
256 #ifdef __cplusplus
257 } // extern "C"
258 #endif
259
260 #endif // UCX_KV_LIST_H
261