Thu, 03 Oct 2024 18:24:13 +0200
add upload dir action
/* * 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 * \copyright 2-Clause BSD License */ #ifndef UCX_LIST_H #define UCX_LIST_H #include "common.h" #include "collection.h" #ifdef __cplusplus extern "C" { #endif /** * 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 { CX_COLLECTION_MEMBERS /** * The list class definition. */ cx_list_class const *cl; /** * The actual implementation in case the list class is delegating. */ cx_list_class const *climpl; }; /** * The class definition for arbitrary lists. */ struct cx_list_class_s { /** * Destructor function. * * Implementations SHALL invoke the content destructor functions if provided * and SHALL deallocate the list memory, if an allocator is provided. */ void (*destructor)(struct cx_list_s *list); /** * Member function for inserting a single element. * Implementors SHOULD see to performant implementations for corner cases. */ int (*insert_element)( struct cx_list_s *list, size_t index, void const *data ); /** * Member function for inserting multiple elements. * Implementors SHOULD see to performant implementations for corner cases. */ size_t (*insert_array)( struct cx_list_s *list, size_t index, void const *data, size_t n ); /** * Member function for inserting an element relative to an iterator position. */ int (*insert_iter)( struct cx_mut_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 removing all elements. */ void (*clear)(struct cx_list_s *list); /** * Member function for swapping two elements. */ int (*swap)( struct cx_list_s *list, size_t i, size_t j ); /** * Member function for element lookup. */ void *(*at)( struct cx_list_s const *list, size_t index ); /** * Member function for finding and optionally removing an element. */ ssize_t (*find_remove)( struct cx_list_s *list, void const *elem, bool remove ); /** * 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); /** * Member function for returning an iterator pointing to the specified index. */ struct cx_iterator_s (*iterator)( struct cx_list_s const *list, size_t index, bool backward ); }; /** * Common type for all list implementations. */ typedef struct cx_list_s CxList; /** * Advises the list to store copies of the objects (default mode of operation). * * Retrieving objects from this list will yield pointers to the copies stored * within this list. * * @param list the list * @see cxListStorePointers() */ __attribute__((__nonnull__)) void cxListStoreObjects(CxList *list); /** * Advises the list to only store pointers to the objects. * * Retrieving objects from this list will yield the original pointers stored. * * @note This function forcibly sets the element size to the size of a pointer. * Invoking this function on a non-empty list that already stores copies of * objects is undefined. * * @param list the list * @see cxListStoreObjects() */ __attribute__((__nonnull__)) void cxListStorePointers(CxList *list); /** * Returns true, if this list is storing pointers instead of the actual data. * * @param list * @return true, if this list is storing pointers * @see cxListStorePointers() */ __attribute__((__nonnull__)) static inline bool cxListIsStoringPointers(CxList const *list) { return list->store_pointer; } /** * Returns the number of elements currently stored in the list. * * @param list the list * @return the number of currently stored elements */ __attribute__((__nonnull__)) static inline size_t cxListSize(CxList const *list) { return list->size; } /** * 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 * @see cxListAddArray() */ __attribute__((__nonnull__)) static inline int cxListAdd( CxList *list, void const *elem ) { return list->cl->insert_element(list, list->size, elem); } /** * Adds multiple items to the end of the list. * * This method is more efficient than invoking cxListAdd() multiple times. * * If there is not enough memory to add all elements, the returned value is * less than \p n. * * If this list is storing pointers instead of objects \p array is expected to * be an array of pointers. * * @param list the list * @param array a pointer to the elements to add * @param n the number of elements to add * @return the number of added elements */ __attribute__((__nonnull__)) static inline size_t cxListAddArray( CxList *list, void const *array, size_t n ) { return list->cl->insert_array(list, list->size, array, n); } /** * 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_element(list, index, elem); } /** * Inserts multiple items to the list at the specified index. * If \p index equals the list size, this is effectively cxListAddArray(). * * This method is usually more efficient than invoking cxListInsert() * multiple times. * * If there is not enough memory to add all elements, the returned value is * less than \p n. * * If this list is storing pointers instead of objects \p array is expected to * be an array of pointers. * * @param list the list * @param index the index where to add the elements * @param array a pointer to the elements to add * @param n the number of elements to add * @return the number of added elements */ __attribute__((__nonnull__)) static inline size_t cxListInsertArray( CxList *list, size_t index, void const *array, size_t n ) { return list->cl->insert_array(list, index, array, n); } /** * 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( CxMutIterator *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( CxMutIterator *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. * * If an element destructor function is specified, it is called before * removing the element. * * @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); } /** * Removes all elements from this list. * * If an element destructor function is specified, it is called for each * element before removing them. * * @param list the list */ __attribute__((__nonnull__)) static inline void cxListClear(CxList *list) { list->cl->clear(list); } /** * Swaps two items in the list. * * Implementations should only allocate temporary memory for the swap, if * it is necessary. * * @param list the list * @param i the index of the first element * @param j the index of the second element * @return zero on success, non-zero if one of the indices is out of bounds */ __attribute__((__nonnull__)) static inline int cxListSwap( CxList *list, size_t i, size_t j ) { return list->cl->swap(list, i, j); } /** * 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 cxListIteratorAt( CxList const *list, size_t index ) { return list->cl->iterator(list, index, false); } /** * Returns a backwards 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 cxListBackwardsIteratorAt( CxList const *list, size_t index ) { return list->cl->iterator(list, index, true); } /** * Returns a mutating 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__)) CxMutIterator cxListMutIteratorAt( CxList *list, size_t index ); /** * Returns a mutating backwards 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__)) CxMutIterator cxListMutBackwardsIteratorAt( CxList *list, size_t 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 cxListIterator(CxList const *list) { return list->cl->iterator(list, 0, false); } /** * Returns a mutating 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 CxMutIterator cxListMutIterator(CxList *list) { return cxListMutIteratorAt(list, 0); } /** * Returns a backwards iterator pointing to the last 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 cxListBackwardsIterator(CxList const *list) { return list->cl->iterator(list, list->size - 1, true); } /** * Returns a mutating backwards iterator pointing to the last 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 CxMutIterator cxListMutBackwardsIterator(CxList *list) { return cxListMutBackwardsIteratorAt(list, list->size - 1); } /** * 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 a negative * value when the element is not found */ __attribute__((__nonnull__)) static inline ssize_t cxListFind( CxList const *list, void const *elem ) { return list->cl->find_remove((CxList*)list, elem, false); } /** * Removes and 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 and remove * @return the index of the now removed element or a negative * value when the element is not found or could not be removed */ __attribute__((__nonnull__)) static inline ssize_t cxListFindRemove( CxList *list, void const *elem ) { return list->cl->find_remove(list, elem, true); } /** * 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, positive if the first list is larger */ __attribute__((__nonnull__)) int cxListCompare( CxList const *list, CxList const *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); /** * A shared instance of an empty list. * * Writing to that list is undefined. */ extern CxList * const cxEmptyList; #ifdef __cplusplus } // extern "C" #endif #endif // UCX_LIST_H