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@453: size_t cxLinkedListRecalculateSize(CxList list); universe@453: 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@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@453: * @param loc_next the location of a \c next pointer within your node struct (negative if your struct does not have one) 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@415: #ifdef __cplusplus universe@415: } /* extern "C" */ universe@415: #endif universe@415: universe@398: #endif /* UCX_LINKED_LIST_H */