src/cx/list.h

Mon, 18 Apr 2022 17:26:21 +0200

author
Mike Becker <universe@uap-core.de>
date
Mon, 18 Apr 2022 17:26:21 +0200
changeset 528
4fbfac557df8
parent 526
b070ef465313
child 618
1f5a8f6f3015
permissions
-rw-r--r--

#179 improve API for list content destruction

     1 /*
     2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
     3  *
     4  * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
     5  *
     6  * Redistribution and use in source and binary forms, with or without
     7  * modification, are permitted provided that the following conditions are met:
     8  *
     9  *   1. Redistributions of source code must retain the above copyright
    10  *      notice, this list of conditions and the following disclaimer.
    11  *
    12  *   2. Redistributions in binary form must reproduce the above copyright
    13  *      notice, this list of conditions and the following disclaimer in the
    14  *      documentation and/or other materials provided with the distribution.
    15  *
    16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    17  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    19  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
    20  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    21  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    22  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    23  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    24  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    25  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    26  * POSSIBILITY OF SUCH DAMAGE.
    27  */
    28 /**
    29  * \file list.h
    30  * \brief Interface for list implementations.
    31  * \author Mike Becker
    32  * \author Olaf Wintermann
    33  * \version 3.0
    34  * \copyright 2-Clause BSD License
    35  */
    37 #ifndef UCX_LIST_H
    38 #define UCX_LIST_H
    40 #include "common.h"
    41 #include "allocator.h"
    42 #include "iterator.h"
    44 #ifdef __cplusplus
    45 extern "C" {
    46 #endif
    48 /**
    49  * A comparator function comparing two list elements.
    50  */
    51 typedef int(*CxListComparator)(
    52         void const *left,
    53         void const *right
    54 );
    56 /**
    57  * List class type.
    58  */
    59 typedef struct cx_list_class_s cx_list_class;
    61 /**
    62  * Structure for holding the base data of a list.
    63  */
    64 struct cx_list_s {
    65     /**
    66      * The list class definition.
    67      */
    68     cx_list_class *cl;
    69     /**
    70      * The allocator to use.
    71      */
    72     CxAllocator const *allocator;
    73     /**
    74      * The comparator function for the elements.
    75      */
    76     CxListComparator cmpfunc;
    77     /**
    78      * The size of each element (payload only).
    79      */
    80     size_t itemsize;
    81     /**
    82      * The size of the list (number of currently stored elements).
    83      */
    84     size_t size;
    85     /**
    86      * The capacity of the list (maximum number of elements).
    87      */
    88     size_t capacity;
    89     union {
    90         /**
    91          * An optional simple destructor for the list contents that admits the free() interface.
    92          *
    93          * @remark Set content_destructor_type to #CX_DESTRUCTOR_SIMPLE.
    94          *
    95          * @attention Read the documentation of the particular list implementation
    96          * whether this destructor shall only destroy the contents or also free the memory.
    97          */
    98         cx_destructor_func simple_destructor;
    99         /**
   100          * An optional advanced destructor for the list contents providing additional data.
   101          *
   102          * @remark Set content_destructor_type to #CX_DESTRUCTOR_ADVANCED.
   103          *
   104          * @attention Read the documentation of the particular list implementation
   105          * whether this destructor shall only destroy the contents or also free the memory.
   106          */
   107         cx_advanced_destructor advanced_destructor;
   108     };
   109     /**
   110      * The type of destructor to use.
   111      */
   112     enum cx_destructor_type content_destructor_type;
   113 };
   115 /**
   116  * The class definition for arbitrary lists.
   117  */
   118 struct cx_list_class_s {
   119     /**
   120      * Destructor function.
   121      */
   122     void (*destructor)(struct cx_list_s *list);
   124     /**
   125      * Member function for adding an element.
   126      */
   127     int (*add)(
   128             struct cx_list_s *list,
   129             void const *elem
   130     );
   132     /**
   133      * Member function for inserting an element.
   134      */
   135     int (*insert)(
   136             struct cx_list_s *list,
   137             size_t index,
   138             void const *elem
   139     );
   141     /**
   142      * Member function for inserting an element relative to an iterator position.
   143      */
   144     int (*insert_iter)(
   145             struct cx_iterator_s *iter,
   146             void const *elem,
   147             int prepend
   148     );
   150     /**
   151      * Member function for removing an element.
   152      */
   153     int (*remove)(
   154             struct cx_list_s *list,
   155             size_t index
   156     );
   158     /**
   159      * Member function for element lookup.
   160      */
   161     void *(*at)(
   162             struct cx_list_s const *list,
   163             size_t index
   164     );
   166     /**
   167      * Member function for finding an element.
   168      */
   169     size_t (*find)(
   170             struct cx_list_s const *list,
   171             void const *elem
   172     );
   174     /**
   175      * Member function for sorting the list in place.
   176      */
   177     void (*sort)(struct cx_list_s *list);
   179     /**
   180      * Member function for comparing this list to another list of the same type.
   181      */
   182     int (*compare)(
   183             struct cx_list_s const *list,
   184             struct cx_list_s const *other
   185     );
   187     /**
   188      * Member function for reversing the order of the items.
   189      */
   190     void (*reverse)(struct cx_list_s *list);
   192     /**
   193      * Returns an iterator pointing to the specified index.
   194      */
   195     struct cx_iterator_s (*iterator)(
   196             struct cx_list_s *list,
   197             size_t index
   198     );
   199 };
   201 /**
   202  * Common type for all list implementations.
   203  */
   204 typedef struct cx_list_s CxList;
   206 /**
   207  * Adds an item to the end of the list.
   208  *
   209  * @param list the list
   210  * @param elem a pointer to the element to add
   211  * @return zero on success, non-zero on memory allocation failure
   212  */
   213 __attribute__((__nonnull__))
   214 static inline int cxListAdd(
   215         CxList *list,
   216         void const *elem
   217 ) {
   218     return list->cl->add(list, elem);
   219 }
   221 /**
   222  * Inserts an item at the specified index.
   223  *
   224  * If \p index equals the list \c size, this is effectively cxListAdd().
   225  *
   226  * @param list the list
   227  * @param index the index the element shall have
   228  * @param elem a pointer to the element to add
   229  * @return zero on success, non-zero on memory allocation failure
   230  * or when the index is out of bounds
   231  * @see cxListInsertAfter()
   232  * @see cxListInsertBefore()
   233  */
   234 __attribute__((__nonnull__))
   235 static inline int cxListInsert(
   236         CxList *list,
   237         size_t index,
   238         void const *elem
   239 ) {
   240     return list->cl->insert(list, index, elem);
   241 }
   243 /**
   244  * Inserts an element after the current location of the specified iterator.
   245  *
   246  * The used iterator remains operational, but all other active iterators should
   247  * be considered invalidated.
   248  *
   249  * If \p iter is not a list iterator, the behavior is undefined.
   250  * If \p iter is a past-the-end iterator, the new element gets appended to the list.
   251  *
   252  * @param iter an iterator
   253  * @param elem the element to insert
   254  * @return zero on success, non-zero on memory allocation failure
   255  * @see cxListInsert()
   256  * @see cxListInsertBefore()
   257  */
   258 __attribute__((__nonnull__))
   259 static inline int cxListInsertAfter(
   260         CxIterator *iter,
   261         void const *elem
   262 ) {
   263     return ((struct cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 0);
   264 }
   266 /**
   267  * Inserts an element before the current location of the specified iterator.
   268  *
   269  * The used iterator remains operational, but all other active iterators should
   270  * be considered invalidated.
   271  *
   272  * If \p iter is not a list iterator, the behavior is undefined.
   273  * If \p iter is a past-the-end iterator, the new element gets appended to the list.
   274  *
   275  * @param iter an iterator
   276  * @param elem the element to insert
   277  * @return zero on success, non-zero on memory allocation failure
   278  * @see cxListInsert()
   279  * @see cxListInsertAfter()
   280  */
   281 __attribute__((__nonnull__))
   282 static inline int cxListInsertBefore(
   283         CxIterator *iter,
   284         void const *elem
   285 ) {
   286     return ((struct cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 1);
   287 }
   289 /**
   290  * Removes the element at the specified index.
   291  * @param list the list
   292  * @param index the index of the element
   293  * @return zero on success, non-zero if the index is out of bounds
   294  */
   295 __attribute__((__nonnull__))
   296 static inline int cxListRemove(
   297         CxList *list,
   298         size_t index
   299 ) {
   300     return list->cl->remove(list, index);
   301 }
   303 /**
   304  * Returns a pointer to the element at the specified index.
   305  *
   306  * @param list the list
   307  * @param index the index of the element
   308  * @return a pointer to the element or \c NULL if the index is out of bounds
   309  */
   310 __attribute__((__nonnull__))
   311 static inline void *cxListAt(
   312         CxList *list,
   313         size_t index
   314 ) {
   315     return list->cl->at(list, index);
   316 }
   318 /**
   319  * Returns an iterator pointing to the item at the specified index.
   320  *
   321  * The returned iterator is position-aware.
   322  *
   323  * If the index is out of range, a past-the-end iterator will be returned.
   324  *
   325  * @param list the list
   326  * @param index the index where the iterator shall point at
   327  * @return a new iterator
   328  */
   329 __attribute__((__nonnull__, __warn_unused_result__))
   330 static inline CxIterator cxListIterator(
   331         CxList *list,
   332         size_t index
   333 ) {
   334     return list->cl->iterator(list, index);
   335 }
   337 /**
   338  * Returns an iterator pointing to the first item of the list.
   339  *
   340  * The returned iterator is position-aware.
   341  *
   342  * If the list is empty, a past-the-end iterator will be returned.
   343  *
   344  * @param list the list
   345  * @return a new iterator
   346  */
   347 __attribute__((__nonnull__, __warn_unused_result__))
   348 static inline CxIterator cxListBegin(CxList *list) {
   349     return list->cl->iterator(list, 0);
   350 }
   352 /**
   353  * Returns the index of the first element that equals \p elem.
   354  *
   355  * Determining equality is performed by the list's comparator function.
   356  *
   357  * @param list the list
   358  * @param elem the element to find
   359  * @return the index of the element or \c (size+1) if the element is not found
   360  */
   361 __attribute__((__nonnull__))
   362 static inline size_t cxListFind(
   363         CxList *list,
   364         void const *elem
   365 ) {
   366     return list->cl->find(list, elem);
   367 }
   369 /**
   370  * Sorts the list in place.
   371  *
   372  * \remark The underlying sort algorithm is implementation defined.
   373  *
   374  * @param list the list
   375  */
   376 __attribute__((__nonnull__))
   377 static inline void cxListSort(CxList *list) {
   378     list->cl->sort(list);
   379 }
   381 /**
   382  * Reverses the order of the items.
   383  *
   384  * @param list the list
   385  */
   386 __attribute__((__nonnull__))
   387 static inline void cxListReverse(CxList *list) {
   388     list->cl->reverse(list);
   389 }
   391 /**
   392  * Compares a list to another list of the same type.
   393  *
   394  * First, the list sizes are compared. If they match, the lists are compared element-wise.
   395  *
   396  * @param list the list
   397  * @param other the list to compare to
   398  * @return zero, if both lists are equal element wise, negative if the first list is smaller, zero if the first list is larger
   399  */
   400 __attribute__((__nonnull__))
   401 static inline int cxListCompare(
   402         CxList *list,
   403         CxList *other
   404 ) {
   405     return list->cl->compare(list, other);
   406 }
   408 /**
   409  * Deallocates the memory of the specified list structure.
   410  *
   411  * Also calls content a destructor function, depending on the configuration
   412  * in CxList.content_destructor_type.
   413  *
   414  * This function itself is a destructor function for the CxList.
   415  *
   416  * @param list the list which shall be destroyed
   417  */
   418 __attribute__((__nonnull__))
   419 void cxListDestroy(CxList *list);
   421 #ifdef __cplusplus
   422 } /* extern "C" */
   423 #endif
   425 #endif /* UCX_LIST_H */

mercurial