Tue, 28 Mar 2023 21:00:33 +0200
allow NULL for allocator and comparator
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 #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
55 /**
56 * A comparator function comparing two list elements.
57 */
58 typedef int(*CxListComparator)(
59 void const *left,
60 void const *right
61 );
63 /**
64 * List class type.
65 */
66 typedef struct cx_list_class_s cx_list_class;
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 };
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);
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 );
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 );
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 );
165 /**
166 * Member function for removing an element.
167 */
168 int (*remove)(
169 struct cx_list_s *list,
170 size_t index
171 );
173 /**
174 * Member function for removing all elements.
175 */
176 void (*clear)(struct cx_list_s *list);
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 );
187 /**
188 * Member function for element lookup.
189 */
190 void *(*at)(
191 struct cx_list_s const *list,
192 size_t index
193 );
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 );
203 /**
204 * Member function for sorting the list in place.
205 */
206 void (*sort)(struct cx_list_s *list);
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 );
216 /**
217 * Member function for reversing the order of the items.
218 */
219 void (*reverse)(struct cx_list_s *list);
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 };
231 /**
232 * Common type for all list implementations.
233 */
234 typedef struct cx_list_s CxList;
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 );
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 );
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 );
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);
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);
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);
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 );
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 );
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 );
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);
725 #ifdef __cplusplus
726 } // extern "C"
727 #endif
729 #endif // UCX_LIST_H