ucx: src/cx/list.h@eafb45eefc51

     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      * The comparator function for the elements.

    75      */

    76     CxListComparator cmpfunc;

    77     /**

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

    79      */

    80     size_t itemsize;

    81     /**

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

    83      */

    84     size_t size;

    85     /**

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

    87      */

    88     size_t capacity;

    89     union {

    90         /**

    91          * An optional simple destructor for the list contents that admits the free() interface.

    92          *

    93          * @remark Set content_destructor_type to #CX_DESTRUCTOR_SIMPLE.

    94          *

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

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

    97          */

    98         cx_destructor_func simple_destructor;

    99         /**

   100          * An optional advanced destructor for the list contents providing additional data.

   101          *

   102          * @remark Set content_destructor_type to #CX_DESTRUCTOR_ADVANCED.

   103          *

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

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

   106          */

   107         cx_advanced_destructor advanced_destructor;

   108     };

   109     /**

   110      * The type of destructor to use.

   111      */

   112     enum cx_destructor_type content_destructor_type;

   113 };

   115 /**

   116  * The class definition for arbitrary lists.

   117  */

   118 struct cx_list_class_s {

   119     /**

   120      * Destructor function.

   121      */

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

   124     /**

   125      * Member function for adding an element.

   126      */

   127     int (*add)(

   128             struct cx_list_s *list,

   129             void const *elem

   130     );

   132     /**

   133      * Member function for adding multiple elements.

   134      */

   135     size_t (*add_array)(

   136             struct cx_list_s *list,

   137             void const *array,

   138             size_t n

   139     );

   141     /**

   142      * Member function for inserting an element.

   143      */

   144     int (*insert)(

   145             struct cx_list_s *list,

   146             size_t index,

   147             void const *elem

   148     );

   150     /**

   151      * Member function for inserting multiple elements.

   152      */

   153     size_t (*insert_array)(

   154             struct cx_list_s *list,

   155             size_t index,

   156             void const *data,

   157             size_t n

   158     );

   160     /**

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

   162      */

   163     int (*insert_iter)(

   164             struct cx_mut_iterator_s *iter,

   165             void const *elem,

   166             int prepend

   167     );

   169     /**

   170      * Member function for removing an element.

   171      */

   172     int (*remove)(

   173             struct cx_list_s *list,

   174             size_t index

   175     );

   177     /**

   178      * Member function for element lookup.

   179      */

   180     void *(*at)(

   181             struct cx_list_s const *list,

   182             size_t index

   183     );

   185     /**

   186      * Member function for finding an element.

   187      */

   188     size_t (*find)(

   189             struct cx_list_s const *list,

   190             void const *elem

   191     );

   193     /**

   194      * Member function for sorting the list in place.

   195      */

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

   198     /**

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

   200      */

   201     int (*compare)(

   202             struct cx_list_s const *list,

   203             struct cx_list_s const *other

   204     );

   206     /**

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

   208      */

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

   211     /**

   212      * Returns an iterator pointing to the specified index.

   213      */

   214     struct cx_iterator_s (*iterator)(

   215             struct cx_list_s const *list,

   216             size_t index

   217     );

   219     /**

   220      * Returns a mutating iterator pointing to the specified index.

   221      */

   222     struct cx_mut_iterator_s (*mut_iterator)(

   223             struct cx_list_s *list,

   224             size_t index

   225     );

   226 };

   228 /**

   229  * Common type for all list implementations.

   230  */

   231 typedef struct cx_list_s CxList;

   233 /**

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

   235  *

   236  * @param list the list

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

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

   239  * @see cxListAddArray()

   240  */

   241 __attribute__((__nonnull__))

   242 static inline int cxListAdd(

   243         CxList *list,

   244         void const *elem

   245 ) {

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

   247 }

   249 /**

   250  * Adds multiple items to the end of the list.

   251  *

   252  * This method is more efficient than invoking cxListAdd() multiple times.

   253  *

   254  * If there is not enough memory to add all elements, the returned value is

   255  * less than \p n.

   256  *

   257  * @param list the list

   258  * @param array a pointer to the elements to add

   259  * @param n the number of elements to add

   260  * @return the number of added elements

   261  */

   262 __attribute__((__nonnull__))

   263 static inline size_t cxListAddArray(

   264         CxList *list,

   265         void const *array,

   266         size_t n

   267 ) {

   268     return list->cl->add_array(list, array, n);

   269 }

   271 /**

   272  * Inserts an item at the specified index.

   273  *

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

   275  *

   276  * @param list the list

   277  * @param index the index the element shall have

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

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

   280  * or when the index is out of bounds

   281  * @see cxListInsertAfter()

   282  * @see cxListInsertBefore()

   283  */

   284 __attribute__((__nonnull__))

   285 static inline int cxListInsert(

   286         CxList *list,

   287         size_t index,

   288         void const *elem

   289 ) {

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

   291 }

   293 /**

   294  * Inserts multiple items to the list at the specified index.

   295  * If \p index equals the list size, this is effectively cxListAddArray().

   296  *

   297  * This method is usually more efficient than invoking cxListInsert()

   298  * multiple times.

   299  *

   300  * If there is not enough memory to add all elements, the returned value is

   301  * less than \p n.

   302  *

   303  * @param list the list

   304  * @param index the index where to add the elements

   305  * @param array a pointer to the elements to add

   306  * @param n the number of elements to add

   307  * @return the number of added elements

   308  */

   309 __attribute__((__nonnull__))

   310 static inline size_t cxListInsertArray(

   311         CxList *list,

   312         size_t index,

   313         void const *array,

   314         size_t n

   315 ) {

   316     return list->cl->insert_array(list, index, array, n);

   317 }

   319 /**

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

   321  *

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

   323  * be considered invalidated.

   324  *

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

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

   327  *

   328  * @param iter an iterator

   329  * @param elem the element to insert

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

   331  * @see cxListInsert()

   332  * @see cxListInsertBefore()

   333  */

   334 __attribute__((__nonnull__))

   335 static inline int cxListInsertAfter(

   336         CxMutIterator *iter,

   337         void const *elem

   338 ) {

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

   340 }

   342 /**

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

   344  *

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

   346  * be considered invalidated.

   347  *

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

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

   350  *

   351  * @param iter an iterator

   352  * @param elem the element to insert

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

   354  * @see cxListInsert()

   355  * @see cxListInsertAfter()

   356  */

   357 __attribute__((__nonnull__))

   358 static inline int cxListInsertBefore(

   359         CxMutIterator *iter,

   360         void const *elem

   361 ) {

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

   363 }

   365 /**

   366  * Removes the element at the specified index.

   367  * @param list the list

   368  * @param index the index of the element

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

   370  */

   371 __attribute__((__nonnull__))

   372 static inline int cxListRemove(

   373         CxList *list,

   374         size_t index

   375 ) {

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

   377 }

   379 /**

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

   381  *

   382  * @param list the list

   383  * @param index the index of the element

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

   385  */

   386 __attribute__((__nonnull__))

   387 static inline void *cxListAt(

   388         CxList *list,

   389         size_t index

   390 ) {

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

   392 }

   394 /**

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

   396  *

   397  * The returned iterator is position-aware.

   398  *

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

   400  *

   401  * @param list the list

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

   403  * @return a new iterator

   404  */

   405 __attribute__((__nonnull__, __warn_unused_result__))

   406 static inline CxIterator cxListIterator(

   407         CxList const *list,

   408         size_t index

   409 ) {

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

   411 }

   413 /**

   414  * Returns a mutating iterator pointing to the item at the specified index.

   415  *

   416  * The returned iterator is position-aware.

   417  *

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

   419  *

   420  * @param list the list

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

   422  * @return a new iterator

   423  */

   424 __attribute__((__nonnull__, __warn_unused_result__))

   425 static inline CxMutIterator cxListMutIterator(

   426         CxList *list,

   427         size_t index

   428 ) {

   429     return list->cl->mut_iterator(list, index);

   430 }

   432 /**

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

   434  *

   435  * The returned iterator is position-aware.

   436  *

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

   438  *

   439  * @param list the list

   440  * @return a new iterator

   441  */

   442 __attribute__((__nonnull__, __warn_unused_result__))

   443 static inline CxIterator cxListBegin(CxList const *list) {

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

   445 }

   447 /**

   448  * Returns a mutating iterator pointing to the first item of the list.

   449  *

   450  * The returned iterator is position-aware.

   451  *

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

   453  *

   454  * @param list the list

   455  * @return a new iterator

   456  */

   457 __attribute__((__nonnull__, __warn_unused_result__))

   458 static inline CxMutIterator cxListBeginMut(CxList *list) {

   459     return list->cl->mut_iterator(list, 0);

   460 }

   462 /**

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

   464  *

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

   466  *

   467  * @param list the list

   468  * @param elem the element to find

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

   470  */

   471 __attribute__((__nonnull__))

   472 static inline size_t cxListFind(

   473         CxList const *list,

   474         void const *elem

   475 ) {

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

   477 }

   479 /**

   480  * Sorts the list in place.

   481  *

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

   483  *

   484  * @param list the list

   485  */

   486 __attribute__((__nonnull__))

   487 static inline void cxListSort(CxList *list) {

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

   489 }

   491 /**

   492  * Reverses the order of the items.

   493  *

   494  * @param list the list

   495  */

   496 __attribute__((__nonnull__))

   497 static inline void cxListReverse(CxList *list) {

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

   499 }

   501 /**

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

   503  *

   504  * First, the list sizes are compared.

   505  * If they match, the lists are compared element-wise.

   506  *

   507  * @param list the list

   508  * @param other the list to compare to

   509  * @return zero, if both lists are equal element wise,

   510  * negative if the first list is smaller, positive if the first list is larger

   511  */

   512 __attribute__((__nonnull__))

   513 int cxListCompare(

   514         CxList const *list,

   515         CxList const *other

   516 );

   518 /**

   519  * Deallocates the memory of the specified list structure.

   520  *

   521  * Also calls content a destructor function, depending on the configuration

   522  * in CxList.content_destructor_type.

   523  *

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

   525  *

   526  * @param list the list which shall be destroyed

   527  */

   528 __attribute__((__nonnull__))

   529 void cxListDestroy(CxList *list);

   531 #ifdef __cplusplus

   532 } // extern "C"

   533 #endif

   535 #endif // UCX_LIST_H

Mercurial > hg > ucx / file revision

src/cx/list.h@eafb45eefc51

src/cx/list.h