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@484: #include "common.h"
universe@398: #include "allocator.h"
universe@494: #include "iterator.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@489: typedef int(*CxListComparator)(
universe@489:         void const *left,
universe@489:         void const *right
universe@489: );
universe@398: 
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@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@508:     CxAllocator const *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@528:     union {
universe@528:         /**
universe@528:          * An optional simple destructor for the list contents that admits the free() interface.
universe@528:          *
universe@528:          * @remark Set content_destructor_type to #CX_DESTRUCTOR_SIMPLE.
universe@528:          *
universe@528:          * @attention Read the documentation of the particular list implementation
universe@528:          * whether this destructor shall only destroy the contents or also free the memory.
universe@528:          */
universe@528:         cx_destructor_func simple_destructor;
universe@528:         /**
universe@528:          * An optional advanced destructor for the list contents providing additional data.
universe@528:          *
universe@528:          * @remark Set content_destructor_type to #CX_DESTRUCTOR_ADVANCED.
universe@528:          *
universe@528:          * @attention Read the documentation of the particular list implementation
universe@528:          * whether this destructor shall only destroy the contents or also free the memory.
universe@528:          */
universe@528:         cx_advanced_destructor advanced_destructor;
universe@528:     };
universe@528:     /**
universe@528:      * The type of destructor to use.
universe@528:      */
universe@528:     enum cx_destructor_type content_destructor_type;
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@500:      * Member function for adding an element.
universe@500:      */
universe@500:     int (*add)(
universe@500:             struct cx_list_s *list,
universe@500:             void const *elem
universe@500:     );
universe@500: 
universe@500:     /**
universe@500:      * Member function for inserting an element.
universe@500:      */
universe@500:     int (*insert)(
universe@500:             struct cx_list_s *list,
universe@500:             size_t index,
universe@500:             void const *elem
universe@500:     );
universe@500: 
universe@500:     /**
universe@500:      * Member function for inserting an element relative to an iterator position.
universe@500:      */
universe@500:     int (*insert_iter)(
universe@500:             struct cx_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@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@500:     size_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@500:      * Returns an iterator pointing to the specified index.
universe@500:      */
universe@500:     struct cx_iterator_s (*iterator)(
universe@500:             struct cx_list_s *list,
universe@500:             size_t index
universe@500:     );
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@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@464:  */
universe@508: __attribute__((__nonnull__))
universe@489: static inline int cxListAdd(
universe@500:         CxList *list,
universe@489:         void const *elem
universe@489: ) {
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:  * @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@469:     return list->cl->insert(list, index, elem);
universe@469: }
universe@398: 
universe@464: /**
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@499:         CxIterator *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@499:         CxIterator *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@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@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@494: static inline CxIterator cxListIterator(
universe@500:         CxList *list,
universe@494:         size_t index
universe@494: ) {
universe@494:     return list->cl->iterator(list, index);
universe@494: }
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@500: static inline CxIterator cxListBegin(CxList *list) {
universe@494:     return list->cl->iterator(list, 0);
universe@494: }
universe@494: 
universe@494: /**
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@508: __attribute__((__nonnull__))
universe@489: static inline size_t cxListFind(
universe@500:         CxList *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@488:  * First, the list sizes are compared. 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@488:  * @return zero, if both lists are equal element wise, negative if the first list is smaller, zero if the first list is larger
universe@488:  */
universe@508: __attribute__((__nonnull__))
universe@488: static inline int cxListCompare(
universe@500:         CxList *list,
universe@500:         CxList *other
universe@488: ) {
universe@488:     return list->cl->compare(list, other);
universe@488: }
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@415: #ifdef __cplusplus
universe@415: } /* extern "C" */
universe@415: #endif
universe@415: 
universe@393: #endif /* UCX_LIST_H */