comparison: src/cx/linked_list.h
src/cx/linked_list.h
- changeset 891
- 49d8cff6f0ee
- parent 890
- 54565fd74e74
equal
deleted
inserted
replaced
| 890:54565fd74e74 | 891:49d8cff6f0ee |
|---|---|
| 102 * @param start_index the start index | 102 * @param start_index the start index |
| 103 * @param loc_advance the location of the pointer to advance | 103 * @param loc_advance the location of the pointer to advance |
| 104 * @param index the search index | 104 * @param index the search index |
| 105 * @return the node found at the specified index | 105 * @return the node found at the specified index |
| 106 */ | 106 */ |
| 107 __attribute__((__nonnull__)) | |
| 107 void *cx_linked_list_at( | 108 void *cx_linked_list_at( |
| 108 const void *start, | 109 const void *start, |
| 109 size_t start_index, | 110 size_t start_index, |
| 110 ptrdiff_t loc_advance, | 111 ptrdiff_t loc_advance, |
| 111 size_t index | 112 size_t index |
| 112 ) __attribute__((__nonnull__)); | 113 ); |
| 113 | 114 |
| 114 /** | 115 /** |
| 115 * Finds the index of an element within a linked list. | 116 * Finds the index of an element within a linked list. |
| 116 * | 117 * |
| 117 * @param start a pointer to the start node | 118 * @param start a pointer to the start node |
| 119 * @param loc_data the location of the \c data pointer within your node struct | 120 * @param loc_data the location of the \c data pointer within your node struct |
| 120 * @param cmp_func a compare function to compare \p elem against the node data | 121 * @param cmp_func a compare function to compare \p elem against the node data |
| 121 * @param elem a pointer to the element to find | 122 * @param elem a pointer to the element to find |
| 122 * @return the index of the element or a negative value if it could not be found | 123 * @return the index of the element or a negative value if it could not be found |
| 123 */ | 124 */ |
| 125 __attribute__((__nonnull__)) | |
| 124 ssize_t cx_linked_list_find( | 126 ssize_t cx_linked_list_find( |
| 125 const void *start, | 127 const void *start, |
| 126 ptrdiff_t loc_advance, | 128 ptrdiff_t loc_advance, |
| 127 ptrdiff_t loc_data, | 129 ptrdiff_t loc_data, |
| 128 cx_compare_func cmp_func, | 130 cx_compare_func cmp_func, |
| 129 const void *elem | 131 const void *elem |
| 130 ) __attribute__((__nonnull__)); | 132 ); |
| 131 | 133 |
| 132 /** | 134 /** |
| 133 * Finds the node containing an element within a linked list. | 135 * Finds the node containing an element within a linked list. |
| 134 * | 136 * |
| 135 * @param result a pointer to the memory where the node pointer (or \c NULL if the element | 137 * @param result a pointer to the memory where the node pointer (or \c NULL if the element |
| 139 * @param loc_data the location of the \c data pointer within your node struct | 141 * @param loc_data the location of the \c data pointer within your node struct |
| 140 * @param cmp_func a compare function to compare \p elem against the node data | 142 * @param cmp_func a compare function to compare \p elem against the node data |
| 141 * @param elem a pointer to the element to find | 143 * @param elem a pointer to the element to find |
| 142 * @return the index of the element or a negative value if it could not be found | 144 * @return the index of the element or a negative value if it could not be found |
| 143 */ | 145 */ |
| 146 __attribute__((__nonnull__)) | |
| 144 ssize_t cx_linked_list_find_node( | 147 ssize_t cx_linked_list_find_node( |
| 145 void **result, | 148 void **result, |
| 146 const void *start, | 149 const void *start, |
| 147 ptrdiff_t loc_advance, | 150 ptrdiff_t loc_advance, |
| 148 ptrdiff_t loc_data, | 151 ptrdiff_t loc_data, |
| 149 cx_compare_func cmp_func, | 152 cx_compare_func cmp_func, |
| 150 const void *elem | 153 const void *elem |
| 151 ) __attribute__((__nonnull__)); | 154 ); |
| 152 | 155 |
| 153 /** | 156 /** |
| 154 * Finds the first node in a linked list. | 157 * Finds the first node in a linked list. |
| 155 * | 158 * |
| 156 * The function starts with the pointer denoted by \p node and traverses the list | 159 * The function starts with the pointer denoted by \p node and traverses the list |
| 159 * | 162 * |
| 160 * @param node a pointer to a node in the list | 163 * @param node a pointer to a node in the list |
| 161 * @param loc_prev the location of the \c prev pointer | 164 * @param loc_prev the location of the \c prev pointer |
| 162 * @return a pointer to the first node | 165 * @return a pointer to the first node |
| 163 */ | 166 */ |
| 167 __attribute__((__nonnull__)) | |
| 164 void *cx_linked_list_first( | 168 void *cx_linked_list_first( |
| 165 const void *node, | 169 const void *node, |
| 166 ptrdiff_t loc_prev | 170 ptrdiff_t loc_prev |
| 167 ) __attribute__((__nonnull__)); | 171 ); |
| 168 | 172 |
| 169 /** | 173 /** |
| 170 * Finds the last node in a linked list. | 174 * Finds the last node in a linked list. |
| 171 * | 175 * |
| 172 * The function starts with the pointer denoted by \p node and traverses the list | 176 * The function starts with the pointer denoted by \p node and traverses the list |
| 175 * | 179 * |
| 176 * @param node a pointer to a node in the list | 180 * @param node a pointer to a node in the list |
| 177 * @param loc_next the location of the \c next pointer | 181 * @param loc_next the location of the \c next pointer |
| 178 * @return a pointer to the last node | 182 * @return a pointer to the last node |
| 179 */ | 183 */ |
| 184 __attribute__((__nonnull__)) | |
| 180 void *cx_linked_list_last( | 185 void *cx_linked_list_last( |
| 181 const void *node, | 186 const void *node, |
| 182 ptrdiff_t loc_next | 187 ptrdiff_t loc_next |
| 183 ) __attribute__((__nonnull__)); | 188 ); |
| 184 | 189 |
| 185 /** | 190 /** |
| 186 * Finds the predecessor of a node in case it is not linked. | 191 * Finds the predecessor of a node in case it is not linked. |
| 187 * | 192 * |
| 188 * \remark If \p node is not contained in the list starting with \p begin, the behavior is undefined. | 193 * \remark If \p node is not contained in the list starting with \p begin, the behavior is undefined. |
| 190 * @param begin the node where to start the search | 195 * @param begin the node where to start the search |
| 191 * @param loc_next the location of the \c next pointer | 196 * @param loc_next the location of the \c next pointer |
| 192 * @param node the successor of the node to find | 197 * @param node the successor of the node to find |
| 193 * @return the node or \c NULL if \p node has no predecessor | 198 * @return the node or \c NULL if \p node has no predecessor |
| 194 */ | 199 */ |
| 200 __attribute__((__nonnull__)) | |
| 195 void *cx_linked_list_prev( | 201 void *cx_linked_list_prev( |
| 196 const void *begin, | 202 const void *begin, |
| 197 ptrdiff_t loc_next, | 203 ptrdiff_t loc_next, |
| 198 const void *node | 204 const void *node |
| 199 ) __attribute__((__nonnull__)); | 205 ); |
| 200 | 206 |
| 201 /** | 207 /** |
| 202 * Adds a new node to a linked list. | 208 * Adds a new node to a linked list. |
| 203 * The node must not be part of any list already. | 209 * The node must not be part of any list already. |
| 204 * | 210 * |
| 208 * @param end a pointer to the end node pointer (if your list has one) | 214 * @param end a pointer to the end node pointer (if your list has one) |
| 209 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) | 215 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) |
| 210 * @param loc_next the location of a \c next pointer within your node struct (required) | 216 * @param loc_next the location of a \c next pointer within your node struct (required) |
| 211 * @param new_node a pointer to the node that shall be appended | 217 * @param new_node a pointer to the node that shall be appended |
| 212 */ | 218 */ |
| 219 __attribute__((__nonnull__(5))) | |
| 213 void cx_linked_list_add( | 220 void cx_linked_list_add( |
| 214 void **begin, | 221 void **begin, |
| 215 void **end, | 222 void **end, |
| 216 ptrdiff_t loc_prev, | 223 ptrdiff_t loc_prev, |
| 217 ptrdiff_t loc_next, | 224 ptrdiff_t loc_next, |
| 218 void *new_node | 225 void *new_node |
| 219 ) __attribute__((__nonnull__(5))); | 226 ); |
| 220 | 227 |
| 221 /** | 228 /** |
| 222 * Prepends a new node to a linked list. | 229 * Prepends a new node to a linked list. |
| 223 * The node must not be part of any list already. | 230 * The node must not be part of any list already. |
| 224 * | 231 * |
| 228 * @param end a pointer to the end node pointer (if your list has one) | 235 * @param end a pointer to the end node pointer (if your list has one) |
| 229 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) | 236 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) |
| 230 * @param loc_next the location of a \c next pointer within your node struct (required) | 237 * @param loc_next the location of a \c next pointer within your node struct (required) |
| 231 * @param new_node a pointer to the node that shall be prepended | 238 * @param new_node a pointer to the node that shall be prepended |
| 232 */ | 239 */ |
| 240 __attribute__((__nonnull__(5))) | |
| 233 void cx_linked_list_prepend( | 241 void cx_linked_list_prepend( |
| 234 void **begin, | 242 void **begin, |
| 235 void **end, | 243 void **end, |
| 236 ptrdiff_t loc_prev, | 244 ptrdiff_t loc_prev, |
| 237 ptrdiff_t loc_next, | 245 ptrdiff_t loc_next, |
| 238 void *new_node | 246 void *new_node |
| 239 ) __attribute__((__nonnull__(5))); | 247 ); |
| 240 | 248 |
| 241 /** | 249 /** |
| 242 * Links two nodes. | 250 * Links two nodes. |
| 243 * | 251 * |
| 244 * @param left the new predecessor of \p right | 252 * @param left the new predecessor of \p right |
| 245 * @param right the new successor of \p left | 253 * @param right the new successor of \p left |
| 246 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) | 254 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) |
| 247 * @param loc_next the location of a \c next pointer within your node struct (required) | 255 * @param loc_next the location of a \c next pointer within your node struct (required) |
| 248 */ | 256 */ |
| 257 __attribute__((__nonnull__)) | |
| 249 void cx_linked_list_link( | 258 void cx_linked_list_link( |
| 250 void *left, | 259 void *left, |
| 251 void *right, | 260 void *right, |
| 252 ptrdiff_t loc_prev, | 261 ptrdiff_t loc_prev, |
| 253 ptrdiff_t loc_next | 262 ptrdiff_t loc_next |
| 254 ) __attribute__((__nonnull__)); | 263 ); |
| 255 | 264 |
| 256 /** | 265 /** |
| 257 * Unlinks two nodes. | 266 * Unlinks two nodes. |
| 258 * | 267 * |
| 259 * If right is not the successor of left, the behavior is undefined. | 268 * If right is not the successor of left, the behavior is undefined. |
| 261 * @param left the predecessor of \p right | 270 * @param left the predecessor of \p right |
| 262 * @param right the successor of \p left | 271 * @param right the successor of \p left |
| 263 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) | 272 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) |
| 264 * @param loc_next the location of a \c next pointer within your node struct (required) | 273 * @param loc_next the location of a \c next pointer within your node struct (required) |
| 265 */ | 274 */ |
| 275 __attribute__((__nonnull__)) | |
| 266 void cx_linked_list_unlink( | 276 void cx_linked_list_unlink( |
| 267 void *left, | 277 void *left, |
| 268 void *right, | 278 void *right, |
| 269 ptrdiff_t loc_prev, | 279 ptrdiff_t loc_prev, |
| 270 ptrdiff_t loc_next | 280 ptrdiff_t loc_next |
| 271 ) __attribute__((__nonnull__)); | 281 ); |
| 272 | 282 |
| 273 /** | 283 /** |
| 274 * Inserts a new node after a given node of a linked list. | 284 * Inserts a new node after a given node of a linked list. |
| 275 * The new node must not be part of any list already. | 285 * The new node must not be part of any list already. |
| 276 * | 286 * |
| 282 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) | 292 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) |
| 283 * @param loc_next the location of a \c next pointer within your node struct (required) | 293 * @param loc_next the location of a \c next pointer within your node struct (required) |
| 284 * @param node the node after which to insert (\c NULL if you want to prepend the node to the list) | 294 * @param node the node after which to insert (\c NULL if you want to prepend the node to the list) |
| 285 * @param new_node a pointer to the node that shall be inserted | 295 * @param new_node a pointer to the node that shall be inserted |
| 286 */ | 296 */ |
| 297 __attribute__((__nonnull__(6))) | |
| 287 void cx_linked_list_insert( | 298 void cx_linked_list_insert( |
| 288 void **begin, | 299 void **begin, |
| 289 void **end, | 300 void **end, |
| 290 ptrdiff_t loc_prev, | 301 ptrdiff_t loc_prev, |
| 291 ptrdiff_t loc_next, | 302 ptrdiff_t loc_next, |
| 292 void *node, | 303 void *node, |
| 293 void *new_node | 304 void *new_node |
| 294 ) __attribute__((__nonnull__(6))); | 305 ); |
| 295 | 306 |
| 296 /** | 307 /** |
| 297 * Inserts a chain of nodes after a given node of a linked list. | 308 * Inserts a chain of nodes after a given node of a linked list. |
| 298 * The chain must not be part of any list already. | 309 * The chain must not be part of any list already. |
| 299 * | 310 * |
| 311 * @param loc_next the location of a \c next pointer within your node struct (required) | 322 * @param loc_next the location of a \c next pointer within your node struct (required) |
| 312 * @param node the node after which to insert (\c NULL to prepend the chain to the list) | 323 * @param node the node after which to insert (\c NULL to prepend the chain to the list) |
| 313 * @param insert_begin a pointer to the first node of the chain that shall be inserted | 324 * @param insert_begin a pointer to the first node of the chain that shall be inserted |
| 314 * @param insert_end a pointer to the last node of the chain (or NULL if the last node shall be determined) | 325 * @param insert_end a pointer to the last node of the chain (or NULL if the last node shall be determined) |
| 315 */ | 326 */ |
| 327 __attribute__((__nonnull__(6))) | |
| 316 void cx_linked_list_insert_chain( | 328 void cx_linked_list_insert_chain( |
| 317 void **begin, | 329 void **begin, |
| 318 void **end, | 330 void **end, |
| 319 ptrdiff_t loc_prev, | 331 ptrdiff_t loc_prev, |
| 320 ptrdiff_t loc_next, | 332 ptrdiff_t loc_next, |
| 321 void *node, | 333 void *node, |
| 322 void *insert_begin, | 334 void *insert_begin, |
| 323 void *insert_end | 335 void *insert_end |
| 324 ) __attribute__((__nonnull__(6))); | 336 ); |
| 325 | 337 |
| 326 /** | 338 /** |
| 327 * Inserts a node into a sorted linked list. | 339 * Inserts a node into a sorted linked list. |
| 328 * The new node must not be part of any list already. | 340 * The new node must not be part of any list already. |
| 329 * | 341 * |
| 335 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) | 347 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) |
| 336 * @param loc_next the location of a \c next pointer within your node struct (required) | 348 * @param loc_next the location of a \c next pointer within your node struct (required) |
| 337 * @param new_node a pointer to the node that shall be inserted | 349 * @param new_node a pointer to the node that shall be inserted |
| 338 * @param cmp_func a compare function that will receive the node pointers | 350 * @param cmp_func a compare function that will receive the node pointers |
| 339 */ | 351 */ |
| 352 __attribute__((__nonnull__(1, 5, 6))) | |
| 340 void cx_linked_list_insert_sorted( | 353 void cx_linked_list_insert_sorted( |
| 341 void **begin, | 354 void **begin, |
| 342 void **end, | 355 void **end, |
| 343 ptrdiff_t loc_prev, | 356 ptrdiff_t loc_prev, |
| 344 ptrdiff_t loc_next, | 357 ptrdiff_t loc_next, |
| 345 void *new_node, | 358 void *new_node, |
| 346 cx_compare_func cmp_func | 359 cx_compare_func cmp_func |
| 347 ) __attribute__((__nonnull__(1, 5, 6))); | 360 ); |
| 348 | 361 |
| 349 /** | 362 /** |
| 350 * Inserts a chain of nodes into a sorted linked list. | 363 * Inserts a chain of nodes into a sorted linked list. |
| 351 * The chain must not be part of any list already. | 364 * The chain must not be part of any list already. |
| 352 * | 365 * |
| 363 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) | 376 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) |
| 364 * @param loc_next the location of a \c next pointer within your node struct (required) | 377 * @param loc_next the location of a \c next pointer within your node struct (required) |
| 365 * @param insert_begin a pointer to the first node of the chain that shall be inserted | 378 * @param insert_begin a pointer to the first node of the chain that shall be inserted |
| 366 * @param cmp_func a compare function that will receive the node pointers | 379 * @param cmp_func a compare function that will receive the node pointers |
| 367 */ | 380 */ |
| 381 __attribute__((__nonnull__(1, 5, 6))) | |
| 368 void cx_linked_list_insert_sorted_chain( | 382 void cx_linked_list_insert_sorted_chain( |
| 369 void **begin, | 383 void **begin, |
| 370 void **end, | 384 void **end, |
| 371 ptrdiff_t loc_prev, | 385 ptrdiff_t loc_prev, |
| 372 ptrdiff_t loc_next, | 386 ptrdiff_t loc_next, |
| 373 void *insert_begin, | 387 void *insert_begin, |
| 374 cx_compare_func cmp_func | 388 cx_compare_func cmp_func |
| 375 ) __attribute__((__nonnull__(1, 5, 6))); | 389 ); |
| 376 | 390 |
| 377 /** | 391 /** |
| 378 * Removes a node from the linked list. | 392 * Removes a node from the linked list. |
| 379 * | 393 * |
| 380 * If the node to remove is the begin (resp. end) node of the list and if \p begin (resp. \p end) | 394 * If the node to remove is the begin (resp. end) node of the list and if \p begin (resp. \p end) |
| 391 * @param end a pointer to the end node pointer (optional) | 405 * @param end a pointer to the end node pointer (optional) |
| 392 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) | 406 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) |
| 393 * @param loc_next the location of a \c next pointer within your node struct (required) | 407 * @param loc_next the location of a \c next pointer within your node struct (required) |
| 394 * @param node the node to remove | 408 * @param node the node to remove |
| 395 */ | 409 */ |
| 410 __attribute__((__nonnull__(5))) | |
| 396 void cx_linked_list_remove( | 411 void cx_linked_list_remove( |
| 397 void **begin, | 412 void **begin, |
| 398 void **end, | 413 void **end, |
| 399 ptrdiff_t loc_prev, | 414 ptrdiff_t loc_prev, |
| 400 ptrdiff_t loc_next, | 415 ptrdiff_t loc_next, |
| 401 void *node | 416 void *node |
| 402 ) __attribute__((__nonnull__(5))); | 417 ); |
| 403 | 418 |
| 404 | 419 |
| 405 /** | 420 /** |
| 406 * Determines the size of a linked list starting with \p node. | 421 * Determines the size of a linked list starting with \p node. |
| 407 * @param node the first node | 422 * @param node the first node |
| 433 * @param loc_prev the location of a \c prev pointer within your node struct (negative if not present) | 448 * @param loc_prev the location of a \c prev pointer within your node struct (negative if not present) |
| 434 * @param loc_next the location of a \c next pointer within your node struct (required) | 449 * @param loc_next the location of a \c next pointer within your node struct (required) |
| 435 * @param loc_data the location of the \c data pointer within your node struct | 450 * @param loc_data the location of the \c data pointer within your node struct |
| 436 * @param cmp_func the compare function defining the sort order | 451 * @param cmp_func the compare function defining the sort order |
| 437 */ | 452 */ |
| 453 __attribute__((__nonnull__(1, 6))) | |
| 438 void cx_linked_list_sort( | 454 void cx_linked_list_sort( |
| 439 void **begin, | 455 void **begin, |
| 440 void **end, | 456 void **end, |
| 441 ptrdiff_t loc_prev, | 457 ptrdiff_t loc_prev, |
| 442 ptrdiff_t loc_next, | 458 ptrdiff_t loc_next, |
| 443 ptrdiff_t loc_data, | 459 ptrdiff_t loc_data, |
| 444 cx_compare_func cmp_func | 460 cx_compare_func cmp_func |
| 445 ) __attribute__((__nonnull__(1, 6))); | 461 ); |
| 446 | 462 |
| 447 | 463 |
| 448 /** | 464 /** |
| 449 * Compares two lists element wise. | 465 * Compares two lists element wise. |
| 450 * | 466 * |
| 456 * @param loc_data the location of the \c data pointer within your node struct | 472 * @param loc_data the location of the \c data pointer within your node struct |
| 457 * @param cmp_func the function to compare the elements | 473 * @param cmp_func the function to compare the elements |
| 458 * @return the first non-zero result of invoking \p cmp_func or: negative if the left list is smaller than the | 474 * @return the first non-zero result of invoking \p cmp_func or: negative if the left list is smaller than the |
| 459 * right list, positive if the left list is larger than the right list, zero if both lists are equal. | 475 * right list, positive if the left list is larger than the right list, zero if both lists are equal. |
| 460 */ | 476 */ |
| 477 __attribute__((__nonnull__(5))) | |
| 461 int cx_linked_list_compare( | 478 int cx_linked_list_compare( |
| 462 const void *begin_left, | 479 const void *begin_left, |
| 463 const void *begin_right, | 480 const void *begin_right, |
| 464 ptrdiff_t loc_advance, | 481 ptrdiff_t loc_advance, |
| 465 ptrdiff_t loc_data, | 482 ptrdiff_t loc_data, |
| 466 cx_compare_func cmp_func | 483 cx_compare_func cmp_func |
| 467 ) __attribute__((__nonnull__(5))); | 484 ); |
| 468 | 485 |
| 469 /** | 486 /** |
| 470 * Reverses the order of the nodes in a linked list. | 487 * Reverses the order of the nodes in a linked list. |
| 471 * | 488 * |
| 472 * @param begin a pointer to the begin node pointer (required) | 489 * @param begin a pointer to the begin node pointer (required) |
| 473 * @param end a pointer to the end node pointer (optional) | 490 * @param end a pointer to the end node pointer (optional) |
| 474 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) | 491 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) |
| 475 * @param loc_next the location of a \c next pointer within your node struct (required) | 492 * @param loc_next the location of a \c next pointer within your node struct (required) |
| 476 */ | 493 */ |
| 494 __attribute__((__nonnull__(1))) | |
| 477 void cx_linked_list_reverse( | 495 void cx_linked_list_reverse( |
| 478 void **begin, | 496 void **begin, |
| 479 void **end, | 497 void **end, |
| 480 ptrdiff_t loc_prev, | 498 ptrdiff_t loc_prev, |
| 481 ptrdiff_t loc_next | 499 ptrdiff_t loc_next |
| 482 ) __attribute__((__nonnull__(1))); | 500 ); |
| 483 | 501 |
| 484 #ifdef __cplusplus | 502 #ifdef __cplusplus |
| 485 } // extern "C" | 503 } // extern "C" |
| 486 #endif | 504 #endif |
| 487 | 505 |
