ucx/cx/linked_list.h

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