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 "allocator.h"
  42 #include "iterator.h"
  43
  44 #ifdef __cplusplus
  45 extern "C" {
  46 #endif
  47
  48 #ifndef CX_STORE_POINTERS
  49 /**
  50  * Special constant used for creating collections that are storing pointers.
  51  */
  52 #define CX_STORE_POINTERS 0
  53 #endif
  54
  55 /**
  56  * A comparator function comparing two list elements.
  57  */
  58 typedef int(*CxListComparator)(
  59         void const *left,
  60         void const *right
  61 );
  62
  63 /**
  64  * List class type.
  65  */
  66 typedef struct cx_list_class_s cx_list_class;
  67
  68 /**
  69  * Structure for holding the base data of a list.
  70  */
  71 struct cx_list_s {
  72     /**
  73      * The list class definition.
  74      */
  75     cx_list_class const *cl;
  76     /**
  77      * The actual implementation in case the list class is delegating.
  78      */
  79     cx_list_class const *climpl;
  80     /**
  81      * The allocator to use.
  82      */
  83     CxAllocator const *allocator;
  84     /**
  85      * The comparator function for the elements.
  86      */
  87     CxListComparator cmpfunc;
  88     /**
  89      * The size of each element (payload only).
  90      */
  91     size_t itemsize;
  92     /**
  93      * The size of the list (number of currently stored elements).
  94      */
  95     size_t size;
  96     /**
  97      * The capacity of the list (maximum number of elements).
  98      */
  99     size_t capacity;
 100     union {
 101         /**
 102          * An optional simple destructor for the list contents that admits the free() interface.
 103          *
 104          * @remark Set content_destructor_type to #CX_DESTRUCTOR_SIMPLE.
 105          *
 106          * @attention Read the documentation of the particular list implementation
 107          * whether this destructor shall only destroy the contents or also free the memory.
 108          */
 109         cx_destructor_func simple_destructor;
 110         /**
 111          * An optional advanced destructor for the list contents providing additional data.
 112          *
 113          * @remark Set content_destructor_type to #CX_DESTRUCTOR_ADVANCED.
 114          *
 115          * @attention Read the documentation of the particular list implementation
 116          * whether this destructor shall only destroy the contents or also free the memory.
 117          */
 118         cx_advanced_destructor advanced_destructor;
 119     };
 120     /**
 121      * The type of destructor to use.
 122      */
 123     enum cx_destructor_type content_destructor_type;
 124 };
 125
 126 /**
 127  * The class definition for arbitrary lists.
 128  */
 129 struct cx_list_class_s {
 130     /**
 131      * Destructor function.
 132      */
 133     void (*destructor)(struct cx_list_s *list);
 134
 135     /**
 136      * Member function for inserting a single elements.
 137      * Implementors SHOULD see to performant implementations for corner cases.
 138      */
 139     int (*insert_element)(
 140             struct cx_list_s *list,
 141             size_t index,
 142             void const *data
 143     );
 144
 145     /**
 146      * Member function for inserting multiple elements.
 147      * Implementors SHOULD see to performant implementations for corner cases.
 148      */
 149     size_t (*insert_array)(
 150             struct cx_list_s *list,
 151             size_t index,
 152             void const *data,
 153             size_t n
 154     );
 155
 156     /**
 157      * Member function for inserting an element relative to an iterator position.
 158      */
 159     int (*insert_iter)(
 160             struct cx_mut_iterator_s *iter,
 161             void const *elem,
 162             int prepend
 163     );
 164
 165     /**
 166      * Member function for removing an element.
 167      */
 168     int (*remove)(
 169             struct cx_list_s *list,
 170             size_t index
 171     );
 172
 173     /**
 174      * Member function for removing all elements.
 175      */
 176     void (*clear)(struct cx_list_s *list);
 177
 178     /**
 179      * Member function for swapping two elements.
 180      */
 181     int (*swap)(
 182             struct cx_list_s *list,
 183             size_t i,
 184             size_t j
 185     );
 186
 187     /**
 188      * Member function for element lookup.
 189      */
 190     void *(*at)(
 191             struct cx_list_s const *list,
 192             size_t index
 193     );
 194
 195     /**
 196      * Member function for finding an element.
 197      */
 198     size_t (*find)(
 199             struct cx_list_s const *list,
 200             void const *elem
 201     );
 202
 203     /**
 204      * Member function for sorting the list in place.
 205      */
 206     void (*sort)(struct cx_list_s *list);
 207
 208     /**
 209      * Member function for comparing this list to another list of the same type.
 210      */
 211     int (*compare)(
 212             struct cx_list_s const *list,
 213             struct cx_list_s const *other
 214     );
 215
 216     /**
 217      * Member function for reversing the order of the items.
 218      */
 219     void (*reverse)(struct cx_list_s *list);
 220
 221     /**
 222      * Member function for returning an iterator pointing to the specified index.
 223      */
 224     struct cx_iterator_s (*iterator)(
 225             struct cx_list_s const *list,
 226             size_t index,
 227             bool backward
 228     );
 229 };
 230
 231 /**
 232  * Common type for all list implementations.
 233  */
 234 typedef struct cx_list_s CxList;
 235
 236 /**
 237  * Invokes the configured destructor function for a specific element.
 238  *
 239  * Usually only used by list implementations. There should be no need
 240  * to invoke this function manually.
 241  *
 242  * @param list the list
 243  * @param elem the element
 244  */
 245 __attribute__((__nonnull__))
 246 void cx_list_invoke_destructor(
 247         struct cx_list_s const *list,
 248         void *elem
 249 );
 250
 251 /**
 252  * Invokes the simple destructor function for a specific element.
 253  *
 254  * Usually only used by list implementations. There should be no need
 255  * to invoke this function manually.
 256  *
 257  * @param list the list
 258  * @param elem the element
 259  */
 260 __attribute__((__nonnull__))
 261 void cx_list_invoke_simple_destructor(
 262         struct cx_list_s const *list,
 263         void *elem
 264 );
 265
 266 /**
 267  * Invokes the advanced destructor function for a specific element.
 268  *
 269  * Usually only used by list implementations. There should be no need
 270  * to invoke this function manually.
 271  *
 272  * @param list the list
 273  * @param elem the element
 274  */
 275 __attribute__((__nonnull__))
 276 void cx_list_invoke_advanced_destructor(
 277         struct cx_list_s const *list,
 278         void *elem
 279 );
 280
 281 /**
 282  * Advises the list to store copies of the objects (default mode of operation).
 283  *
 284  * Retrieving objects from this list will yield pointers to the copies stored
 285  * within this list.
 286  *
 287  * @param list the list
 288  * @see cxListStorePointers()
 289  */
 290 __attribute__((__nonnull__))
 291 void cxListStoreObjects(CxList *list);
 292
 293 /**
 294  * Advises the list to only store pointers to the objects.
 295  *
 296  * Retrieving objects from this list will yield the original pointers stored.
 297  *
 298  * @note This function forcibly sets the element size to the size of a pointer.
 299  * Invoking this function on a non-empty list that already stores copies of
 300  * objects is undefined.
 301  *
 302  * @param list the list
 303  * @see cxListStoreObjects()
 304  */
 305 __attribute__((__nonnull__))
 306 void cxListStorePointers(CxList *list);
 307
 308 /**
 309  * Returns true, if this list is storing pointers instead of the actual data.
 310  *
 311  * @param list
 312  * @return
 313  * @see cxListStorePointers()
 314  */
 315 __attribute__((__nonnull__))
 316 bool cxListIsStoringPointers(CxList const *list);
 317
 318 /**
 319  * Adds an item to the end of the list.
 320  *
 321  * @param list the list
 322  * @param elem a pointer to the element to add
 323  * @return zero on success, non-zero on memory allocation failure
 324  * @see cxListAddArray()
 325  */
 326 __attribute__((__nonnull__))
 327 static inline int cxListAdd(
 328         CxList *list,
 329         void const *elem
 330 ) {
 331     return list->cl->insert_element(list, list->size, elem);
 332 }
 333
 334 /**
 335  * Adds multiple items to the end of the list.
 336  *
 337  * This method is more efficient than invoking cxListAdd() multiple times.
 338  *
 339  * If there is not enough memory to add all elements, the returned value is
 340  * less than \p n.
 341  *
 342  * If this list is storing pointers instead of objects \p array is expected to
 343  * be an array of pointers.
 344  *
 345  * @param list the list
 346  * @param array a pointer to the elements to add
 347  * @param n the number of elements to add
 348  * @return the number of added elements
 349  */
 350 __attribute__((__nonnull__))
 351 static inline size_t cxListAddArray(
 352         CxList *list,
 353         void const *array,
 354         size_t n
 355 ) {
 356     return list->cl->insert_array(list, list->size, array, n);
 357 }
 358
 359 /**
 360  * Inserts an item at the specified index.
 361  *
 362  * If \p index equals the list \c size, this is effectively cxListAdd().
 363  *
 364  * @param list the list
 365  * @param index the index the element shall have
 366  * @param elem a pointer to the element to add
 367  * @return zero on success, non-zero on memory allocation failure
 368  * or when the index is out of bounds
 369  * @see cxListInsertAfter()
 370  * @see cxListInsertBefore()
 371  */
 372 __attribute__((__nonnull__))
 373 static inline int cxListInsert(
 374         CxList *list,
 375         size_t index,
 376         void const *elem
 377 ) {
 378     return list->cl->insert_element(list, index, elem);
 379 }
 380
 381 /**
 382  * Inserts multiple items to the list at the specified index.
 383  * If \p index equals the list size, this is effectively cxListAddArray().
 384  *
 385  * This method is usually more efficient than invoking cxListInsert()
 386  * multiple times.
 387  *
 388  * If there is not enough memory to add all elements, the returned value is
 389  * less than \p n.
 390  *
 391  * If this list is storing pointers instead of objects \p array is expected to
 392  * be an array of pointers.
 393  *
 394  * @param list the list
 395  * @param index the index where to add the elements
 396  * @param array a pointer to the elements to add
 397  * @param n the number of elements to add
 398  * @return the number of added elements
 399  */
 400 __attribute__((__nonnull__))
 401 static inline size_t cxListInsertArray(
 402         CxList *list,
 403         size_t index,
 404         void const *array,
 405         size_t n
 406 ) {
 407     return list->cl->insert_array(list, index, array, n);
 408 }
 409
 410 /**
 411  * Inserts an element after the current location of the specified iterator.
 412  *
 413  * The used iterator remains operational, but all other active iterators should
 414  * be considered invalidated.
 415  *
 416  * If \p iter is not a list iterator, the behavior is undefined.
 417  * If \p iter is a past-the-end iterator, the new element gets appended to the list.
 418  *
 419  * @param iter an iterator
 420  * @param elem the element to insert
 421  * @return zero on success, non-zero on memory allocation failure
 422  * @see cxListInsert()
 423  * @see cxListInsertBefore()
 424  */
 425 __attribute__((__nonnull__))
 426 static inline int cxListInsertAfter(
 427         CxMutIterator *iter,
 428         void const *elem
 429 ) {
 430     return ((struct cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 0);
 431 }
 432
 433 /**
 434  * Inserts an element before the current location of the specified iterator.
 435  *
 436  * The used iterator remains operational, but all other active iterators should
 437  * be considered invalidated.
 438  *
 439  * If \p iter is not a list iterator, the behavior is undefined.
 440  * If \p iter is a past-the-end iterator, the new element gets appended to the list.
 441  *
 442  * @param iter an iterator
 443  * @param elem the element to insert
 444  * @return zero on success, non-zero on memory allocation failure
 445  * @see cxListInsert()
 446  * @see cxListInsertAfter()
 447  */
 448 __attribute__((__nonnull__))
 449 static inline int cxListInsertBefore(
 450         CxMutIterator *iter,
 451         void const *elem
 452 ) {
 453     return ((struct cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 1);
 454 }
 455
 456 /**
 457  * Removes the element at the specified index.
 458  *
 459  * If an element destructor function is specified, it is called before
 460  * removing the element.
 461  *
 462  * @param list the list
 463  * @param index the index of the element
 464  * @return zero on success, non-zero if the index is out of bounds
 465  */
 466 __attribute__((__nonnull__))
 467 static inline int cxListRemove(
 468         CxList *list,
 469         size_t index
 470 ) {
 471     return list->cl->remove(list, index);
 472 }
 473
 474 /**
 475  * Removes all elements from this list.
 476  *
 477  * If an element destructor function is specified, it is called for each
 478  * element before removing them.
 479  *
 480  * @param list the list
 481  */
 482 __attribute__((__nonnull__))
 483 static inline void cxListClear(CxList *list) {
 484     list->cl->clear(list);
 485 }
 486
 487 /**
 488  * Swaps two items in the list.
 489  *
 490  * Implementations should only allocate temporary memory for the swap, if
 491  * it is necessary.
 492  *
 493  * @param list the list
 494  * @param i the index of the first element
 495  * @param j the index of the second element
 496  * @return zero on success, non-zero if one of the indices is out of bounds
 497  */
 498 __attribute__((__nonnull__))
 499 static inline int cxListSwap(
 500         CxList *list,
 501         size_t i,
 502         size_t j
 503 ) {
 504     return list->cl->swap(list, i, j);
 505 }
 506
 507 /**
 508  * Returns a pointer to the element at the specified index.
 509  *
 510  * @param list the list
 511  * @param index the index of the element
 512  * @return a pointer to the element or \c NULL if the index is out of bounds
 513  */
 514 __attribute__((__nonnull__))
 515 static inline void *cxListAt(
 516         CxList *list,
 517         size_t index
 518 ) {
 519     return list->cl->at(list, index);
 520 }
 521
 522 /**
 523  * Returns an iterator pointing to the item at the specified index.
 524  *
 525  * The returned iterator is position-aware.
 526  *
 527  * If the index is out of range, a past-the-end iterator will be returned.
 528  *
 529  * @param list the list
 530  * @param index the index where the iterator shall point at
 531  * @return a new iterator
 532  */
 533 __attribute__((__nonnull__, __warn_unused_result__))
 534 static inline CxIterator cxListIteratorAt(
 535         CxList const *list,
 536         size_t index
 537 ) {
 538     return list->cl->iterator(list, index, false);
 539 }
 540
 541 /**
 542  * Returns a backwards iterator pointing to the item at the specified index.
 543  *
 544  * The returned iterator is position-aware.
 545  *
 546  * If the index is out of range, a past-the-end iterator will be returned.
 547  *
 548  * @param list the list
 549  * @param index the index where the iterator shall point at
 550  * @return a new iterator
 551  */
 552 __attribute__((__nonnull__, __warn_unused_result__))
 553 static inline CxIterator cxListBackwardsIteratorAt(
 554         CxList const *list,
 555         size_t index
 556 ) {
 557     return list->cl->iterator(list, index, true);
 558 }
 559
 560 /**
 561  * Returns a mutating iterator pointing to the item at the specified index.
 562  *
 563  * The returned iterator is position-aware.
 564  *
 565  * If the index is out of range, a past-the-end iterator will be returned.
 566  *
 567  * @param list the list
 568  * @param index the index where the iterator shall point at
 569  * @return a new iterator
 570  */
 571 __attribute__((__nonnull__, __warn_unused_result__))
 572 CxMutIterator cxListMutIteratorAt(
 573         CxList *list,
 574         size_t index
 575 );
 576
 577 /**
 578  * Returns a mutating backwards iterator pointing to the item at the
 579  * specified index.
 580  *
 581  * The returned iterator is position-aware.
 582  *
 583  * If the index is out of range, a past-the-end iterator will be returned.
 584  *
 585  * @param list the list
 586  * @param index the index where the iterator shall point at
 587  * @return a new iterator
 588  */
 589 __attribute__((__nonnull__, __warn_unused_result__))
 590 CxMutIterator cxListMutBackwardsIteratorAt(
 591         CxList *list,
 592         size_t index
 593 );
 594
 595 /**
 596  * Returns an iterator pointing to the first item of the list.
 597  *
 598  * The returned iterator is position-aware.
 599  *
 600  * If the list is empty, a past-the-end iterator will be returned.
 601  *
 602  * @param list the list
 603  * @return a new iterator
 604  */
 605 __attribute__((__nonnull__, __warn_unused_result__))
 606 static inline CxIterator cxListIterator(CxList const *list) {
 607     return list->cl->iterator(list, 0, false);
 608 }
 609
 610 /**
 611  * Returns a mutating iterator pointing to the first item of the list.
 612  *
 613  * The returned iterator is position-aware.
 614  *
 615  * If the list is empty, a past-the-end iterator will be returned.
 616  *
 617  * @param list the list
 618  * @return a new iterator
 619  */
 620 __attribute__((__nonnull__, __warn_unused_result__))
 621 static inline CxMutIterator cxListMutIterator(CxList *list) {
 622     return cxListMutIteratorAt(list, 0);
 623 }
 624
 625
 626 /**
 627  * Returns a backwards iterator pointing to the last item of the list.
 628  *
 629  * The returned iterator is position-aware.
 630  *
 631  * If the list is empty, a past-the-end iterator will be returned.
 632  *
 633  * @param list the list
 634  * @return a new iterator
 635  */
 636 __attribute__((__nonnull__, __warn_unused_result__))
 637 static inline CxIterator cxListBackwardsIterator(CxList const *list) {
 638     return list->cl->iterator(list, list->size - 1, true);
 639 }
 640
 641 /**
 642  * Returns a mutating backwards iterator pointing to the last item of the list.
 643  *
 644  * The returned iterator is position-aware.
 645  *
 646  * If the list is empty, a past-the-end iterator will be returned.
 647  *
 648  * @param list the list
 649  * @return a new iterator
 650  */
 651 __attribute__((__nonnull__, __warn_unused_result__))
 652 static inline CxMutIterator cxListMutBackwardsIterator(CxList *list) {
 653     return cxListMutBackwardsIteratorAt(list, list->size - 1);
 654 }
 655
 656 /**
 657  * Returns the index of the first element that equals \p elem.
 658  *
 659  * Determining equality is performed by the list's comparator function.
 660  *
 661  * @param list the list
 662  * @param elem the element to find
 663  * @return the index of the element or \c (size+1) if the element is not found
 664  */
 665 __attribute__((__nonnull__))
 666 static inline size_t cxListFind(
 667         CxList const *list,
 668         void const *elem
 669 ) {
 670     return list->cl->find(list, elem);
 671 }
 672
 673 /**
 674  * Sorts the list in place.
 675  *
 676  * \remark The underlying sort algorithm is implementation defined.
 677  *
 678  * @param list the list
 679  */
 680 __attribute__((__nonnull__))
 681 static inline void cxListSort(CxList *list) {
 682     list->cl->sort(list);
 683 }
 684
 685 /**
 686  * Reverses the order of the items.
 687  *
 688  * @param list the list
 689  */
 690 __attribute__((__nonnull__))
 691 static inline void cxListReverse(CxList *list) {
 692     list->cl->reverse(list);
 693 }
 694
 695 /**
 696  * Compares a list to another list of the same type.
 697  *
 698  * First, the list sizes are compared.
 699  * If they match, the lists are compared element-wise.
 700  *
 701  * @param list the list
 702  * @param other the list to compare to
 703  * @return zero, if both lists are equal element wise,
 704  * negative if the first list is smaller, positive if the first list is larger
 705  */
 706 __attribute__((__nonnull__))
 707 int cxListCompare(
 708         CxList const *list,
 709         CxList const *other
 710 );
 711
 712 /**
 713  * Deallocates the memory of the specified list structure.
 714  *
 715  * Also calls content a destructor function, depending on the configuration
 716  * in CxList.content_destructor_type.
 717  *
 718  * This function itself is a destructor function for the CxList.
 719  *
 720  * @param list the list which shall be destroyed
 721  */
 722 __attribute__((__nonnull__))
 723 void cxListDestroy(CxList *list);
 724
 725 #ifdef __cplusplus
 726 } // extern "C"
 727 #endif
 728
 729 #endif // UCX_LIST_H