Mercurial > hg > dav / file comparison

comparison: ucx/cx/list.h

ucx/cx/list.h

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

Mercurial Repository: dav

mercurial