src/cx/list.h

Tue, 15 Feb 2022 19:48:25 +0100

author
Mike Becker <universe@uap-core.de>
date
Tue, 15 Feb 2022 19:48:25 +0100
changeset 504
aaf89ce0cbf6
parent 503
a89857072ace
child 505
03e9151bea32
permissions
-rw-r--r--

add convenience function to configure list memory management

     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 *allocator;
    73     /**
    74      * A mandatory destructor for the list structure.
    75      */
    76     cx_destructor_func list_destructor;
    77     /**
    78      * An optional destructor for the list contents.
    79      */
    80     cx_destructor_func content_destructor;
    81     /**
    82      * The comparator function for the elements.
    83      */
    84     CxListComparator cmpfunc;
    85     /**
    86      * The size of each element (payload only).
    87      */
    88     size_t itemsize;
    89     /**
    90      * The size of the list (number of currently stored elements).
    91      */
    92     size_t size;
    93     /**
    94      * The capacity of the list (maximum number of elements).
    95      */
    96     size_t capacity;
    97     /**
    98      * Flag indicating whether cxListDestroy() shall free the list structure,
    99      * even if cx_list_s.list_destructor did not do that.
   100      */
   101     bool autofree;
   102     /**
   103      * Flag indicating whether cxListDestroy() shall free each list element,
   104      * even if cx_list_s.content_destructor did not do that.
   105      */
   106     bool autofree_contents;
   107 };
   109 /**
   110  * The class definition for arbitrary lists.
   111  */
   112 struct cx_list_class_s {
   113     /**
   114      * Member function for adding an element.
   115      */
   116     int (*add)(
   117             struct cx_list_s *list,
   118             void const *elem
   119     );
   121     /**
   122      * Member function for inserting an element.
   123      */
   124     int (*insert)(
   125             struct cx_list_s *list,
   126             size_t index,
   127             void const *elem
   128     );
   130     /**
   131      * Member function for inserting an element relative to an iterator position.
   132      */
   133     int (*insert_iter)(
   134             struct cx_iterator_s *iter,
   135             void const *elem,
   136             int prepend
   137     );
   139     /**
   140      * Member function for removing an element.
   141      */
   142     int (*remove)(
   143             struct cx_list_s *list,
   144             size_t index
   145     );
   147     /**
   148      * Member function for element lookup.
   149      */
   150     void *(*at)(
   151             struct cx_list_s const *list,
   152             size_t index
   153     );
   155     /**
   156      * Member function for finding an element.
   157      */
   158     size_t (*find)(
   159             struct cx_list_s const *list,
   160             void const *elem
   161     );
   163     /**
   164      * Member function for sorting the list in place.
   165      */
   166     void (*sort)(struct cx_list_s *list);
   168     /**
   169      * Member function for comparing this list to another list of the same type.
   170      */
   171     int (*compare)(
   172             struct cx_list_s const *list,
   173             struct cx_list_s const *other
   174     );
   176     /**
   177      * Member function for reversing the order of the items.
   178      */
   179     void (*reverse)(struct cx_list_s *list);
   181     /**
   182      * Returns an iterator pointing to the specified index.
   183      */
   184     struct cx_iterator_s (*iterator)(
   185             struct cx_list_s *list,
   186             size_t index
   187     );
   188 };
   190 /**
   191  * Common type for all list implementations.
   192  */
   193 typedef struct cx_list_s CxList;
   195 /**
   196  * Convenience function to configure the memory management for this a list.
   197  * @param list the list to configure
   198  * @param list_destructor an alternative list destructor to use (if \c NULL, the current destructor remains unchanged)
   199  * @param content_destructor the content destructor to use (if \c NULL, no content destructor is used)
   200  * @param list_autofree a flag indicating, if the list allocator shall free the list, if the destructor did not do that
   201  * @param content_autofree a flag indicating, if the list allocator shall free an element,
   202  * if the content destructor did not do that or no content destructor exists
   203  */
   204 static inline void cxListMemoryMgmt(
   205         CxList *list,
   206         cx_destructor_func list_destructor,
   207         cx_destructor_func content_destructor,
   208         bool list_autofree,
   209         bool content_autofree
   210 ) {
   211     if (list_destructor != NULL) list->list_destructor = list_destructor;
   212     list->content_destructor = content_destructor;
   213     list->autofree = list_autofree;
   214     list->autofree_contents = content_autofree;
   215 }
   217 /**
   218  * Adds an item to the end of the list.
   219  *
   220  * @param list the list
   221  * @param elem a pointer to the element to add
   222  * @return zero on success, non-zero on memory allocation failure
   223  */
   224 static inline int cxListAdd(
   225         CxList *list,
   226         void const *elem
   227 ) {
   228     return list->cl->add(list, elem);
   229 }
   231 /**
   232  * Inserts an item at the specified index.
   233  *
   234  * If \p index equals the list \c size, this is effectively cxListAdd().
   235  *
   236  * @param list the list
   237  * @param index the index the element shall have
   238  * @param elem a pointer to the element to add
   239  * @return zero on success, non-zero on memory allocation failure
   240  * or when the index is out of bounds
   241  * @see cxListInsertAfter()
   242  * @see cxListInsertBefore()
   243  */
   244 static inline int cxListInsert(
   245         CxList *list,
   246         size_t index,
   247         void const *elem
   248 ) {
   249     return list->cl->insert(list, index, elem);
   250 }
   252 /**
   253  * Inserts an element after the current location of the specified iterator.
   254  *
   255  * The used iterator remains operational, but all other active iterators should
   256  * be considered invalidated.
   257  *
   258  * If \p iter is not a list iterator, the behavior is undefined.
   259  * If \p iter is a past-the-end iterator, the new element gets appended to the list.
   260  *
   261  * @param iter an iterator
   262  * @param elem the element to insert
   263  * @return zero on success, non-zero on memory allocation failure
   264  * @see cxListInsert()
   265  * @see cxListInsertBefore()
   266  */
   267 static inline int cxListInsertAfter(
   268         CxIterator *iter,
   269         void const *elem
   270 ) {
   271     return ((struct cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 0);
   272 }
   274 /**
   275  * Inserts an element before the current location of the specified iterator.
   276  *
   277  * The used iterator remains operational, but all other active iterators should
   278  * be considered invalidated.
   279  *
   280  * If \p iter is not a list iterator, the behavior is undefined.
   281  * If \p iter is a past-the-end iterator, the new element gets appended to the list.
   282  *
   283  * @param iter an iterator
   284  * @param elem the element to insert
   285  * @return zero on success, non-zero on memory allocation failure
   286  * @see cxListInsert()
   287  * @see cxListInsertAfter()
   288  */
   289 static inline int cxListInsertBefore(
   290         CxIterator *iter,
   291         void const *elem
   292 ) {
   293     return ((struct cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 1);
   294 }
   296 /**
   297  * Removes the element at the specified index.
   298  * @param list the list
   299  * @param index the index of the element
   300  * @return zero on success, non-zero if the index is out of bounds
   301  */
   302 static inline int cxListRemove(
   303         CxList *list,
   304         size_t index
   305 ) {
   306     return list->cl->remove(list, index);
   307 }
   309 /**
   310  * Returns a pointer to the element at the specified index.
   311  *
   312  * @param list the list
   313  * @param index the index of the element
   314  * @return a pointer to the element or \c NULL if the index is out of bounds
   315  */
   316 static inline void *cxListAt(
   317         CxList *list,
   318         size_t index
   319 ) {
   320     return list->cl->at(list, index);
   321 }
   323 /**
   324  * Returns an iterator pointing to the item at the specified index.
   325  *
   326  * The returned iterator is position-aware.
   327  *
   328  * If the index is out of range, a past-the-end iterator will be returned.
   329  *
   330  * @param list the list
   331  * @param index the index where the iterator shall point at
   332  * @return a new iterator
   333  */
   334 static inline CxIterator cxListIterator(
   335         CxList *list,
   336         size_t index
   337 ) {
   338     return list->cl->iterator(list, index);
   339 }
   341 /**
   342  * Returns an iterator pointing to the first item of the list.
   343  *
   344  * The returned iterator is position-aware.
   345  *
   346  * If the list is empty, a past-the-end iterator will be returned.
   347  *
   348  * @param list the list
   349  * @return a new iterator
   350  */
   351 static inline CxIterator cxListBegin(CxList *list) {
   352     return list->cl->iterator(list, 0);
   353 }
   355 /**
   356  * Returns the index of the first element that equals \p elem.
   357  *
   358  * Determining equality is performed by the list's comparator function.
   359  *
   360  * @param list the list
   361  * @param elem the element to find
   362  * @return the index of the element or \c (size+1) if the element is not found
   363  */
   364 static inline size_t cxListFind(
   365         CxList *list,
   366         void const *elem
   367 ) {
   368     return list->cl->find(list, elem);
   369 }
   371 /**
   372  * Sorts the list in place.
   373  *
   374  * \remark The underlying sort algorithm is implementation defined.
   375  *
   376  * @param list the list
   377  */
   378 static inline void cxListSort(CxList *list) {
   379     list->cl->sort(list);
   380 }
   382 /**
   383  * Reverses the order of the items.
   384  *
   385  * @param list the list
   386  */
   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 static inline int cxListCompare(
   401         CxList *list,
   402         CxList *other
   403 ) {
   404     return list->cl->compare(list, other);
   405 }
   407 /**
   408  * Calls the list's destructor function for every element.
   409  * If CxList.autofree_content is \c true, the elements are automatically free'd
   410  * unless the content destructor function did not already do that.
   411  * Similarly, if CxList.autofree is \c true, the list structure is free'd, unless
   412  * the list destructor function did not already do that.
   413  *
   414  * This function itself is a destructor function for the CxList.
   415  *
   416  * @param list the list which contents shall be destroyed
   417  * @return \p list if the list structure has been free'd during the process
   418  */
   419 __attribute__((__nonnull__))
   420 CxList *cxListDestroy(CxList *list);
   422 #ifdef __cplusplus
   423 } /* extern "C" */
   424 #endif
   426 #endif /* UCX_LIST_H */

mercurial