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@681: #include "common.h"
universe@677: #include "collection.h"
universe@398: 
universe@415: #ifdef __cplusplus
universe@415: extern "C" {
universe@415: #endif
universe@415: 
universe@464: /**
universe@500:  * List class type.
universe@464:  */
universe@500: typedef struct cx_list_class_s 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@677:     CX_COLLECTION_MEMBERS
universe@464:     /**
universe@464:      * The list class definition.
universe@464:      */
universe@641:     cx_list_class const *cl;
universe@641:     /**
universe@641:      * The actual implementation in case the list class is delegating.
universe@641:      */
universe@641:     cx_list_class const *climpl;
universe@435: };
universe@398: 
universe@464: /**
universe@500:  * The class definition for arbitrary lists.
universe@500:  */
universe@500: struct cx_list_class_s {
universe@500:     /**
universe@524:      * Destructor function.
universe@524:      */
universe@524:     void (*destructor)(struct cx_list_s *list);
universe@524: 
universe@524:     /**
universe@641:      * Member function for inserting a single elements.
universe@641:      * Implementors SHOULD see to performant implementations for corner cases.
universe@641:      */
universe@641:     int (*insert_element)(
universe@641:             struct cx_list_s *list,
universe@641:             size_t index,
universe@641:             void const *data
universe@641:     );
universe@641: 
universe@641:     /**
universe@638:      * Member function for inserting multiple elements.
universe@640:      * Implementors SHOULD see to performant implementations for corner cases.
universe@638:      */
universe@638:     size_t (*insert_array)(
universe@638:             struct cx_list_s *list,
universe@638:             size_t index,
universe@638:             void const *data,
universe@638:             size_t n
universe@638:     );
universe@638: 
universe@638:     /**
universe@500:      * Member function for inserting an element relative to an iterator position.
universe@500:      */
universe@500:     int (*insert_iter)(
universe@630:             struct cx_mut_iterator_s *iter,
universe@500:             void const *elem,
universe@500:             int prepend
universe@500:     );
universe@500: 
universe@500:     /**
universe@500:      * Member function for removing an element.
universe@500:      */
universe@500:     int (*remove)(
universe@500:             struct cx_list_s *list,
universe@500:             size_t index
universe@500:     );
universe@500: 
universe@500:     /**
universe@664:      * Member function for removing all elements.
universe@664:      */
universe@664:     void (*clear)(struct cx_list_s *list);
universe@664: 
universe@664:     /**
universe@647:      * Member function for swapping two elements.
universe@647:      */
universe@647:     int (*swap)(
universe@647:             struct cx_list_s *list,
universe@647:             size_t i,
universe@647:             size_t j
universe@647:     );
universe@647: 
universe@647:     /**
universe@500:      * Member function for element lookup.
universe@500:      */
universe@500:     void *(*at)(
universe@500:             struct cx_list_s const *list,
universe@500:             size_t index
universe@500:     );
universe@500: 
universe@500:     /**
universe@500:      * Member function for finding an element.
universe@500:      */
universe@699:     ssize_t (*find)(
universe@500:             struct cx_list_s const *list,
universe@500:             void const *elem
universe@500:     );
universe@500: 
universe@500:     /**
universe@500:      * Member function for sorting the list in place.
universe@500:      */
universe@500:     void (*sort)(struct cx_list_s *list);
universe@500: 
universe@500:     /**
universe@500:      * Member function for comparing this list to another list of the same type.
universe@500:      */
universe@500:     int (*compare)(
universe@500:             struct cx_list_s const *list,
universe@500:             struct cx_list_s const *other
universe@500:     );
universe@500: 
universe@500:     /**
universe@500:      * Member function for reversing the order of the items.
universe@500:      */
universe@500:     void (*reverse)(struct cx_list_s *list);
universe@500: 
universe@500:     /**
universe@640:      * Member function for returning an iterator pointing to the specified index.
universe@500:      */
universe@500:     struct cx_iterator_s (*iterator)(
universe@630:             struct cx_list_s const *list,
universe@655:             size_t index,
universe@655:             bool backward
universe@630:     );
universe@500: };
universe@500: 
universe@500: /**
universe@464:  * Common type for all list implementations.
universe@464:  */
universe@500: typedef struct cx_list_s CxList;
universe@398: 
universe@464: /**
universe@641:  * Advises the list to store copies of the objects (default mode of operation).
universe@641:  *
universe@641:  * Retrieving objects from this list will yield pointers to the copies stored
universe@641:  * within this list.
universe@641:  *
universe@641:  * @param list the list
universe@641:  * @see cxListStorePointers()
universe@641:  */
universe@641: __attribute__((__nonnull__))
universe@641: void cxListStoreObjects(CxList *list);
universe@641: 
universe@641: /**
universe@641:  * Advises the list to only store pointers to the objects.
universe@641:  *
universe@641:  * Retrieving objects from this list will yield the original pointers stored.
universe@641:  *
universe@641:  * @note This function forcibly sets the element size to the size of a pointer.
universe@641:  * Invoking this function on a non-empty list that already stores copies of
universe@641:  * objects is undefined.
universe@641:  *
universe@641:  * @param list the list
universe@641:  * @see cxListStoreObjects()
universe@641:  */
universe@641: __attribute__((__nonnull__))
universe@641: void cxListStorePointers(CxList *list);
universe@641: 
universe@641: /**
universe@641:  * Returns true, if this list is storing pointers instead of the actual data.
universe@641:  *
universe@641:  * @param list
universe@677:  * @return true, if this list is storing pointers
universe@641:  * @see cxListStorePointers()
universe@641:  */
universe@641: __attribute__((__nonnull__))
universe@677: static inline bool cxListIsStoringPointers(CxList const *list) {
universe@677:     return list->store_pointer;
universe@677: }
universe@677: 
universe@677: /**
universe@677:  * Returns the number of elements currently stored in the list.
universe@677:  *
universe@677:  * @param list the list
universe@677:  * @return the number of currently stored elements
universe@677:  */
universe@677: __attribute__((__nonnull__))
universe@677: static inline size_t cxListSize(CxList const *list) {
universe@677:     return list->size;
universe@677: }
universe@641: 
universe@641: /**
universe@464:  * Adds an item to the end of the list.
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@629:  * @see cxListAddArray()
universe@464:  */
universe@508: __attribute__((__nonnull__))
universe@489: static inline int cxListAdd(
universe@500:         CxList *list,
universe@489:         void const *elem
universe@489: ) {
universe@641:     return list->cl->insert_element(list, list->size, elem);
universe@469: }
universe@398: 
universe@464: /**
universe@629:  * Adds multiple items to the end of the list.
universe@629:  *
universe@629:  * This method is more efficient than invoking cxListAdd() multiple times.
universe@629:  *
universe@629:  * If there is not enough memory to add all elements, the returned value is
universe@629:  * less than \p n.
universe@629:  *
universe@641:  * If this list is storing pointers instead of objects \p array is expected to
universe@641:  * be an array of pointers.
universe@641:  *
universe@629:  * @param list the list
universe@629:  * @param array a pointer to the elements to add
universe@629:  * @param n the number of elements to add
universe@629:  * @return the number of added elements
universe@629:  */
universe@629: __attribute__((__nonnull__))
universe@629: static inline size_t cxListAddArray(
universe@629:         CxList *list,
universe@629:         void const *array,
universe@629:         size_t n
universe@629: ) {
universe@640:     return list->cl->insert_array(list, list->size, array, n);
universe@629: }
universe@629: 
universe@629: /**
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:  * @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@499:  * @see cxListInsertAfter()
universe@499:  * @see cxListInsertBefore()
universe@464:  */
universe@508: __attribute__((__nonnull__))
universe@489: static inline int cxListInsert(
universe@500:         CxList *list,
universe@489:         size_t index,
universe@489:         void const *elem
universe@489: ) {
universe@641:     return list->cl->insert_element(list, index, elem);
universe@469: }
universe@398: 
universe@464: /**
universe@638:  * Inserts multiple items to the list at the specified index.
universe@638:  * If \p index equals the list size, this is effectively cxListAddArray().
universe@638:  *
universe@638:  * This method is usually more efficient than invoking cxListInsert()
universe@638:  * multiple times.
universe@638:  *
universe@638:  * If there is not enough memory to add all elements, the returned value is
universe@638:  * less than \p n.
universe@638:  *
universe@641:  * If this list is storing pointers instead of objects \p array is expected to
universe@641:  * be an array of pointers.
universe@641:  *
universe@638:  * @param list the list
universe@638:  * @param index the index where to add the elements
universe@638:  * @param array a pointer to the elements to add
universe@638:  * @param n the number of elements to add
universe@638:  * @return the number of added elements
universe@638:  */
universe@638: __attribute__((__nonnull__))
universe@638: static inline size_t cxListInsertArray(
universe@638:         CxList *list,
universe@638:         size_t index,
universe@638:         void const *array,
universe@638:         size_t n
universe@638: ) {
universe@638:     return list->cl->insert_array(list, index, array, n);
universe@638: }
universe@638: 
universe@638: /**
universe@499:  * Inserts an element after the current location of the specified iterator.
universe@499:  *
universe@499:  * The used iterator remains operational, but all other active iterators should
universe@499:  * be considered invalidated.
universe@499:  *
universe@499:  * If \p iter is not a list iterator, the behavior is undefined.
universe@499:  * If \p iter is a past-the-end iterator, the new element gets appended to the list.
universe@499:  *
universe@499:  * @param iter an iterator
universe@499:  * @param elem the element to insert
universe@499:  * @return zero on success, non-zero on memory allocation failure
universe@499:  * @see cxListInsert()
universe@499:  * @see cxListInsertBefore()
universe@499:  */
universe@508: __attribute__((__nonnull__))
universe@499: static inline int cxListInsertAfter(
universe@630:         CxMutIterator *iter,
universe@499:         void const *elem
universe@499: ) {
universe@500:     return ((struct cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 0);
universe@499: }
universe@499: 
universe@499: /**
universe@499:  * Inserts an element before the current location of the specified iterator.
universe@499:  *
universe@499:  * The used iterator remains operational, but all other active iterators should
universe@499:  * be considered invalidated.
universe@499:  *
universe@499:  * If \p iter is not a list iterator, the behavior is undefined.
universe@499:  * If \p iter is a past-the-end iterator, the new element gets appended to the list.
universe@499:  *
universe@499:  * @param iter an iterator
universe@499:  * @param elem the element to insert
universe@499:  * @return zero on success, non-zero on memory allocation failure
universe@499:  * @see cxListInsert()
universe@499:  * @see cxListInsertAfter()
universe@499:  */
universe@508: __attribute__((__nonnull__))
universe@499: static inline int cxListInsertBefore(
universe@630:         CxMutIterator *iter,
universe@499:         void const *elem
universe@499: ) {
universe@500:     return ((struct cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 1);
universe@499: }
universe@499: 
universe@499: /**
universe@464:  * Removes the element at the specified index.
universe@664:  *
universe@664:  * If an element destructor function is specified, it is called before
universe@664:  * removing the element.
universe@664:  *
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@508: __attribute__((__nonnull__))
universe@489: static inline int cxListRemove(
universe@500:         CxList *list,
universe@489:         size_t index
universe@489: ) {
universe@469:     return list->cl->remove(list, index);
universe@469: }
universe@398: 
universe@464: /**
universe@664:  * Removes all elements from this list.
universe@664:  *
universe@664:  * If an element destructor function is specified, it is called for each
universe@664:  * element before removing them.
universe@664:  *
universe@664:  * @param list the list
universe@664:  */
universe@664: __attribute__((__nonnull__))
universe@664: static inline void cxListClear(CxList *list) {
universe@664:     list->cl->clear(list);
universe@664: }
universe@664: 
universe@664: /**
universe@647:  * Swaps two items in the list.
universe@647:  *
universe@647:  * Implementations should only allocate temporary memory for the swap, if
universe@647:  * it is necessary.
universe@647:  *
universe@647:  * @param list the list
universe@647:  * @param i the index of the first element
universe@647:  * @param j the index of the second element
universe@647:  * @return zero on success, non-zero if one of the indices is out of bounds
universe@647:  */
universe@647: __attribute__((__nonnull__))
universe@647: static inline int cxListSwap(
universe@647:         CxList *list,
universe@647:         size_t i,
universe@647:         size_t j
universe@647: ) {
universe@647:     return list->cl->swap(list, i, j);
universe@647: }
universe@647: 
universe@647: /**
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@508: __attribute__((__nonnull__))
universe@489: static inline void *cxListAt(
universe@500:         CxList *list,
universe@489:         size_t index
universe@489: ) {
universe@469:     return list->cl->at(list, index);
universe@469: }
universe@439: 
universe@464: /**
universe@494:  * Returns an iterator pointing to the item at the specified index.
universe@494:  *
universe@494:  * The returned iterator is position-aware.
universe@494:  *
universe@494:  * If the index is out of range, a past-the-end iterator will be returned.
universe@494:  *
universe@494:  * @param list the list
universe@494:  * @param index the index where the iterator shall point at
universe@494:  * @return a new iterator
universe@494:  */
universe@508: __attribute__((__nonnull__, __warn_unused_result__))
universe@655: static inline CxIterator cxListIteratorAt(
universe@630:         CxList const *list,
universe@630:         size_t index
universe@630: ) {
universe@655:     return list->cl->iterator(list, index, false);
universe@655: }
universe@655: 
universe@655: /**
universe@655:  * Returns a backwards iterator pointing to the item at the specified index.
universe@655:  *
universe@655:  * The returned iterator is position-aware.
universe@655:  *
universe@655:  * If the index is out of range, a past-the-end iterator will be returned.
universe@655:  *
universe@655:  * @param list the list
universe@655:  * @param index the index where the iterator shall point at
universe@655:  * @return a new iterator
universe@655:  */
universe@655: __attribute__((__nonnull__, __warn_unused_result__))
universe@655: static inline CxIterator cxListBackwardsIteratorAt(
universe@655:         CxList const *list,
universe@655:         size_t index
universe@655: ) {
universe@655:     return list->cl->iterator(list, index, true);
universe@630: }
universe@630: 
universe@630: /**
universe@630:  * Returns a mutating iterator pointing to the item at the specified index.
universe@630:  *
universe@630:  * The returned iterator is position-aware.
universe@630:  *
universe@630:  * If the index is out of range, a past-the-end iterator will be returned.
universe@630:  *
universe@630:  * @param list the list
universe@630:  * @param index the index where the iterator shall point at
universe@630:  * @return a new iterator
universe@630:  */
universe@630: __attribute__((__nonnull__, __warn_unused_result__))
universe@655: CxMutIterator cxListMutIteratorAt(
universe@655:         CxList *list,
universe@655:         size_t index
universe@655: );
universe@655: 
universe@655: /**
universe@655:  * Returns a mutating backwards iterator pointing to the item at the
universe@655:  * specified index.
universe@655:  *
universe@655:  * The returned iterator is position-aware.
universe@655:  *
universe@655:  * If the index is out of range, a past-the-end iterator will be returned.
universe@655:  *
universe@655:  * @param list the list
universe@655:  * @param index the index where the iterator shall point at
universe@655:  * @return a new iterator
universe@655:  */
universe@655: __attribute__((__nonnull__, __warn_unused_result__))
universe@655: CxMutIterator cxListMutBackwardsIteratorAt(
universe@500:         CxList *list,
universe@494:         size_t index
universe@640: );
universe@494: 
universe@494: /**
universe@494:  * Returns an iterator pointing to the first item of the list.
universe@494:  *
universe@494:  * The returned iterator is position-aware.
universe@494:  *
universe@494:  * If the list is empty, a past-the-end iterator will be returned.
universe@494:  *
universe@494:  * @param list the list
universe@494:  * @return a new iterator
universe@494:  */
universe@508: __attribute__((__nonnull__, __warn_unused_result__))
universe@655: static inline CxIterator cxListIterator(CxList const *list) {
universe@655:     return list->cl->iterator(list, 0, false);
universe@494: }
universe@494: 
universe@494: /**
universe@630:  * Returns a mutating iterator pointing to the first item of the list.
universe@630:  *
universe@630:  * The returned iterator is position-aware.
universe@630:  *
universe@630:  * If the list is empty, a past-the-end iterator will be returned.
universe@630:  *
universe@630:  * @param list the list
universe@630:  * @return a new iterator
universe@630:  */
universe@630: __attribute__((__nonnull__, __warn_unused_result__))
universe@655: static inline CxMutIterator cxListMutIterator(CxList *list) {
universe@655:     return cxListMutIteratorAt(list, 0);
universe@655: }
universe@655: 
universe@655: 
universe@655: /**
universe@655:  * Returns a backwards iterator pointing to the last item of the list.
universe@655:  *
universe@655:  * The returned iterator is position-aware.
universe@655:  *
universe@655:  * If the list is empty, a past-the-end iterator will be returned.
universe@655:  *
universe@655:  * @param list the list
universe@655:  * @return a new iterator
universe@655:  */
universe@655: __attribute__((__nonnull__, __warn_unused_result__))
universe@655: static inline CxIterator cxListBackwardsIterator(CxList const *list) {
universe@655:     return list->cl->iterator(list, list->size - 1, true);
universe@655: }
universe@655: 
universe@655: /**
universe@655:  * Returns a mutating backwards iterator pointing to the last item of the list.
universe@655:  *
universe@655:  * The returned iterator is position-aware.
universe@655:  *
universe@655:  * If the list is empty, a past-the-end iterator will be returned.
universe@655:  *
universe@655:  * @param list the list
universe@655:  * @return a new iterator
universe@655:  */
universe@655: __attribute__((__nonnull__, __warn_unused_result__))
universe@655: static inline CxMutIterator cxListMutBackwardsIterator(CxList *list) {
universe@655:     return cxListMutBackwardsIteratorAt(list, list->size - 1);
universe@630: }
universe@630: 
universe@630: /**
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@699:  * @return the index of the element or a negative
universe@699:  * value when the element is not found
universe@464:  */
universe@508: __attribute__((__nonnull__))
universe@699: static inline ssize_t cxListFind(
universe@621:         CxList const *list,
universe@489:         void const *elem
universe@489: ) {
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@508: __attribute__((__nonnull__))
universe@500: static inline void cxListSort(CxList *list) {
universe@469:     list->cl->sort(list);
universe@469: }
universe@404: 
universe@488: /**
universe@490:  * Reverses the order of the items.
universe@490:  *
universe@490:  * @param list the list
universe@490:  */
universe@508: __attribute__((__nonnull__))
universe@500: static inline void cxListReverse(CxList *list) {
universe@490:     list->cl->reverse(list);
universe@490: }
universe@490: 
universe@490: /**
universe@488:  * Compares a list to another list of the same type.
universe@488:  *
universe@618:  * First, the list sizes are compared.
universe@618:  * If they match, the lists are compared element-wise.
universe@488:  *
universe@488:  * @param list the list
universe@488:  * @param other the list to compare to
universe@618:  * @return zero, if both lists are equal element wise,
universe@618:  * negative if the first list is smaller, positive if the first list is larger
universe@488:  */
universe@508: __attribute__((__nonnull__))
universe@618: int cxListCompare(
universe@618:         CxList const *list,
universe@618:         CxList const *other
universe@618: );
universe@488: 
universe@503: /**
universe@528:  * Deallocates the memory of the specified list structure.
universe@528:  *
universe@528:  * Also calls content a destructor function, depending on the configuration
universe@528:  * in CxList.content_destructor_type.
universe@503:  *
universe@503:  * This function itself is a destructor function for the CxList.
universe@503:  *
universe@528:  * @param list the list which shall be destroyed
universe@503:  */
universe@503: __attribute__((__nonnull__))
universe@528: void cxListDestroy(CxList *list);
universe@503: 
universe@704: /**
universe@704:  * A shared instance of an empty list.
universe@704:  *
universe@704:  * Writing to that list is undefined.
universe@704:  */
universe@704: extern CxList * const cxEmptyList;
universe@704: 
universe@704: 
universe@415: #ifdef __cplusplus
universe@628: } // extern "C"
universe@415: #endif
universe@415: 
universe@628: #endif // UCX_LIST_H