ucx/cx/list.h

   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  */
  36
  37 #ifndef UCX_LIST_H
  38 #define UCX_LIST_H
  39
  40 #include "common.h"
  41 #include "collection.h"
  42
  43 #ifdef __cplusplus
  44 extern "C" {
  45 #endif
  46
  47 /**
  48  * List class type.
  49  */
  50 typedef struct cx_list_class_s cx_list_class;
  51
  52 /**
  53  * Structure for holding the base data of a list.
  54  */
  55 struct cx_list_s {
  56     CX_COLLECTION_MEMBERS
  57     /**
  58      * The list class definition.
  59      */
  60     cx_list_class const *cl;
  61     /**
  62      * The actual implementation in case the list class is delegating.
  63      */
  64     cx_list_class const *climpl;
  65 };
  66
  67 /**
  68  * The class definition for arbitrary lists.
  69  */
  70 struct cx_list_class_s {
  71     /**
  72      * Destructor function.
  73      *
  74      * Implementations SHALL invoke the content destructor functions if provided
  75      * and SHALL deallocate the list memory, if an allocator is provided.
  76      */
  77     void (*destructor)(struct cx_list_s *list);
  78
  79     /**
  80      * Member function for inserting a single element.
  81      * Implementors SHOULD see to performant implementations for corner cases.
  82      */
  83     int (*insert_element)(
  84             struct cx_list_s *list,
  85             size_t index,
  86             void const *data
  87     );
  88
  89     /**
  90      * Member function for inserting multiple elements.
  91      * Implementors SHOULD see to performant implementations for corner cases.
  92      */
  93     size_t (*insert_array)(
  94             struct cx_list_s *list,
  95             size_t index,
  96             void const *data,
  97             size_t n
  98     );
  99
 100     /**
 101      * Member function for inserting an element relative to an iterator position.
 102      */
 103     int (*insert_iter)(
 104             struct cx_mut_iterator_s *iter,
 105             void const *elem,
 106             int prepend
 107     );
 108
 109     /**
 110      * Member function for removing an element.
 111      */
 112     int (*remove)(
 113             struct cx_list_s *list,
 114             size_t index
 115     );
 116
 117     /**
 118      * Member function for removing all elements.
 119      */
 120     void (*clear)(struct cx_list_s *list);
 121
 122     /**
 123      * Member function for swapping two elements.
 124      */
 125     int (*swap)(
 126             struct cx_list_s *list,
 127             size_t i,
 128             size_t j
 129     );
 130
 131     /**
 132      * Member function for element lookup.
 133      */
 134     void *(*at)(
 135             struct cx_list_s const *list,
 136             size_t index
 137     );
 138
 139     /**
 140      * Member function for finding an element.
 141      */
 142     ssize_t (*find)(
 143             struct cx_list_s const *list,
 144             void const *elem
 145     );
 146
 147     /**
 148      * Member function for sorting the list in-place.
 149      */
 150     void (*sort)(struct cx_list_s *list);
 151
 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     );
 159
 160     /**
 161      * Member function for reversing the order of the items.
 162      */
 163     void (*reverse)(struct cx_list_s *list);
 164
 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 };
 174
 175 /**
 176  * Common type for all list implementations.
 177  */
 178 typedef struct cx_list_s CxList;
 179
 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);
 191
 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);
 206
 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 }
 218
 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 }
 229
 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 }
 245
 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 }
 270
 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 }
 292
 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 }
 321
 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 }
 344
 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 }
 367
 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 }
 385
 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 }
 398
 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 }
 418
 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 }
 433
 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 }
 452
 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 }
 471
 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 );
 488
 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 );
 506
 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 }
 521
 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 }
 536
 537
 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 }
 552
 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 }
 567
 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(list, elem);
 584 }
 585
 586 /**
 587  * Sorts the list in-place.
 588  *
 589  * \remark The underlying sort algorithm is implementation defined.
 590  *
 591  * @param list the list
 592  */
 593 __attribute__((__nonnull__))
 594 static inline void cxListSort(CxList *list) {
 595     list->cl->sort(list);
 596 }
 597
 598 /**
 599  * Reverses the order of the items.
 600  *
 601  * @param list the list
 602  */
 603 __attribute__((__nonnull__))
 604 static inline void cxListReverse(CxList *list) {
 605     list->cl->reverse(list);
 606 }
 607
 608 /**
 609  * Compares a list to another list of the same type.
 610  *
 611  * First, the list sizes are compared.
 612  * If they match, the lists are compared element-wise.
 613  *
 614  * @param list the list
 615  * @param other the list to compare to
 616  * @return zero, if both lists are equal element wise,
 617  * negative if the first list is smaller, positive if the first list is larger
 618  */
 619 __attribute__((__nonnull__))
 620 int cxListCompare(
 621         CxList const *list,
 622         CxList const *other
 623 );
 624
 625 /**
 626  * Deallocates the memory of the specified list structure.
 627  *
 628  * Also calls content a destructor function, depending on the configuration
 629  * in CxList.content_destructor_type.
 630  *
 631  * This function itself is a destructor function for the CxList.
 632  *
 633  * @param list the list which shall be destroyed
 634  */
 635 __attribute__((__nonnull__))
 636 void cxListDestroy(CxList *list);
 637
 638 /**
 639  * A shared instance of an empty list.
 640  *
 641  * Writing to that list is undefined.
 642  */
 643 extern CxList * const cxEmptyList;
 644
 645
 646 #ifdef __cplusplus
 647 } // extern "C"
 648 #endif
 649
 650 #endif // UCX_LIST_H