comparison: src/cx/linked_list.h
src/cx/linked_list.h
- changeset 985
- 68754c7de906
- parent 926
- 8fdd8d78c14b
equal
deleted
inserted
replaced
| 984:e8f354a25ac8 | 985:68754c7de906 |
|---|---|
| 62 * (if \c NULL, and the list is not storing pointers, sort and find | 62 * (if \c NULL, and the list is not storing pointers, sort and find |
| 63 * functions will not work) | 63 * functions will not work) |
| 64 * @param elem_size the size of each element in bytes | 64 * @param elem_size the size of each element in bytes |
| 65 * @return the created list | 65 * @return the created list |
| 66 */ | 66 */ |
| 67 cx_attr_nodiscard | |
| 68 cx_attr_malloc | |
| 69 cx_attr_dealloc(cxListDestroy, 1) | |
| 67 CxList *cxLinkedListCreate( | 70 CxList *cxLinkedListCreate( |
| 68 const CxAllocator *allocator, | 71 const CxAllocator *allocator, |
| 69 cx_compare_func comparator, | 72 cx_compare_func comparator, |
| 70 size_t elem_size | 73 size_t elem_size |
| 71 ); | 74 ); |
| 102 * @param start_index the start index | 105 * @param start_index the start index |
| 103 * @param loc_advance the location of the pointer to advance | 106 * @param loc_advance the location of the pointer to advance |
| 104 * @param index the search index | 107 * @param index the search index |
| 105 * @return the node found at the specified index | 108 * @return the node found at the specified index |
| 106 */ | 109 */ |
| 107 __attribute__((__nonnull__)) | 110 cx_attr_nonnull |
| 111 cx_attr_nodiscard | |
| 108 void *cx_linked_list_at( | 112 void *cx_linked_list_at( |
| 109 const void *start, | 113 const void *start, |
| 110 size_t start_index, | 114 size_t start_index, |
| 111 ptrdiff_t loc_advance, | 115 ptrdiff_t loc_advance, |
| 112 size_t index | 116 size_t index |
| 120 * @param loc_data the location of the \c data pointer within your node struct | 124 * @param loc_data the location of the \c data pointer within your node struct |
| 121 * @param cmp_func a compare function to compare \p elem against the node data | 125 * @param cmp_func a compare function to compare \p elem against the node data |
| 122 * @param elem a pointer to the element to find | 126 * @param elem a pointer to the element to find |
| 123 * @return the index of the element or a negative value if it could not be found | 127 * @return the index of the element or a negative value if it could not be found |
| 124 */ | 128 */ |
| 125 __attribute__((__nonnull__)) | 129 cx_attr_nonnull |
| 126 ssize_t cx_linked_list_find( | 130 ssize_t cx_linked_list_find( |
| 127 const void *start, | 131 const void *start, |
| 128 ptrdiff_t loc_advance, | 132 ptrdiff_t loc_advance, |
| 129 ptrdiff_t loc_data, | 133 ptrdiff_t loc_data, |
| 130 cx_compare_func cmp_func, | 134 cx_compare_func cmp_func, |
| 141 * @param loc_data the location of the \c data pointer within your node struct | 145 * @param loc_data the location of the \c data pointer within your node struct |
| 142 * @param cmp_func a compare function to compare \p elem against the node data | 146 * @param cmp_func a compare function to compare \p elem against the node data |
| 143 * @param elem a pointer to the element to find | 147 * @param elem a pointer to the element to find |
| 144 * @return the index of the element or a negative value if it could not be found | 148 * @return the index of the element or a negative value if it could not be found |
| 145 */ | 149 */ |
| 146 __attribute__((__nonnull__)) | 150 cx_attr_nonnull |
| 147 ssize_t cx_linked_list_find_node( | 151 ssize_t cx_linked_list_find_node( |
| 148 void **result, | 152 void **result, |
| 149 const void *start, | 153 const void *start, |
| 150 ptrdiff_t loc_advance, | 154 ptrdiff_t loc_advance, |
| 151 ptrdiff_t loc_data, | 155 ptrdiff_t loc_data, |
| 162 * | 166 * |
| 163 * @param node a pointer to a node in the list | 167 * @param node a pointer to a node in the list |
| 164 * @param loc_prev the location of the \c prev pointer | 168 * @param loc_prev the location of the \c prev pointer |
| 165 * @return a pointer to the first node | 169 * @return a pointer to the first node |
| 166 */ | 170 */ |
| 167 __attribute__((__nonnull__)) | 171 cx_attr_nonnull |
| 172 cx_attr_returns_nonnull | |
| 168 void *cx_linked_list_first( | 173 void *cx_linked_list_first( |
| 169 const void *node, | 174 const void *node, |
| 170 ptrdiff_t loc_prev | 175 ptrdiff_t loc_prev |
| 171 ); | 176 ); |
| 172 | 177 |
| 179 * | 184 * |
| 180 * @param node a pointer to a node in the list | 185 * @param node a pointer to a node in the list |
| 181 * @param loc_next the location of the \c next pointer | 186 * @param loc_next the location of the \c next pointer |
| 182 * @return a pointer to the last node | 187 * @return a pointer to the last node |
| 183 */ | 188 */ |
| 184 __attribute__((__nonnull__)) | 189 cx_attr_nonnull |
| 190 cx_attr_returns_nonnull | |
| 185 void *cx_linked_list_last( | 191 void *cx_linked_list_last( |
| 186 const void *node, | 192 const void *node, |
| 187 ptrdiff_t loc_next | 193 ptrdiff_t loc_next |
| 188 ); | 194 ); |
| 189 | 195 |
| 195 * @param begin the node where to start the search | 201 * @param begin the node where to start the search |
| 196 * @param loc_next the location of the \c next pointer | 202 * @param loc_next the location of the \c next pointer |
| 197 * @param node the successor of the node to find | 203 * @param node the successor of the node to find |
| 198 * @return the node or \c NULL if \p node has no predecessor | 204 * @return the node or \c NULL if \p node has no predecessor |
| 199 */ | 205 */ |
| 200 __attribute__((__nonnull__)) | 206 cx_attr_nonnull |
| 201 void *cx_linked_list_prev( | 207 void *cx_linked_list_prev( |
| 202 const void *begin, | 208 const void *begin, |
| 203 ptrdiff_t loc_next, | 209 ptrdiff_t loc_next, |
| 204 const void *node | 210 const void *node |
| 205 ); | 211 ); |
| 214 * @param end a pointer to the end node pointer (if your list has one) | 220 * @param end a pointer to the end node pointer (if your list has one) |
| 215 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) | 221 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) |
| 216 * @param loc_next the location of a \c next pointer within your node struct (required) | 222 * @param loc_next the location of a \c next pointer within your node struct (required) |
| 217 * @param new_node a pointer to the node that shall be appended | 223 * @param new_node a pointer to the node that shall be appended |
| 218 */ | 224 */ |
| 219 __attribute__((__nonnull__(5))) | 225 cx_attr_nonnull_arg(5) |
| 220 void cx_linked_list_add( | 226 void cx_linked_list_add( |
| 221 void **begin, | 227 void **begin, |
| 222 void **end, | 228 void **end, |
| 223 ptrdiff_t loc_prev, | 229 ptrdiff_t loc_prev, |
| 224 ptrdiff_t loc_next, | 230 ptrdiff_t loc_next, |
| 235 * @param end a pointer to the end node pointer (if your list has one) | 241 * @param end a pointer to the end node pointer (if your list has one) |
| 236 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) | 242 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) |
| 237 * @param loc_next the location of a \c next pointer within your node struct (required) | 243 * @param loc_next the location of a \c next pointer within your node struct (required) |
| 238 * @param new_node a pointer to the node that shall be prepended | 244 * @param new_node a pointer to the node that shall be prepended |
| 239 */ | 245 */ |
| 240 __attribute__((__nonnull__(5))) | 246 cx_attr_nonnull_arg(5) |
| 241 void cx_linked_list_prepend( | 247 void cx_linked_list_prepend( |
| 242 void **begin, | 248 void **begin, |
| 243 void **end, | 249 void **end, |
| 244 ptrdiff_t loc_prev, | 250 ptrdiff_t loc_prev, |
| 245 ptrdiff_t loc_next, | 251 ptrdiff_t loc_next, |
| 252 * @param left the new predecessor of \p right | 258 * @param left the new predecessor of \p right |
| 253 * @param right the new successor of \p left | 259 * @param right the new successor of \p left |
| 254 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) | 260 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) |
| 255 * @param loc_next the location of a \c next pointer within your node struct (required) | 261 * @param loc_next the location of a \c next pointer within your node struct (required) |
| 256 */ | 262 */ |
| 257 __attribute__((__nonnull__)) | 263 cx_attr_nonnull |
| 258 void cx_linked_list_link( | 264 void cx_linked_list_link( |
| 259 void *left, | 265 void *left, |
| 260 void *right, | 266 void *right, |
| 261 ptrdiff_t loc_prev, | 267 ptrdiff_t loc_prev, |
| 262 ptrdiff_t loc_next | 268 ptrdiff_t loc_next |
| 270 * @param left the predecessor of \p right | 276 * @param left the predecessor of \p right |
| 271 * @param right the successor of \p left | 277 * @param right the successor of \p left |
| 272 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) | 278 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) |
| 273 * @param loc_next the location of a \c next pointer within your node struct (required) | 279 * @param loc_next the location of a \c next pointer within your node struct (required) |
| 274 */ | 280 */ |
| 275 __attribute__((__nonnull__)) | 281 cx_attr_nonnull |
| 276 void cx_linked_list_unlink( | 282 void cx_linked_list_unlink( |
| 277 void *left, | 283 void *left, |
| 278 void *right, | 284 void *right, |
| 279 ptrdiff_t loc_prev, | 285 ptrdiff_t loc_prev, |
| 280 ptrdiff_t loc_next | 286 ptrdiff_t loc_next |
| 292 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) | 298 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) |
| 293 * @param loc_next the location of a \c next pointer within your node struct (required) | 299 * @param loc_next the location of a \c next pointer within your node struct (required) |
| 294 * @param node the node after which to insert (\c NULL if you want to prepend the node to the list) | 300 * @param node the node after which to insert (\c NULL if you want to prepend the node to the list) |
| 295 * @param new_node a pointer to the node that shall be inserted | 301 * @param new_node a pointer to the node that shall be inserted |
| 296 */ | 302 */ |
| 297 __attribute__((__nonnull__(6))) | 303 cx_attr_nonnull_arg(6) |
| 298 void cx_linked_list_insert( | 304 void cx_linked_list_insert( |
| 299 void **begin, | 305 void **begin, |
| 300 void **end, | 306 void **end, |
| 301 ptrdiff_t loc_prev, | 307 ptrdiff_t loc_prev, |
| 302 ptrdiff_t loc_next, | 308 ptrdiff_t loc_next, |
| 322 * @param loc_next the location of a \c next pointer within your node struct (required) | 328 * @param loc_next the location of a \c next pointer within your node struct (required) |
| 323 * @param node the node after which to insert (\c NULL to prepend the chain to the list) | 329 * @param node the node after which to insert (\c NULL to prepend the chain to the list) |
| 324 * @param insert_begin a pointer to the first node of the chain that shall be inserted | 330 * @param insert_begin a pointer to the first node of the chain that shall be inserted |
| 325 * @param insert_end a pointer to the last node of the chain (or NULL if the last node shall be determined) | 331 * @param insert_end a pointer to the last node of the chain (or NULL if the last node shall be determined) |
| 326 */ | 332 */ |
| 327 __attribute__((__nonnull__(6))) | 333 cx_attr_nonnull_arg(6) |
| 328 void cx_linked_list_insert_chain( | 334 void cx_linked_list_insert_chain( |
| 329 void **begin, | 335 void **begin, |
| 330 void **end, | 336 void **end, |
| 331 ptrdiff_t loc_prev, | 337 ptrdiff_t loc_prev, |
| 332 ptrdiff_t loc_next, | 338 ptrdiff_t loc_next, |
| 347 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) | 353 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) |
| 348 * @param loc_next the location of a \c next pointer within your node struct (required) | 354 * @param loc_next the location of a \c next pointer within your node struct (required) |
| 349 * @param new_node a pointer to the node that shall be inserted | 355 * @param new_node a pointer to the node that shall be inserted |
| 350 * @param cmp_func a compare function that will receive the node pointers | 356 * @param cmp_func a compare function that will receive the node pointers |
| 351 */ | 357 */ |
| 352 __attribute__((__nonnull__(1, 5, 6))) | 358 cx_attr_nonnull_arg(1, 5, 6) |
| 353 void cx_linked_list_insert_sorted( | 359 void cx_linked_list_insert_sorted( |
| 354 void **begin, | 360 void **begin, |
| 355 void **end, | 361 void **end, |
| 356 ptrdiff_t loc_prev, | 362 ptrdiff_t loc_prev, |
| 357 ptrdiff_t loc_next, | 363 ptrdiff_t loc_next, |
| 376 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) | 382 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) |
| 377 * @param loc_next the location of a \c next pointer within your node struct (required) | 383 * @param loc_next the location of a \c next pointer within your node struct (required) |
| 378 * @param insert_begin a pointer to the first node of the chain that shall be inserted | 384 * @param insert_begin a pointer to the first node of the chain that shall be inserted |
| 379 * @param cmp_func a compare function that will receive the node pointers | 385 * @param cmp_func a compare function that will receive the node pointers |
| 380 */ | 386 */ |
| 381 __attribute__((__nonnull__(1, 5, 6))) | 387 cx_attr_nonnull_arg(1, 5, 6) |
| 382 void cx_linked_list_insert_sorted_chain( | 388 void cx_linked_list_insert_sorted_chain( |
| 383 void **begin, | 389 void **begin, |
| 384 void **end, | 390 void **end, |
| 385 ptrdiff_t loc_prev, | 391 ptrdiff_t loc_prev, |
| 386 ptrdiff_t loc_next, | 392 ptrdiff_t loc_next, |
| 407 * @param loc_next the location of a \c next pointer within your node struct (required) | 413 * @param loc_next the location of a \c next pointer within your node struct (required) |
| 408 * @param node the start node of the chain | 414 * @param node the start node of the chain |
| 409 * @param num the number of nodes to remove | 415 * @param num the number of nodes to remove |
| 410 * @return the actual number of nodes that were removed (may be less when the list did not have enough nodes) | 416 * @return the actual number of nodes that were removed (may be less when the list did not have enough nodes) |
| 411 */ | 417 */ |
| 412 __attribute__((__nonnull__(5))) | 418 cx_attr_nonnull_arg(5) |
| 413 size_t cx_linked_list_remove_chain( | 419 size_t cx_linked_list_remove_chain( |
| 414 void **begin, | 420 void **begin, |
| 415 void **end, | 421 void **end, |
| 416 ptrdiff_t loc_prev, | 422 ptrdiff_t loc_prev, |
| 417 ptrdiff_t loc_next, | 423 ptrdiff_t loc_next, |
| 436 * @param end a pointer to the end node pointer (optional) | 442 * @param end a pointer to the end node pointer (optional) |
| 437 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) | 443 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) |
| 438 * @param loc_next the location of a \c next pointer within your node struct (required) | 444 * @param loc_next the location of a \c next pointer within your node struct (required) |
| 439 * @param node the node to remove | 445 * @param node the node to remove |
| 440 */ | 446 */ |
| 441 __attribute__((__nonnull__(5))) | 447 cx_attr_nonnull_arg(5) |
| 442 static inline void cx_linked_list_remove( | 448 static inline void cx_linked_list_remove( |
| 443 void **begin, | 449 void **begin, |
| 444 void **end, | 450 void **end, |
| 445 ptrdiff_t loc_prev, | 451 ptrdiff_t loc_prev, |
| 446 ptrdiff_t loc_next, | 452 ptrdiff_t loc_next, |
| 480 * @param loc_prev the location of a \c prev pointer within your node struct (negative if not present) | 486 * @param loc_prev the location of a \c prev pointer within your node struct (negative if not present) |
| 481 * @param loc_next the location of a \c next pointer within your node struct (required) | 487 * @param loc_next the location of a \c next pointer within your node struct (required) |
| 482 * @param loc_data the location of the \c data pointer within your node struct | 488 * @param loc_data the location of the \c data pointer within your node struct |
| 483 * @param cmp_func the compare function defining the sort order | 489 * @param cmp_func the compare function defining the sort order |
| 484 */ | 490 */ |
| 485 __attribute__((__nonnull__(1, 6))) | 491 cx_attr_nonnull_arg(1, 6) |
| 486 void cx_linked_list_sort( | 492 void cx_linked_list_sort( |
| 487 void **begin, | 493 void **begin, |
| 488 void **end, | 494 void **end, |
| 489 ptrdiff_t loc_prev, | 495 ptrdiff_t loc_prev, |
| 490 ptrdiff_t loc_next, | 496 ptrdiff_t loc_next, |
| 504 * @param loc_data the location of the \c data pointer within your node struct | 510 * @param loc_data the location of the \c data pointer within your node struct |
| 505 * @param cmp_func the function to compare the elements | 511 * @param cmp_func the function to compare the elements |
| 506 * @return the first non-zero result of invoking \p cmp_func or: negative if the left list is smaller than the | 512 * @return the first non-zero result of invoking \p cmp_func or: negative if the left list is smaller than the |
| 507 * right list, positive if the left list is larger than the right list, zero if both lists are equal. | 513 * right list, positive if the left list is larger than the right list, zero if both lists are equal. |
| 508 */ | 514 */ |
| 509 __attribute__((__nonnull__(5))) | 515 cx_attr_nonnull_arg(5) |
| 510 int cx_linked_list_compare( | 516 int cx_linked_list_compare( |
| 511 const void *begin_left, | 517 const void *begin_left, |
| 512 const void *begin_right, | 518 const void *begin_right, |
| 513 ptrdiff_t loc_advance, | 519 ptrdiff_t loc_advance, |
| 514 ptrdiff_t loc_data, | 520 ptrdiff_t loc_data, |
| 521 * @param begin a pointer to the begin node pointer (required) | 527 * @param begin a pointer to the begin node pointer (required) |
| 522 * @param end a pointer to the end node pointer (optional) | 528 * @param end a pointer to the end node pointer (optional) |
| 523 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) | 529 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) |
| 524 * @param loc_next the location of a \c next pointer within your node struct (required) | 530 * @param loc_next the location of a \c next pointer within your node struct (required) |
| 525 */ | 531 */ |
| 526 __attribute__((__nonnull__(1))) | 532 cx_attr_nonnull_arg(1) |
| 527 void cx_linked_list_reverse( | 533 void cx_linked_list_reverse( |
| 528 void **begin, | 534 void **begin, |
| 529 void **end, | 535 void **end, |
| 530 ptrdiff_t loc_prev, | 536 ptrdiff_t loc_prev, |
| 531 ptrdiff_t loc_next | 537 ptrdiff_t loc_next |
