src/cx/list.h

Mon, 18 Dec 2023 18:22:53 +0100

author
Mike Becker <universe@uap-core.de>
date
Mon, 18 Dec 2023 18:22:53 +0100
changeset 764
ccbdbd088455
parent 759
475335643af4
permissions
-rw-r--r--

add cxListFindRemove and cx_linked_list_find_node

resolves #339

     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  * \copyright 2-Clause BSD License
    34  */
    36 #ifndef UCX_LIST_H
    37 #define UCX_LIST_H
    39 #include "common.h"
    40 #include "collection.h"
    42 #ifdef __cplusplus
    43 extern "C" {
    44 #endif
    46 /**
    47  * List class type.
    48  */
    49 typedef struct cx_list_class_s cx_list_class;
    51 /**
    52  * Structure for holding the base data of a list.
    53  */
    54 struct cx_list_s {
    55     CX_COLLECTION_MEMBERS
    56     /**
    57      * The list class definition.
    58      */
    59     cx_list_class const *cl;
    60     /**
    61      * The actual implementation in case the list class is delegating.
    62      */
    63     cx_list_class const *climpl;
    64 };
    66 /**
    67  * The class definition for arbitrary lists.
    68  */
    69 struct cx_list_class_s {
    70     /**
    71      * Destructor function.
    72      *
    73      * Implementations SHALL invoke the content destructor functions if provided
    74      * and SHALL deallocate the list memory, if an allocator is provided.
    75      */
    76     void (*destructor)(struct cx_list_s *list);
    78     /**
    79      * Member function for inserting a single element.
    80      * Implementors SHOULD see to performant implementations for corner cases.
    81      */
    82     int (*insert_element)(
    83             struct cx_list_s *list,
    84             size_t index,
    85             void const *data
    86     );
    88     /**
    89      * Member function for inserting multiple elements.
    90      * Implementors SHOULD see to performant implementations for corner cases.
    91      */
    92     size_t (*insert_array)(
    93             struct cx_list_s *list,
    94             size_t index,
    95             void const *data,
    96             size_t n
    97     );
    99     /**
   100      * Member function for inserting an element relative to an iterator position.
   101      */
   102     int (*insert_iter)(
   103             struct cx_mut_iterator_s *iter,
   104             void const *elem,
   105             int prepend
   106     );
   108     /**
   109      * Member function for removing an element.
   110      */
   111     int (*remove)(
   112             struct cx_list_s *list,
   113             size_t index
   114     );
   116     /**
   117      * Member function for removing all elements.
   118      */
   119     void (*clear)(struct cx_list_s *list);
   121     /**
   122      * Member function for swapping two elements.
   123      */
   124     int (*swap)(
   125             struct cx_list_s *list,
   126             size_t i,
   127             size_t j
   128     );
   130     /**
   131      * Member function for element lookup.
   132      */
   133     void *(*at)(
   134             struct cx_list_s const *list,
   135             size_t index
   136     );
   138     /**
   139      * Member function for finding and optionally removing an element.
   140      */
   141     ssize_t (*find_remove)(
   142             struct cx_list_s *list,
   143             void const *elem,
   144             bool remove
   145     );
   147     /**
   148      * Member function for sorting the list in-place.
   149      */
   150     void (*sort)(struct cx_list_s *list);
   152     /**
   153      * Member function for comparing this list to another list of the same type.
   154      */
   155     int (*compare)(
   156             struct cx_list_s const *list,
   157             struct cx_list_s const *other
   158     );
   160     /**
   161      * Member function for reversing the order of the items.
   162      */
   163     void (*reverse)(struct cx_list_s *list);
   165     /**
   166      * Member function for returning an iterator pointing to the specified index.
   167      */
   168     struct cx_iterator_s (*iterator)(
   169             struct cx_list_s const *list,
   170             size_t index,
   171             bool backward
   172     );
   173 };
   175 /**
   176  * Common type for all list implementations.
   177  */
   178 typedef struct cx_list_s CxList;
   180 /**
   181  * Advises the list to store copies of the objects (default mode of operation).
   182  *
   183  * Retrieving objects from this list will yield pointers to the copies stored
   184  * within this list.
   185  *
   186  * @param list the list
   187  * @see cxListStorePointers()
   188  */
   189 __attribute__((__nonnull__))
   190 void cxListStoreObjects(CxList *list);
   192 /**
   193  * Advises the list to only store pointers to the objects.
   194  *
   195  * Retrieving objects from this list will yield the original pointers stored.
   196  *
   197  * @note This function forcibly sets the element size to the size of a pointer.
   198  * Invoking this function on a non-empty list that already stores copies of
   199  * objects is undefined.
   200  *
   201  * @param list the list
   202  * @see cxListStoreObjects()
   203  */
   204 __attribute__((__nonnull__))
   205 void cxListStorePointers(CxList *list);
   207 /**
   208  * Returns true, if this list is storing pointers instead of the actual data.
   209  *
   210  * @param list
   211  * @return true, if this list is storing pointers
   212  * @see cxListStorePointers()
   213  */
   214 __attribute__((__nonnull__))
   215 static inline bool cxListIsStoringPointers(CxList const *list) {
   216     return list->store_pointer;
   217 }
   219 /**
   220  * Returns the number of elements currently stored in the list.
   221  *
   222  * @param list the list
   223  * @return the number of currently stored elements
   224  */
   225 __attribute__((__nonnull__))
   226 static inline size_t cxListSize(CxList const *list) {
   227     return list->size;
   228 }
   230 /**
   231  * Adds an item to the end of the list.
   232  *
   233  * @param list the list
   234  * @param elem a pointer to the element to add
   235  * @return zero on success, non-zero on memory allocation failure
   236  * @see cxListAddArray()
   237  */
   238 __attribute__((__nonnull__))
   239 static inline int cxListAdd(
   240         CxList *list,
   241         void const *elem
   242 ) {
   243     return list->cl->insert_element(list, list->size, elem);
   244 }
   246 /**
   247  * Adds multiple items to the end of the list.
   248  *
   249  * This method is more efficient than invoking cxListAdd() multiple times.
   250  *
   251  * If there is not enough memory to add all elements, the returned value is
   252  * less than \p n.
   253  *
   254  * If this list is storing pointers instead of objects \p array is expected to
   255  * be an array of pointers.
   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->insert_array(list, list->size, 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_element(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  * If this list is storing pointers instead of objects \p array is expected to
   304  * be an array of pointers.
   305  *
   306  * @param list the list
   307  * @param index the index where to add the elements
   308  * @param array a pointer to the elements to add
   309  * @param n the number of elements to add
   310  * @return the number of added elements
   311  */
   312 __attribute__((__nonnull__))
   313 static inline size_t cxListInsertArray(
   314         CxList *list,
   315         size_t index,
   316         void const *array,
   317         size_t n
   318 ) {
   319     return list->cl->insert_array(list, index, array, n);
   320 }
   322 /**
   323  * Inserts an element after the current location of the specified iterator.
   324  *
   325  * The used iterator remains operational, but all other active iterators should
   326  * be considered invalidated.
   327  *
   328  * If \p iter is not a list iterator, the behavior is undefined.
   329  * If \p iter is a past-the-end iterator, the new element gets appended to the list.
   330  *
   331  * @param iter an iterator
   332  * @param elem the element to insert
   333  * @return zero on success, non-zero on memory allocation failure
   334  * @see cxListInsert()
   335  * @see cxListInsertBefore()
   336  */
   337 __attribute__((__nonnull__))
   338 static inline int cxListInsertAfter(
   339         CxMutIterator *iter,
   340         void const *elem
   341 ) {
   342     return ((struct cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 0);
   343 }
   345 /**
   346  * Inserts an element before the current location of the specified iterator.
   347  *
   348  * The used iterator remains operational, but all other active iterators should
   349  * be considered invalidated.
   350  *
   351  * If \p iter is not a list iterator, the behavior is undefined.
   352  * If \p iter is a past-the-end iterator, the new element gets appended to the list.
   353  *
   354  * @param iter an iterator
   355  * @param elem the element to insert
   356  * @return zero on success, non-zero on memory allocation failure
   357  * @see cxListInsert()
   358  * @see cxListInsertAfter()
   359  */
   360 __attribute__((__nonnull__))
   361 static inline int cxListInsertBefore(
   362         CxMutIterator *iter,
   363         void const *elem
   364 ) {
   365     return ((struct cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 1);
   366 }
   368 /**
   369  * Removes the element at the specified index.
   370  *
   371  * If an element destructor function is specified, it is called before
   372  * removing the element.
   373  *
   374  * @param list the list
   375  * @param index the index of the element
   376  * @return zero on success, non-zero if the index is out of bounds
   377  */
   378 __attribute__((__nonnull__))
   379 static inline int cxListRemove(
   380         CxList *list,
   381         size_t index
   382 ) {
   383     return list->cl->remove(list, index);
   384 }
   386 /**
   387  * Removes all elements from this list.
   388  *
   389  * If an element destructor function is specified, it is called for each
   390  * element before removing them.
   391  *
   392  * @param list the list
   393  */
   394 __attribute__((__nonnull__))
   395 static inline void cxListClear(CxList *list) {
   396     list->cl->clear(list);
   397 }
   399 /**
   400  * Swaps two items in the list.
   401  *
   402  * Implementations should only allocate temporary memory for the swap, if
   403  * it is necessary.
   404  *
   405  * @param list the list
   406  * @param i the index of the first element
   407  * @param j the index of the second element
   408  * @return zero on success, non-zero if one of the indices is out of bounds
   409  */
   410 __attribute__((__nonnull__))
   411 static inline int cxListSwap(
   412         CxList *list,
   413         size_t i,
   414         size_t j
   415 ) {
   416     return list->cl->swap(list, i, j);
   417 }
   419 /**
   420  * Returns a pointer to the element at the specified index.
   421  *
   422  * @param list the list
   423  * @param index the index of the element
   424  * @return a pointer to the element or \c NULL if the index is out of bounds
   425  */
   426 __attribute__((__nonnull__))
   427 static inline void *cxListAt(
   428         CxList *list,
   429         size_t index
   430 ) {
   431     return list->cl->at(list, index);
   432 }
   434 /**
   435  * Returns an iterator pointing to the item at the specified index.
   436  *
   437  * The returned iterator is position-aware.
   438  *
   439  * If the index is out of range, a past-the-end iterator will be returned.
   440  *
   441  * @param list the list
   442  * @param index the index where the iterator shall point at
   443  * @return a new iterator
   444  */
   445 __attribute__((__nonnull__, __warn_unused_result__))
   446 static inline CxIterator cxListIteratorAt(
   447         CxList const *list,
   448         size_t index
   449 ) {
   450     return list->cl->iterator(list, index, false);
   451 }
   453 /**
   454  * Returns a backwards iterator pointing to the item at the specified index.
   455  *
   456  * The returned iterator is position-aware.
   457  *
   458  * If the index is out of range, a past-the-end iterator will be returned.
   459  *
   460  * @param list the list
   461  * @param index the index where the iterator shall point at
   462  * @return a new iterator
   463  */
   464 __attribute__((__nonnull__, __warn_unused_result__))
   465 static inline CxIterator cxListBackwardsIteratorAt(
   466         CxList const *list,
   467         size_t index
   468 ) {
   469     return list->cl->iterator(list, index, true);
   470 }
   472 /**
   473  * Returns a mutating iterator pointing to the item at the specified index.
   474  *
   475  * The returned iterator is position-aware.
   476  *
   477  * If the index is out of range, a past-the-end iterator will be returned.
   478  *
   479  * @param list the list
   480  * @param index the index where the iterator shall point at
   481  * @return a new iterator
   482  */
   483 __attribute__((__nonnull__, __warn_unused_result__))
   484 CxMutIterator cxListMutIteratorAt(
   485         CxList *list,
   486         size_t index
   487 );
   489 /**
   490  * Returns a mutating backwards iterator pointing to the item at the
   491  * specified index.
   492  *
   493  * The returned iterator is position-aware.
   494  *
   495  * If the index is out of range, a past-the-end iterator will be returned.
   496  *
   497  * @param list the list
   498  * @param index the index where the iterator shall point at
   499  * @return a new iterator
   500  */
   501 __attribute__((__nonnull__, __warn_unused_result__))
   502 CxMutIterator cxListMutBackwardsIteratorAt(
   503         CxList *list,
   504         size_t index
   505 );
   507 /**
   508  * Returns an iterator pointing to the first item of the list.
   509  *
   510  * The returned iterator is position-aware.
   511  *
   512  * If the list is empty, a past-the-end iterator will be returned.
   513  *
   514  * @param list the list
   515  * @return a new iterator
   516  */
   517 __attribute__((__nonnull__, __warn_unused_result__))
   518 static inline CxIterator cxListIterator(CxList const *list) {
   519     return list->cl->iterator(list, 0, false);
   520 }
   522 /**
   523  * Returns a mutating iterator pointing to the first item of the list.
   524  *
   525  * The returned iterator is position-aware.
   526  *
   527  * If the list is empty, a past-the-end iterator will be returned.
   528  *
   529  * @param list the list
   530  * @return a new iterator
   531  */
   532 __attribute__((__nonnull__, __warn_unused_result__))
   533 static inline CxMutIterator cxListMutIterator(CxList *list) {
   534     return cxListMutIteratorAt(list, 0);
   535 }
   538 /**
   539  * Returns a backwards iterator pointing to the last item of the list.
   540  *
   541  * The returned iterator is position-aware.
   542  *
   543  * If the list is empty, a past-the-end iterator will be returned.
   544  *
   545  * @param list the list
   546  * @return a new iterator
   547  */
   548 __attribute__((__nonnull__, __warn_unused_result__))
   549 static inline CxIterator cxListBackwardsIterator(CxList const *list) {
   550     return list->cl->iterator(list, list->size - 1, true);
   551 }
   553 /**
   554  * Returns a mutating backwards iterator pointing to the last item of the list.
   555  *
   556  * The returned iterator is position-aware.
   557  *
   558  * If the list is empty, a past-the-end iterator will be returned.
   559  *
   560  * @param list the list
   561  * @return a new iterator
   562  */
   563 __attribute__((__nonnull__, __warn_unused_result__))
   564 static inline CxMutIterator cxListMutBackwardsIterator(CxList *list) {
   565     return cxListMutBackwardsIteratorAt(list, list->size - 1);
   566 }
   568 /**
   569  * Returns the index of the first element that equals \p elem.
   570  *
   571  * Determining equality is performed by the list's comparator function.
   572  *
   573  * @param list the list
   574  * @param elem the element to find
   575  * @return the index of the element or a negative
   576  * value when the element is not found
   577  */
   578 __attribute__((__nonnull__))
   579 static inline ssize_t cxListFind(
   580         CxList const *list,
   581         void const *elem
   582 ) {
   583     return list->cl->find_remove((CxList*)list, elem, false);
   584 }
   586 /**
   587  * Removes and returns the index of the first element that equals \p elem.
   588  *
   589  * Determining equality is performed by the list's comparator function.
   590  *
   591  * @param list the list
   592  * @param elem the element to find and remove
   593  * @return the index of the now removed element or a negative
   594  * value when the element is not found or could not be removed
   595  */
   596 __attribute__((__nonnull__))
   597 static inline ssize_t cxListFindRemove(
   598         CxList *list,
   599         void const *elem
   600 ) {
   601     return list->cl->find_remove(list, elem, true);
   602 }
   604 /**
   605  * Sorts the list in-place.
   606  *
   607  * \remark The underlying sort algorithm is implementation defined.
   608  *
   609  * @param list the list
   610  */
   611 __attribute__((__nonnull__))
   612 static inline void cxListSort(CxList *list) {
   613     list->cl->sort(list);
   614 }
   616 /**
   617  * Reverses the order of the items.
   618  *
   619  * @param list the list
   620  */
   621 __attribute__((__nonnull__))
   622 static inline void cxListReverse(CxList *list) {
   623     list->cl->reverse(list);
   624 }
   626 /**
   627  * Compares a list to another list of the same type.
   628  *
   629  * First, the list sizes are compared.
   630  * If they match, the lists are compared element-wise.
   631  *
   632  * @param list the list
   633  * @param other the list to compare to
   634  * @return zero, if both lists are equal element wise,
   635  * negative if the first list is smaller, positive if the first list is larger
   636  */
   637 __attribute__((__nonnull__))
   638 int cxListCompare(
   639         CxList const *list,
   640         CxList const *other
   641 );
   643 /**
   644  * Deallocates the memory of the specified list structure.
   645  *
   646  * Also calls content a destructor function, depending on the configuration
   647  * in CxList.content_destructor_type.
   648  *
   649  * This function itself is a destructor function for the CxList.
   650  *
   651  * @param list the list which shall be destroyed
   652  */
   653 __attribute__((__nonnull__))
   654 void cxListDestroy(CxList *list);
   656 /**
   657  * A shared instance of an empty list.
   658  *
   659  * Writing to that list is undefined.
   660  */
   661 extern CxList * const cxEmptyList;
   664 #ifdef __cplusplus
   665 } // extern "C"
   666 #endif
   668 #endif // UCX_LIST_H

mercurial