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: * \version 3.0 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@400: #include universe@398: #include "list.h" universe@398: universe@415: #ifdef __cplusplus universe@415: extern "C" { universe@415: #endif universe@415: universe@466: /** universe@466: * Allocates a linked list for storing elements with \p item_size bytes each. universe@466: * universe@466: * Elements added to the list are copied. universe@466: * universe@466: * @param allocator the allocator for allocating the list nodes universe@466: * @param comparator the comparator for the elements universe@466: * @param item_size the size of each element in bytes universe@466: * @return the created list universe@466: */ universe@453: CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size); universe@453: universe@466: /** universe@466: * Allocates a linked list for storing pointers. universe@466: * universe@466: * If you want to store the elements directly in this list, use cxLinkedListCreate(). universe@466: * universe@466: * @param allocator the allocator for allocating the list nodes universe@466: * @param comparator the comparator for the elements universe@466: * @return the created list universe@466: */ universe@466: CxList cxPointerLinkedListCreate(CxAllocator allocator, CxListComparator comparator); universe@466: universe@466: /** universe@466: * Deallocates the memory of the entire list. universe@466: * universe@466: * \attention If this is a pointer list, the memory the pointers are referring to is \em not freed. universe@466: * universe@466: * @param list the list universe@466: */ universe@453: void cxLinkedListDestroy(CxList list); universe@453: universe@438: /** 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@438: void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index); universe@438: universe@453: /** universe@453: * Finds the last node in a linked list. universe@453: * universe@456: * The function starts with the pointer denoted by \p begin 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@456: * @param begin a pointer to the begin node universe@456: * @param loc_next the location of the \c next pointer universe@456: * @return a pointer to the last node or \c NULL if \p begin is \c NULL universe@453: */ universe@456: void *cx_linked_list_last(void *begin, ptrdiff_t loc_next); 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@473: void *cx_linked_list_prev(void *begin, ptrdiff_t loc_next, void *node); universe@473: universe@473: /** universe@453: * Adds a new node to a linked list. universe@453: * universe@453: * \remark One of the pointers \p begin and \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@453: void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node); universe@406: universe@468: /** 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@473: * \li \p loc_next and \p loc_prev universe@473: * \li \p loc_next and \p begin universe@473: * universe@473: * This function returns an adjacent node according to the following rules: universe@473: * \li if the node has only one adjacent node, that one is returned universe@473: * \li otherwise, the former \c prev node is returned universe@473: * universe@473: * \remark The \c next and \c prev pointers of the removed node are cleared by this function. 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: * @return an adjacent node or \c NULL, if this was the last node universe@473: */ universe@473: void *cx_linked_list_remove(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node); 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@468: size_t cx_linked_list_size(void *node, ptrdiff_t loc_next); universe@468: universe@468: /** universe@468: * Sorts a linked list based on a comparison function. universe@468: * universe@468: * This function can work with linked lists of the following structures: universe@468: * \code universe@468: * typedef struct node node; universe@468: * struct node { universe@468: * node* prev; universe@468: * node* next; universe@468: * my_payload data; // in this case set follow_ptr = 0 universe@468: * } universe@468: * universe@468: * typedef struct ptr_node ptr_node; universe@468: * struct ptr_node { universe@468: * ptr_node* prev; universe@468: * ptr_node* next; universe@468: * my_payload* data; // in this case set follow_ptr = 1 universe@468: * } universe@468: * \endcode universe@468: * 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 follow_ptr \c false if the pointer denoted by \p loc_data shall be passed to the \p cmp_func. universe@468: * If \c true, the data at \p loc_data is dereferenced, assuming to be a pointer, and then passed to \p cmp_func. universe@468: * @param cmp_func the compare function defining the sort order universe@468: */ universe@468: void cx_linked_list_sort(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, universe@468: ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func); universe@468: universe@473: 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@473: void cx_linked_list_reverse(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next); universe@473: universe@415: #ifdef __cplusplus universe@415: } /* extern "C" */ universe@415: #endif universe@415: universe@398: #endif /* UCX_LINKED_LIST_H */