ucx: src/cx/list.h@b070ef465313

     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      * An optional destructor for the list contents.

    75      *

    76      * @attention Read the documentation of the particular list implementation

    77      * whether this destructor shall only destroy the contents or also free the memory.

    78      */

    79     cx_destructor_func content_destructor;

    80     /**

    81      * The comparator function for the elements.

    82      */

    83     CxListComparator cmpfunc;

    84     /**

    85      * The size of each element (payload only).

    86      */

    87     size_t itemsize;

    88     /**

    89      * The size of the list (number of currently stored elements).

    90      */

    91     size_t size;

    92     /**

    93      * The capacity of the list (maximum number of elements).

    94      */

    95     size_t capacity;

    96 };

    98 /**

    99  * The class definition for arbitrary lists.

   100  */

   101 struct cx_list_class_s {

   102     /**

   103      * Destructor function.

   104      */

   105     void (*destructor)(struct cx_list_s *list);

   107     /**

   108      * Member function for adding an element.

   109      */

   110     int (*add)(

   111             struct cx_list_s *list,

   112             void const *elem

   113     );

   115     /**

   116      * Member function for inserting an element.

   117      */

   118     int (*insert)(

   119             struct cx_list_s *list,

   120             size_t index,

   121             void const *elem

   122     );

   124     /**

   125      * Member function for inserting an element relative to an iterator position.

   126      */

   127     int (*insert_iter)(

   128             struct cx_iterator_s *iter,

   129             void const *elem,

   130             int prepend

   131     );

   133     /**

   134      * Member function for removing an element.

   135      */

   136     int (*remove)(

   137             struct cx_list_s *list,

   138             size_t index

   139     );

   141     /**

   142      * Member function for element lookup.

   143      */

   144     void *(*at)(

   145             struct cx_list_s const *list,

   146             size_t index

   147     );

   149     /**

   150      * Member function for finding an element.

   151      */

   152     size_t (*find)(

   153             struct cx_list_s const *list,

   154             void const *elem

   155     );

   157     /**

   158      * Member function for sorting the list in place.

   159      */

   160     void (*sort)(struct cx_list_s *list);

   162     /**

   163      * Member function for comparing this list to another list of the same type.

   164      */

   165     int (*compare)(

   166             struct cx_list_s const *list,

   167             struct cx_list_s const *other

   168     );

   170     /**

   171      * Member function for reversing the order of the items.

   172      */

   173     void (*reverse)(struct cx_list_s *list);

   175     /**

   176      * Returns an iterator pointing to the specified index.

   177      */

   178     struct cx_iterator_s (*iterator)(

   179             struct cx_list_s *list,

   180             size_t index

   181     );

   182 };

   184 /**

   185  * Common type for all list implementations.

   186  */

   187 typedef struct cx_list_s CxList;

   189 /**

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

   191  *

   192  * @param list the list

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

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

   195  */

   196 __attribute__((__nonnull__))

   197 static inline int cxListAdd(

   198         CxList *list,

   199         void const *elem

   200 ) {

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

   202 }

   204 /**

   205  * Inserts an item at the specified index.

   206  *

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

   208  *

   209  * @param list the list

   210  * @param index the index the element shall have

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

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

   213  * or when the index is out of bounds

   214  * @see cxListInsertAfter()

   215  * @see cxListInsertBefore()

   216  */

   217 __attribute__((__nonnull__))

   218 static inline int cxListInsert(

   219         CxList *list,

   220         size_t index,

   221         void const *elem

   222 ) {

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

   224 }

   226 /**

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

   228  *

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

   230  * be considered invalidated.

   231  *

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

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

   234  *

   235  * @param iter an iterator

   236  * @param elem the element to insert

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

   238  * @see cxListInsert()

   239  * @see cxListInsertBefore()

   240  */

   241 __attribute__((__nonnull__))

   242 static inline int cxListInsertAfter(

   243         CxIterator *iter,

   244         void const *elem

   245 ) {

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

   247 }

   249 /**

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

   251  *

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

   253  * be considered invalidated.

   254  *

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

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

   257  *

   258  * @param iter an iterator

   259  * @param elem the element to insert

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

   261  * @see cxListInsert()

   262  * @see cxListInsertAfter()

   263  */

   264 __attribute__((__nonnull__))

   265 static inline int cxListInsertBefore(

   266         CxIterator *iter,

   267         void const *elem

   268 ) {

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

   270 }

   272 /**

   273  * Removes the element at the specified index.

   274  * @param list the list

   275  * @param index the index of the element

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

   277  */

   278 __attribute__((__nonnull__))

   279 static inline int cxListRemove(

   280         CxList *list,

   281         size_t index

   282 ) {

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

   284 }

   286 /**

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

   288  *

   289  * @param list the list

   290  * @param index the index of the element

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

   292  */

   293 __attribute__((__nonnull__))

   294 static inline void *cxListAt(

   295         CxList *list,

   296         size_t index

   297 ) {

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

   299 }

   301 /**

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

   303  *

   304  * The returned iterator is position-aware.

   305  *

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

   307  *

   308  * @param list the list

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

   310  * @return a new iterator

   311  */

   312 __attribute__((__nonnull__, __warn_unused_result__))

   313 static inline CxIterator cxListIterator(

   314         CxList *list,

   315         size_t index

   316 ) {

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

   318 }

   320 /**

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

   322  *

   323  * The returned iterator is position-aware.

   324  *

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

   326  *

   327  * @param list the list

   328  * @return a new iterator

   329  */

   330 __attribute__((__nonnull__, __warn_unused_result__))

   331 static inline CxIterator cxListBegin(CxList *list) {

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

   333 }

   335 /**

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

   337  *

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

   339  *

   340  * @param list the list

   341  * @param elem the element to find

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

   343  */

   344 __attribute__((__nonnull__))

   345 static inline size_t cxListFind(

   346         CxList *list,

   347         void const *elem

   348 ) {

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

   350 }

   352 /**

   353  * Sorts the list in place.

   354  *

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

   356  *

   357  * @param list the list

   358  */

   359 __attribute__((__nonnull__))

   360 static inline void cxListSort(CxList *list) {

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

   362 }

   364 /**

   365  * Reverses the order of the items.

   366  *

   367  * @param list the list

   368  */

   369 __attribute__((__nonnull__))

   370 static inline void cxListReverse(CxList *list) {

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

   372 }

   374 /**

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

   376  *

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

   378  *

   379  * @param list the list

   380  * @param other the list to compare to

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

   382  */

   383 __attribute__((__nonnull__))

   384 static inline int cxListCompare(

   385         CxList *list,

   386         CxList *other

   387 ) {

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

   389 }

   391 /**

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

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

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

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

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

   397  *

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

   399  *

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

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

   402  */

   403 __attribute__((__nonnull__))

   404 CxList *cxListDestroy(CxList *list);

   406 #ifdef __cplusplus

   407 } /* extern "C" */

   408 #endif

   410 #endif /* UCX_LIST_H */

Mercurial > hg > ucx / file revision

src/cx/list.h@b070ef465313

src/cx/list.h