universe@398: /*
universe@398:  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
universe@398:  *
universe@398:  * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
universe@398:  *
universe@398:  * Redistribution and use in source and binary forms, with or without
universe@398:  * modification, are permitted provided that the following conditions are met:
universe@398:  *
universe@398:  *   1. Redistributions of source code must retain the above copyright
universe@398:  *      notice, this list of conditions and the following disclaimer.
universe@398:  *
universe@398:  *   2. Redistributions in binary form must reproduce the above copyright
universe@398:  *      notice, this list of conditions and the following disclaimer in the
universe@398:  *      documentation and/or other materials provided with the distribution.
universe@398:  *
universe@398:  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
universe@398:  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
universe@398:  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
universe@398:  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
universe@398:  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
universe@398:  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
universe@398:  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
universe@398:  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
universe@398:  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
universe@398:  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
universe@398:  * POSSIBILITY OF SUCH DAMAGE.
universe@398:  */
universe@453: /**
universe@453:  * \file linked_list.h
universe@453:  * \brief Linked list implementation.
universe@453:  * \details Also provides several low-level functions for custom linked list implementations.
universe@453:  * \author Mike Becker
universe@453:  * \author Olaf Wintermann
universe@453:  * \copyright 2-Clause BSD License
universe@453:  */
universe@398: 
universe@398: #ifndef UCX_LINKED_LIST_H
universe@398: #define UCX_LINKED_LIST_H
universe@398: 
universe@484: #include "common.h"
universe@398: #include "list.h"
universe@398: 
universe@415: #ifdef __cplusplus
universe@415: extern "C" {
universe@415: #endif
universe@415: 
universe@466: /**
universe@807:  * The maximum item size that uses SBO swap instead of relinking.
universe@647:  */
universe@807: extern unsigned cx_linked_list_swap_sbo_size;
universe@647: 
universe@647: /**
universe@466:  * Allocates a linked list for storing elements with \p item_size bytes each.
universe@466:  *
universe@669:  * If \p item_size is CX_STORE_POINTERS, the created list will be created as if
universe@763:  * cxListStorePointers() was called immediately after creation and the compare
universe@763:  * function will be automatically set to cx_cmp_ptr(), if none is given.
universe@669:  *
universe@466:  * @param allocator the allocator for allocating the list nodes
universe@670:  * (if \c NULL the cxDefaultAllocator will be used)
universe@466:  * @param comparator the comparator for the elements
universe@763:  * (if \c NULL, and the list is not storing pointers, sort and find
universe@763:  * functions will not work)
universe@466:  * @param item_size the size of each element in bytes
universe@466:  * @return the created list
universe@466:  */
universe@500: CxList *cxLinkedListCreate(
universe@508:         CxAllocator const *allocator,
universe@677:         cx_compare_func comparator,
universe@481:         size_t item_size
universe@670: );
universe@453: 
universe@466: /**
universe@662:  * Allocates a linked list for storing elements with \p item_size bytes each.
universe@662:  *
universe@662:  * The list will use cxDefaultAllocator and no comparator function. If you want
universe@662:  * to call functions that need a comparator, you must either set one immediately
universe@662:  * after list creation or use cxLinkedListCreate().
universe@662:  *
universe@669:  * If \p item_size is CX_STORE_POINTERS, the created list will be created as if
universe@763:  * cxListStorePointers() was called immediately after creation and the compare
universe@763:  * function will be automatically set to cx_cmp_ptr().
universe@669:  *
universe@662:  * @param item_size the size of each element in bytes
universe@662:  * @return the created list
universe@662:  */
universe@670: #define cxLinkedListCreateSimple(item_size) \
universe@670:     cxLinkedListCreate(NULL, NULL, item_size)
universe@662: 
universe@662: /**
universe@438:  * Finds the node at a certain index.
universe@438:  *
universe@438:  * This function can be used to start at an arbitrary position within the list.
universe@438:  * If the search index is large than the start index, \p loc_advance must denote
universe@438:  * the location of some sort of \c next pointer (i.e. a pointer to the next node).
universe@438:  * But it is also possible that the search index is smaller than the start index
universe@438:  * (e.g. in cases where traversing a list backwards is faster) in which case
universe@438:  * \p loc_advance must denote the location of some sort of \c prev pointer
universe@438:  * (i.e. a pointer to the previous node).
universe@438:  *
universe@438:  * @param start a pointer to the start node
universe@438:  * @param start_index the start index
universe@438:  * @param loc_advance the location of the pointer to advance
universe@438:  * @param index the search index
universe@438:  * @return the node found at the specified index
universe@438:  */
universe@481: void *cx_linked_list_at(
universe@508:         void const *start,
universe@481:         size_t start_index,
universe@481:         ptrdiff_t loc_advance,
universe@481:         size_t index
universe@481: ) __attribute__((__nonnull__));
universe@438: 
universe@453: /**
universe@480:  * Finds the index of an element within a linked list.
universe@480:  *
universe@480:  * @param start a pointer to the start node
universe@480:  * @param loc_advance the location of the pointer to advance
universe@480:  * @param loc_data the location of the \c data pointer within your node struct
universe@480:  * @param cmp_func a compare function to compare \p elem against the node data
universe@480:  * @param elem a pointer to the element to find
universe@699:  * @return the index of the element or a negative value if it could not be found
universe@480:  */
universe@699: ssize_t cx_linked_list_find(
universe@489:         void const *start,
universe@481:         ptrdiff_t loc_advance,
universe@481:         ptrdiff_t loc_data,
universe@677:         cx_compare_func cmp_func,
universe@489:         void const *elem
universe@481: ) __attribute__((__nonnull__));
universe@480: 
universe@480: /**
universe@764:  * Finds the node containing an element within a linked list.
universe@764:  *
universe@764:  * @param result a pointer to the memory where the node pointer (or \c NULL if the element
universe@764:  * could not be found) shall be stored to
universe@764:  * @param start a pointer to the start node
universe@764:  * @param loc_advance the location of the pointer to advance
universe@764:  * @param loc_data the location of the \c data pointer within your node struct
universe@764:  * @param cmp_func a compare function to compare \p elem against the node data
universe@764:  * @param elem a pointer to the element to find
universe@764:  * @return the index of the element or a negative value if it could not be found
universe@764:  */
universe@764: ssize_t cx_linked_list_find_node(
universe@764:         void **result,
universe@764:         void const *start,
universe@764:         ptrdiff_t loc_advance,
universe@764:         ptrdiff_t loc_data,
universe@764:         cx_compare_func cmp_func,
universe@764:         void const *elem
universe@764: ) __attribute__((__nonnull__));
universe@764: 
universe@764: /**
universe@475:  * Finds the first node in a linked list.
universe@475:  *
universe@475:  * The function starts with the pointer denoted by \p node and traverses the list
universe@475:  * along a prev pointer whose location within the node struct is
universe@475:  * denoted by \p loc_prev.
universe@475:  *
universe@475:  * @param node a pointer to a node in the list
universe@475:  * @param loc_prev the location of the \c prev pointer
universe@485:  * @return a pointer to the first node
universe@475:  */
universe@481: void *cx_linked_list_first(
universe@508:         void const *node,
universe@481:         ptrdiff_t loc_prev
universe@481: ) __attribute__((__nonnull__));
universe@475: 
universe@475: /**
universe@453:  * Finds the last node in a linked list.
universe@453:  *
universe@475:  * The function starts with the pointer denoted by \p node and traverses the list
universe@456:  * along a next pointer whose location within the node struct is
universe@453:  * denoted by \p loc_next.
universe@453:  *
universe@475:  * @param node a pointer to a node in the list
universe@456:  * @param loc_next the location of the \c next pointer
universe@478:  * @return a pointer to the last node
universe@453:  */
universe@481: void *cx_linked_list_last(
universe@508:         void const *node,
universe@481:         ptrdiff_t loc_next
universe@481: ) __attribute__((__nonnull__));
universe@398: 
universe@453: /**
universe@473:  * Finds the predecessor of a node in case it is not linked.
universe@473:  *
universe@473:  * \remark If \p node is not contained in the list starting with \p begin, the behavior is undefined.
universe@473:  *
universe@473:  * @param begin the node where to start the search
universe@473:  * @param loc_next the location of the \c next pointer
universe@473:  * @param node the successor of the node to find
universe@473:  * @return the node or \c NULL if \p node has no predecessor
universe@473:  */
universe@481: void *cx_linked_list_prev(
universe@508:         void const *begin,
universe@481:         ptrdiff_t loc_next,
universe@508:         void const *node
universe@481: ) __attribute__((__nonnull__));
universe@473: 
universe@473: /**
universe@453:  * Adds a new node to a linked list.
universe@475:  * The node must not be part of any list already.
universe@453:  *
universe@478:  * \remark One of the pointers \p begin or \p end may be \c NULL, but not both.
universe@453:  *
universe@453:  * @param begin a pointer to the begin node pointer (if your list has one)
universe@453:  * @param end a pointer to the end node pointer (if your list has one)
universe@453:  * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
universe@473:  * @param loc_next the location of a \c next pointer within your node struct (required)
universe@453:  * @param new_node a pointer to the node that shall be appended
universe@453:  */
universe@481: void cx_linked_list_add(
universe@481:         void **begin,
universe@481:         void **end,
universe@481:         ptrdiff_t loc_prev,
universe@481:         ptrdiff_t loc_next,
universe@481:         void *new_node
universe@481: ) __attribute__((__nonnull__(5)));
universe@406: 
universe@468: /**
universe@475:  * Prepends a new node to a linked list.
universe@475:  * The node must not be part of any list already.
universe@475:  *
universe@478:  * \remark One of the pointers \p begin or \p end may be \c NULL, but not both.
universe@475:  *
universe@475:  * @param begin a pointer to the begin node pointer (if your list has one)
universe@475:  * @param end a pointer to the end node pointer (if your list has one)
universe@475:  * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
universe@475:  * @param loc_next the location of a \c next pointer within your node struct (required)
universe@475:  * @param new_node a pointer to the node that shall be prepended
universe@475:  */
universe@481: void cx_linked_list_prepend(
universe@481:         void **begin,
universe@481:         void **end,
universe@481:         ptrdiff_t loc_prev,
universe@481:         ptrdiff_t loc_next,
universe@481:         void *new_node
universe@481: ) __attribute__((__nonnull__(5)));
universe@481: 
universe@481: /**
universe@481:  * Links two nodes.
universe@481:  *
universe@481:  * @param left the new predecessor of \p right
universe@481:  * @param right the new successor of \p left
universe@481:  * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
universe@481:  * @param loc_next the location of a \c next pointer within your node struct (required)
universe@481:  */
universe@481: void cx_linked_list_link(
universe@481:         void *left,
universe@481:         void *right,
universe@481:         ptrdiff_t loc_prev,
universe@481:         ptrdiff_t loc_next
universe@481: ) __attribute__((__nonnull__));
universe@481: 
universe@481: /**
universe@481:  * Unlinks two nodes.
universe@481:  *
universe@481:  * If right is not the successor of left, the behavior is undefined.
universe@481:  *
universe@481:  * @param left the predecessor of \p right
universe@481:  * @param right the successor of \p left
universe@481:  * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
universe@481:  * @param loc_next the location of a \c next pointer within your node struct (required)
universe@481:  */
universe@481: void cx_linked_list_unlink(
universe@481:         void *left,
universe@481:         void *right,
universe@481:         ptrdiff_t loc_prev,
universe@481:         ptrdiff_t loc_next
universe@481: ) __attribute__((__nonnull__));
universe@481: 
universe@481: /**
universe@481:  * Inserts a new node after a given node of a linked list.
universe@481:  * The new node must not be part of any list already.
universe@481:  *
universe@481:  * \note If you specify \c NULL as the \p node to insert after, this function needs either the \p begin or
universe@481:  * the \p end pointer to determine the start of the list. Then the new node will be prepended to the list.
universe@481:  *
universe@481:  * @param begin a pointer to the begin node pointer (if your list has one)
universe@481:  * @param end a pointer to the end node pointer (if your list has one)
universe@481:  * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
universe@481:  * @param loc_next the location of a \c next pointer within your node struct (required)
universe@481:  * @param node the node after which to insert (\c NULL if you want to prepend the node to the list)
universe@481:  * @param new_node a pointer to the node that shall be prepended
universe@481:  */
universe@481: void cx_linked_list_insert(
universe@481:         void **begin,
universe@481:         void **end,
universe@481:         ptrdiff_t loc_prev,
universe@481:         ptrdiff_t loc_next,
universe@481:         void *node,
universe@481:         void *new_node
universe@481: ) __attribute__((__nonnull__(6)));
universe@481: 
universe@481: /**
universe@481:  * Inserts a chain of nodes after a given node of a linked list.
universe@481:  * The chain must not be part of any list already.
universe@481:  *
universe@481:  * If you do not explicitly specify the end of the chain, it will be determined by traversing
universe@481:  * the \c next pointer.
universe@481:  *
universe@481:  * \note If you specify \c NULL as the \p node to insert after, this function needs either the \p begin or
universe@481:  * the \p end pointer to determine the start of the list. If only the \p end pointer is specified, you also need
universe@481:  * to provide a valid \p loc_prev location.
universe@481:  * Then the chain will be prepended to the list.
universe@481:  *
universe@481:  * @param begin a pointer to the begin node pointer (if your list has one)
universe@481:  * @param end a pointer to the end node pointer (if your list has one)
universe@481:  * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
universe@481:  * @param loc_next the location of a \c next pointer within your node struct (required)
universe@481:  * @param node the node after which to insert (\c NULL to prepend the chain to the list)
universe@481:  * @param insert_begin a pointer to the first node of the chain that shall be inserted
universe@481:  * @param insert_end a pointer to the last node of the chain (or NULL if the last node shall be determined)
universe@481:  */
universe@481: void cx_linked_list_insert_chain(
universe@481:         void **begin,
universe@481:         void **end,
universe@481:         ptrdiff_t loc_prev,
universe@481:         ptrdiff_t loc_next,
universe@481:         void *node,
universe@481:         void *insert_begin,
universe@481:         void *insert_end
universe@481: ) __attribute__((__nonnull__(6)));
universe@475: 
universe@475: /**
universe@473:  * Removes a node from the linked list.
universe@473:  *
universe@473:  * If the node to remove is the begin (resp. end) node of the list and if \p begin (resp. \p end)
universe@473:  * addresses are provided, the pointers are adjusted accordingly.
universe@473:  *
universe@473:  * The following combinations of arguments are valid (more arguments are optional):
universe@477:  * \li \p loc_next and \p loc_prev (ancestor node is determined by using the prev pointer, overall O(1) performance)
universe@477:  * \li \p loc_next and \p begin (ancestor node is determined by list traversal, overall O(n) performance)
universe@473:  *
universe@476:  * \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:  * to traverse to a former adjacent node in the list.
universe@473:  *
universe@473:  * @param begin a pointer to the begin node pointer (optional)
universe@473:  * @param end a pointer to the end node pointer (optional)
universe@473:  * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
universe@473:  * @param loc_next the location of a \c next pointer within your node struct (required)
universe@473:  * @param node the node to remove
universe@473:  */
universe@481: void cx_linked_list_remove(
universe@481:         void **begin,
universe@481:         void **end,
universe@481:         ptrdiff_t loc_prev,
universe@481:         ptrdiff_t loc_next,
universe@481:         void *node
universe@481: ) __attribute__((__nonnull__(5)));
universe@473: 
universe@473: 
universe@473: /**
universe@468:  * Determines the size of a linked list starting with \p node.
universe@468:  * @param node the first node
universe@468:  * @param loc_next the location of the \c next pointer within the node struct
universe@468:  * @return the size of the list or zero if \p node is \c NULL
universe@468:  */
universe@481: size_t cx_linked_list_size(
universe@489:         void const *node,
universe@481:         ptrdiff_t loc_next
universe@481: );
universe@468: 
universe@468: /**
universe@468:  * Sorts a linked list based on a comparison function.
universe@468:  *
universe@639:  * This function can work with linked lists of the following structure:
universe@468:  * \code
universe@468:  * typedef struct node node;
universe@468:  * struct node {
universe@468:  *   node* prev;
universe@468:  *   node* next;
universe@639:  *   my_payload data;
universe@468:  * }
universe@468:  * \endcode
universe@468:  *
universe@476:  * @note This is a recursive function with at most logarithmic recursion depth.
universe@476:  *
universe@468:  * @param begin a pointer to the begin node pointer (required)
universe@468:  * @param end a pointer to the end node pointer (optional)
universe@468:  * @param loc_prev the location of a \c prev pointer within your node struct (negative if not present)
universe@468:  * @param loc_next the location of a \c next pointer within your node struct (required)
universe@468:  * @param loc_data the location of the \c data pointer within your node struct
universe@468:  * @param cmp_func the compare function defining the sort order
universe@468:  */
universe@481: void cx_linked_list_sort(
universe@481:         void **begin,
universe@481:         void **end,
universe@481:         ptrdiff_t loc_prev,
universe@481:         ptrdiff_t loc_next,
universe@481:         ptrdiff_t loc_data,
universe@677:         cx_compare_func cmp_func
universe@639: ) __attribute__((__nonnull__(1, 6)));
universe@473: 
universe@486: 
universe@486: /**
universe@486:  * Compares two lists element wise.
universe@486:  *
universe@488:  * \note Both list must have the same structure.
universe@488:  *
universe@486:  * @param begin_left the begin of the left list (\c NULL denotes an empty list)
universe@486:  * @param begin_right the begin of the right list  (\c NULL denotes an empty list)
universe@486:  * @param loc_advance the location of the pointer to advance
universe@486:  * @param loc_data the location of the \c data pointer within your node struct
universe@486:  * @param cmp_func the function to compare the elements
universe@552:  * @return the first non-zero result of invoking \p cmp_func or: negative if the left list is smaller than the
universe@552:  * right list, positive if the left list is larger than the right list, zero if both lists are equal.
universe@486:  */
universe@486: int cx_linked_list_compare(
universe@489:         void const *begin_left,
universe@489:         void const *begin_right,
universe@486:         ptrdiff_t loc_advance,
universe@486:         ptrdiff_t loc_data,
universe@677:         cx_compare_func cmp_func
universe@639: ) __attribute__((__nonnull__(5)));
universe@486: 
universe@473: /**
universe@473:  * Reverses the order of the nodes in a linked list.
universe@473:  *
universe@473:  * @param begin a pointer to the begin node pointer (required)
universe@473:  * @param end a pointer to the end node pointer (optional)
universe@473:  * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
universe@473:  * @param loc_next the location of a \c next pointer within your node struct (required)
universe@473:  */
universe@481: void cx_linked_list_reverse(
universe@481:         void **begin,
universe@481:         void **end,
universe@481:         ptrdiff_t loc_prev,
universe@481:         ptrdiff_t loc_next
universe@481: ) __attribute__((__nonnull__(1)));
universe@473: 
universe@415: #ifdef __cplusplus
universe@628: } // extern "C"
universe@415: #endif
universe@415: 
universe@628: #endif // UCX_LINKED_LIST_H