Tue, 04 Oct 2022 19:25:07 +0200
fix over-optimization of strstr
1. it's actually less performant to frequently read bytes
from an array instead of using the native word length
2. the SBO buffer should be local and not static to allow
multi-threading usage
/* * 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 */