ucx: src/cx/list.h@6ce8cfa10a96

     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  * Internal type for the list structure - use CxList instead.

    58  */

    59 typedef struct cx_list_s cx_list_s;

    61 /**

    62  * The class definition for arbitrary lists.

    63  */

    64 typedef struct {

    65     /**

    66      * Member function for adding an element.

    67      */

    68     int (*add)(

    69             cx_list_s *list,

    70             void const *elem

    71     );

    73     /**

    74      * Member function for inserting an element.

    75      */

    76     int (*insert)(

    77             cx_list_s *list,

    78             size_t index,

    79             void const *elem

    80     );

    82     /**

    83      * Member function for removing an element.

    84      */

    85     int (*remove)(

    86             cx_list_s *list,

    87             size_t index

    88     );

    90     /**

    91      * Member function for element lookup.

    92      */

    93     void *(*at)(

    94             cx_list_s const *list,

    95             size_t index

    96     );

    98     /**

    99      * Member function for finding an element.

   100      */

   101     size_t (*find)(

   102             cx_list_s const *list,

   103             void const *elem

   104     );

   106     /**

   107      * Member function for sorting the list in place.

   108      */

   109     void (*sort)(cx_list_s *list);

   111     /**

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

   113      */

   114     int (*compare)(

   115             cx_list_s const *list,

   116             cx_list_s const *other

   117     );

   119     /**

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

   121      */

   122     void (*reverse)(cx_list_s *list);

   124     /**

   125      * Returns an iterator pointing to the specified index.

   126      */

   127     CxIterator (*iterator)(

   128             cx_list_s const *list,

   129             size_t index

   130     );

   131 } cx_list_class;

   133 /**

   134  * Structure for holding the base data of a list.

   135  */

   136 struct cx_list_s {

   137     /**

   138      * The list class definition.

   139      */

   140     cx_list_class *cl;

   141     /**

   142      * The allocator to use.

   143      */

   144     CxAllocator allocator;

   145     /**

   146      * The comparator function for the elements.

   147      */

   148     CxListComparator cmpfunc;

   149     /**

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

   151      */

   152     size_t itemsize;

   153     /**

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

   155      */

   156     size_t size;

   157     /**

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

   159      */

   160     size_t capacity;

   161 };

   163 /**

   164  * Common type for all list implementations.

   165  */

   166 typedef cx_list_s *CxList;

   168 /**

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

   170  *

   171  * \remark It is implementation defined whether

   172  * the contents of the element are copied or the

   173  * pointer is added to the list. In the latter case

   174  * the \c itemsize of the list SHALL be \c sizeof(void*).

   175  *

   176  * @param list the list

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

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

   179  */

   180 static inline int cxListAdd(

   181         CxList list,

   182         void const *elem

   183 ) {

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

   185 }

   187 /**

   188  * Inserts an item at the specified index.

   189  *

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

   191  *

   192  * \remark It is implementation defined whether

   193  * the contents of the element are copied or the

   194  * pointer is added to the list. In the latter case

   195  * the \c itemsize of the list SHALL be \c sizeof(void*).

   196  *

   197  * @param list the list

   198  * @param index the index the element shall have

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

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

   201  * or when the index is out of bounds

   202  */

   203 static inline int cxListInsert(

   204         CxList list,

   205         size_t index,

   206         void const *elem

   207 ) {

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

   209 }

   211 /**

   212  * Removes the element at the specified index.

   213  * @param list the list

   214  * @param index the index of the element

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

   216  */

   217 static inline int cxListRemove(

   218         CxList list,

   219         size_t index

   220 ) {

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

   222 }

   224 /**

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

   226  *

   227  * @param list the list

   228  * @param index the index of the element

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

   230  */

   231 static inline void *cxListAt(

   232         CxList list,

   233         size_t index

   234 ) {

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

   236 }

   238 /**

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

   240  *

   241  * The returned iterator is position-aware.

   242  *

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

   244  *

   245  * @param list the list

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

   247  * @return a new iterator

   248  */

   249 static inline CxIterator cxListIterator(

   250         CxList list,

   251         size_t index

   252 ) {

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

   254 }

   256 /**

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

   258  *

   259  * The returned iterator is position-aware.

   260  *

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

   262  *

   263  * @param list the list

   264  * @return a new iterator

   265  */

   266 static inline CxIterator cxListBegin(CxList list) {

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

   268 }

   270 /**

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

   272  *

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

   274  *

   275  * @param list the list

   276  * @param elem the element to find

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

   278  */

   279 static inline size_t cxListFind(

   280         CxList list,

   281         void const *elem

   282 ) {

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

   284 }

   286 /**

   287  * Sorts the list in place.

   288  *

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

   290  *

   291  * @param list the list

   292  */

   293 static inline void cxListSort(CxList list) {

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

   295 }

   297 /**

   298  * Reverses the order of the items.

   299  *

   300  * @param list the list

   301  */

   302 static inline void cxListReverse(CxList list) {

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

   304 }

   306 /**

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

   308  *

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

   310  *

   311  * @param list the list

   312  * @param other the list to compare to

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

   314  */

   315 static inline int cxListCompare(

   316         CxList list,

   317         CxList other

   318 ) {

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

   320 }

   322 #ifdef __cplusplus

   323 } /* extern "C" */

   324 #endif

   326 #endif /* UCX_LIST_H */

Mercurial > hg > ucx / file revision

src/cx/list.h@6ce8cfa10a96

src/cx/list.h