comparison: src/cx/linked_list.h
src/cx/linked_list.h
- changeset 639
- 309e8b08c60e
- parent 629
- 6c81ee4f11ad
- child 647
- 2e6e9d9f2159
equal
deleted
inserted
replaced
| 638:eafb45eefc51 | 639:309e8b08c60e |
|---|---|
| 61 CxListComparator comparator, | 61 CxListComparator comparator, |
| 62 size_t item_size | 62 size_t item_size |
| 63 ) __attribute__((__nonnull__)); | 63 ) __attribute__((__nonnull__)); |
| 64 | 64 |
| 65 /** | 65 /** |
| 66 * Allocates a linked list for storing pointers. | |
| 67 * | |
| 68 * If you want to store the elements directly in this list, use cxLinkedListCreate(). | |
| 69 * | |
| 70 * @remark Since only pointers are stored in this list, a possible destructor | |
| 71 * MAY free the memory pointed to by its argument in order to prevent memory leaks. | |
| 72 * | |
| 73 * @param allocator the allocator for allocating the list nodes | |
| 74 * @param comparator the comparator for the elements | |
| 75 * @return the created list | |
| 76 */ | |
| 77 CxList *cxPointerLinkedListCreate( | |
| 78 CxAllocator const *allocator, | |
| 79 CxListComparator comparator | |
| 80 ) __attribute__((__nonnull__)); | |
| 81 | |
| 82 /** | |
| 83 * Finds the node at a certain index. | 66 * Finds the node at a certain index. |
| 84 * | 67 * |
| 85 * This function can be used to start at an arbitrary position within the list. | 68 * This function can be used to start at an arbitrary position within the list. |
| 86 * If the search index is large than the start index, \p loc_advance must denote | 69 * If the search index is large than the start index, \p loc_advance must denote |
| 87 * the location of some sort of \c next pointer (i.e. a pointer to the next node). | 70 * the location of some sort of \c next pointer (i.e. a pointer to the next node). |
| 107 * Finds the index of an element within a linked list. | 90 * Finds the index of an element within a linked list. |
| 108 * | 91 * |
| 109 * @param start a pointer to the start node | 92 * @param start a pointer to the start node |
| 110 * @param loc_advance the location of the pointer to advance | 93 * @param loc_advance the location of the pointer to advance |
| 111 * @param loc_data the location of the \c data pointer within your node struct | 94 * @param loc_data the location of the \c data pointer within your node struct |
| 112 * @param follow_ptr \c false if the pointer denoted by \p loc_data shall be passed to the \p cmp_func. | |
| 113 * If \c true, the data at \p loc_data is assumed to be a pointer, dereferenced, and then passed to \p cmp_func. | |
| 114 * @param cmp_func a compare function to compare \p elem against the node data | 95 * @param cmp_func a compare function to compare \p elem against the node data |
| 115 * @param elem a pointer to the element to find | 96 * @param elem a pointer to the element to find |
| 116 * @return the index of the element or a past-one index if the element could not be found | 97 * @return the index of the element or a past-one index if the element could not be found |
| 117 */ | 98 */ |
| 118 size_t cx_linked_list_find( | 99 size_t cx_linked_list_find( |
| 119 void const *start, | 100 void const *start, |
| 120 ptrdiff_t loc_advance, | 101 ptrdiff_t loc_advance, |
| 121 ptrdiff_t loc_data, | 102 ptrdiff_t loc_data, |
| 122 bool follow_ptr, | |
| 123 CxListComparator cmp_func, | 103 CxListComparator cmp_func, |
| 124 void const *elem | 104 void const *elem |
| 125 ) __attribute__((__nonnull__)); | 105 ) __attribute__((__nonnull__)); |
| 126 | 106 |
| 127 /** | 107 /** |
| 337 ); | 317 ); |
| 338 | 318 |
| 339 /** | 319 /** |
| 340 * Sorts a linked list based on a comparison function. | 320 * Sorts a linked list based on a comparison function. |
| 341 * | 321 * |
| 342 * This function can work with linked lists of the following structures: | 322 * This function can work with linked lists of the following structure: |
| 343 * \code | 323 * \code |
| 344 * typedef struct node node; | 324 * typedef struct node node; |
| 345 * struct node { | 325 * struct node { |
| 346 * node* prev; | 326 * node* prev; |
| 347 * node* next; | 327 * node* next; |
| 348 * my_payload data; // in this case set follow_ptr = 0 | 328 * my_payload data; |
| 349 * } | |
| 350 * | |
| 351 * typedef struct ptr_node ptr_node; | |
| 352 * struct ptr_node { | |
| 353 * ptr_node* prev; | |
| 354 * ptr_node* next; | |
| 355 * my_payload* data; // in this case set follow_ptr = 1 | |
| 356 * } | 329 * } |
| 357 * \endcode | 330 * \endcode |
| 358 * | 331 * |
| 359 * @note This is a recursive function with at most logarithmic recursion depth. | 332 * @note This is a recursive function with at most logarithmic recursion depth. |
| 360 * | 333 * |
| 361 * @param begin a pointer to the begin node pointer (required) | 334 * @param begin a pointer to the begin node pointer (required) |
| 362 * @param end a pointer to the end node pointer (optional) | 335 * @param end a pointer to the end node pointer (optional) |
| 363 * @param loc_prev the location of a \c prev pointer within your node struct (negative if not present) | 336 * @param loc_prev the location of a \c prev pointer within your node struct (negative if not present) |
| 364 * @param loc_next the location of a \c next pointer within your node struct (required) | 337 * @param loc_next the location of a \c next pointer within your node struct (required) |
| 365 * @param loc_data the location of the \c data pointer within your node struct | 338 * @param loc_data the location of the \c data pointer within your node struct |
| 366 * @param follow_ptr \c false if the pointer denoted by \p loc_data shall be passed to the \p cmp_func. | |
| 367 * If \c true, the data at \p loc_data is assumed to be a pointer, dereferenced, and then passed to \p cmp_func. | |
| 368 * @param cmp_func the compare function defining the sort order | 339 * @param cmp_func the compare function defining the sort order |
| 369 */ | 340 */ |
| 370 void cx_linked_list_sort( | 341 void cx_linked_list_sort( |
| 371 void **begin, | 342 void **begin, |
| 372 void **end, | 343 void **end, |
| 373 ptrdiff_t loc_prev, | 344 ptrdiff_t loc_prev, |
| 374 ptrdiff_t loc_next, | 345 ptrdiff_t loc_next, |
| 375 ptrdiff_t loc_data, | 346 ptrdiff_t loc_data, |
| 376 bool follow_ptr, | |
| 377 CxListComparator cmp_func | 347 CxListComparator cmp_func |
| 378 ) __attribute__((__nonnull__(1, 7))); | 348 ) __attribute__((__nonnull__(1, 6))); |
| 379 | 349 |
| 380 | 350 |
| 381 /** | 351 /** |
| 382 * Compares two lists element wise. | 352 * Compares two lists element wise. |
| 383 * | |
| 384 * The \c follow_ptr flags have the following meaning: if \c false, the pointer denoted by \p loc_data shall | |
| 385 * directly be passed to the \p cmp_func. | |
| 386 * If \c true, the data at \p loc_data is assumed to be a pointer, dereferenced, and then passed to \p cmp_func. | |
| 387 * | 353 * |
| 388 * \note Both list must have the same structure. | 354 * \note Both list must have the same structure. |
| 389 * | 355 * |
| 390 * @param begin_left the begin of the left list (\c NULL denotes an empty list) | 356 * @param begin_left the begin of the left list (\c NULL denotes an empty list) |
| 391 * @param begin_right the begin of the right list (\c NULL denotes an empty list) | 357 * @param begin_right the begin of the right list (\c NULL denotes an empty list) |
| 392 * @param loc_advance the location of the pointer to advance | 358 * @param loc_advance the location of the pointer to advance |
| 393 * @param loc_data the location of the \c data pointer within your node struct | 359 * @param loc_data the location of the \c data pointer within your node struct |
| 394 * @param follow_ptr_left indicates whether pointers in the left list shall be dereferenced | |
| 395 * @param follow_ptr_right indicates whether pointers in the right list shall be dereferenced | |
| 396 * @param cmp_func the function to compare the elements | 360 * @param cmp_func the function to compare the elements |
| 397 * @return the first non-zero result of invoking \p cmp_func or: negative if the left list is smaller than the | 361 * @return the first non-zero result of invoking \p cmp_func or: negative if the left list is smaller than the |
| 398 * right list, positive if the left list is larger than the right list, zero if both lists are equal. | 362 * right list, positive if the left list is larger than the right list, zero if both lists are equal. |
| 399 */ | 363 */ |
| 400 int cx_linked_list_compare( | 364 int cx_linked_list_compare( |
| 401 void const *begin_left, | 365 void const *begin_left, |
| 402 void const *begin_right, | 366 void const *begin_right, |
| 403 ptrdiff_t loc_advance, | 367 ptrdiff_t loc_advance, |
| 404 ptrdiff_t loc_data, | 368 ptrdiff_t loc_data, |
| 405 bool follow_ptr_left, | |
| 406 bool follow_ptr_right, | |
| 407 CxListComparator cmp_func | 369 CxListComparator cmp_func |
| 408 ) __attribute__((__nonnull__(7))); | 370 ) __attribute__((__nonnull__(5))); |
| 409 | 371 |
| 410 /** | 372 /** |
| 411 * Reverses the order of the nodes in a linked list. | 373 * Reverses the order of the nodes in a linked list. |
| 412 * | 374 * |
| 413 * @param begin a pointer to the begin node pointer (required) | 375 * @param begin a pointer to the begin node pointer (required) |
