Mercurial > hg > dav / file comparison

comparison: ucx/cx/linked_list.h

ucx/cx/linked_list.h

changeset 888
af685cc9d623
parent 854
1c8401ece69e
equal deleted inserted replaced
877:b60487c3ec36 888:af685cc9d623
42 #ifdef __cplusplus 42 #ifdef __cplusplus
43 extern "C" { 43 extern "C" {
44 #endif 44 #endif
45 45
46 /** 46 /**
47 * Metadata for a linked list.
48 */
49 typedef struct cx_linked_list_s {
50 /** Base members. */
51 struct cx_list_s base;
52 /**
53 * Location of the prev pointer (mandatory).
54 */
55 off_t loc_prev;
56 /**
57 * Location of the next pointer (mandatory).
58 */
59 off_t loc_next;
60 /**
61 * Location of the payload (mandatory).
62 */
63 off_t loc_data;
64 /**
65 * Additional bytes to allocate @em behind the payload (e.g. for metadata).
66 */
67 size_t extra_data_len;
68 /**
69 * Pointer to the first node.
70 */
71 void *begin;
72 /**
73 * Pointer to the last node.
74 */
75 void *end;
76 } cx_linked_list;
77
78 /**
47 * Allocates a linked list for storing elements with @p elem_size bytes each. 79 * Allocates a linked list for storing elements with @p elem_size bytes each.
48 * 80 *
49 * If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of 81 * If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of
50 * copies of the added elements and the compare function will be automatically set 82 * copies of the added elements, and the compare function will be automatically set
51 * to cx_cmp_ptr(), if none is given. 83 * to cx_cmp_ptr() if none is given.
52 * 84 *
53 * @param allocator the allocator for allocating the list nodes 85 * @param allocator the allocator for allocating the list nodes
54 * (if @c NULL, a default stdlib allocator will be used) 86 * (if @c NULL, the cxDefaultAllocator will be used)
55 * @param comparator the comparator for the elements 87 * @param comparator the comparator for the elements
56 * (if @c NULL, and the list is not storing pointers, sort and find 88 * (if @c NULL, and the list is not storing pointers, sort and find
57 * functions will not work) 89 * functions will not work)
58 * @param elem_size the size of each element in bytes 90 * @param elem_size the size of each element in bytes
59 * @return the created list 91 * @return the created list
60 */ 92 */
61 cx_attr_nodiscard 93 cx_attr_nodiscard cx_attr_malloc cx_attr_dealloc(cxListFree, 1)
62 cx_attr_malloc 94 CX_EXPORT CxList *cxLinkedListCreate(const CxAllocator *allocator,
63 cx_attr_dealloc(cxListFree, 1) 95 cx_compare_func comparator, size_t elem_size);
64 cx_attr_export
65 CxList *cxLinkedListCreate(
66 const CxAllocator *allocator,
67 cx_compare_func comparator,
68 size_t elem_size
69 );
70 96
71 /** 97 /**
72 * Allocates a linked list for storing elements with @p elem_size bytes each. 98 * Allocates a linked list for storing elements with @p elem_size bytes each.
73 * 99 *
74 * The list will use cxDefaultAllocator and no comparator function. If you want 100 * The list will use cxDefaultAllocator and no comparator function. If you want
75 * to call functions that need a comparator, you must either set one immediately 101 * to call functions that need a comparator, you must either set one immediately
76 * after list creation or use cxLinkedListCreate(). 102 * after list creation or use cxLinkedListCreate().
77 * 103 *
78 * If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of 104 * If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of
79 * copies of the added elements and the compare function will be automatically set 105 * copies of the added elements, and the compare function will be automatically set
80 * to cx_cmp_ptr(), if none is given. 106 * to cx_cmp_ptr().
81 * 107 *
82 * @param elem_size (@c size_t) the size of each element in bytes 108 * @param elem_size (@c size_t) the size of each element in bytes
83 * @return (@c CxList*) the created list 109 * @return (@c CxList*) the created list
84 */ 110 */
85 #define cxLinkedListCreateSimple(elem_size) \ 111 #define cxLinkedListCreateSimple(elem_size) \
86 cxLinkedListCreate(NULL, NULL, elem_size) 112 cxLinkedListCreate(NULL, NULL, elem_size)
87 113
88 /** 114 /**
89 * Finds the node at a certain index. 115 * Finds the node at a certain index.
90 * 116 *
91 * This function can be used to start at an arbitrary position within the list. 117 * This function can be used to start at an arbitrary position within the list.
92 * If the search index is large than the start index, @p loc_advance must denote 118 * If the search index is larger than the start index, @p loc_advance must denote
93 * the location of some sort of @c next pointer (i.e. a pointer to the next node). 119 * the location of a @c next pointer (i.e., a pointer to the next node).
94 * But it is also possible that the search index is smaller than the start index 120 * But it is also possible that the search index is smaller than the start index
95 * (e.g. in cases where traversing a list backwards is faster) in which case 121 * (e.g., in cases where traversing a list backwards is faster).
96 * @p loc_advance must denote the location of some sort of @c prev pointer 122 * In that case @p loc_advance must denote the location of a @c prev pointer
97 * (i.e. a pointer to the previous node). 123 * (i.e., a pointer to the previous node).
98 * 124 *
99 * @param start a pointer to the start node 125 * @param start a pointer to the start node
100 * @param start_index the start index 126 * @param start_index the start index
101 * @param loc_advance the location of the pointer to advance 127 * @param loc_advance the location of the pointer to advance
102 * @param index the search index 128 * @param index the search index
103 * @return the node found at the specified index 129 * @return the node found at the specified index
104 */ 130 */
105 cx_attr_nonnull 131 cx_attr_nonnull cx_attr_nodiscard
106 cx_attr_nodiscard 132 CX_EXPORT void *cx_linked_list_at(const void *start,size_t start_index,
107 cx_attr_export 133 ptrdiff_t loc_advance, size_t index);
108 void *cx_linked_list_at(
109 const void *start,
110 size_t start_index,
111 ptrdiff_t loc_advance,
112 size_t index
113 );
114 134
115 /** 135 /**
116 * Finds the node containing an element within a linked list. 136 * Finds the node containing an element within a linked list.
117 * 137 *
118 * @param start a pointer to the start node 138 * @param start a pointer to the start node
120 * @param loc_data the location of the @c data pointer within your node struct 140 * @param loc_data the location of the @c data pointer within your node struct
121 * @param cmp_func a compare function to compare @p elem against the node data 141 * @param cmp_func a compare function to compare @p elem against the node data
122 * @param elem a pointer to the element to find 142 * @param elem a pointer to the element to find
123 * @param found_index an optional pointer where the index of the found node 143 * @param found_index an optional pointer where the index of the found node
124 * (given that @p start has index 0) is stored 144 * (given that @p start has index 0) is stored
125 * @return the index of the element, if found - unspecified if not found 145 * @return a pointer to the found node or @c NULL if no matching node was found
126 */ 146 */
127 cx_attr_nonnull_arg(1, 4, 5) 147 cx_attr_nonnull_arg(1, 4, 5)
128 cx_attr_export 148 CX_EXPORT void *cx_linked_list_find(const void *start, ptrdiff_t loc_advance,
129 void *cx_linked_list_find( 149 ptrdiff_t loc_data, cx_compare_func cmp_func, const void *elem,
130 const void *start, 150 size_t *found_index);
131 ptrdiff_t loc_advance,
132 ptrdiff_t loc_data,
133 cx_compare_func cmp_func,
134 const void *elem,
135 size_t *found_index
136 );
137 151
138 /** 152 /**
139 * Finds the first node in a linked list. 153 * Finds the first node in a linked list.
140 * 154 *
141 * The function starts with the pointer denoted by @p node and traverses the list 155 * The function starts with the pointer denoted by @p node and traverses the list
144 * 158 *
145 * @param node a pointer to a node in the list 159 * @param node a pointer to a node in the list
146 * @param loc_prev the location of the @c prev pointer 160 * @param loc_prev the location of the @c prev pointer
147 * @return a pointer to the first node 161 * @return a pointer to the first node
148 */ 162 */
149 cx_attr_nonnull 163 cx_attr_nonnull cx_attr_returns_nonnull
150 cx_attr_returns_nonnull 164 CX_EXPORT void *cx_linked_list_first(const void *node, ptrdiff_t loc_prev);
151 cx_attr_export
152 void *cx_linked_list_first(
153 const void *node,
154 ptrdiff_t loc_prev
155 );
156 165
157 /** 166 /**
158 * Finds the last node in a linked list. 167 * Finds the last node in a linked list.
159 * 168 *
160 * The function starts with the pointer denoted by @p node and traverses the list 169 * The function starts with the pointer denoted by @p node and traverses the list
163 * 172 *
164 * @param node a pointer to a node in the list 173 * @param node a pointer to a node in the list
165 * @param loc_next the location of the @c next pointer 174 * @param loc_next the location of the @c next pointer
166 * @return a pointer to the last node 175 * @return a pointer to the last node
167 */ 176 */
168 cx_attr_nonnull 177 cx_attr_nonnull cx_attr_returns_nonnull
169 cx_attr_returns_nonnull 178 CX_EXPORT void *cx_linked_list_last(const void *node, ptrdiff_t loc_next);
170 cx_attr_export
171 void *cx_linked_list_last(
172 const void *node,
173 ptrdiff_t loc_next
174 );
175 179
176 /** 180 /**
177 * Finds the predecessor of a node in case it is not linked. 181 * Finds the predecessor of a node in case it is not linked.
178 * 182 *
179 * @remark If @p node is not contained in the list starting with @p begin, the behavior is undefined. 183 * @remark If @p node is not contained in the list starting with @p begin, the behavior is undefined.
182 * @param loc_next the location of the @c next pointer 186 * @param loc_next the location of the @c next pointer
183 * @param node the successor of the node to find 187 * @param node the successor of the node to find
184 * @return the node or @c NULL if @p node has no predecessor 188 * @return the node or @c NULL if @p node has no predecessor
185 */ 189 */
186 cx_attr_nonnull 190 cx_attr_nonnull
187 cx_attr_export 191 CX_EXPORT void *cx_linked_list_prev(const void *begin, ptrdiff_t loc_next, const void *node);
188 void *cx_linked_list_prev(
189 const void *begin,
190 ptrdiff_t loc_next,
191 const void *node
192 );
193 192
194 /** 193 /**
195 * Adds a new node to a linked list. 194 * Adds a new node to a linked list.
196 * The node must not be part of any list already. 195 * The node must not be part of any list yet.
197 * 196 *
198 * @remark One of the pointers @p begin or @p end may be @c NULL, but not both. 197 * @remark One of the pointers @p begin or @p end may be @c NULL, but not both.
199 * 198 *
200 * @param begin a pointer to the beginning node pointer (if your list has one) 199 * @param begin a pointer to the beginning node pointer (if your list has one)
201 * @param end a pointer to the end node pointer (if your list has one) 200 * @param end a pointer to the end node pointer (if your list has one)
202 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one) 201 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
203 * @param loc_next the location of a @c next pointer within your node struct (required) 202 * @param loc_next the location of a @c next pointer within your node struct (required)
204 * @param new_node a pointer to the node that shall be appended 203 * @param new_node a pointer to the node that shall be appended
205 */ 204 */
206 cx_attr_nonnull_arg(5) 205 cx_attr_nonnull_arg(5)
207 cx_attr_export 206 CX_EXPORT void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node);
208 void cx_linked_list_add(
209 void **begin,
210 void **end,
211 ptrdiff_t loc_prev,
212 ptrdiff_t loc_next,
213 void *new_node
214 );
215 207
216 /** 208 /**
217 * Prepends a new node to a linked list. 209 * Prepends a new node to a linked list.
218 * The node must not be part of any list already. 210 * The node must not be part of any list yet.
219 * 211 *
220 * @remark One of the pointers @p begin or @p end may be @c NULL, but not both. 212 * @remark One of the pointers @p begin or @p end may be @c NULL, but not both.
221 * 213 *
222 * @param begin a pointer to the beginning node pointer (if your list has one) 214 * @param begin a pointer to the beginning node pointer (if your list has one)
223 * @param end a pointer to the end node pointer (if your list has one) 215 * @param end a pointer to the end node pointer (if your list has one)
224 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one) 216 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
225 * @param loc_next the location of a @c next pointer within your node struct (required) 217 * @param loc_next the location of a @c next pointer within your node struct (required)
226 * @param new_node a pointer to the node that shall be prepended 218 * @param new_node a pointer to the node that shall be prepended
227 */ 219 */
228 cx_attr_nonnull_arg(5) 220 cx_attr_nonnull_arg(5)
229 cx_attr_export 221 CX_EXPORT void cx_linked_list_prepend(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node);
230 void cx_linked_list_prepend(
231 void **begin,
232 void **end,
233 ptrdiff_t loc_prev,
234 ptrdiff_t loc_next,
235 void *new_node
236 );
237 222
238 /** 223 /**
239 * Links two nodes. 224 * Links two nodes.
240 * 225 *
241 * @param left the new predecessor of @p right 226 * @param left the new predecessor of @p right
242 * @param right the new successor of @p left 227 * @param right the new successor of @p left
243 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one) 228 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
244 * @param loc_next the location of a @c next pointer within your node struct (required) 229 * @param loc_next the location of a @c next pointer within your node struct (required)
245 */ 230 */
246 cx_attr_nonnull 231 cx_attr_nonnull
247 cx_attr_export 232 CX_EXPORT void cx_linked_list_link(void *left, void *right, ptrdiff_t loc_prev, ptrdiff_t loc_next);
248 void cx_linked_list_link(
249 void *left,
250 void *right,
251 ptrdiff_t loc_prev,
252 ptrdiff_t loc_next
253 );
254 233
255 /** 234 /**
256 * Unlinks two nodes. 235 * Unlinks two nodes.
257 * 236 *
258 * If right is not the successor of left, the behavior is undefined. 237 * If right is not the successor of left, the behavior is undefined.
261 * @param right the successor of @p left 240 * @param right the successor of @p left
262 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one) 241 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
263 * @param loc_next the location of a @c next pointer within your node struct (required) 242 * @param loc_next the location of a @c next pointer within your node struct (required)
264 */ 243 */
265 cx_attr_nonnull 244 cx_attr_nonnull
266 cx_attr_export 245 CX_EXPORT void cx_linked_list_unlink(void *left, void *right, ptrdiff_t loc_prev, ptrdiff_t loc_next);
267 void cx_linked_list_unlink(
268 void *left,
269 void *right,
270 ptrdiff_t loc_prev,
271 ptrdiff_t loc_next
272 );
273 246
274 /** 247 /**
275 * Inserts a new node after a given node of a linked list. 248 * Inserts a new node after a given node of a linked list.
276 * The new node must not be part of any list already. 249 * The new node must not be part of any list yet.
277 * 250 *
278 * @note If you specify @c NULL as the @p node to insert after, this function needs either the @p begin or 251 * @note If you specify @c NULL as the @p node to insert after, this function needs either the @p begin or
279 * the @p end pointer to determine the start of the list. Then the new node will be prepended to the list. 252 * the @p end pointer to determine the start of the list. Then the new node will be prepended to the list.
280 * 253 *
281 * @param begin a pointer to the beginning node pointer (if your list has one) 254 * @param begin a pointer to the beginning node pointer (if your list has one)
284 * @param loc_next the location of a @c next pointer within your node struct (required) 257 * @param loc_next the location of a @c next pointer within your node struct (required)
285 * @param node the node after which to insert (@c NULL if you want to prepend the node to the list) 258 * @param node the node after which to insert (@c NULL if you want to prepend the node to the list)
286 * @param new_node a pointer to the node that shall be inserted 259 * @param new_node a pointer to the node that shall be inserted
287 */ 260 */
288 cx_attr_nonnull_arg(6) 261 cx_attr_nonnull_arg(6)
289 cx_attr_export 262 CX_EXPORT void cx_linked_list_insert(void **begin, void **end,
290 void cx_linked_list_insert( 263 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node, void *new_node);
291 void **begin,
292 void **end,
293 ptrdiff_t loc_prev,
294 ptrdiff_t loc_next,
295 void *node,
296 void *new_node
297 );
298 264
299 /** 265 /**
300 * Inserts a chain of nodes after a given node of a linked list. 266 * Inserts a chain of nodes after a given node of a linked list.
301 * The chain must not be part of any list already. 267 * The chain must not be part of any list yet.
302 * 268 *
303 * If you do not explicitly specify the end of the chain, it will be determined by traversing 269 * If you do not explicitly specify the end of the chain, it will be determined by traversing
304 * the @c next pointer. 270 * the @c next pointer.
305 * 271 *
306 * @note If you specify @c NULL as the @p node to insert after, this function needs either the @p begin or 272 * @note If you specify @c NULL as the @p node to insert after, this function needs either the @p begin or
315 * @param node the node after which to insert (@c NULL to prepend the chain to the list) 281 * @param node the node after which to insert (@c NULL to prepend the chain to the list)
316 * @param insert_begin a pointer to the first node of the chain that shall be inserted 282 * @param insert_begin a pointer to the first node of the chain that shall be inserted
317 * @param insert_end a pointer to the last node of the chain (or NULL if the last node shall be determined) 283 * @param insert_end a pointer to the last node of the chain (or NULL if the last node shall be determined)
318 */ 284 */
319 cx_attr_nonnull_arg(6) 285 cx_attr_nonnull_arg(6)
320 cx_attr_export 286 CX_EXPORT void cx_linked_list_insert_chain(void **begin, void **end,
321 void cx_linked_list_insert_chain( 287 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node, void *insert_begin, void *insert_end);
322 void **begin,
323 void **end,
324 ptrdiff_t loc_prev,
325 ptrdiff_t loc_next,
326 void *node,
327 void *insert_begin,
328 void *insert_end
329 );
330 288
331 /** 289 /**
332 * Inserts a node into a sorted linked list. 290 * Inserts a node into a sorted linked list.
333 * The new node must not be part of any list already. 291 * The new node must not be part of any list yet.
334 * 292 *
335 * If the list starting with the node pointed to by @p begin is not sorted 293 * If the list starting with the node pointed to by @p begin is not sorted
336 * already, the behavior is undefined. 294 * already, the behavior is undefined.
337 * 295 *
338 * @param begin a pointer to the beginning node pointer (required) 296 * @param begin a pointer to the beginning node pointer (required)
341 * @param loc_next the location of a @c next pointer within your node struct (required) 299 * @param loc_next the location of a @c next pointer within your node struct (required)
342 * @param new_node a pointer to the node that shall be inserted 300 * @param new_node a pointer to the node that shall be inserted
343 * @param cmp_func a compare function that will receive the node pointers 301 * @param cmp_func a compare function that will receive the node pointers
344 */ 302 */
345 cx_attr_nonnull_arg(1, 5, 6) 303 cx_attr_nonnull_arg(1, 5, 6)
346 cx_attr_export 304 CX_EXPORT void cx_linked_list_insert_sorted(void **begin, void **end,
347 void cx_linked_list_insert_sorted( 305 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node, cx_compare_func cmp_func);
348 void **begin,
349 void **end,
350 ptrdiff_t loc_prev,
351 ptrdiff_t loc_next,
352 void *new_node,
353 cx_compare_func cmp_func
354 );
355 306
356 /** 307 /**
357 * Inserts a chain of nodes into a sorted linked list. 308 * Inserts a chain of nodes into a sorted linked list.
358 * The chain must not be part of any list already. 309 * The chain must not be part of any list yet.
359 * 310 *
360 * If either the list starting with the node pointed to by @p begin or the list 311 * If either the list starting with the node pointed to by @p begin or the list
361 * starting with @p insert_begin is not sorted, the behavior is undefined. 312 * starting with @p insert_begin is not sorted, the behavior is undefined.
362 * 313 *
363 * @attention In contrast to cx_linked_list_insert_chain(), the source chain 314 * @attention In contrast to cx_linked_list_insert_chain(), the source chain
364 * will be broken and inserted into the target list so that the resulting list 315 * will be broken and inserted into the target list so that the resulting list
365 * will be sorted according to @p cmp_func. That means, each node in the source 316 * will be sorted according to @p cmp_func. That means each node in the source
366 * chain may be re-linked with nodes from the target list. 317 * chain may be re-linked with nodes from the target list.
367 * 318 *
368 * @param begin a pointer to the beginning node pointer (required) 319 * @param begin a pointer to the beginning node pointer (required)
369 * @param end a pointer to the end node pointer (if your list has one) 320 * @param end a pointer to the end node pointer (if your list has one)
370 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one) 321 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
371 * @param loc_next the location of a @c next pointer within your node struct (required) 322 * @param loc_next the location of a @c next pointer within your node struct (required)
372 * @param insert_begin a pointer to the first node of the chain that shall be inserted 323 * @param insert_begin a pointer to the first node of the chain that shall be inserted
373 * @param cmp_func a compare function that will receive the node pointers 324 * @param cmp_func a compare function that will receive the node pointers
374 */ 325 */
375 cx_attr_nonnull_arg(1, 5, 6) 326 cx_attr_nonnull_arg(1, 5, 6)
376 cx_attr_export 327 CX_EXPORT void cx_linked_list_insert_sorted_chain(void **begin, void **end,
377 void cx_linked_list_insert_sorted_chain( 328 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *insert_begin, cx_compare_func cmp_func);
378 void **begin, 329
379 void **end, 330 /**
380 ptrdiff_t loc_prev, 331 * Inserts a node into a sorted linked list if no other node with the same value already exists.
381 ptrdiff_t loc_next, 332 * The new node must not be part of any list yet.
382 void *insert_begin, 333 *
383 cx_compare_func cmp_func 334 * If the list starting with the node pointed to by @p begin is not sorted
384 ); 335 * already, the behavior is undefined.
336 *
337 * @param begin a pointer to the beginning node pointer (required)
338 * @param end a pointer to the end node pointer (if your list has one)
339 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
340 * @param loc_next the location of a @c next pointer within your node struct (required)
341 * @param new_node a pointer to the node that shall be inserted
342 * @param cmp_func a compare function that will receive the node pointers
343 * @retval zero when the node was inserted
344 * @retval non-zero when a node with the same value already exists
345 */
346 cx_attr_nonnull_arg(1, 5, 6)
347 CX_EXPORT int cx_linked_list_insert_unique(void **begin, void **end,
348 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node, cx_compare_func cmp_func);
349
350 /**
351 * Inserts a chain of nodes into a sorted linked list, avoiding duplicates.
352 * The chain must not be part of any list yet.
353 *
354 * If either the list starting with the node pointed to by @p begin or the list
355 * starting with @p insert_begin is not sorted, the behavior is undefined.
356 *
357 * @attention In contrast to cx_linked_list_insert_sorted(), not all nodes of the
358 * chain might be added. This function returns a new chain consisting of all the duplicates.
359 *
360 * @param begin a pointer to the beginning node pointer (required)
361 * @param end a pointer to the end node pointer (if your list has one)
362 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
363 * @param loc_next the location of a @c next pointer within your node struct (required)
364 * @param insert_begin a pointer to the first node of the chain that shall be inserted
365 * @param cmp_func a compare function that will receive the node pointers
366 * @return a pointer to a new chain with all duplicates that were not inserted (or @c NULL when there were no duplicates)
367 */
368 cx_attr_nonnull_arg(1, 5, 6) cx_attr_nodiscard
369 CX_EXPORT void *cx_linked_list_insert_unique_chain(void **begin, void **end,
370 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *insert_begin, cx_compare_func cmp_func);
385 371
386 /** 372 /**
387 * Removes a chain of nodes from the linked list. 373 * Removes a chain of nodes from the linked list.
388 * 374 *
389 * If one of the nodes to remove is the beginning (resp. end) node of the list and if @p begin (resp. @p end) 375 * If one of the nodes to remove is the beginning (resp. end) node of the list, and if @p begin (resp. @p end)
390 * addresses are provided, the pointers are adjusted accordingly. 376 * addresses are provided, the pointers are adjusted accordingly.
391 * 377 *
392 * The following combinations of arguments are valid (more arguments are optional): 378 * The following combinations of arguments are valid (more arguments are optional):
393 * @li @p loc_next and @p loc_prev (ancestor node is determined by using the prev pointer, overall O(1) performance) 379 * @li @p loc_next and @p loc_prev (ancestor node is determined by using the prev pointer, overall O(1) performance)
394 * @li @p loc_next and @p begin (ancestor node is determined by list traversal, overall O(n) performance) 380 * @li @p loc_next and @p begin (ancestor node is determined by list traversal, overall O(n) performance)
395 * 381 *
396 * @remark The @c next and @c prev pointers of the removed node are not cleared by this function and may still be used 382 * @remark The @c next and @c prev pointers of the removed chain are not cleared by this function and may still be used
397 * to traverse to a former adjacent node in the list, or within the chain. 383 * to traverse to a former adjacent node in the list, or within the chain.
398 * 384 *
399 * @param begin a pointer to the beginning node pointer (optional) 385 * @param begin a pointer to the beginning node pointer (optional)
400 * @param end a pointer to the end node pointer (optional) 386 * @param end a pointer to the end node pointer (optional)
401 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one) 387 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
403 * @param node the start node of the chain 389 * @param node the start node of the chain
404 * @param num the number of nodes to remove 390 * @param num the number of nodes to remove
405 * @return the actual number of nodes that were removed (can be less when the list did not have enough nodes) 391 * @return the actual number of nodes that were removed (can be less when the list did not have enough nodes)
406 */ 392 */
407 cx_attr_nonnull_arg(5) 393 cx_attr_nonnull_arg(5)
408 cx_attr_export 394 CX_EXPORT size_t cx_linked_list_remove_chain(void **begin, void **end,
409 size_t cx_linked_list_remove_chain( 395 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node, size_t num);
410 void **begin,
411 void **end,
412 ptrdiff_t loc_prev,
413 ptrdiff_t loc_next,
414 void *node,
415 size_t num
416 );
417 396
418 /** 397 /**
419 * Removes a node from the linked list. 398 * Removes a node from the linked list.
420 * 399 *
421 * If the node to remove is the beginning (resp. end) node of the list and if @p begin (resp. @p end) 400 * If the node to remove is the beginning (resp. end) node of the list, and if @p begin (resp. @p end)
422 * addresses are provided, the pointers are adjusted accordingly. 401 * addresses are provided, the pointers are adjusted accordingly.
423 * 402 *
424 * The following combinations of arguments are valid (more arguments are optional): 403 * The following combinations of arguments are valid (more arguments are optional):
425 * @li @p loc_next and @p loc_prev (ancestor node is determined by using the prev pointer, overall O(1) performance) 404 * @li @p loc_next and @p loc_prev (ancestor node is determined by using the prev pointer, overall O(1) performance)
426 * @li @p loc_next and @p begin (ancestor node is determined by list traversal, overall O(n) performance) 405 * @li @p loc_next and @p begin (ancestor node is determined by list traversal, overall O(n) performance)
433 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one) 412 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
434 * @param loc_next the location of a @c next pointer within your node struct (required) 413 * @param loc_next the location of a @c next pointer within your node struct (required)
435 * @param node the node to remove 414 * @param node the node to remove
436 */ 415 */
437 cx_attr_nonnull_arg(5) 416 cx_attr_nonnull_arg(5)
438 static inline void cx_linked_list_remove( 417 CX_EXPORT void cx_linked_list_remove(void **begin, void **end,
439 void **begin, 418 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node);
440 void **end,
441 ptrdiff_t loc_prev,
442 ptrdiff_t loc_next,
443 void *node
444 ) {
445 cx_linked_list_remove_chain(begin, end, loc_prev, loc_next, node, 1);
446 }
447 419
448 /** 420 /**
449 * Determines the size of a linked list starting with @p node. 421 * Determines the size of a linked list starting with @p node.
450 * 422 *
451 * @param node the first node 423 * @param node the first node
452 * @param loc_next the location of the @c next pointer within the node struct 424 * @param loc_next the location of the @c next pointer within the node struct
453 * @return the size of the list or zero if @p node is @c NULL 425 * @return the size of the list or zero if @p node is @c NULL
454 */ 426 */
455 cx_attr_nodiscard 427 cx_attr_nodiscard
456 cx_attr_export 428 CX_EXPORT size_t cx_linked_list_size(const void *node, ptrdiff_t loc_next);
457 size_t cx_linked_list_size(
458 const void *node,
459 ptrdiff_t loc_next
460 );
461 429
462 /** 430 /**
463 * Sorts a linked list based on a comparison function. 431 * Sorts a linked list based on a comparison function.
464 * 432 *
465 * This function can work with linked lists of the following structure: 433 * This function can work with linked lists of the following structure:
480 * @param loc_next the location of a @c next pointer within your node struct (required) 448 * @param loc_next the location of a @c next pointer within your node struct (required)
481 * @param loc_data the location of the @c data pointer within your node struct 449 * @param loc_data the location of the @c data pointer within your node struct
482 * @param cmp_func the compare function defining the sort order 450 * @param cmp_func the compare function defining the sort order
483 */ 451 */
484 cx_attr_nonnull_arg(1, 6) 452 cx_attr_nonnull_arg(1, 6)
485 cx_attr_export 453 CX_EXPORT void cx_linked_list_sort(void **begin, void **end,
486 void cx_linked_list_sort( 454 ptrdiff_t loc_prev, ptrdiff_t loc_next, ptrdiff_t loc_data, cx_compare_func cmp_func);
487 void **begin,
488 void **end,
489 ptrdiff_t loc_prev,
490 ptrdiff_t loc_next,
491 ptrdiff_t loc_data,
492 cx_compare_func cmp_func
493 );
494 455
495 456
496 /** 457 /**
497 * Compares two lists element wise. 458 * Compares two lists element wise.
498 * 459 *
499 * @attention Both list must have the same structure. 460 * @attention Both lists must have the same structure.
500 * 461 *
501 * @param begin_left the beginning of the left list (@c NULL denotes an empty list) 462 * @param begin_left the beginning of the left list (@c NULL denotes an empty list)
502 * @param begin_right the beginning of the right list (@c NULL denotes an empty list) 463 * @param begin_right the beginning of the right list (@c NULL denotes an empty list)
503 * @param loc_advance the location of the pointer to advance 464 * @param loc_advance the location of the pointer to advance
504 * @param loc_data the location of the @c data pointer within your node struct 465 * @param loc_data the location of the @c data pointer within your node struct
505 * @param cmp_func the function to compare the elements 466 * @param cmp_func the function to compare the elements
506 * @return the first non-zero result of invoking @p cmp_func or: negative if the left list is smaller than the 467 * @return the first non-zero result of invoking @p cmp_func or: negative if the left list is smaller than the
507 * right list, positive if the left list is larger than the right list, zero if both lists are equal. 468 * right list, positive if the left list is larger than the right list, zero if both lists are equal.
508 */ 469 */
509 cx_attr_nonnull_arg(5) 470 cx_attr_nonnull_arg(5)
510 cx_attr_export 471 CX_EXPORT int cx_linked_list_compare(const void *begin_left, const void *begin_right,
511 int cx_linked_list_compare( 472 ptrdiff_t loc_advance, ptrdiff_t loc_data, cx_compare_func cmp_func);
512 const void *begin_left,
513 const void *begin_right,
514 ptrdiff_t loc_advance,
515 ptrdiff_t loc_data,
516 cx_compare_func cmp_func
517 );
518 473
519 /** 474 /**
520 * Reverses the order of the nodes in a linked list. 475 * Reverses the order of the nodes in a linked list.
521 * 476 *
522 * @param begin a pointer to the beginning node pointer (required) 477 * @param begin a pointer to the beginning node pointer (required)
523 * @param end a pointer to the end node pointer (optional) 478 * @param end a pointer to the end node pointer (optional)
524 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one) 479 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
525 * @param loc_next the location of a @c next pointer within your node struct (required) 480 * @param loc_next the location of a @c next pointer within your node struct (required)
526 */ 481 */
527 cx_attr_nonnull_arg(1) 482 cx_attr_nonnull_arg(1)
528 cx_attr_export 483 CX_EXPORT void cx_linked_list_reverse(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next);
529 void cx_linked_list_reverse(
530 void **begin,
531 void **end,
532 ptrdiff_t loc_prev,
533 ptrdiff_t loc_next
534 );
535 484
536 #ifdef __cplusplus 485 #ifdef __cplusplus
537 } // extern "C" 486 } // extern "C"
538 #endif 487 #endif
539 488

Mercurial Repository: dav

mercurial