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 list.h * \brief Interface for list implementations. * \author Mike Becker * \author Olaf Wintermann * \version 3.0 * \copyright 2-Clause BSD License */ #ifndef UCX_LIST_H #define UCX_LIST_H #include "common.h" #include "allocator.h" #include "iterator.h" #ifdef __cplusplus extern "C" { #endif /** * A comparator function comparing two list elements. */ typedef int(*CxListComparator)( void const *left, void const *right ); /** * List class type. */ typedef struct cx_list_class_s cx_list_class; /** * Structure for holding the base data of a list. */ struct cx_list_s { /** * The list class definition. */ cx_list_class *cl; /** * The allocator to use. */ CxAllocator const *allocator; /** * The comparator function for the elements. */ CxListComparator cmpfunc; /** * The size of each element (payload only). */ size_t itemsize; /** * The size of the list (number of currently stored elements). */ size_t size; /** * The capacity of the list (maximum number of elements). */ size_t capacity; union { /** * An optional simple destructor for the list contents that admits the free() interface. * * @remark Set content_destructor_type to #CX_DESTRUCTOR_SIMPLE. * * @attention Read the documentation of the particular list implementation * whether this destructor shall only destroy the contents or also free the memory. */ cx_destructor_func simple_destructor; /** * An optional advanced destructor for the list contents providing additional data. * * @remark Set content_destructor_type to #CX_DESTRUCTOR_ADVANCED. * * @attention Read the documentation of the particular list implementation * whether this destructor shall only destroy the contents or also free the memory. */ cx_advanced_destructor advanced_destructor; }; /** * The type of destructor to use. */ enum cx_destructor_type content_destructor_type; }; /** * The class definition for arbitrary lists. */ struct cx_list_class_s { /** * Destructor function. */ void (*destructor)(struct cx_list_s *list); /** * Member function for adding an element. */ int (*add)( struct cx_list_s *list, void const *elem ); /** * Member function for inserting an element. */ int (*insert)( struct cx_list_s *list, size_t index, void const *elem ); /** * Member function for inserting an element relative to an iterator position. */ int (*insert_iter)( struct cx_iterator_s *iter, void const *elem, int prepend ); /** * Member function for removing an element. */ int (*remove)( struct cx_list_s *list, size_t index ); /** * Member function for element lookup. */ void *(*at)( struct cx_list_s const *list, size_t index ); /** * Member function for finding an element. */ size_t (*find)( struct cx_list_s const *list, void const *elem ); /** * Member function for sorting the list in place. */ void (*sort)(struct cx_list_s *list); /** * Member function for comparing this list to another list of the same type. */ int (*compare)( struct cx_list_s const *list, struct cx_list_s const *other ); /** * Member function for reversing the order of the items. */ void (*reverse)(struct cx_list_s *list); /** * Returns an iterator pointing to the specified index. */ struct cx_iterator_s (*iterator)( struct cx_list_s *list, size_t index ); }; /** * Common type for all list implementations. */ typedef struct cx_list_s CxList; /** * Adds an item to the end of the list. * * @param list the list * @param elem a pointer to the element to add * @return zero on success, non-zero on memory allocation failure */ __attribute__((__nonnull__)) static inline int cxListAdd( CxList *list, void const *elem ) { return list->cl->add(list, elem); } /** * Inserts an item at the specified index. * * If \p index equals the list \c size, this is effectively cxListAdd(). * * @param list the list * @param index the index the element shall have * @param elem a pointer to the element to add * @return zero on success, non-zero on memory allocation failure * or when the index is out of bounds * @see cxListInsertAfter() * @see cxListInsertBefore() */ __attribute__((__nonnull__)) static inline int cxListInsert( CxList *list, size_t index, void const *elem ) { return list->cl->insert(list, index, elem); } /** * Inserts an element after the current location of the specified iterator. * * The used iterator remains operational, but all other active iterators should * be considered invalidated. * * If \p iter is not a list iterator, the behavior is undefined. * If \p iter is a past-the-end iterator, the new element gets appended to the list. * * @param iter an iterator * @param elem the element to insert * @return zero on success, non-zero on memory allocation failure * @see cxListInsert() * @see cxListInsertBefore() */ __attribute__((__nonnull__)) static inline int cxListInsertAfter( CxIterator *iter, void const *elem ) { return ((struct cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 0); } /** * Inserts an element before the current location of the specified iterator. * * The used iterator remains operational, but all other active iterators should * be considered invalidated. * * If \p iter is not a list iterator, the behavior is undefined. * If \p iter is a past-the-end iterator, the new element gets appended to the list. * * @param iter an iterator * @param elem the element to insert * @return zero on success, non-zero on memory allocation failure * @see cxListInsert() * @see cxListInsertAfter() */ __attribute__((__nonnull__)) static inline int cxListInsertBefore( CxIterator *iter, void const *elem ) { return ((struct cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 1); } /** * Removes the element at the specified index. * @param list the list * @param index the index of the element * @return zero on success, non-zero if the index is out of bounds */ __attribute__((__nonnull__)) static inline int cxListRemove( CxList *list, size_t index ) { return list->cl->remove(list, index); } /** * Returns a pointer to the element at the specified index. * * @param list the list * @param index the index of the element * @return a pointer to the element or \c NULL if the index is out of bounds */ __attribute__((__nonnull__)) static inline void *cxListAt( CxList *list, size_t index ) { return list->cl->at(list, index); } /** * Returns an iterator pointing to the item at the specified index. * * The returned iterator is position-aware. * * If the index is out of range, a past-the-end iterator will be returned. * * @param list the list * @param index the index where the iterator shall point at * @return a new iterator */ __attribute__((__nonnull__, __warn_unused_result__)) static inline CxIterator cxListIterator( CxList *list, size_t index ) { return list->cl->iterator(list, index); } /** * Returns an iterator pointing to the first item of the list. * * The returned iterator is position-aware. * * If the list is empty, a past-the-end iterator will be returned. * * @param list the list * @return a new iterator */ __attribute__((__nonnull__, __warn_unused_result__)) static inline CxIterator cxListBegin(CxList *list) { return list->cl->iterator(list, 0); } /** * Returns the index of the first element that equals \p elem. * * Determining equality is performed by the list's comparator function. * * @param list the list * @param elem the element to find * @return the index of the element or \c (size+1) if the element is not found */ __attribute__((__nonnull__)) static inline size_t cxListFind( CxList *list, void const *elem ) { return list->cl->find(list, elem); } /** * Sorts the list in place. * * \remark The underlying sort algorithm is implementation defined. * * @param list the list */ __attribute__((__nonnull__)) static inline void cxListSort(CxList *list) { list->cl->sort(list); } /** * Reverses the order of the items. * * @param list the list */ __attribute__((__nonnull__)) static inline void cxListReverse(CxList *list) { list->cl->reverse(list); } /** * Compares a list to another list of the same type. * * First, the list sizes are compared. If they match, the lists are compared element-wise. * * @param list the list * @param other the list to compare to * @return zero, if both lists are equal element wise, negative if the first list is smaller, zero if the first list is larger */ __attribute__((__nonnull__)) static inline int cxListCompare( CxList *list, CxList *other ) { return list->cl->compare(list, other); } /** * Deallocates the memory of the specified list structure. * * Also calls content a destructor function, depending on the configuration * in CxList.content_destructor_type. * * This function itself is a destructor function for the CxList. * * @param list the list which shall be destroyed */ __attribute__((__nonnull__)) void cxListDestroy(CxList *list); #ifdef __cplusplus } /* extern "C" */ #endif #endif /* UCX_LIST_H */