ucx: src/cx/list.h@e98b09018d32

     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     cx_destructor_func content_destructor;

    77     /**

    78      * The comparator function for the elements.

    79      */

    80     CxListComparator cmpfunc;

    81     /**

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

    83      */

    84     size_t itemsize;

    85     /**

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

    87      */

    88     size_t size;

    89     /**

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

    91      */

    92     size_t capacity;

    93     /**

    94      * Flag indicating whether cxListDestroy() shall free each list element,

    95      * even if cx_list_s.content_destructor did not do that.

    96      */

    97     bool autofree_contents;

    98 };

   100 /**

   101  * The class definition for arbitrary lists.

   102  */

   103 struct cx_list_class_s {

   104     /**

   105      * Destructor function.

   106      */

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

   109     /**

   110      * Member function for adding an element.

   111      */

   112     int (*add)(

   113             struct cx_list_s *list,

   114             void const *elem

   115     );

   117     /**

   118      * Member function for inserting an element.

   119      */

   120     int (*insert)(

   121             struct cx_list_s *list,

   122             size_t index,

   123             void const *elem

   124     );

   126     /**

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

   128      */

   129     int (*insert_iter)(

   130             struct cx_iterator_s *iter,

   131             void const *elem,

   132             int prepend

   133     );

   135     /**

   136      * Member function for removing an element.

   137      */

   138     int (*remove)(

   139             struct cx_list_s *list,

   140             size_t index

   141     );

   143     /**

   144      * Member function for element lookup.

   145      */

   146     void *(*at)(

   147             struct cx_list_s const *list,

   148             size_t index

   149     );

   151     /**

   152      * Member function for finding an element.

   153      */

   154     size_t (*find)(

   155             struct cx_list_s const *list,

   156             void const *elem

   157     );

   159     /**

   160      * Member function for sorting the list in place.

   161      */

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

   164     /**

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

   166      */

   167     int (*compare)(

   168             struct cx_list_s const *list,

   169             struct cx_list_s const *other

   170     );

   172     /**

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

   174      */

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

   177     /**

   178      * Returns an iterator pointing to the specified index.

   179      */

   180     struct cx_iterator_s (*iterator)(

   181             struct cx_list_s *list,

   182             size_t index

   183     );

   184 };

   186 /**

   187  * Common type for all list implementations.

   188  */

   189 typedef struct cx_list_s CxList;

   191 /**

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

   193  *

   194  * @param list the list

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

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

   197  */

   198 __attribute__((__nonnull__))

   199 static inline int cxListAdd(

   200         CxList *list,

   201         void const *elem

   202 ) {

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

   204 }

   206 /**

   207  * Inserts an item at the specified index.

   208  *

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

   210  *

   211  * @param list the list

   212  * @param index the index the element shall have

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

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

   215  * or when the index is out of bounds

   216  * @see cxListInsertAfter()

   217  * @see cxListInsertBefore()

   218  */

   219 __attribute__((__nonnull__))

   220 static inline int cxListInsert(

   221         CxList *list,

   222         size_t index,

   223         void const *elem

   224 ) {

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

   226 }

   228 /**

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

   230  *

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

   232  * be considered invalidated.

   233  *

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

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

   236  *

   237  * @param iter an iterator

   238  * @param elem the element to insert

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

   240  * @see cxListInsert()

   241  * @see cxListInsertBefore()

   242  */

   243 __attribute__((__nonnull__))

   244 static inline int cxListInsertAfter(

   245         CxIterator *iter,

   246         void const *elem

   247 ) {

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

   249 }

   251 /**

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

   253  *

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

   255  * be considered invalidated.

   256  *

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

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

   259  *

   260  * @param iter an iterator

   261  * @param elem the element to insert

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

   263  * @see cxListInsert()

   264  * @see cxListInsertAfter()

   265  */

   266 __attribute__((__nonnull__))

   267 static inline int cxListInsertBefore(

   268         CxIterator *iter,

   269         void const *elem

   270 ) {

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

   272 }

   274 /**

   275  * Removes the element at the specified index.

   276  * @param list the list

   277  * @param index the index of the element

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

   279  */

   280 __attribute__((__nonnull__))

   281 static inline int cxListRemove(

   282         CxList *list,

   283         size_t index

   284 ) {

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

   286 }

   288 /**

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

   290  *

   291  * @param list the list

   292  * @param index the index of the element

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

   294  */

   295 __attribute__((__nonnull__))

   296 static inline void *cxListAt(

   297         CxList *list,

   298         size_t index

   299 ) {

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

   301 }

   303 /**

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

   305  *

   306  * The returned iterator is position-aware.

   307  *

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

   309  *

   310  * @param list the list

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

   312  * @return a new iterator

   313  */

   314 __attribute__((__nonnull__, __warn_unused_result__))

   315 static inline CxIterator cxListIterator(

   316         CxList *list,

   317         size_t index

   318 ) {

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

   320 }

   322 /**

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

   324  *

   325  * The returned iterator is position-aware.

   326  *

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

   328  *

   329  * @param list the list

   330  * @return a new iterator

   331  */

   332 __attribute__((__nonnull__, __warn_unused_result__))

   333 static inline CxIterator cxListBegin(CxList *list) {

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

   335 }

   337 /**

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

   339  *

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

   341  *

   342  * @param list the list

   343  * @param elem the element to find

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

   345  */

   346 __attribute__((__nonnull__))

   347 static inline size_t cxListFind(

   348         CxList *list,

   349         void const *elem

   350 ) {

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

   352 }

   354 /**

   355  * Sorts the list in place.

   356  *

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

   358  *

   359  * @param list the list

   360  */

   361 __attribute__((__nonnull__))

   362 static inline void cxListSort(CxList *list) {

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

   364 }

   366 /**

   367  * Reverses the order of the items.

   368  *

   369  * @param list the list

   370  */

   371 __attribute__((__nonnull__))

   372 static inline void cxListReverse(CxList *list) {

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

   374 }

   376 /**

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

   378  *

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

   380  *

   381  * @param list the list

   382  * @param other the list to compare to

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

   384  */

   385 __attribute__((__nonnull__))

   386 static inline int cxListCompare(

   387         CxList *list,

   388         CxList *other

   389 ) {

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

   391 }

   393 /**

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

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

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

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

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

   399  *

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

   401  *

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

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

   404  */

   405 __attribute__((__nonnull__))

   406 CxList *cxListDestroy(CxList *list);

   408 #ifdef __cplusplus

   409 } /* extern "C" */

   410 #endif

   412 #endif /* UCX_LIST_H */

Mercurial > hg > ucx / file revision

src/cx/list.h@e98b09018d32

src/cx/list.h