src/cx/linked_list.h

Mon, 24 Apr 2023 19:08:56 +0200

author
Mike Becker <universe@uap-core.de>
date
Mon, 24 Apr 2023 19:08:56 +0200
changeset 701
72a440c437e9
parent 699
35b2b99ee523
child 759
475335643af4
permissions
-rw-r--r--

explicitly set cmake policy CMP0077

universe@398 1 /*
universe@398 2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
universe@398 3 *
universe@398 4 * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
universe@398 5 *
universe@398 6 * Redistribution and use in source and binary forms, with or without
universe@398 7 * modification, are permitted provided that the following conditions are met:
universe@398 8 *
universe@398 9 * 1. Redistributions of source code must retain the above copyright
universe@398 10 * notice, this list of conditions and the following disclaimer.
universe@398 11 *
universe@398 12 * 2. Redistributions in binary form must reproduce the above copyright
universe@398 13 * notice, this list of conditions and the following disclaimer in the
universe@398 14 * documentation and/or other materials provided with the distribution.
universe@398 15 *
universe@398 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
universe@398 17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
universe@398 18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
universe@398 19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
universe@398 20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
universe@398 21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
universe@398 22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
universe@398 23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
universe@398 24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
universe@398 25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
universe@398 26 * POSSIBILITY OF SUCH DAMAGE.
universe@398 27 */
universe@453 28 /**
universe@453 29 * \file linked_list.h
universe@453 30 * \brief Linked list implementation.
universe@453 31 * \details Also provides several low-level functions for custom linked list implementations.
universe@453 32 * \author Mike Becker
universe@453 33 * \author Olaf Wintermann
universe@453 34 * \version 3.0
universe@453 35 * \copyright 2-Clause BSD License
universe@453 36 */
universe@398 37
universe@398 38 #ifndef UCX_LINKED_LIST_H
universe@398 39 #define UCX_LINKED_LIST_H
universe@398 40
universe@484 41 #include "common.h"
universe@398 42 #include "list.h"
universe@398 43
universe@415 44 #ifdef __cplusplus
universe@415 45 extern "C" {
universe@415 46 #endif
universe@415 47
universe@466 48 /**
universe@647 49 * Set this flag to true, if you want to disable the use of SBO for
universe@647 50 * linked list swap operations.
universe@647 51 */
universe@647 52 extern bool CX_DISABLE_LINKED_LIST_SWAP_SBO;
universe@647 53
universe@647 54 /**
universe@466 55 * Allocates a linked list for storing elements with \p item_size bytes each.
universe@466 56 *
universe@669 57 * If \p item_size is CX_STORE_POINTERS, the created list will be created as if
universe@669 58 * cxListStorePointers() was called immediately after creation.
universe@669 59 *
universe@466 60 * @param allocator the allocator for allocating the list nodes
universe@670 61 * (if \c NULL the cxDefaultAllocator will be used)
universe@466 62 * @param comparator the comparator for the elements
universe@670 63 * (if \c NULL sort and find functions will not work)
universe@466 64 * @param item_size the size of each element in bytes
universe@466 65 * @return the created list
universe@466 66 */
universe@500 67 CxList *cxLinkedListCreate(
universe@508 68 CxAllocator const *allocator,
universe@677 69 cx_compare_func comparator,
universe@481 70 size_t item_size
universe@670 71 );
universe@453 72
universe@466 73 /**
universe@662 74 * Allocates a linked list for storing elements with \p item_size bytes each.
universe@662 75 *
universe@662 76 * The list will use cxDefaultAllocator and no comparator function. If you want
universe@662 77 * to call functions that need a comparator, you must either set one immediately
universe@662 78 * after list creation or use cxLinkedListCreate().
universe@662 79 *
universe@669 80 * If \p item_size is CX_STORE_POINTERS, the created list will be created as if
universe@669 81 * cxListStorePointers() was called immediately after creation.
universe@669 82 *
universe@662 83 * @param item_size the size of each element in bytes
universe@662 84 * @return the created list
universe@662 85 */
universe@670 86 #define cxLinkedListCreateSimple(item_size) \
universe@670 87 cxLinkedListCreate(NULL, NULL, item_size)
universe@662 88
universe@662 89 /**
universe@438 90 * Finds the node at a certain index.
universe@438 91 *
universe@438 92 * This function can be used to start at an arbitrary position within the list.
universe@438 93 * If the search index is large than the start index, \p loc_advance must denote
universe@438 94 * the location of some sort of \c next pointer (i.e. a pointer to the next node).
universe@438 95 * But it is also possible that the search index is smaller than the start index
universe@438 96 * (e.g. in cases where traversing a list backwards is faster) in which case
universe@438 97 * \p loc_advance must denote the location of some sort of \c prev pointer
universe@438 98 * (i.e. a pointer to the previous node).
universe@438 99 *
universe@438 100 * @param start a pointer to the start node
universe@438 101 * @param start_index the start index
universe@438 102 * @param loc_advance the location of the pointer to advance
universe@438 103 * @param index the search index
universe@438 104 * @return the node found at the specified index
universe@438 105 */
universe@481 106 void *cx_linked_list_at(
universe@508 107 void const *start,
universe@481 108 size_t start_index,
universe@481 109 ptrdiff_t loc_advance,
universe@481 110 size_t index
universe@481 111 ) __attribute__((__nonnull__));
universe@438 112
universe@453 113 /**
universe@480 114 * Finds the index of an element within a linked list.
universe@480 115 *
universe@480 116 * @param start a pointer to the start node
universe@480 117 * @param loc_advance the location of the pointer to advance
universe@480 118 * @param loc_data the location of the \c data pointer within your node struct
universe@480 119 * @param cmp_func a compare function to compare \p elem against the node data
universe@480 120 * @param elem a pointer to the element to find
universe@699 121 * @return the index of the element or a negative value if it could not be found
universe@480 122 */
universe@699 123 ssize_t cx_linked_list_find(
universe@489 124 void const *start,
universe@481 125 ptrdiff_t loc_advance,
universe@481 126 ptrdiff_t loc_data,
universe@677 127 cx_compare_func cmp_func,
universe@489 128 void const *elem
universe@481 129 ) __attribute__((__nonnull__));
universe@480 130
universe@480 131 /**
universe@475 132 * Finds the first node in a linked list.
universe@475 133 *
universe@475 134 * The function starts with the pointer denoted by \p node and traverses the list
universe@475 135 * along a prev pointer whose location within the node struct is
universe@475 136 * denoted by \p loc_prev.
universe@475 137 *
universe@475 138 * @param node a pointer to a node in the list
universe@475 139 * @param loc_prev the location of the \c prev pointer
universe@485 140 * @return a pointer to the first node
universe@475 141 */
universe@481 142 void *cx_linked_list_first(
universe@508 143 void const *node,
universe@481 144 ptrdiff_t loc_prev
universe@481 145 ) __attribute__((__nonnull__));
universe@475 146
universe@475 147 /**
universe@453 148 * Finds the last node in a linked list.
universe@453 149 *
universe@475 150 * The function starts with the pointer denoted by \p node and traverses the list
universe@456 151 * along a next pointer whose location within the node struct is
universe@453 152 * denoted by \p loc_next.
universe@453 153 *
universe@475 154 * @param node a pointer to a node in the list
universe@456 155 * @param loc_next the location of the \c next pointer
universe@478 156 * @return a pointer to the last node
universe@453 157 */
universe@481 158 void *cx_linked_list_last(
universe@508 159 void const *node,
universe@481 160 ptrdiff_t loc_next
universe@481 161 ) __attribute__((__nonnull__));
universe@398 162
universe@453 163 /**
universe@473 164 * Finds the predecessor of a node in case it is not linked.
universe@473 165 *
universe@473 166 * \remark If \p node is not contained in the list starting with \p begin, the behavior is undefined.
universe@473 167 *
universe@473 168 * @param begin the node where to start the search
universe@473 169 * @param loc_next the location of the \c next pointer
universe@473 170 * @param node the successor of the node to find
universe@473 171 * @return the node or \c NULL if \p node has no predecessor
universe@473 172 */
universe@481 173 void *cx_linked_list_prev(
universe@508 174 void const *begin,
universe@481 175 ptrdiff_t loc_next,
universe@508 176 void const *node
universe@481 177 ) __attribute__((__nonnull__));
universe@473 178
universe@473 179 /**
universe@453 180 * Adds a new node to a linked list.
universe@475 181 * The node must not be part of any list already.
universe@453 182 *
universe@478 183 * \remark One of the pointers \p begin or \p end may be \c NULL, but not both.
universe@453 184 *
universe@453 185 * @param begin a pointer to the begin node pointer (if your list has one)
universe@453 186 * @param end a pointer to the end node pointer (if your list has one)
universe@453 187 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
universe@473 188 * @param loc_next the location of a \c next pointer within your node struct (required)
universe@453 189 * @param new_node a pointer to the node that shall be appended
universe@453 190 */
universe@481 191 void cx_linked_list_add(
universe@481 192 void **begin,
universe@481 193 void **end,
universe@481 194 ptrdiff_t loc_prev,
universe@481 195 ptrdiff_t loc_next,
universe@481 196 void *new_node
universe@481 197 ) __attribute__((__nonnull__(5)));
universe@406 198
universe@468 199 /**
universe@475 200 * Prepends a new node to a linked list.
universe@475 201 * The node must not be part of any list already.
universe@475 202 *
universe@478 203 * \remark One of the pointers \p begin or \p end may be \c NULL, but not both.
universe@475 204 *
universe@475 205 * @param begin a pointer to the begin node pointer (if your list has one)
universe@475 206 * @param end a pointer to the end node pointer (if your list has one)
universe@475 207 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
universe@475 208 * @param loc_next the location of a \c next pointer within your node struct (required)
universe@475 209 * @param new_node a pointer to the node that shall be prepended
universe@475 210 */
universe@481 211 void cx_linked_list_prepend(
universe@481 212 void **begin,
universe@481 213 void **end,
universe@481 214 ptrdiff_t loc_prev,
universe@481 215 ptrdiff_t loc_next,
universe@481 216 void *new_node
universe@481 217 ) __attribute__((__nonnull__(5)));
universe@481 218
universe@481 219 /**
universe@481 220 * Links two nodes.
universe@481 221 *
universe@481 222 * @param left the new predecessor of \p right
universe@481 223 * @param right the new successor of \p left
universe@481 224 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
universe@481 225 * @param loc_next the location of a \c next pointer within your node struct (required)
universe@481 226 */
universe@481 227 void cx_linked_list_link(
universe@481 228 void *left,
universe@481 229 void *right,
universe@481 230 ptrdiff_t loc_prev,
universe@481 231 ptrdiff_t loc_next
universe@481 232 ) __attribute__((__nonnull__));
universe@481 233
universe@481 234 /**
universe@481 235 * Unlinks two nodes.
universe@481 236 *
universe@481 237 * If right is not the successor of left, the behavior is undefined.
universe@481 238 *
universe@481 239 * @param left the predecessor of \p right
universe@481 240 * @param right the successor of \p left
universe@481 241 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
universe@481 242 * @param loc_next the location of a \c next pointer within your node struct (required)
universe@481 243 */
universe@481 244 void cx_linked_list_unlink(
universe@481 245 void *left,
universe@481 246 void *right,
universe@481 247 ptrdiff_t loc_prev,
universe@481 248 ptrdiff_t loc_next
universe@481 249 ) __attribute__((__nonnull__));
universe@481 250
universe@481 251 /**
universe@481 252 * Inserts a new node after a given node of a linked list.
universe@481 253 * The new node must not be part of any list already.
universe@481 254 *
universe@481 255 * \note If you specify \c NULL as the \p node to insert after, this function needs either the \p begin or
universe@481 256 * the \p end pointer to determine the start of the list. Then the new node will be prepended to the list.
universe@481 257 *
universe@481 258 * @param begin a pointer to the begin node pointer (if your list has one)
universe@481 259 * @param end a pointer to the end node pointer (if your list has one)
universe@481 260 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
universe@481 261 * @param loc_next the location of a \c next pointer within your node struct (required)
universe@481 262 * @param node the node after which to insert (\c NULL if you want to prepend the node to the list)
universe@481 263 * @param new_node a pointer to the node that shall be prepended
universe@481 264 */
universe@481 265 void cx_linked_list_insert(
universe@481 266 void **begin,
universe@481 267 void **end,
universe@481 268 ptrdiff_t loc_prev,
universe@481 269 ptrdiff_t loc_next,
universe@481 270 void *node,
universe@481 271 void *new_node
universe@481 272 ) __attribute__((__nonnull__(6)));
universe@481 273
universe@481 274 /**
universe@481 275 * Inserts a chain of nodes after a given node of a linked list.
universe@481 276 * The chain must not be part of any list already.
universe@481 277 *
universe@481 278 * If you do not explicitly specify the end of the chain, it will be determined by traversing
universe@481 279 * the \c next pointer.
universe@481 280 *
universe@481 281 * \note If you specify \c NULL as the \p node to insert after, this function needs either the \p begin or
universe@481 282 * the \p end pointer to determine the start of the list. If only the \p end pointer is specified, you also need
universe@481 283 * to provide a valid \p loc_prev location.
universe@481 284 * Then the chain will be prepended to the list.
universe@481 285 *
universe@481 286 * @param begin a pointer to the begin node pointer (if your list has one)
universe@481 287 * @param end a pointer to the end node pointer (if your list has one)
universe@481 288 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
universe@481 289 * @param loc_next the location of a \c next pointer within your node struct (required)
universe@481 290 * @param node the node after which to insert (\c NULL to prepend the chain to the list)
universe@481 291 * @param insert_begin a pointer to the first node of the chain that shall be inserted
universe@481 292 * @param insert_end a pointer to the last node of the chain (or NULL if the last node shall be determined)
universe@481 293 */
universe@481 294 void cx_linked_list_insert_chain(
universe@481 295 void **begin,
universe@481 296 void **end,
universe@481 297 ptrdiff_t loc_prev,
universe@481 298 ptrdiff_t loc_next,
universe@481 299 void *node,
universe@481 300 void *insert_begin,
universe@481 301 void *insert_end
universe@481 302 ) __attribute__((__nonnull__(6)));
universe@475 303
universe@475 304 /**
universe@473 305 * Removes a node from the linked list.
universe@473 306 *
universe@473 307 * If the node to remove is the begin (resp. end) node of the list and if \p begin (resp. \p end)
universe@473 308 * addresses are provided, the pointers are adjusted accordingly.
universe@473 309 *
universe@473 310 * The following combinations of arguments are valid (more arguments are optional):
universe@477 311 * \li \p loc_next and \p loc_prev (ancestor node is determined by using the prev pointer, overall O(1) performance)
universe@477 312 * \li \p loc_next and \p begin (ancestor node is determined by list traversal, overall O(n) performance)
universe@473 313 *
universe@476 314 * \remark The \c next and \c prev pointers of the removed node are not cleared by this function and may still be used
universe@476 315 * to traverse to a former adjacent node in the list.
universe@473 316 *
universe@473 317 * @param begin a pointer to the begin node pointer (optional)
universe@473 318 * @param end a pointer to the end node pointer (optional)
universe@473 319 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
universe@473 320 * @param loc_next the location of a \c next pointer within your node struct (required)
universe@473 321 * @param node the node to remove
universe@473 322 */
universe@481 323 void cx_linked_list_remove(
universe@481 324 void **begin,
universe@481 325 void **end,
universe@481 326 ptrdiff_t loc_prev,
universe@481 327 ptrdiff_t loc_next,
universe@481 328 void *node
universe@481 329 ) __attribute__((__nonnull__(5)));
universe@473 330
universe@473 331
universe@473 332 /**
universe@468 333 * Determines the size of a linked list starting with \p node.
universe@468 334 * @param node the first node
universe@468 335 * @param loc_next the location of the \c next pointer within the node struct
universe@468 336 * @return the size of the list or zero if \p node is \c NULL
universe@468 337 */
universe@481 338 size_t cx_linked_list_size(
universe@489 339 void const *node,
universe@481 340 ptrdiff_t loc_next
universe@481 341 );
universe@468 342
universe@468 343 /**
universe@468 344 * Sorts a linked list based on a comparison function.
universe@468 345 *
universe@639 346 * This function can work with linked lists of the following structure:
universe@468 347 * \code
universe@468 348 * typedef struct node node;
universe@468 349 * struct node {
universe@468 350 * node* prev;
universe@468 351 * node* next;
universe@639 352 * my_payload data;
universe@468 353 * }
universe@468 354 * \endcode
universe@468 355 *
universe@476 356 * @note This is a recursive function with at most logarithmic recursion depth.
universe@476 357 *
universe@468 358 * @param begin a pointer to the begin node pointer (required)
universe@468 359 * @param end a pointer to the end node pointer (optional)
universe@468 360 * @param loc_prev the location of a \c prev pointer within your node struct (negative if not present)
universe@468 361 * @param loc_next the location of a \c next pointer within your node struct (required)
universe@468 362 * @param loc_data the location of the \c data pointer within your node struct
universe@468 363 * @param cmp_func the compare function defining the sort order
universe@468 364 */
universe@481 365 void cx_linked_list_sort(
universe@481 366 void **begin,
universe@481 367 void **end,
universe@481 368 ptrdiff_t loc_prev,
universe@481 369 ptrdiff_t loc_next,
universe@481 370 ptrdiff_t loc_data,
universe@677 371 cx_compare_func cmp_func
universe@639 372 ) __attribute__((__nonnull__(1, 6)));
universe@473 373
universe@486 374
universe@486 375 /**
universe@486 376 * Compares two lists element wise.
universe@486 377 *
universe@488 378 * \note Both list must have the same structure.
universe@488 379 *
universe@486 380 * @param begin_left the begin of the left list (\c NULL denotes an empty list)
universe@486 381 * @param begin_right the begin of the right list (\c NULL denotes an empty list)
universe@486 382 * @param loc_advance the location of the pointer to advance
universe@486 383 * @param loc_data the location of the \c data pointer within your node struct
universe@486 384 * @param cmp_func the function to compare the elements
universe@552 385 * @return the first non-zero result of invoking \p cmp_func or: negative if the left list is smaller than the
universe@552 386 * right list, positive if the left list is larger than the right list, zero if both lists are equal.
universe@486 387 */
universe@486 388 int cx_linked_list_compare(
universe@489 389 void const *begin_left,
universe@489 390 void const *begin_right,
universe@486 391 ptrdiff_t loc_advance,
universe@486 392 ptrdiff_t loc_data,
universe@677 393 cx_compare_func cmp_func
universe@639 394 ) __attribute__((__nonnull__(5)));
universe@486 395
universe@473 396 /**
universe@473 397 * Reverses the order of the nodes in a linked list.
universe@473 398 *
universe@473 399 * @param begin a pointer to the begin node pointer (required)
universe@473 400 * @param end a pointer to the end node pointer (optional)
universe@473 401 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
universe@473 402 * @param loc_next the location of a \c next pointer within your node struct (required)
universe@473 403 */
universe@481 404 void cx_linked_list_reverse(
universe@481 405 void **begin,
universe@481 406 void **end,
universe@481 407 ptrdiff_t loc_prev,
universe@481 408 ptrdiff_t loc_next
universe@481 409 ) __attribute__((__nonnull__(1)));
universe@473 410
universe@415 411 #ifdef __cplusplus
universe@628 412 } // extern "C"
universe@415 413 #endif
universe@415 414
universe@628 415 #endif // UCX_LINKED_LIST_H

mercurial