ucx: src/cx/list.h@3dc9075df822

     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 inserting an element relative to an iterator position.

    84      */

    85     int (*insert_iter)(

    86             CxIterator *iter,

    87             void const *elem,

    88             int prepend

    89     );

    91     /**

    92      * Member function for removing an element.

    93      */

    94     int (*remove)(

    95             cx_list_s *list,

    96             size_t index

    97     );

    99     /**

   100      * Member function for element lookup.

   101      */

   102     void *(*at)(

   103             cx_list_s const *list,

   104             size_t index

   105     );

   107     /**

   108      * Member function for finding an element.

   109      */

   110     size_t (*find)(

   111             cx_list_s const *list,

   112             void const *elem

   113     );

   115     /**

   116      * Member function for sorting the list in place.

   117      */

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

   120     /**

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

   122      */

   123     int (*compare)(

   124             cx_list_s const *list,

   125             cx_list_s const *other

   126     );

   128     /**

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

   130      */

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

   133     /**

   134      * Returns an iterator pointing to the specified index.

   135      */

   136     CxIterator (*iterator)(

   137             cx_list_s *list,

   138             size_t index

   139     );

   140 } cx_list_class;

   142 /**

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

   144  */

   145 struct cx_list_s {

   146     /**

   147      * The list class definition.

   148      */

   149     cx_list_class *cl;

   150     /**

   151      * The allocator to use.

   152      */

   153     CxAllocator allocator;

   154     /**

   155      * The comparator function for the elements.

   156      */

   157     CxListComparator cmpfunc;

   158     /**

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

   160      */

   161     size_t itemsize;

   162     /**

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

   164      */

   165     size_t size;

   166     /**

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

   168      */

   169     size_t capacity;

   170 };

   172 /**

   173  * Common type for all list implementations.

   174  */

   175 typedef cx_list_s *CxList;

   177 /**

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

   179  *

   180  * @param list the list

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

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

   183  */

   184 static inline int cxListAdd(

   185         CxList list,

   186         void const *elem

   187 ) {

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

   189 }

   191 /**

   192  * Inserts an item at the specified index.

   193  *

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

   195  *

   196  * @param list the list

   197  * @param index the index the element shall have

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

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

   200  * or when the index is out of bounds

   201  * @see cxListInsertAfter()

   202  * @see cxListInsertBefore()

   203  */

   204 static inline int cxListInsert(

   205         CxList list,

   206         size_t index,

   207         void const *elem

   208 ) {

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

   210 }

   212 /**

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

   214  *

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

   216  * be considered invalidated.

   217  *

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

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

   220  *

   221  * @param iter an iterator

   222  * @param elem the element to insert

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

   224  * @see cxListInsert()

   225  * @see cxListInsertBefore()

   226  */

   227 static inline int cxListInsertAfter(

   228         CxIterator *iter,

   229         void const *elem

   230 ) {

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

   232 }

   234 /**

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

   236  *

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

   238  * be considered invalidated.

   239  *

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

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

   242  *

   243  * @param iter an iterator

   244  * @param elem the element to insert

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

   246  * @see cxListInsert()

   247  * @see cxListInsertAfter()

   248  */

   249 static inline int cxListInsertBefore(

   250         CxIterator *iter,

   251         void const *elem

   252 ) {

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

   254 }

   256 /**

   257  * Removes the element at the specified index.

   258  * @param list the list

   259  * @param index the index of the element

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

   261  */

   262 static inline int cxListRemove(

   263         CxList list,

   264         size_t index

   265 ) {

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

   267 }

   269 /**

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

   271  *

   272  * @param list the list

   273  * @param index the index of the element

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

   275  */

   276 static inline void *cxListAt(

   277         CxList list,

   278         size_t index

   279 ) {

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

   281 }

   283 /**

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

   285  *

   286  * The returned iterator is position-aware.

   287  *

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

   289  *

   290  * @param list the list

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

   292  * @return a new iterator

   293  */

   294 static inline CxIterator cxListIterator(

   295         CxList list,

   296         size_t index

   297 ) {

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

   299 }

   301 /**

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

   303  *

   304  * The returned iterator is position-aware.

   305  *

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

   307  *

   308  * @param list the list

   309  * @return a new iterator

   310  */

   311 static inline CxIterator cxListBegin(CxList list) {

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

   313 }

   315 /**

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

   317  *

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

   319  *

   320  * @param list the list

   321  * @param elem the element to find

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

   323  */

   324 static inline size_t cxListFind(

   325         CxList list,

   326         void const *elem

   327 ) {

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

   329 }

   331 /**

   332  * Sorts the list in place.

   333  *

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

   335  *

   336  * @param list the list

   337  */

   338 static inline void cxListSort(CxList list) {

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

   340 }

   342 /**

   343  * Reverses the order of the items.

   344  *

   345  * @param list the list

   346  */

   347 static inline void cxListReverse(CxList list) {

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

   349 }

   351 /**

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

   353  *

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

   355  *

   356  * @param list the list

   357  * @param other the list to compare to

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

   359  */

   360 static inline int cxListCompare(

   361         CxList list,

   362         CxList other

   363 ) {

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

   365 }

   367 #ifdef __cplusplus

   368 } /* extern "C" */

   369 #endif

   371 #endif /* UCX_LIST_H */

Mercurial > hg > ucx / file revision

src/cx/list.h@3dc9075df822

src/cx/list.h