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