Sun, 23 Oct 2022 16:49:35 +0200
#216 test hashing functions
/* * 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 * \version 3.0 * \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 /** * Allocates a linked list for storing elements with \p item_size bytes each. * * @remark Elements added to the list are copied, therefore a possible destructor * MUST NOT free the memory pointed to by its argument. * * @param allocator the allocator for allocating the list nodes * @param comparator the comparator for the elements * @param item_size the size of each element in bytes * @return the created list */ CxList *cxLinkedListCreate( CxAllocator const *allocator, CxListComparator comparator, size_t item_size ) __attribute__((__nonnull__)); /** * Allocates a linked list for storing pointers. * * If you want to store the elements directly in this list, use cxLinkedListCreate(). * * @remark Since only pointers are stored in this list, a possible destructor * MAY free the memory pointed to by its argument in order to prevent memory leaks. * * @param allocator the allocator for allocating the list nodes * @param comparator the comparator for the elements * @return the created list */ CxList *cxPointerLinkedListCreate( CxAllocator const *allocator, CxListComparator comparator ) __attribute__((__nonnull__)); /** * Creates a linked list using the data from an array. * * @remark Elements added to the list are copied, therefore a possible destructor * MUST NOT free the memory pointed to by its argument. * * @param allocator the allocator for allocating the list nodes * @param comparator the comparator for the elements * @param item_size the size of one item in the array * @param num_items the number of items * @param array the array data * @return the created list */ CxList *cxLinkedListFromArray( CxAllocator const *allocator, CxListComparator comparator, size_t item_size, size_t num_items, void const *array ) __attribute__((__nonnull__)); /** * 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 */ void *cx_linked_list_at( void const *start, size_t start_index, ptrdiff_t loc_advance, size_t index ) __attribute__((__nonnull__)); /** * 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 follow_ptr \c false if the pointer denoted by \p loc_data shall be passed to the \p cmp_func. * If \c true, the data at \p loc_data is assumed to be a pointer, dereferenced, and then passed to \p cmp_func. * @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 past-one index if the element could not be found */ size_t cx_linked_list_find( void const *start, ptrdiff_t loc_advance, ptrdiff_t loc_data, bool follow_ptr, CxListComparator cmp_func, void const *elem ) __attribute__((__nonnull__)); /** * 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 */ void *cx_linked_list_first( void const *node, ptrdiff_t loc_prev ) __attribute__((__nonnull__)); /** * 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 */ void *cx_linked_list_last( void const *node, ptrdiff_t loc_next ) __attribute__((__nonnull__)); /** * 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 */ void *cx_linked_list_prev( void const *begin, ptrdiff_t loc_next, void const *node ) __attribute__((__nonnull__)); /** * 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 */ void cx_linked_list_add( void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node ) __attribute__((__nonnull__(5))); /** * 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 */ void cx_linked_list_prepend( void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node ) __attribute__((__nonnull__(5))); /** * 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) */ void cx_linked_list_link( void *left, void *right, ptrdiff_t loc_prev, ptrdiff_t loc_next ) __attribute__((__nonnull__)); /** * 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) */ void cx_linked_list_unlink( void *left, void *right, ptrdiff_t loc_prev, ptrdiff_t loc_next ) __attribute__((__nonnull__)); /** * 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 prepended */ void cx_linked_list_insert( void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node, void *new_node ) __attribute__((__nonnull__(6))); /** * 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) */ 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 ) __attribute__((__nonnull__(6))); /** * 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 */ void cx_linked_list_remove( void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node ) __attribute__((__nonnull__(5))); /** * 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( void const *node, ptrdiff_t loc_next ); /** * Sorts a linked list based on a comparison function. * * This function can work with linked lists of the following structures: * \code * typedef struct node node; * struct node { * node* prev; * node* next; * my_payload data; // in this case set follow_ptr = 0 * } * * typedef struct ptr_node ptr_node; * struct ptr_node { * ptr_node* prev; * ptr_node* next; * my_payload* data; // in this case set follow_ptr = 1 * } * \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 follow_ptr \c false if the pointer denoted by \p loc_data shall be passed to the \p cmp_func. * If \c true, the data at \p loc_data is assumed to be a pointer, dereferenced, and then passed to \p cmp_func. * @param cmp_func the compare function defining the sort order */ void cx_linked_list_sort( void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, ptrdiff_t loc_data, bool follow_ptr, CxListComparator cmp_func ) __attribute__((__nonnull__(1, 7))); /** * Compares two lists element wise. * * The \c follow_ptr flags have the following meaning: if \c false, the pointer denoted by \p loc_data shall * directly be passed to the \p cmp_func. * If \c true, the data at \p loc_data is assumed to be a pointer, dereferenced, and then passed to \p cmp_func. * * \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 follow_ptr_left indicates whether pointers in the left list shall be dereferenced * @param follow_ptr_right indicates whether pointers in the right list shall be dereferenced * @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. */ int cx_linked_list_compare( void const *begin_left, void const *begin_right, ptrdiff_t loc_advance, ptrdiff_t loc_data, bool follow_ptr_left, bool follow_ptr_right, CxListComparator cmp_func ) __attribute__((__nonnull__(7))); /** * 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) */ void cx_linked_list_reverse( void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next ) __attribute__((__nonnull__(1))); #ifdef __cplusplus } /* extern "C" */ #endif #endif /* UCX_LINKED_LIST_H */