ucx: src/cx/list.h@8aea65ae1eaf

     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      * 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 list.

   197  *

   198  * @param list the list to configure

   199  * @param list_destructor an alternative list destructor to use (if \c NULL, the current destructor remains unchanged)

   200  * @param content_destructor the content destructor to use (if \c NULL, no content destructor is used)

   201  * @param list_autofree a flag indicating, if the list allocator shall free the list, if the destructor did not do that

   202  * @param content_autofree a flag indicating, if the list allocator shall free an element,

   203  * if the content destructor did not do that or no content destructor exists

   204  */

   205 __attribute__((__nonnull__(1)))

   206 static inline void cxListMemoryMgmt(

   207         CxList *list,

   208         cx_destructor_func list_destructor,

   209         cx_destructor_func content_destructor,

   210         bool list_autofree,

   211         bool content_autofree

   212 ) {

   213     if (list_destructor != NULL) list->list_destructor = list_destructor;

   214     list->content_destructor = content_destructor;

   215     list->autofree = list_autofree;

   216     list->autofree_contents = content_autofree;

   217 }

   219 /**

   220  * Adds an item to the end of the list.

   221  *

   222  * @param list the list

   223  * @param elem a pointer to the element to add

   224  * @return zero on success, non-zero on memory allocation failure

   225  */

   226 __attribute__((__nonnull__))

   227 static inline int cxListAdd(

   228         CxList *list,

   229         void const *elem

   230 ) {

   231     return list->cl->add(list, elem);

   232 }

   234 /**

   235  * Inserts an item at the specified index.

   236  *

   237  * If \p index equals the list \c size, this is effectively cxListAdd().

   238  *

   239  * @param list the list

   240  * @param index the index the element shall have

   241  * @param elem a pointer to the element to add

   242  * @return zero on success, non-zero on memory allocation failure

   243  * or when the index is out of bounds

   244  * @see cxListInsertAfter()

   245  * @see cxListInsertBefore()

   246  */

   247 __attribute__((__nonnull__))

   248 static inline int cxListInsert(

   249         CxList *list,

   250         size_t index,

   251         void const *elem

   252 ) {

   253     return list->cl->insert(list, index, elem);

   254 }

   256 /**

   257  * Inserts an element after the current location of the specified iterator.

   258  *

   259  * The used iterator remains operational, but all other active iterators should

   260  * be considered invalidated.

   261  *

   262  * If \p iter is not a list iterator, the behavior is undefined.

   263  * If \p iter is a past-the-end iterator, the new element gets appended to the list.

   264  *

   265  * @param iter an iterator

   266  * @param elem the element to insert

   267  * @return zero on success, non-zero on memory allocation failure

   268  * @see cxListInsert()

   269  * @see cxListInsertBefore()

   270  */

   271 __attribute__((__nonnull__))

   272 static inline int cxListInsertAfter(

   273         CxIterator *iter,

   274         void const *elem

   275 ) {

   276     return ((struct cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 0);

   277 }

   279 /**

   280  * Inserts an element before the current location of the specified iterator.

   281  *

   282  * The used iterator remains operational, but all other active iterators should

   283  * be considered invalidated.

   284  *

   285  * If \p iter is not a list iterator, the behavior is undefined.

   286  * If \p iter is a past-the-end iterator, the new element gets appended to the list.

   287  *

   288  * @param iter an iterator

   289  * @param elem the element to insert

   290  * @return zero on success, non-zero on memory allocation failure

   291  * @see cxListInsert()

   292  * @see cxListInsertAfter()

   293  */

   294 __attribute__((__nonnull__))

   295 static inline int cxListInsertBefore(

   296         CxIterator *iter,

   297         void const *elem

   298 ) {

   299     return ((struct cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 1);

   300 }

   302 /**

   303  * Removes the element at the specified index.

   304  * @param list the list

   305  * @param index the index of the element

   306  * @return zero on success, non-zero if the index is out of bounds

   307  */

   308 __attribute__((__nonnull__))

   309 static inline int cxListRemove(

   310         CxList *list,

   311         size_t index

   312 ) {

   313     return list->cl->remove(list, index);

   314 }

   316 /**

   317  * Returns a pointer to the element at the specified index.

   318  *

   319  * @param list the list

   320  * @param index the index of the element

   321  * @return a pointer to the element or \c NULL if the index is out of bounds

   322  */

   323 __attribute__((__nonnull__))

   324 static inline void *cxListAt(

   325         CxList *list,

   326         size_t index

   327 ) {

   328     return list->cl->at(list, index);

   329 }

   331 /**

   332  * Returns an iterator pointing to the item at the specified index.

   333  *

   334  * The returned iterator is position-aware.

   335  *

   336  * If the index is out of range, a past-the-end iterator will be returned.

   337  *

   338  * @param list the list

   339  * @param index the index where the iterator shall point at

   340  * @return a new iterator

   341  */

   342 __attribute__((__nonnull__, __warn_unused_result__))

   343 static inline CxIterator cxListIterator(

   344         CxList *list,

   345         size_t index

   346 ) {

   347     return list->cl->iterator(list, index);

   348 }

   350 /**

   351  * Returns an iterator pointing to the first item of the list.

   352  *

   353  * The returned iterator is position-aware.

   354  *

   355  * If the list is empty, a past-the-end iterator will be returned.

   356  *

   357  * @param list the list

   358  * @return a new iterator

   359  */

   360 __attribute__((__nonnull__, __warn_unused_result__))

   361 static inline CxIterator cxListBegin(CxList *list) {

   362     return list->cl->iterator(list, 0);

   363 }

   365 /**

   366  * Returns the index of the first element that equals \p elem.

   367  *

   368  * Determining equality is performed by the list's comparator function.

   369  *

   370  * @param list the list

   371  * @param elem the element to find

   372  * @return the index of the element or \c (size+1) if the element is not found

   373  */

   374 __attribute__((__nonnull__))

   375 static inline size_t cxListFind(

   376         CxList *list,

   377         void const *elem

   378 ) {

   379     return list->cl->find(list, elem);

   380 }

   382 /**

   383  * Sorts the list in place.

   384  *

   385  * \remark The underlying sort algorithm is implementation defined.

   386  *

   387  * @param list the list

   388  */

   389 __attribute__((__nonnull__))

   390 static inline void cxListSort(CxList *list) {

   391     list->cl->sort(list);

   392 }

   394 /**

   395  * Reverses the order of the items.

   396  *

   397  * @param list the list

   398  */

   399 __attribute__((__nonnull__))

   400 static inline void cxListReverse(CxList *list) {

   401     list->cl->reverse(list);

   402 }

   404 /**

   405  * Compares a list to another list of the same type.

   406  *

   407  * First, the list sizes are compared. If they match, the lists are compared element-wise.

   408  *

   409  * @param list the list

   410  * @param other the list to compare to

   411  * @return zero, if both lists are equal element wise, negative if the first list is smaller, zero if the first list is larger

   412  */

   413 __attribute__((__nonnull__))

   414 static inline int cxListCompare(

   415         CxList *list,

   416         CxList *other

   417 ) {

   418     return list->cl->compare(list, other);

   419 }

   421 /**

   422  * Calls the list's destructor function for every element.

   423  * If CxList.autofree_content is \c true, the elements are automatically free'd

   424  * unless the content destructor function did not already do that.

   425  * Similarly, if CxList.autofree is \c true, the list structure is free'd, unless

   426  * the list destructor function did not already do that.

   427  *

   428  * This function itself is a destructor function for the CxList.

   429  *

   430  * @param list the list which contents shall be destroyed

   431  * @return \p list if the list structure has not been free'd during the process

   432  */

   433 __attribute__((__nonnull__))

   434 CxList *cxListDestroy(CxList *list);

   436 #ifdef __cplusplus

   437 } /* extern "C" */

   438 #endif

   440 #endif /* UCX_LIST_H */

Mercurial > hg > ucx / file revision

src/cx/list.h@8aea65ae1eaf

src/cx/list.h