Mercurial > hg > ucx / file comparison

comparison: src/cx/list.h

src/cx/list.h

changeset 1426
3a89b31f0724
parent 1424
563033aa998c
child 1428
0ac4aa1737fd
equal deleted inserted replaced
1425:83284b289430 1426:3a89b31f0724
37 #define UCX_LIST_H 37 #define UCX_LIST_H
38 38
39 #include "common.h" 39 #include "common.h"
40 #include "collection.h" 40 #include "collection.h"
41 41
42 #include <assert.h>
43
44 #ifdef __cplusplus 42 #ifdef __cplusplus
45 extern "C" { 43 extern "C" {
46 #endif 44 #endif
47 45
48 /** 46 /**
83 /** 81 /**
84 * Member function for inserting a single element. 82 * Member function for inserting a single element.
85 * The data pointer may be @c NULL, in which case the function shall only allocate memory. 83 * The data pointer may be @c NULL, in which case the function shall only allocate memory.
86 * Returns a pointer to the allocated memory or @c NULL if allocation fails. 84 * Returns a pointer to the allocated memory or @c NULL if allocation fails.
87 */ 85 */
88 void *(*insert_element)( 86 void *(*insert_element)(struct cx_list_s *list, size_t index, const void *data);
89 struct cx_list_s *list,
90 size_t index,
91 const void *data
92 );
93 87
94 /** 88 /**
95 * Member function for inserting multiple elements. 89 * Member function for inserting multiple elements.
96 * 90 *
97 * @see cx_list_default_insert_array() 91 * @see cx_list_default_insert_array()
98 */ 92 */
99 size_t (*insert_array)( 93 size_t (*insert_array)(struct cx_list_s *list, size_t index, const void *data, size_t n);
100 struct cx_list_s *list,
101 size_t index,
102 const void *data,
103 size_t n
104 );
105 94
106 /** 95 /**
107 * Member function for inserting sorted elements into a sorted list. 96 * Member function for inserting sorted elements into a sorted list.
108 * 97 *
109 * @see cx_list_default_insert_sorted() 98 * @see cx_list_default_insert_sorted()
110 */ 99 */
111 size_t (*insert_sorted)( 100 size_t (*insert_sorted)(struct cx_list_s *list, const void *sorted_data, size_t n);
112 struct cx_list_s *list,
113 const void *sorted_data,
114 size_t n
115 );
116 101
117 /** 102 /**
118 * Member function for inserting multiple elements if they do not exist. 103 * Member function for inserting multiple elements if they do not exist.
119 * 104 *
120 * @see cx_list_default_insert_unique() 105 * @see cx_list_default_insert_unique()
121 */ 106 */
122 size_t (*insert_unique)( 107 size_t (*insert_unique)(struct cx_list_s *list, const void *sorted_data, size_t n);
123 struct cx_list_s *list,
124 const void *sorted_data,
125 size_t n
126 );
127 108
128 /** 109 /**
129 * Member function for inserting an element relative to an iterator position. 110 * Member function for inserting an element relative to an iterator position.
130 */ 111 */
131 int (*insert_iter)( 112 int (*insert_iter)(struct cx_iterator_s *iter, const void *elem, int prepend);
132 struct cx_iterator_s *iter,
133 const void *elem,
134 int prepend
135 );
136 113
137 /** 114 /**
138 * Member function for removing elements. 115 * Member function for removing elements.
139 * 116 *
140 * Implementations SHALL check if @p targetbuf is set and copy the elements 117 * Implementations SHALL check if @p targetbuf is set and copy the elements
142 * When @p targetbuf is not set, the destructors SHALL be invoked. 119 * When @p targetbuf is not set, the destructors SHALL be invoked.
143 * 120 *
144 * The function SHALL return the actual number of elements removed, which 121 * The function SHALL return the actual number of elements removed, which
145 * might be lower than @p num when going out of bounds. 122 * might be lower than @p num when going out of bounds.
146 */ 123 */
147 size_t (*remove)( 124 size_t (*remove)(struct cx_list_s *list, size_t index, size_t num, void *targetbuf);
148 struct cx_list_s *list,
149 size_t index,
150 size_t num,
151 void *targetbuf
152 );
153 125
154 /** 126 /**
155 * Member function for removing all elements. 127 * Member function for removing all elements.
156 */ 128 */
157 void (*clear)(struct cx_list_s *list); 129 void (*clear)(struct cx_list_s *list);
159 /** 131 /**
160 * Member function for swapping two elements. 132 * Member function for swapping two elements.
161 * 133 *
162 * @see cx_list_default_swap() 134 * @see cx_list_default_swap()
163 */ 135 */
164 int (*swap)( 136 int (*swap)(struct cx_list_s *list, size_t i, size_t j);
165 struct cx_list_s *list,
166 size_t i,
167 size_t j
168 );
169 137
170 /** 138 /**
171 * Member function for element lookup. 139 * Member function for element lookup.
172 */ 140 */
173 void *(*at)( 141 void *(*at)(const struct cx_list_s *list, size_t index);
174 const struct cx_list_s *list,
175 size_t index
176 );
177 142
178 /** 143 /**
179 * Member function for finding and optionally removing an element. 144 * Member function for finding and optionally removing an element.
180 */ 145 */
181 size_t (*find_remove)( 146 size_t (*find_remove)(struct cx_list_s *list, const void *elem, bool remove);
182 struct cx_list_s *list,
183 const void *elem,
184 bool remove
185 );
186 147
187 /** 148 /**
188 * Member function for sorting the list. 149 * Member function for sorting the list.
189 * 150 *
190 * @see cx_list_default_sort() 151 * @see cx_list_default_sort()
194 /** 155 /**
195 * Optional member function for comparing this list 156 * Optional member function for comparing this list
196 * to another list of the same type. 157 * to another list of the same type.
197 * If set to @c NULL, the comparison won't be optimized. 158 * If set to @c NULL, the comparison won't be optimized.
198 */ 159 */
199 int (*compare)( 160 int (*compare)(const struct cx_list_s *list, const struct cx_list_s *other);
200 const struct cx_list_s *list,
201 const struct cx_list_s *other
202 );
203 161
204 /** 162 /**
205 * Member function for reversing the order of the items. 163 * Member function for reversing the order of the items.
206 */ 164 */
207 void (*reverse)(struct cx_list_s *list); 165 void (*reverse)(struct cx_list_s *list);
208 166
209 /** 167 /**
210 * Member function for returning an iterator pointing to the specified index. 168 * Member function for returning an iterator pointing to the specified index.
211 */ 169 */
212 struct cx_iterator_s (*iterator)( 170 struct cx_iterator_s (*iterator)(const struct cx_list_s *list, size_t index, bool backward);
213 const struct cx_list_s *list,
214 size_t index,
215 bool backward
216 );
217 }; 171 };
218 172
219 /** 173 /**
220 * Common type for all list implementations. 174 * Common type for all list implementations.
221 */ 175 */
227 * Writing to that list is not allowed. 181 * Writing to that list is not allowed.
228 * 182 *
229 * You can use this as a placeholder for initializing CxList pointers 183 * You can use this as a placeholder for initializing CxList pointers
230 * for which you do not want to reserve memory right from the beginning. 184 * for which you do not want to reserve memory right from the beginning.
231 */ 185 */
232 cx_attr_export 186 CX_EXPORT extern CxList *const cxEmptyList;
233 extern CxList *const cxEmptyList;
234 187
235 /** 188 /**
236 * Default implementation of an array insert. 189 * Default implementation of an array insert.
237 * 190 *
238 * This function uses the element insert function for each element of the array. 191 * This function uses the element insert function for each element of the array.
245 * @param data a pointer to the array of data to insert 198 * @param data a pointer to the array of data to insert
246 * @param n the number of elements to insert 199 * @param n the number of elements to insert
247 * @return the number of elements actually inserted 200 * @return the number of elements actually inserted
248 */ 201 */
249 cx_attr_nonnull 202 cx_attr_nonnull
250 cx_attr_export 203 CX_EXPORT size_t cx_list_default_insert_array(struct cx_list_s *list,
251 size_t cx_list_default_insert_array( 204 size_t index, const void *data, size_t n);
252 struct cx_list_s *list,
253 size_t index,
254 const void *data,
255 size_t n
256 );
257 205
258 /** 206 /**
259 * Default implementation of a sorted insert. 207 * Default implementation of a sorted insert.
260 * 208 *
261 * This function uses the array insert function to insert consecutive groups 209 * This function uses the array insert function to insert consecutive groups
270 * @param sorted_data a pointer to the array of pre-sorted data to insert 218 * @param sorted_data a pointer to the array of pre-sorted data to insert
271 * @param n the number of elements to insert 219 * @param n the number of elements to insert
272 * @return the number of elements actually inserted 220 * @return the number of elements actually inserted
273 */ 221 */
274 cx_attr_nonnull 222 cx_attr_nonnull
275 cx_attr_export 223 CX_EXPORT size_t cx_list_default_insert_sorted(struct cx_list_s *list,
276 size_t cx_list_default_insert_sorted( 224 const void *sorted_data, size_t n);
277 struct cx_list_s *list,
278 const void *sorted_data,
279 size_t n
280 );
281 225
282 /** 226 /**
283 * Default implementation of an array insert where only elements are inserted when they don't exist in the list. 227 * Default implementation of an array insert where only elements are inserted when they don't exist in the list.
284 * 228 *
285 * This function is similar to cx_list_default_insert_sorted(), except it skips elements that are already in the list. 229 * This function is similar to cx_list_default_insert_sorted(), except it skips elements that are already in the list.
294 * @param sorted_data a pointer to the array of pre-sorted data to insert 238 * @param sorted_data a pointer to the array of pre-sorted data to insert
295 * @param n the number of elements to insert 239 * @param n the number of elements to insert
296 * @return the number of elements from the @p sorted_data that are definitely present in the list after this call 240 * @return the number of elements from the @p sorted_data that are definitely present in the list after this call
297 */ 241 */
298 cx_attr_nonnull 242 cx_attr_nonnull
299 cx_attr_export 243 CX_EXPORT size_t cx_list_default_insert_unique(struct cx_list_s *list,
300 size_t cx_list_default_insert_unique( 244 const void *sorted_data, size_t n);
301 struct cx_list_s *list,
302 const void *sorted_data,
303 size_t n
304 );
305 245
306 /** 246 /**
307 * Default unoptimized sort implementation. 247 * Default unoptimized sort implementation.
308 * 248 *
309 * This function will copy all data to an array, sort the array with standard 249 * This function will copy all data to an array, sort the array with standard
313 * version for your list. 253 * version for your list.
314 * 254 *
315 * @param list the list that shall be sorted 255 * @param list the list that shall be sorted
316 */ 256 */
317 cx_attr_nonnull 257 cx_attr_nonnull
318 cx_attr_export 258 CX_EXPORT void cx_list_default_sort(struct cx_list_s *list);
319 void cx_list_default_sort(struct cx_list_s *list);
320 259
321 /** 260 /**
322 * Default unoptimized swap implementation. 261 * Default unoptimized swap implementation.
323 * 262 *
324 * Use this in your own list class if you do not want to implement an optimized 263 * Use this in your own list class if you do not want to implement an optimized
330 * @retval zero success 269 * @retval zero success
331 * @retval non-zero when indices are out of bounds or memory 270 * @retval non-zero when indices are out of bounds or memory
332 * allocation for the temporary buffer fails 271 * allocation for the temporary buffer fails
333 */ 272 */
334 cx_attr_nonnull 273 cx_attr_nonnull
335 cx_attr_export 274 CX_EXPORT int cx_list_default_swap(struct cx_list_s *list, size_t i, size_t j);
336 int cx_list_default_swap(struct cx_list_s *list, size_t i, size_t j);
337 275
338 /** 276 /**
339 * Initializes a list struct. 277 * Initializes a list struct.
340 * 278 *
341 * Only use this function if you are creating your own list implementation. 279 * Only use this function if you are creating your own list implementation.
378 * @param allocator the allocator for the elements 316 * @param allocator the allocator for the elements
379 * @param comparator a compare function for the elements 317 * @param comparator a compare function for the elements
380 * @param elem_size the size of one element 318 * @param elem_size the size of one element
381 */ 319 */
382 cx_attr_nonnull_arg(1, 2, 3) 320 cx_attr_nonnull_arg(1, 2, 3)
383 cx_attr_export 321 CX_EXPORT void cx_list_init(struct cx_list_s *list,
384 void cx_list_init( 322 struct cx_list_class_s *cl, const struct cx_allocator_s *allocator,
385 struct cx_list_s *list, 323 cx_compare_func comparator, size_t elem_size);
386 struct cx_list_class_s *cl,
387 const struct cx_allocator_s *allocator,
388 cx_compare_func comparator,
389 size_t elem_size
390 );
391 324
392 /** 325 /**
393 * Returns the number of elements currently stored in the list. 326 * Returns the number of elements currently stored in the list.
394 * 327 *
395 * @param list the list 328 * @param list the list
396 * @return the number of currently stored elements 329 * @return the number of currently stored elements
397 */ 330 */
398 cx_attr_nonnull 331 cx_attr_nonnull
399 static inline size_t cxListSize(const CxList *list) { 332 CX_EXPORT size_t cxListSize(const CxList *list);
400 return list->collection.size;
401 }
402 333
403 /** 334 /**
404 * Adds an item to the end of the list. 335 * Adds an item to the end of the list.
405 * 336 *
406 * @param list the list 337 * @param list the list
409 * @retval non-zero memory allocation failure 340 * @retval non-zero memory allocation failure
410 * @see cxListAddArray() 341 * @see cxListAddArray()
411 * @see cxListEmplace() 342 * @see cxListEmplace()
412 */ 343 */
413 cx_attr_nonnull 344 cx_attr_nonnull
414 static inline int cxListAdd( 345 CX_EXPORT int cxListAdd(CxList *list, const void *elem);
415 CxList *list,
416 const void *elem
417 ) {
418 list->collection.sorted = false;
419 return list->cl->insert_element(list, list->collection.size, elem) == NULL;
420 }
421 346
422 /** 347 /**
423 * Adds multiple items to the end of the list. 348 * Adds multiple items to the end of the list.
424 * 349 *
425 * This method is more efficient than invoking cxListAdd() multiple times. 350 * This method is more efficient than invoking cxListAdd() multiple times.
434 * @param array a pointer to the elements to add 359 * @param array a pointer to the elements to add
435 * @param n the number of elements to add 360 * @param n the number of elements to add
436 * @return the number of added elements 361 * @return the number of added elements
437 */ 362 */
438 cx_attr_nonnull 363 cx_attr_nonnull
439 static inline size_t cxListAddArray( 364 CX_EXPORT size_t cxListAddArray(CxList *list, const void *array, size_t n);
440 CxList *list,
441 const void *array,
442 size_t n
443 ) {
444 list->collection.sorted = false;
445 return list->cl->insert_array(list, list->collection.size, array, n);
446 }
447 365
448 /** 366 /**
449 * Inserts an item at the specified index. 367 * Inserts an item at the specified index.
450 * 368 *
451 * If the @p index equals the list @c size, this is effectively cxListAdd(). 369 * If the @p index equals the list @c size, this is effectively cxListAdd().
458 * @see cxListInsertAfter() 376 * @see cxListInsertAfter()
459 * @see cxListInsertBefore() 377 * @see cxListInsertBefore()
460 * @see cxListEmplaceAt() 378 * @see cxListEmplaceAt()
461 */ 379 */
462 cx_attr_nonnull 380 cx_attr_nonnull
463 static inline int cxListInsert( 381 CX_EXPORT int cxListInsert(CxList *list, size_t index, const void *elem);
464 CxList *list,
465 size_t index,
466 const void *elem
467 ) {
468 list->collection.sorted = false;
469 return list->cl->insert_element(list, index, elem) == NULL;
470 }
471 382
472 /** 383 /**
473 * Allocates memory for an element at the specified index and returns a pointer to that memory. 384 * Allocates memory for an element at the specified index and returns a pointer to that memory.
474 * 385 *
475 * @remark When the list is storing pointers, this will return a @c void**. 386 * @remark When the list is storing pointers, this will return a @c void**.
479 * @return a pointer to the allocated memory; @c NULL when the operation fails, or the index is out-of-bounds 390 * @return a pointer to the allocated memory; @c NULL when the operation fails, or the index is out-of-bounds
480 * @see cxListEmplace() 391 * @see cxListEmplace()
481 * @see cxListInsert() 392 * @see cxListInsert()
482 */ 393 */
483 cx_attr_nonnull 394 cx_attr_nonnull
484 static inline void *cxListEmplaceAt(CxList *list, size_t index) { 395 CX_EXPORT void *cxListEmplaceAt(CxList *list, size_t index);
485 list->collection.sorted = false;
486 return list->cl->insert_element(list, index, NULL);
487 }
488
489 396
490 /** 397 /**
491 * Allocates memory for an element at the end of the list and returns a pointer to that memory. 398 * Allocates memory for an element at the end of the list and returns a pointer to that memory.
492 * 399 *
493 * @remark When the list is storing pointers, this will return a @c void**. 400 * @remark When the list is storing pointers, this will return a @c void**.
496 * @return a pointer to the allocated memory; @c NULL when the operation fails, or the index is out-of-bounds 403 * @return a pointer to the allocated memory; @c NULL when the operation fails, or the index is out-of-bounds
497 * @see cxListEmplaceAt() 404 * @see cxListEmplaceAt()
498 * @see cxListAdd() 405 * @see cxListAdd()
499 */ 406 */
500 cx_attr_nonnull 407 cx_attr_nonnull
501 static inline void *cxListEmplace(CxList *list) { 408 CX_EXPORT void *cxListEmplace(CxList *list);
502 list->collection.sorted = false;
503 return list->cl->insert_element(list, list->collection.size, NULL);
504 }
505 409
506 /** 410 /**
507 * Inserts an item into a sorted list. 411 * Inserts an item into a sorted list.
508 * 412 *
509 * If the list is not sorted already, the behavior is undefined. 413 * If the list is not sorted already, the behavior is undefined.
512 * @param elem a pointer to the element to add 416 * @param elem a pointer to the element to add
513 * @retval zero success 417 * @retval zero success
514 * @retval non-zero memory allocation failure 418 * @retval non-zero memory allocation failure
515 */ 419 */
516 cx_attr_nonnull 420 cx_attr_nonnull
517 static inline int cxListInsertSorted( 421 CX_EXPORT int cxListInsertSorted(CxList *list, const void *elem);
518 CxList *list,
519 const void *elem
520 ) {
521 assert(list->collection.sorted || list->collection.size == 0);
522 list->collection.sorted = true;
523 const void *data = list->collection.store_pointer ? &elem : elem;
524 return list->cl->insert_sorted(list, data, 1) == 0;
525 }
526 422
527 /** 423 /**
528 * Inserts an item into a sorted list if it does not exist. 424 * Inserts an item into a sorted list if it does not exist.
529 * 425 *
530 * If the list is not sorted already, the behavior is undefined. 426 * If the list is not sorted already, the behavior is undefined.
533 * @param elem a pointer to the element to add 429 * @param elem a pointer to the element to add
534 * @retval zero success (also when the element was already in the list) 430 * @retval zero success (also when the element was already in the list)
535 * @retval non-zero memory allocation failure 431 * @retval non-zero memory allocation failure
536 */ 432 */
537 cx_attr_nonnull 433 cx_attr_nonnull
538 static inline int cxListInsertUnique( 434 CX_EXPORT int cxListInsertUnique(CxList *list, const void *elem);
539 CxList *list,
540 const void *elem
541 ) {
542 assert(list->collection.sorted || list->collection.size == 0);
543 list->collection.sorted = true;
544 const void *data = list->collection.store_pointer ? &elem : elem;
545 return list->cl->insert_unique(list, data, 1) == 0;
546 }
547 435
548 /** 436 /**
549 * Inserts multiple items to the list at the specified index. 437 * Inserts multiple items to the list at the specified index.
550 * If the @p index equals the list size, this is effectively cxListAddArray(). 438 * If the @p index equals the list size, this is effectively cxListAddArray().
551 * 439 *
563 * @param array a pointer to the elements to add 451 * @param array a pointer to the elements to add
564 * @param n the number of elements to add 452 * @param n the number of elements to add
565 * @return the number of added elements 453 * @return the number of added elements
566 */ 454 */
567 cx_attr_nonnull 455 cx_attr_nonnull
568 static inline size_t cxListInsertArray( 456 CX_EXPORT size_t cxListInsertArray(CxList *list, size_t index, const void *array, size_t n);
569 CxList *list,
570 size_t index,
571 const void *array,
572 size_t n
573 ) {
574 list->collection.sorted = false;
575 return list->cl->insert_array(list, index, array, n);
576 }
577 457
578 /** 458 /**
579 * Inserts a sorted array into a sorted list. 459 * Inserts a sorted array into a sorted list.
580 * 460 *
581 * This method is usually more efficient than inserting each element separately 461 * This method is usually more efficient than inserting each element separately
593 * @param array a pointer to the elements to add 473 * @param array a pointer to the elements to add
594 * @param n the number of elements to add 474 * @param n the number of elements to add
595 * @return the number of added elements 475 * @return the number of added elements
596 */ 476 */
597 cx_attr_nonnull 477 cx_attr_nonnull
598 static inline size_t cxListInsertSortedArray( 478 CX_EXPORT size_t cxListInsertSortedArray(CxList *list, const void *array, size_t n);
599 CxList *list,
600 const void *array,
601 size_t n
602 ) {
603 assert(list->collection.sorted || list->collection.size == 0);
604 list->collection.sorted = true;
605 return list->cl->insert_sorted(list, array, n);
606 }
607 479
608 /** 480 /**
609 * Inserts a sorted array into a sorted list, skipping duplicates. 481 * Inserts a sorted array into a sorted list, skipping duplicates.
610 * 482 *
611 * This method is usually more efficient than inserting each element separately 483 * This method is usually more efficient than inserting each element separately
632 * @return the number of added elements 504 * @return the number of added elements
633 * 505 *
634 * @return the number of elements from the @p sorted_data that are definitely present in the list after this call 506 * @return the number of elements from the @p sorted_data that are definitely present in the list after this call
635 */ 507 */
636 cx_attr_nonnull 508 cx_attr_nonnull
637 static inline size_t cxListInsertUniqueArray( 509 CX_EXPORT size_t cxListInsertUniqueArray(CxList *list, const void *array, size_t n);
638 CxList *list,
639 const void *array,
640 size_t n
641 ) {
642 assert(list->collection.sorted || list->collection.size == 0);
643 list->collection.sorted = true;
644 return list->cl->insert_unique(list, array, n);
645 }
646 510
647 /** 511 /**
648 * Inserts an element after the current location of the specified iterator. 512 * Inserts an element after the current location of the specified iterator.
649 * 513 *
650 * The used iterator remains operational, but all other active iterators should 514 * The used iterator remains operational, but all other active iterators should
659 * @retval non-zero memory allocation failure 523 * @retval non-zero memory allocation failure
660 * @see cxListInsert() 524 * @see cxListInsert()
661 * @see cxListInsertBefore() 525 * @see cxListInsertBefore()
662 */ 526 */
663 cx_attr_nonnull 527 cx_attr_nonnull
664 static inline int cxListInsertAfter( 528 CX_EXPORT int cxListInsertAfter(CxIterator *iter, const void *elem);
665 CxIterator *iter,
666 const void *elem
667 ) {
668 CxList* list = (CxList*)iter->src_handle.m;
669 list->collection.sorted = false;
670 return list->cl->insert_iter(iter, elem, 0);
671 }
672 529
673 /** 530 /**
674 * Inserts an element before the current location of the specified iterator. 531 * Inserts an element before the current location of the specified iterator.
675 * 532 *
676 * The used iterator remains operational, but all other active iterators should 533 * The used iterator remains operational, but all other active iterators should
685 * @retval non-zero memory allocation failure 542 * @retval non-zero memory allocation failure
686 * @see cxListInsert() 543 * @see cxListInsert()
687 * @see cxListInsertAfter() 544 * @see cxListInsertAfter()
688 */ 545 */
689 cx_attr_nonnull 546 cx_attr_nonnull
690 static inline int cxListInsertBefore( 547 CX_EXPORT int cxListInsertBefore(CxIterator *iter, const void *elem);
691 CxIterator *iter,
692 const void *elem
693 ) {
694 CxList* list = (CxList*)iter->src_handle.m;
695 list->collection.sorted = false;
696 return list->cl->insert_iter(iter, elem, 1);
697 }
698 548
699 /** 549 /**
700 * Removes the element at the specified index. 550 * Removes the element at the specified index.
701 * 551 *
702 * If an element destructor function is specified, it is called before 552 * If an element destructor function is specified, it is called before
706 * @param index the index of the element 556 * @param index the index of the element
707 * @retval zero success 557 * @retval zero success
708 * @retval non-zero index out of bounds 558 * @retval non-zero index out of bounds
709 */ 559 */
710 cx_attr_nonnull 560 cx_attr_nonnull
711 static inline int cxListRemove( 561 CX_EXPORT int cxListRemove(CxList *list, size_t index);
712 CxList *list,
713 size_t index
714 ) {
715 return list->cl->remove(list, index, 1, NULL) == 0;
716 }
717 562
718 /** 563 /**
719 * Removes and returns the element at the specified index. 564 * Removes and returns the element at the specified index.
720 * 565 *
721 * No destructor is called, and instead the element is copied to the 566 * No destructor is called, and instead the element is copied to the
726 * @param index the index of the element 571 * @param index the index of the element
727 * @param targetbuf a buffer where to copy the element 572 * @param targetbuf a buffer where to copy the element
728 * @retval zero success 573 * @retval zero success
729 * @retval non-zero index out of bounds 574 * @retval non-zero index out of bounds
730 */ 575 */
731 cx_attr_nonnull 576 cx_attr_nonnull cx_attr_access_w(3)
732 cx_attr_access_w(3) 577 CX_EXPORT int cxListRemoveAndGet(CxList *list, size_t index, void *targetbuf);
733 static inline int cxListRemoveAndGet(
734 CxList *list,
735 size_t index,
736 void *targetbuf
737 ) {
738 return list->cl->remove(list, index, 1, targetbuf) == 0;
739 }
740 578
741 /** 579 /**
742 * Removes and returns the first element of the list. 580 * Removes and returns the first element of the list.
743 * 581 *
744 * No destructor is called, and instead the element is copied to the 582 * No destructor is called, and instead the element is copied to the
750 * @retval zero success 588 * @retval zero success
751 * @retval non-zero the list is empty 589 * @retval non-zero the list is empty
752 * @see cxListPopFront() 590 * @see cxListPopFront()
753 * @see cxListRemoveAndGetLast() 591 * @see cxListRemoveAndGetLast()
754 */ 592 */
755 cx_attr_nonnull 593 cx_attr_nonnull cx_attr_access_w(2)
756 cx_attr_access_w(2) 594 CX_EXPORT int cxListRemoveAndGetFirst(CxList *list, void *targetbuf);
757 static inline int cxListRemoveAndGetFirst(
758 CxList *list,
759 void *targetbuf
760 ) {
761 return list->cl->remove(list, 0, 1, targetbuf) == 0;
762 }
763 595
764 /** 596 /**
765 * Removes and returns the first element of the list. 597 * Removes and returns the first element of the list.
766 * 598 *
767 * Alias for cxListRemoveAndGetFirst(). 599 * Alias for cxListRemoveAndGetFirst().
790 * @param list the list 622 * @param list the list
791 * @param targetbuf a buffer where to copy the element 623 * @param targetbuf a buffer where to copy the element
792 * @retval zero success 624 * @retval zero success
793 * @retval non-zero the list is empty 625 * @retval non-zero the list is empty
794 */ 626 */
795 cx_attr_nonnull 627 cx_attr_nonnull cx_attr_access_w(2)
796 cx_attr_access_w(2) 628 CX_EXPORT int cxListRemoveAndGetLast(CxList *list, void *targetbuf);
797 static inline int cxListRemoveAndGetLast(
798 CxList *list,
799 void *targetbuf
800 ) {
801 // note: index may wrap - member function will catch that
802 return list->cl->remove(list, list->collection.size - 1, 1, targetbuf) == 0;
803 }
804 629
805 /** 630 /**
806 * Removes and returns the last element of the list. 631 * Removes and returns the last element of the list.
807 * 632 *
808 * Alias for cxListRemoveAndGetLast(). 633 * Alias for cxListRemoveAndGetLast().
834 * @param index the index of the element 659 * @param index the index of the element
835 * @param num the number of elements to remove 660 * @param num the number of elements to remove
836 * @return the actual number of removed elements 661 * @return the actual number of removed elements
837 */ 662 */
838 cx_attr_nonnull 663 cx_attr_nonnull
839 static inline size_t cxListRemoveArray( 664 CX_EXPORT size_t cxListRemoveArray(CxList *list, size_t index, size_t num);
840 CxList *list,
841 size_t index,
842 size_t num
843 ) {
844 return list->cl->remove(list, index, num, NULL);
845 }
846 665
847 /** 666 /**
848 * Removes and returns multiple elements starting at the specified index. 667 * Removes and returns multiple elements starting at the specified index.
849 * 668 *
850 * No destructor is called, and instead the elements are copied to the 669 * No destructor is called, and instead the elements are copied to the
855 * @param index the index of the element 674 * @param index the index of the element
856 * @param num the number of elements to remove 675 * @param num the number of elements to remove
857 * @param targetbuf a buffer where to copy the elements 676 * @param targetbuf a buffer where to copy the elements
858 * @return the actual number of removed elements 677 * @return the actual number of removed elements
859 */ 678 */
860 cx_attr_nonnull 679 cx_attr_nonnull cx_attr_access_w(4)
861 cx_attr_access_w(4) 680 CX_EXPORT size_t cxListRemoveArrayAndGet(CxList *list, size_t index, size_t num, void *targetbuf);
862 static inline size_t cxListRemoveArrayAndGet(
863 CxList *list,
864 size_t index,
865 size_t num,
866 void *targetbuf
867 ) {
868 return list->cl->remove(list, index, num, targetbuf);
869 }
870 681
871 /** 682 /**
872 * Removes all elements from this list. 683 * Removes all elements from this list.
873 * 684 *
874 * If element destructor functions are specified, they are called for each 685 * If element destructor functions are specified, they are called for each
875 * element before removing them. 686 * element before removing them.
876 * 687 *
877 * @param list the list 688 * @param list the list
878 */ 689 */
879 cx_attr_nonnull 690 cx_attr_nonnull
880 static inline void cxListClear(CxList *list) { 691 CX_EXPORT void cxListClear(CxList *list);
881 list->cl->clear(list);
882 list->collection.sorted = true; // empty lists are always sorted
883 }
884 692
885 /** 693 /**
886 * Swaps two items in the list. 694 * Swaps two items in the list.
887 * 695 *
888 * Implementations should only allocate temporary memory for the swap if 696 * Implementations should only allocate temporary memory for the swap if
894 * @retval zero success 702 * @retval zero success
895 * @retval non-zero one of the indices is out of bounds, 703 * @retval non-zero one of the indices is out of bounds,
896 * or the swap needed extra memory, but allocation failed 704 * or the swap needed extra memory, but allocation failed
897 */ 705 */
898 cx_attr_nonnull 706 cx_attr_nonnull
899 static inline int cxListSwap( 707 CX_EXPORT int cxListSwap(CxList *list, size_t i, size_t j);
900 CxList *list,
901 size_t i,
902 size_t j
903 ) {
904 list->collection.sorted = false;
905 return list->cl->swap(list, i, j);
906 }
907 708
908 /** 709 /**
909 * Returns a pointer to the element at the specified index. 710 * Returns a pointer to the element at the specified index.
910 * 711 *
911 * If the list is storing pointers, returns the pointer stored at the specified index. 712 * If the list is storing pointers, returns the pointer stored at the specified index.
913 * @param list the list 714 * @param list the list
914 * @param index the index of the element 715 * @param index the index of the element
915 * @return a pointer to the element or @c NULL if the index is out of bounds 716 * @return a pointer to the element or @c NULL if the index is out of bounds
916 */ 717 */
917 cx_attr_nonnull 718 cx_attr_nonnull
918 static inline void *cxListAt( 719 CX_EXPORT void *cxListAt(const CxList *list, size_t index);
919 const CxList *list,
920 size_t index
921 ) {
922 return list->cl->at(list, index);
923 }
924 720
925 /** 721 /**
926 * Returns a pointer to the first element. 722 * Returns a pointer to the first element.
927 * 723 *
928 * If the list is storing pointers, returns the first pointer stored in the list. 724 * If the list is storing pointers, returns the first pointer stored in the list.
929 * 725 *
930 * @param list the list 726 * @param list the list
931 * @return a pointer to the first element or @c NULL if the list is empty 727 * @return a pointer to the first element or @c NULL if the list is empty
932 */ 728 */
933 cx_attr_nonnull 729 cx_attr_nonnull
934 static inline void *cxListFirst(const CxList *list) { 730 CX_EXPORT void *cxListFirst(const CxList *list);
935 return list->cl->at(list, 0);
936 }
937 731
938 /** 732 /**
939 * Returns a pointer to the last element. 733 * Returns a pointer to the last element.
940 * 734 *
941 * If the list is storing pointers, returns the last pointer stored in the list. 735 * If the list is storing pointers, returns the last pointer stored in the list.
942 * 736 *
943 * @param list the list 737 * @param list the list
944 * @return a pointer to the last element or @c NULL if the list is empty 738 * @return a pointer to the last element or @c NULL if the list is empty
945 */ 739 */
946 cx_attr_nonnull 740 cx_attr_nonnull
947 static inline void *cxListLast(const CxList *list) { 741 CX_EXPORT void *cxListLast(const CxList *list);
948 return list->cl->at(list, list->collection.size - 1); 742
949 } 743 /**
950 744 * Sets the element at the specified index in the list.
951 /** 745 *
952 * Sets the element at the specified index in the list 746 * This overwrites the element in-place without calling any destructor
747 * on the overwritten element.
953 * 748 *
954 * @param list the list to set the element in 749 * @param list the list to set the element in
955 * @param index the index to set the element at 750 * @param index the index to set the element at
956 * @param elem element to set 751 * @param elem element to set
957 * @retval zero on success 752 * @retval zero on success
958 * @retval non-zero when index is out of bounds 753 * @retval non-zero when index is out of bounds
959 */ 754 */
960 cx_attr_nonnull 755 cx_attr_nonnull
961 cx_attr_export 756 CX_EXPORT int cxListSet(CxList *list, size_t index, const void *elem);
962 int cxListSet(
963 CxList *list,
964 size_t index,
965 const void *elem
966 );
967 757
968 /** 758 /**
969 * Returns an iterator pointing to the item at the specified index. 759 * Returns an iterator pointing to the item at the specified index.
970 * 760 *
971 * The returned iterator is position-aware. 761 * The returned iterator is position-aware.
975 * @param list the list 765 * @param list the list
976 * @param index the index where the iterator shall point at 766 * @param index the index where the iterator shall point at
977 * @return a new iterator 767 * @return a new iterator
978 */ 768 */
979 cx_attr_nodiscard 769 cx_attr_nodiscard
980 static inline CxIterator cxListIteratorAt( 770 CX_EXPORT CxIterator cxListIteratorAt(const CxList *list, size_t index);
981 const CxList *list,
982 size_t index
983 ) {
984 if (list == NULL) list = cxEmptyList;
985 return list->cl->iterator(list, index, false);
986 }
987 771
988 /** 772 /**
989 * Returns a backwards iterator pointing to the item at the specified index. 773 * Returns a backwards iterator pointing to the item at the specified index.
990 * 774 *
991 * The returned iterator is position-aware. 775 * The returned iterator is position-aware.
995 * @param list the list 779 * @param list the list
996 * @param index the index where the iterator shall point at 780 * @param index the index where the iterator shall point at
997 * @return a new iterator 781 * @return a new iterator
998 */ 782 */
999 cx_attr_nodiscard 783 cx_attr_nodiscard
1000 static inline CxIterator cxListBackwardsIteratorAt( 784 CX_EXPORT CxIterator cxListBackwardsIteratorAt(const CxList *list, size_t index);
1001 const CxList *list,
1002 size_t index
1003 ) {
1004 if (list == NULL) list = cxEmptyList;
1005 return list->cl->iterator(list, index, true);
1006 }
1007 785
1008 /** 786 /**
1009 * Returns a mutating iterator pointing to the item at the specified index. 787 * Returns a mutating iterator pointing to the item at the specified index.
1010 * 788 *
1011 * The returned iterator is position-aware. 789 * The returned iterator is position-aware.
1015 * @param list the list 793 * @param list the list
1016 * @param index the index where the iterator shall point at 794 * @param index the index where the iterator shall point at
1017 * @return a new iterator 795 * @return a new iterator
1018 */ 796 */
1019 cx_attr_nodiscard 797 cx_attr_nodiscard
1020 cx_attr_export 798 CX_EXPORT CxIterator cxListMutIteratorAt(CxList *list, size_t index);
1021 CxIterator cxListMutIteratorAt(
1022 CxList *list,
1023 size_t index
1024 );
1025 799
1026 /** 800 /**
1027 * Returns a mutating backwards iterator pointing to the item at the 801 * Returns a mutating backwards iterator pointing to the item at the
1028 * specified index. 802 * specified index.
1029 * 803 *
1034 * @param list the list 808 * @param list the list
1035 * @param index the index where the iterator shall point at 809 * @param index the index where the iterator shall point at
1036 * @return a new iterator 810 * @return a new iterator
1037 */ 811 */
1038 cx_attr_nodiscard 812 cx_attr_nodiscard
1039 cx_attr_export 813 CX_EXPORT CxIterator cxListMutBackwardsIteratorAt(CxList *list, size_t index);
1040 CxIterator cxListMutBackwardsIteratorAt(
1041 CxList *list,
1042 size_t index
1043 );
1044 814
1045 /** 815 /**
1046 * Returns an iterator pointing to the first item of the list. 816 * Returns an iterator pointing to the first item of the list.
1047 * 817 *
1048 * The returned iterator is position-aware. 818 * The returned iterator is position-aware.
1051 * 821 *
1052 * @param list the list 822 * @param list the list
1053 * @return a new iterator 823 * @return a new iterator
1054 */ 824 */
1055 cx_attr_nodiscard 825 cx_attr_nodiscard
1056 static inline CxIterator cxListIterator(const CxList *list) { 826 CX_EXPORT CxIterator cxListIterator(const CxList *list);
1057 if (list == NULL) list = cxEmptyList;
1058 return list->cl->iterator(list, 0, false);
1059 }
1060 827
1061 /** 828 /**
1062 * Returns a mutating iterator pointing to the first item of the list. 829 * Returns a mutating iterator pointing to the first item of the list.
1063 * 830 *
1064 * The returned iterator is position-aware. 831 * The returned iterator is position-aware.
1067 * 834 *
1068 * @param list the list 835 * @param list the list
1069 * @return a new iterator 836 * @return a new iterator
1070 */ 837 */
1071 cx_attr_nodiscard 838 cx_attr_nodiscard
1072 static inline CxIterator cxListMutIterator(CxList *list) { 839 CX_EXPORT CxIterator cxListMutIterator(CxList *list);
1073 if (list == NULL) list = cxEmptyList;
1074 return cxListMutIteratorAt(list, 0);
1075 }
1076
1077 840
1078 /** 841 /**
1079 * Returns a backwards iterator pointing to the last item of the list. 842 * Returns a backwards iterator pointing to the last item of the list.
1080 * 843 *
1081 * The returned iterator is position-aware. 844 * The returned iterator is position-aware.
1084 * 847 *
1085 * @param list the list 848 * @param list the list
1086 * @return a new iterator 849 * @return a new iterator
1087 */ 850 */
1088 cx_attr_nodiscard 851 cx_attr_nodiscard
1089 static inline CxIterator cxListBackwardsIterator(const CxList *list) { 852 CX_EXPORT CxIterator cxListBackwardsIterator(const CxList *list);
1090 if (list == NULL) list = cxEmptyList;
1091 return list->cl->iterator(list, list->collection.size - 1, true);
1092 }
1093 853
1094 /** 854 /**
1095 * Returns a mutating backwards iterator pointing to the last item of the list. 855 * Returns a mutating backwards iterator pointing to the last item of the list.
1096 * 856 *
1097 * The returned iterator is position-aware. 857 * The returned iterator is position-aware.
1100 * 860 *
1101 * @param list the list 861 * @param list the list
1102 * @return a new iterator 862 * @return a new iterator
1103 */ 863 */
1104 cx_attr_nodiscard 864 cx_attr_nodiscard
1105 static inline CxIterator cxListMutBackwardsIterator(CxList *list) { 865 CX_EXPORT CxIterator cxListMutBackwardsIterator(CxList *list);
1106 if (list == NULL) list = cxEmptyList;
1107 return cxListMutBackwardsIteratorAt(list, list->collection.size - 1);
1108 }
1109 866
1110 /** 867 /**
1111 * Returns the index of the first element that equals @p elem. 868 * Returns the index of the first element that equals @p elem.
1112 * 869 *
1113 * Determining equality is performed by the list's comparator function. 870 * Determining equality is performed by the list's comparator function.
1116 * @param elem the element to find 873 * @param elem the element to find
1117 * @return the index of the element or the size of the list when the element is not found 874 * @return the index of the element or the size of the list when the element is not found
1118 * @see cxListIndexValid() 875 * @see cxListIndexValid()
1119 * @see cxListContains() 876 * @see cxListContains()
1120 */ 877 */
1121 cx_attr_nonnull 878 cx_attr_nonnull cx_attr_nodiscard
1122 cx_attr_nodiscard 879 CX_EXPORT size_t cxListFind(const CxList *list, const void *elem);
1123 static inline size_t cxListFind(
1124 const CxList *list,
1125 const void *elem
1126 ) {
1127 return list->cl->find_remove((CxList*)list, elem, false);
1128 }
1129 880
1130 /** 881 /**
1131 * Checks if the list contains the specified element. 882 * Checks if the list contains the specified element.
1132 * 883 *
1133 * The elements are compared with the list's comparator function. 884 * The elements are compared with the list's comparator function.
1136 * @param elem the element to find 887 * @param elem the element to find
1137 * @retval true if the element is contained 888 * @retval true if the element is contained
1138 * @retval false if the element is not contained 889 * @retval false if the element is not contained
1139 * @see cxListFind() 890 * @see cxListFind()
1140 */ 891 */
1141 cx_attr_nonnull 892 cx_attr_nonnull cx_attr_nodiscard
1142 cx_attr_nodiscard 893 CX_EXPORT bool cxListContains(const CxList* list, const void* elem);
1143 static inline bool cxListContains(
1144 const CxList* list,
1145 const void* elem
1146 ) {
1147 return list->cl->find_remove((CxList*)list, elem, false) < list->collection.size;
1148 }
1149 894
1150 /** 895 /**
1151 * Checks if the specified index is within bounds. 896 * Checks if the specified index is within bounds.
1152 * 897 *
1153 * @param list the list 898 * @param list the list
1154 * @param index the index 899 * @param index the index
1155 * @retval true if the index is within bounds 900 * @retval true if the index is within bounds
1156 * @retval false if the index is out of bounds 901 * @retval false if the index is out of bounds
1157 */ 902 */
1158 cx_attr_nonnull 903 cx_attr_nonnull cx_attr_nodiscard
1159 cx_attr_nodiscard 904 CX_EXPORT bool cxListIndexValid(const CxList *list, size_t index);
1160 static inline bool cxListIndexValid(const CxList *list, size_t index) {
1161 return index < list->collection.size;
1162 }
1163 905
1164 /** 906 /**
1165 * Removes and returns the index of the first element that equals @p elem. 907 * Removes and returns the index of the first element that equals @p elem.
1166 * 908 *
1167 * Determining equality is performed by the list's comparator function. 909 * Determining equality is performed by the list's comparator function.
1171 * @return the index of the now removed element or the list size 913 * @return the index of the now removed element or the list size
1172 * when the element is not found or could not be removed 914 * when the element is not found or could not be removed
1173 * @see cxListIndexValid() 915 * @see cxListIndexValid()
1174 */ 916 */
1175 cx_attr_nonnull 917 cx_attr_nonnull
1176 static inline size_t cxListFindRemove( 918 CX_EXPORT size_t cxListFindRemove(CxList *list, const void *elem);
1177 CxList *list,
1178 const void *elem
1179 ) {
1180 return list->cl->find_remove(list, elem, true);
1181 }
1182 919
1183 /** 920 /**
1184 * Sorts the list. 921 * Sorts the list.
1185 * 922 *
1186 * @remark The underlying sort algorithm is implementation defined. 923 * @remark The underlying sort algorithm is implementation defined.
1187 * 924 *
1188 * @param list the list 925 * @param list the list
1189 */ 926 */
1190 cx_attr_nonnull 927 cx_attr_nonnull
1191 static inline void cxListSort(CxList *list) { 928 CX_EXPORT void cxListSort(CxList *list);
1192 if (list->collection.sorted) return;
1193 list->cl->sort(list);
1194 list->collection.sorted = true;
1195 }
1196 929
1197 /** 930 /**
1198 * Reverses the order of the items. 931 * Reverses the order of the items.
1199 * 932 *
1200 * @param list the list 933 * @param list the list
1201 */ 934 */
1202 cx_attr_nonnull 935 cx_attr_nonnull
1203 static inline void cxListReverse(CxList *list) { 936 CX_EXPORT void cxListReverse(CxList *list);
1204 // still sorted, but not according to the cmp_func
1205 list->collection.sorted = false;
1206 list->cl->reverse(list);
1207 }
1208 937
1209 /** 938 /**
1210 * Compares a list to another list of the same type. 939 * Compares a list to another list of the same type.
1211 * 940 *
1212 * First, the list sizes are compared. 941 * First, the list sizes are compared.
1213 * If they match, the lists are compared element-wise. 942 * If they match, the lists are compared element-wise.
1214 * 943 *
1215 * @param list the list 944 * @param list the list
1216 * @param other the list to compare to 945 * @param other the list to compare to
1217 * @retval zero both lists are equal element wise 946 * @retval zero both lists are equal element wise
1218 * @retval negative the first list is smaller 947 * @retval negative the first list is smaller,
1219 * or the first non-equal element in the first list is smaller 948 * or the first non-equal element in the first list is smaller
1220 * @retval positive the first list is larger 949 * @retval positive the first list is larger
1221 * or the first non-equal element in the first list is larger 950 * or the first non-equal element in the first list is larger
1222 */ 951 */
1223 cx_attr_nonnull 952 cx_attr_nonnull cx_attr_nodiscard
1224 cx_attr_nodiscard 953 CX_EXPORT int cxListCompare(const CxList *list, const CxList *other);
1225 cx_attr_export
1226 int cxListCompare(
1227 const CxList *list,
1228 const CxList *other
1229 );
1230 954
1231 /** 955 /**
1232 * Deallocates the memory of the specified list structure. 956 * Deallocates the memory of the specified list structure.
1233 * 957 *
1234 * Also calls the content destructor functions for each element, if specified. 958 * Also calls the content destructor functions for each element, if specified.
1235 * 959 *
1236 * @param list the list that shall be freed 960 * @param list the list that shall be freed
1237 */ 961 */
1238 cx_attr_export 962 CX_EXPORT void cxListFree(CxList *list);
1239 void cxListFree(CxList *list);
1240 963
1241 964
1242 #ifdef __cplusplus 965 #ifdef __cplusplus
1243 } // extern "C" 966 } // extern "C"
1244 #endif 967 #endif

Mercurial Repository: ucx

mercurial