ucx: src/cx/list.h@536646d1575b

     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 };

    95 /**

    96  * The class definition for arbitrary lists.

    97  */

    98 struct cx_list_class_s {

    99     /**

   100      * Destructor function.

   101      */

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

   104     /**

   105      * Member function for adding an element.

   106      */

   107     int (*add)(

   108             struct cx_list_s *list,

   109             void const *elem

   110     );

   112     /**

   113      * Member function for inserting an element.

   114      */

   115     int (*insert)(

   116             struct cx_list_s *list,

   117             size_t index,

   118             void const *elem

   119     );

   121     /**

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

   123      */

   124     int (*insert_iter)(

   125             struct cx_iterator_s *iter,

   126             void const *elem,

   127             int prepend

   128     );

   130     /**

   131      * Member function for removing an element.

   132      */

   133     int (*remove)(

   134             struct cx_list_s *list,

   135             size_t index

   136     );

   138     /**

   139      * Member function for element lookup.

   140      */

   141     void *(*at)(

   142             struct cx_list_s const *list,

   143             size_t index

   144     );

   146     /**

   147      * Member function for finding an element.

   148      */

   149     size_t (*find)(

   150             struct cx_list_s const *list,

   151             void const *elem

   152     );

   154     /**

   155      * Member function for sorting the list in place.

   156      */

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

   159     /**

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

   161      */

   162     int (*compare)(

   163             struct cx_list_s const *list,

   164             struct cx_list_s const *other

   165     );

   167     /**

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

   169      */

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

   172     /**

   173      * Returns an iterator pointing to the specified index.

   174      */

   175     struct cx_iterator_s (*iterator)(

   176             struct cx_list_s *list,

   177             size_t index

   178     );

   179 };

   181 /**

   182  * Common type for all list implementations.

   183  */

   184 typedef struct cx_list_s CxList;

   186 /**

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

   188  *

   189  * @param list the list

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

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

   192  */

   193 __attribute__((__nonnull__))

   194 static inline int cxListAdd(

   195         CxList *list,

   196         void const *elem

   197 ) {

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

   199 }

   201 /**

   202  * Inserts an item at the specified index.

   203  *

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

   205  *

   206  * @param list the list

   207  * @param index the index the element shall have

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

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

   210  * or when the index is out of bounds

   211  * @see cxListInsertAfter()

   212  * @see cxListInsertBefore()

   213  */

   214 __attribute__((__nonnull__))

   215 static inline int cxListInsert(

   216         CxList *list,

   217         size_t index,

   218         void const *elem

   219 ) {

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

   221 }

   223 /**

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

   225  *

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

   227  * be considered invalidated.

   228  *

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

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

   231  *

   232  * @param iter an iterator

   233  * @param elem the element to insert

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

   235  * @see cxListInsert()

   236  * @see cxListInsertBefore()

   237  */

   238 __attribute__((__nonnull__))

   239 static inline int cxListInsertAfter(

   240         CxIterator *iter,

   241         void const *elem

   242 ) {

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

   244 }

   246 /**

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

   248  *

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

   250  * be considered invalidated.

   251  *

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

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

   254  *

   255  * @param iter an iterator

   256  * @param elem the element to insert

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

   258  * @see cxListInsert()

   259  * @see cxListInsertAfter()

   260  */

   261 __attribute__((__nonnull__))

   262 static inline int cxListInsertBefore(

   263         CxIterator *iter,

   264         void const *elem

   265 ) {

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

   267 }

   269 /**

   270  * Removes the element at the specified index.

   271  * @param list the list

   272  * @param index the index of the element

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

   274  */

   275 __attribute__((__nonnull__))

   276 static inline int cxListRemove(

   277         CxList *list,

   278         size_t index

   279 ) {

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

   281 }

   283 /**

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

   285  *

   286  * @param list the list

   287  * @param index the index of the element

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

   289  */

   290 __attribute__((__nonnull__))

   291 static inline void *cxListAt(

   292         CxList *list,

   293         size_t index

   294 ) {

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

   296 }

   298 /**

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

   300  *

   301  * The returned iterator is position-aware.

   302  *

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

   304  *

   305  * @param list the list

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

   307  * @return a new iterator

   308  */

   309 __attribute__((__nonnull__, __warn_unused_result__))

   310 static inline CxIterator cxListIterator(

   311         CxList *list,

   312         size_t index

   313 ) {

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

   315 }

   317 /**

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

   319  *

   320  * The returned iterator is position-aware.

   321  *

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

   323  *

   324  * @param list the list

   325  * @return a new iterator

   326  */

   327 __attribute__((__nonnull__, __warn_unused_result__))

   328 static inline CxIterator cxListBegin(CxList *list) {

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

   330 }

   332 /**

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

   334  *

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

   336  *

   337  * @param list the list

   338  * @param elem the element to find

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

   340  */

   341 __attribute__((__nonnull__))

   342 static inline size_t cxListFind(

   343         CxList *list,

   344         void const *elem

   345 ) {

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

   347 }

   349 /**

   350  * Sorts the list in place.

   351  *

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

   353  *

   354  * @param list the list

   355  */

   356 __attribute__((__nonnull__))

   357 static inline void cxListSort(CxList *list) {

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

   359 }

   361 /**

   362  * Reverses the order of the items.

   363  *

   364  * @param list the list

   365  */

   366 __attribute__((__nonnull__))

   367 static inline void cxListReverse(CxList *list) {

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

   369 }

   371 /**

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

   373  *

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

   375  *

   376  * @param list the list

   377  * @param other the list to compare to

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

   379  */

   380 __attribute__((__nonnull__))

   381 static inline int cxListCompare(

   382         CxList *list,

   383         CxList *other

   384 ) {

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

   386 }

   388 /**

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

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

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

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

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

   394  *

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

   396  *

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

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

   399  */

   400 __attribute__((__nonnull__))

   401 CxList *cxListDestroy(CxList *list);

   403 #ifdef __cplusplus

   404 } /* extern "C" */

   405 #endif

   407 #endif /* UCX_LIST_H */

Mercurial > hg > ucx / file revision

src/cx/list.h@536646d1575b

src/cx/list.h