src/cx/list.h

Wed, 25 Jan 2023 19:19:29 +0100

author
Mike Becker <universe@uap-core.de>
date
Wed, 25 Jan 2023 19:19:29 +0100
changeset 640
55cc3b373c5e
parent 638
eafb45eefc51
child 641
d402fead3386
permissions
-rw-r--r--

simplify list class - fixes #236

     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 inserting multiple elements.
   126      * Implementors SHOULD see to performant implementations for corner cases.
   127      */
   128     size_t (*insert_array)(
   129             struct cx_list_s *list,
   130             size_t index,
   131             void const *data,
   132             size_t n
   133     );
   135     /**
   136      * Member function for inserting an element relative to an iterator position.
   137      */
   138     int (*insert_iter)(
   139             struct cx_mut_iterator_s *iter,
   140             void const *elem,
   141             int prepend
   142     );
   144     /**
   145      * Member function for removing an element.
   146      */
   147     int (*remove)(
   148             struct cx_list_s *list,
   149             size_t index
   150     );
   152     /**
   153      * Member function for element lookup.
   154      */
   155     void *(*at)(
   156             struct cx_list_s const *list,
   157             size_t index
   158     );
   160     /**
   161      * Member function for finding an element.
   162      */
   163     size_t (*find)(
   164             struct cx_list_s const *list,
   165             void const *elem
   166     );
   168     /**
   169      * Member function for sorting the list in place.
   170      */
   171     void (*sort)(struct cx_list_s *list);
   173     /**
   174      * Member function for comparing this list to another list of the same type.
   175      */
   176     int (*compare)(
   177             struct cx_list_s const *list,
   178             struct cx_list_s const *other
   179     );
   181     /**
   182      * Member function for reversing the order of the items.
   183      */
   184     void (*reverse)(struct cx_list_s *list);
   186     /**
   187      * Member function for returning an iterator pointing to the specified index.
   188      */
   189     struct cx_iterator_s (*iterator)(
   190             struct cx_list_s const *list,
   191             size_t index
   192     );
   193 };
   195 /**
   196  * Common type for all list implementations.
   197  */
   198 typedef struct cx_list_s CxList;
   200 /**
   201  * Adds an item to the end of the list.
   202  *
   203  * @param list the list
   204  * @param elem a pointer to the element to add
   205  * @return zero on success, non-zero on memory allocation failure
   206  * @see cxListAddArray()
   207  */
   208 __attribute__((__nonnull__))
   209 static inline int cxListAdd(
   210         CxList *list,
   211         void const *elem
   212 ) {
   213     return list->cl->insert_array(list, list->size, elem, 1) != 1;
   214 }
   216 /**
   217  * Adds multiple items to the end of the list.
   218  *
   219  * This method is more efficient than invoking cxListAdd() multiple times.
   220  *
   221  * If there is not enough memory to add all elements, the returned value is
   222  * less than \p n.
   223  *
   224  * @param list the list
   225  * @param array a pointer to the elements to add
   226  * @param n the number of elements to add
   227  * @return the number of added elements
   228  */
   229 __attribute__((__nonnull__))
   230 static inline size_t cxListAddArray(
   231         CxList *list,
   232         void const *array,
   233         size_t n
   234 ) {
   235     return list->cl->insert_array(list, list->size, array, n);
   236 }
   238 /**
   239  * Inserts an item at the specified index.
   240  *
   241  * If \p index equals the list \c size, this is effectively cxListAdd().
   242  *
   243  * @param list the list
   244  * @param index the index the element shall have
   245  * @param elem a pointer to the element to add
   246  * @return zero on success, non-zero on memory allocation failure
   247  * or when the index is out of bounds
   248  * @see cxListInsertAfter()
   249  * @see cxListInsertBefore()
   250  */
   251 __attribute__((__nonnull__))
   252 static inline int cxListInsert(
   253         CxList *list,
   254         size_t index,
   255         void const *elem
   256 ) {
   257     return list->cl->insert_array(list, index, elem, 1) != 1;
   258 }
   260 /**
   261  * Inserts multiple items to the list at the specified index.
   262  * If \p index equals the list size, this is effectively cxListAddArray().
   263  *
   264  * This method is usually more efficient than invoking cxListInsert()
   265  * multiple times.
   266  *
   267  * If there is not enough memory to add all elements, the returned value is
   268  * less than \p n.
   269  *
   270  * @param list the list
   271  * @param index the index where to add the elements
   272  * @param array a pointer to the elements to add
   273  * @param n the number of elements to add
   274  * @return the number of added elements
   275  */
   276 __attribute__((__nonnull__))
   277 static inline size_t cxListInsertArray(
   278         CxList *list,
   279         size_t index,
   280         void const *array,
   281         size_t n
   282 ) {
   283     return list->cl->insert_array(list, index, array, n);
   284 }
   286 /**
   287  * Inserts an element after the current location of the specified iterator.
   288  *
   289  * The used iterator remains operational, but all other active iterators should
   290  * be considered invalidated.
   291  *
   292  * If \p iter is not a list iterator, the behavior is undefined.
   293  * If \p iter is a past-the-end iterator, the new element gets appended to the list.
   294  *
   295  * @param iter an iterator
   296  * @param elem the element to insert
   297  * @return zero on success, non-zero on memory allocation failure
   298  * @see cxListInsert()
   299  * @see cxListInsertBefore()
   300  */
   301 __attribute__((__nonnull__))
   302 static inline int cxListInsertAfter(
   303         CxMutIterator *iter,
   304         void const *elem
   305 ) {
   306     return ((struct cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 0);
   307 }
   309 /**
   310  * Inserts an element before the current location of the specified iterator.
   311  *
   312  * The used iterator remains operational, but all other active iterators should
   313  * be considered invalidated.
   314  *
   315  * If \p iter is not a list iterator, the behavior is undefined.
   316  * If \p iter is a past-the-end iterator, the new element gets appended to the list.
   317  *
   318  * @param iter an iterator
   319  * @param elem the element to insert
   320  * @return zero on success, non-zero on memory allocation failure
   321  * @see cxListInsert()
   322  * @see cxListInsertAfter()
   323  */
   324 __attribute__((__nonnull__))
   325 static inline int cxListInsertBefore(
   326         CxMutIterator *iter,
   327         void const *elem
   328 ) {
   329     return ((struct cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 1);
   330 }
   332 /**
   333  * Removes the element at the specified index.
   334  * @param list the list
   335  * @param index the index of the element
   336  * @return zero on success, non-zero if the index is out of bounds
   337  */
   338 __attribute__((__nonnull__))
   339 static inline int cxListRemove(
   340         CxList *list,
   341         size_t index
   342 ) {
   343     return list->cl->remove(list, index);
   344 }
   346 /**
   347  * Returns a pointer to the element at the specified index.
   348  *
   349  * @param list the list
   350  * @param index the index of the element
   351  * @return a pointer to the element or \c NULL if the index is out of bounds
   352  */
   353 __attribute__((__nonnull__))
   354 static inline void *cxListAt(
   355         CxList *list,
   356         size_t index
   357 ) {
   358     return list->cl->at(list, index);
   359 }
   361 /**
   362  * Returns an iterator pointing to the item at the specified index.
   363  *
   364  * The returned iterator is position-aware.
   365  *
   366  * If the index is out of range, a past-the-end iterator will be returned.
   367  *
   368  * @param list the list
   369  * @param index the index where the iterator shall point at
   370  * @return a new iterator
   371  */
   372 __attribute__((__nonnull__, __warn_unused_result__))
   373 static inline CxIterator cxListIterator(
   374         CxList const *list,
   375         size_t index
   376 ) {
   377     return list->cl->iterator(list, index);
   378 }
   380 /**
   381  * Returns a mutating iterator pointing to the item at the specified index.
   382  *
   383  * The returned iterator is position-aware.
   384  *
   385  * If the index is out of range, a past-the-end iterator will be returned.
   386  *
   387  * @param list the list
   388  * @param index the index where the iterator shall point at
   389  * @return a new iterator
   390  */
   391 __attribute__((__nonnull__, __warn_unused_result__))
   392 CxMutIterator cxListMutIterator(
   393         CxList *list,
   394         size_t index
   395 );
   397 /**
   398  * Returns an iterator pointing to the first item of the list.
   399  *
   400  * The returned iterator is position-aware.
   401  *
   402  * If the list is empty, a past-the-end iterator will be returned.
   403  *
   404  * @param list the list
   405  * @return a new iterator
   406  */
   407 __attribute__((__nonnull__, __warn_unused_result__))
   408 static inline CxIterator cxListBegin(CxList const *list) {
   409     return list->cl->iterator(list, 0);
   410 }
   412 /**
   413  * Returns a mutating iterator pointing to the first item of the list.
   414  *
   415  * The returned iterator is position-aware.
   416  *
   417  * If the list is empty, a past-the-end iterator will be returned.
   418  *
   419  * @param list the list
   420  * @return a new iterator
   421  */
   422 __attribute__((__nonnull__, __warn_unused_result__))
   423 static inline CxMutIterator cxListBeginMut(CxList *list) {
   424     return cxListMutIterator(list, 0);
   425 }
   427 /**
   428  * Returns the index of the first element that equals \p elem.
   429  *
   430  * Determining equality is performed by the list's comparator function.
   431  *
   432  * @param list the list
   433  * @param elem the element to find
   434  * @return the index of the element or \c (size+1) if the element is not found
   435  */
   436 __attribute__((__nonnull__))
   437 static inline size_t cxListFind(
   438         CxList const *list,
   439         void const *elem
   440 ) {
   441     return list->cl->find(list, elem);
   442 }
   444 /**
   445  * Sorts the list in place.
   446  *
   447  * \remark The underlying sort algorithm is implementation defined.
   448  *
   449  * @param list the list
   450  */
   451 __attribute__((__nonnull__))
   452 static inline void cxListSort(CxList *list) {
   453     list->cl->sort(list);
   454 }
   456 /**
   457  * Reverses the order of the items.
   458  *
   459  * @param list the list
   460  */
   461 __attribute__((__nonnull__))
   462 static inline void cxListReverse(CxList *list) {
   463     list->cl->reverse(list);
   464 }
   466 /**
   467  * Compares a list to another list of the same type.
   468  *
   469  * First, the list sizes are compared.
   470  * If they match, the lists are compared element-wise.
   471  *
   472  * @param list the list
   473  * @param other the list to compare to
   474  * @return zero, if both lists are equal element wise,
   475  * negative if the first list is smaller, positive if the first list is larger
   476  */
   477 __attribute__((__nonnull__))
   478 int cxListCompare(
   479         CxList const *list,
   480         CxList const *other
   481 );
   483 /**
   484  * Deallocates the memory of the specified list structure.
   485  *
   486  * Also calls content a destructor function, depending on the configuration
   487  * in CxList.content_destructor_type.
   488  *
   489  * This function itself is a destructor function for the CxList.
   490  *
   491  * @param list the list which shall be destroyed
   492  */
   493 __attribute__((__nonnull__))
   494 void cxListDestroy(CxList *list);
   496 #ifdef __cplusplus
   497 } // extern "C"
   498 #endif
   500 #endif // UCX_LIST_H

mercurial