universe@390: /* universe@390: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. universe@390: * universe@390: * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved. universe@390: * universe@390: * Redistribution and use in source and binary forms, with or without universe@390: * modification, are permitted provided that the following conditions are met: universe@390: * universe@390: * 1. Redistributions of source code must retain the above copyright universe@390: * notice, this list of conditions and the following disclaimer. universe@390: * universe@390: * 2. Redistributions in binary form must reproduce the above copyright universe@390: * notice, this list of conditions and the following disclaimer in the universe@390: * documentation and/or other materials provided with the distribution. universe@390: * universe@390: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" universe@390: * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE universe@390: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE universe@390: * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE universe@390: * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR universe@390: * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF universe@390: * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS universe@390: * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN universe@390: * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) universe@390: * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE universe@390: * POSSIBILITY OF SUCH DAMAGE. universe@390: */ universe@453: /** universe@453: * \file list.h universe@453: * \brief Interface for 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@390: universe@390: #ifndef UCX_LIST_H universe@390: #define UCX_LIST_H universe@390: universe@398: #include universe@398: #include "allocator.h" universe@398: universe@415: #ifdef __cplusplus universe@415: extern "C" { universe@415: #endif universe@415: universe@464: /** universe@464: * A comparator function comparing two list elements. universe@464: */ universe@412: typedef int(*CxListComparator)(void const *left, void const *right); universe@398: universe@464: /** universe@464: * Internal type for the list structure - use CxList instead. universe@464: */ universe@435: typedef struct cx_list_s cx_list_s; universe@435: universe@464: /** universe@464: * The class definition for arbitrary lists. universe@464: */ universe@398: typedef struct { universe@464: /** universe@464: * Member function for adding an element. universe@464: */ universe@435: int (*add)(cx_list_s *list, void *elem); universe@435: universe@464: /** universe@464: * Member function for inserting an element. universe@464: */ universe@435: int (*insert)(cx_list_s *list, size_t index, void *elem); universe@435: universe@464: /** universe@464: * Member function for removing an element. universe@464: */ universe@438: int (*remove)(cx_list_s *list, size_t index); universe@435: universe@464: /** universe@464: * Member function for element lookup. universe@464: */ universe@439: void *(*at)(cx_list_s *list, size_t index); universe@439: universe@464: /** universe@464: * Member function for finding an element. universe@464: */ universe@435: size_t (*find)(cx_list_s *list, void *elem); universe@435: universe@464: /** universe@469: * Member function for sorting the list in place. universe@469: */ universe@469: void (*sort)(cx_list_s *list); universe@435: } cx_list_class; universe@435: universe@464: /** universe@464: * Structure for holding the base data of a list. universe@464: */ universe@435: struct cx_list_s { universe@464: /** universe@464: * The list class definition. universe@464: */ universe@435: cx_list_class *cl; universe@464: /** universe@464: * The allocator to use. universe@464: */ universe@398: CxAllocator allocator; universe@464: /** universe@464: * The comparator function for the elements. universe@464: */ universe@398: CxListComparator cmpfunc; universe@464: /** universe@464: * The size of each element (payload only). universe@464: */ universe@401: size_t itemsize; universe@464: /** universe@464: * The size of the list (number of currently stored elements). universe@464: */ universe@401: size_t size; universe@464: /** universe@464: * The capacity of the list (maximum number of elements). universe@464: */ universe@401: size_t capacity; universe@435: }; universe@398: universe@464: /** universe@464: * Common type for all list implementations. universe@464: */ universe@412: typedef cx_list_s *CxList; universe@398: universe@464: /** universe@464: * Adds an item to the end of the list. universe@464: * universe@464: * \remark It is implementation defined whether universe@464: * the contents of the element are copied or the universe@464: * pointer is added to the list. In the latter case universe@464: * the \c itemsize of the list SHALL be \c sizeof(void*). universe@464: * universe@464: * @param list the list universe@464: * @param elem a pointer to the element to add universe@464: * @return zero on success, non-zero on memory allocation failure universe@464: */ universe@469: static inline int cxListAdd(CxList list, void *elem) { universe@469: return list->cl->add(list, elem); universe@469: } universe@398: universe@464: /** universe@464: * Inserts an item at the specified index. universe@464: * universe@464: * If \p index equals the list \c size, this is effectively cxListAdd(). universe@464: * universe@464: * \remark It is implementation defined whether universe@464: * the contents of the element are copied or the universe@464: * pointer is added to the list. In the latter case universe@464: * the \c itemsize of the list SHALL be \c sizeof(void*). universe@464: * universe@464: * @param list the list universe@464: * @param index the index the element shall have universe@464: * @param elem a pointer to the element to add universe@464: * @return zero on success, non-zero on memory allocation failure universe@464: * or when the index is out of bounds universe@464: */ universe@469: static inline int cxListInsert(CxList list, size_t index, void *elem) { universe@469: return list->cl->insert(list, index, elem); universe@469: } universe@398: universe@464: /** universe@464: * Removes the element at the specified index. universe@464: * @param list the list universe@464: * @param index the index of the element universe@464: * @return zero on success, non-zero if the index is out of bounds universe@464: */ universe@469: static inline int cxListRemove(CxList list, size_t index) { universe@469: return list->cl->remove(list, index); universe@469: } universe@398: universe@464: /** universe@464: * Returns a pointer to the element at the specified index. universe@464: * universe@464: * @param list the list universe@464: * @param index the index of the element universe@464: * @return a pointer to the element or \c NULL if the index is out of bounds universe@464: */ universe@469: static inline void *cxListAt(CxList list, size_t index) { universe@469: return list->cl->at(list, index); universe@469: } universe@439: universe@464: /** universe@464: * Returns the index of the first element that equals \p elem. universe@464: * universe@464: * Determining equality is performed by the list's comparator function. universe@464: * universe@464: * @param list the list universe@464: * @param elem the element to find universe@464: * @return the index of the element or \c (size+1) if the element is not found universe@464: */ universe@469: static inline size_t cxListFind(CxList list, void *elem) { universe@469: return list->cl->find(list, elem); universe@469: } universe@398: universe@464: /** universe@469: * Sorts the list in place. universe@469: * universe@469: * \remark The underlying sort algorithm is implementation defined. universe@469: * universe@469: * @param list the list universe@469: */ universe@469: static inline void cxListSort(CxList list) { universe@469: list->cl->sort(list); universe@469: } universe@404: universe@415: #ifdef __cplusplus universe@415: } /* extern "C" */ universe@415: #endif universe@415: universe@393: #endif /* UCX_LIST_H */