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