comparison: src/cx/linked_list.h
src/cx/linked_list.h
- changeset 481
- eef025d82a34
- parent 480
- e3be53a3354f
- child 484
- 9e6900b1cf9d
equal
deleted
inserted
replaced
| 480:e3be53a3354f | 481:eef025d82a34 |
|---|---|
| 53 * @param allocator the allocator for allocating the list nodes | 53 * @param allocator the allocator for allocating the list nodes |
| 54 * @param comparator the comparator for the elements | 54 * @param comparator the comparator for the elements |
| 55 * @param item_size the size of each element in bytes | 55 * @param item_size the size of each element in bytes |
| 56 * @return the created list | 56 * @return the created list |
| 57 */ | 57 */ |
| 58 CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size); | 58 CxList cxLinkedListCreate( |
| 59 CxAllocator allocator, | |
| 60 CxListComparator comparator, | |
| 61 size_t item_size | |
| 62 ); | |
| 59 | 63 |
| 60 /** | 64 /** |
| 61 * Allocates a linked list for storing pointers. | 65 * Allocates a linked list for storing pointers. |
| 62 * | 66 * |
| 63 * If you want to store the elements directly in this list, use cxLinkedListCreate(). | 67 * If you want to store the elements directly in this list, use cxLinkedListCreate(). |
| 64 * | 68 * |
| 65 * @param allocator the allocator for allocating the list nodes | 69 * @param allocator the allocator for allocating the list nodes |
| 66 * @param comparator the comparator for the elements | 70 * @param comparator the comparator for the elements |
| 67 * @return the created list | 71 * @return the created list |
| 68 */ | 72 */ |
| 69 CxList cxPointerLinkedListCreate(CxAllocator allocator, CxListComparator comparator); | 73 CxList cxPointerLinkedListCreate( |
| 74 CxAllocator allocator, | |
| 75 CxListComparator comparator | |
| 76 ); | |
| 70 | 77 |
| 71 /** | 78 /** |
| 72 * Deallocates the memory of the entire list. | 79 * Deallocates the memory of the entire list. |
| 73 * | 80 * |
| 74 * \attention If this is a pointer list, the memory the pointers are referring to is \em not freed. | 81 * \attention If this is a pointer list, the memory the pointers are referring to is \em not freed. |
| 92 * @param start_index the start index | 99 * @param start_index the start index |
| 93 * @param loc_advance the location of the pointer to advance | 100 * @param loc_advance the location of the pointer to advance |
| 94 * @param index the search index | 101 * @param index the search index |
| 95 * @return the node found at the specified index | 102 * @return the node found at the specified index |
| 96 */ | 103 */ |
| 97 void *cx_linked_list_at(void *start, size_t start_index, ptrdiff_t loc_advance, size_t index) | 104 void *cx_linked_list_at( |
| 98 __attribute__((__nonnull__)); | 105 void *start, |
| 106 size_t start_index, | |
| 107 ptrdiff_t loc_advance, | |
| 108 size_t index | |
| 109 ) __attribute__((__nonnull__)); | |
| 99 | 110 |
| 100 /** | 111 /** |
| 101 * Finds the index of an element within a linked list. | 112 * Finds the index of an element within a linked list. |
| 102 * | 113 * |
| 103 * @param start a pointer to the start node | 114 * @param start a pointer to the start node |
| 107 * If \c true, the data at \p loc_data is assumed to be a pointer, dereferenced, and then passed to \p cmp_func. | 118 * If \c true, the data at \p loc_data is assumed to be a pointer, dereferenced, and then passed to \p cmp_func. |
| 108 * @param cmp_func a compare function to compare \p elem against the node data | 119 * @param cmp_func a compare function to compare \p elem against the node data |
| 109 * @param elem a pointer to the element to find | 120 * @param elem a pointer to the element to find |
| 110 * @return the index of the element or a past-one index if the element could not be found | 121 * @return the index of the element or a past-one index if the element could not be found |
| 111 */ | 122 */ |
| 112 size_t cx_linked_list_find(void *start, ptrdiff_t loc_advance, ptrdiff_t loc_data, int follow_ptr, | 123 size_t cx_linked_list_find( |
| 113 CxListComparator cmp_func, void *elem) | 124 void *start, |
| 114 __attribute__((__nonnull__)); | 125 ptrdiff_t loc_advance, |
| 126 ptrdiff_t loc_data, | |
| 127 int follow_ptr, | |
| 128 CxListComparator cmp_func, | |
| 129 void *elem | |
| 130 ) __attribute__((__nonnull__)); | |
| 115 | 131 |
| 116 /** | 132 /** |
| 117 * Finds the first node in a linked list. | 133 * Finds the first node in a linked list. |
| 118 * | 134 * |
| 119 * The function starts with the pointer denoted by \p node and traverses the list | 135 * The function starts with the pointer denoted by \p node and traverses the list |
| 121 * denoted by \p loc_prev. | 137 * denoted by \p loc_prev. |
| 122 * | 138 * |
| 123 * @param node a pointer to a node in the list | 139 * @param node a pointer to a node in the list |
| 124 * @param loc_prev the location of the \c prev pointer | 140 * @param loc_prev the location of the \c prev pointer |
| 125 */ | 141 */ |
| 126 void *cx_linked_list_first(void *node, ptrdiff_t loc_prev) | 142 void *cx_linked_list_first( |
| 127 __attribute__((__nonnull__)); | 143 void *node, |
| 144 ptrdiff_t loc_prev | |
| 145 ) __attribute__((__nonnull__)); | |
| 128 | 146 |
| 129 /** | 147 /** |
| 130 * Finds the last node in a linked list. | 148 * Finds the last node in a linked list. |
| 131 * | 149 * |
| 132 * The function starts with the pointer denoted by \p node and traverses the list | 150 * The function starts with the pointer denoted by \p node and traverses the list |
| 135 * | 153 * |
| 136 * @param node a pointer to a node in the list | 154 * @param node a pointer to a node in the list |
| 137 * @param loc_next the location of the \c next pointer | 155 * @param loc_next the location of the \c next pointer |
| 138 * @return a pointer to the last node | 156 * @return a pointer to the last node |
| 139 */ | 157 */ |
| 140 void *cx_linked_list_last(void *node, ptrdiff_t loc_next) | 158 void *cx_linked_list_last( |
| 141 __attribute__((__nonnull__)); | 159 void *node, |
| 160 ptrdiff_t loc_next | |
| 161 ) __attribute__((__nonnull__)); | |
| 142 | 162 |
| 143 /** | 163 /** |
| 144 * Finds the predecessor of a node in case it is not linked. | 164 * Finds the predecessor of a node in case it is not linked. |
| 145 * | 165 * |
| 146 * \remark If \p node is not contained in the list starting with \p begin, the behavior is undefined. | 166 * \remark If \p node is not contained in the list starting with \p begin, the behavior is undefined. |
| 148 * @param begin the node where to start the search | 168 * @param begin the node where to start the search |
| 149 * @param loc_next the location of the \c next pointer | 169 * @param loc_next the location of the \c next pointer |
| 150 * @param node the successor of the node to find | 170 * @param node the successor of the node to find |
| 151 * @return the node or \c NULL if \p node has no predecessor | 171 * @return the node or \c NULL if \p node has no predecessor |
| 152 */ | 172 */ |
| 153 void *cx_linked_list_prev(void *begin, ptrdiff_t loc_next, void *node) | 173 void *cx_linked_list_prev( |
| 154 __attribute__((__nonnull__)); | 174 void *begin, |
| 175 ptrdiff_t loc_next, | |
| 176 void *node | |
| 177 ) __attribute__((__nonnull__)); | |
| 155 | 178 |
| 156 /** | 179 /** |
| 157 * Adds a new node to a linked list. | 180 * Adds a new node to a linked list. |
| 158 * The node must not be part of any list already. | 181 * The node must not be part of any list already. |
| 159 * | 182 * |
| 163 * @param end a pointer to the end node pointer (if your list has one) | 186 * @param end a pointer to the end node pointer (if your list has one) |
| 164 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) | 187 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) |
| 165 * @param loc_next the location of a \c next pointer within your node struct (required) | 188 * @param loc_next the location of a \c next pointer within your node struct (required) |
| 166 * @param new_node a pointer to the node that shall be appended | 189 * @param new_node a pointer to the node that shall be appended |
| 167 */ | 190 */ |
| 168 void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) | 191 void cx_linked_list_add( |
| 169 __attribute__((__nonnull__(5))); | 192 void **begin, |
| 193 void **end, | |
| 194 ptrdiff_t loc_prev, | |
| 195 ptrdiff_t loc_next, | |
| 196 void *new_node | |
| 197 ) __attribute__((__nonnull__(5))); | |
| 170 | 198 |
| 171 /** | 199 /** |
| 172 * Prepends a new node to a linked list. | 200 * Prepends a new node to a linked list. |
| 173 * The node must not be part of any list already. | 201 * The node must not be part of any list already. |
| 174 * | 202 * |
| 178 * @param end a pointer to the end node pointer (if your list has one) | 206 * @param end a pointer to the end node pointer (if your list has one) |
| 179 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) | 207 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) |
| 180 * @param loc_next the location of a \c next pointer within your node struct (required) | 208 * @param loc_next the location of a \c next pointer within your node struct (required) |
| 181 * @param new_node a pointer to the node that shall be prepended | 209 * @param new_node a pointer to the node that shall be prepended |
| 182 */ | 210 */ |
| 183 void cx_linked_list_prepend(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node) | 211 void cx_linked_list_prepend( |
| 184 __attribute__((__nonnull__(5))); | 212 void **begin, |
| 213 void **end, | |
| 214 ptrdiff_t loc_prev, | |
| 215 ptrdiff_t loc_next, | |
| 216 void *new_node | |
| 217 ) __attribute__((__nonnull__(5))); | |
| 218 | |
| 219 /** | |
| 220 * Links two nodes. | |
| 221 * | |
| 222 * @param left the new predecessor of \p right | |
| 223 * @param right the new successor of \p left | |
| 224 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) | |
| 225 * @param loc_next the location of a \c next pointer within your node struct (required) | |
| 226 */ | |
| 227 void cx_linked_list_link( | |
| 228 void *left, | |
| 229 void *right, | |
| 230 ptrdiff_t loc_prev, | |
| 231 ptrdiff_t loc_next | |
| 232 ) __attribute__((__nonnull__)); | |
| 233 | |
| 234 /** | |
| 235 * Unlinks two nodes. | |
| 236 * | |
| 237 * If right is not the successor of left, the behavior is undefined. | |
| 238 * | |
| 239 * @param left the predecessor of \p right | |
| 240 * @param right the successor of \p left | |
| 241 * @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_next the location of a \c next pointer within your node struct (required) | |
| 243 */ | |
| 244 void cx_linked_list_unlink( | |
| 245 void *left, | |
| 246 void *right, | |
| 247 ptrdiff_t loc_prev, | |
| 248 ptrdiff_t loc_next | |
| 249 ) __attribute__((__nonnull__)); | |
| 250 | |
| 251 /** | |
| 252 * Inserts a new node after a given node of a linked list. | |
| 253 * The new node must not be part of any list already. | |
| 254 * | |
| 255 * \note If you specify \c NULL as the \p node to insert after, this function needs either the \p begin or | |
| 256 * the \p end pointer to determine the start of the list. Then the new node will be prepended to the list. | |
| 257 * | |
| 258 * @param begin a pointer to the begin node pointer (if your list has one) | |
| 259 * @param end a pointer to the end node pointer (if your list has one) | |
| 260 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) | |
| 261 * @param loc_next the location of a \c next pointer within your node struct (required) | |
| 262 * @param node the node after which to insert (\c NULL if you want to prepend the node to the list) | |
| 263 * @param new_node a pointer to the node that shall be prepended | |
| 264 */ | |
| 265 void cx_linked_list_insert( | |
| 266 void **begin, | |
| 267 void **end, | |
| 268 ptrdiff_t loc_prev, | |
| 269 ptrdiff_t loc_next, | |
| 270 void *node, | |
| 271 void *new_node | |
| 272 ) __attribute__((__nonnull__(6))); | |
| 273 | |
| 274 /** | |
| 275 * Inserts a chain of nodes after a given node of a linked list. | |
| 276 * The chain must not be part of any list already. | |
| 277 * | |
| 278 * If you do not explicitly specify the end of the chain, it will be determined by traversing | |
| 279 * the \c next pointer. | |
| 280 * | |
| 281 * \note If you specify \c NULL as the \p node to insert after, this function needs either the \p begin or | |
| 282 * the \p end pointer to determine the start of the list. If only the \p end pointer is specified, you also need | |
| 283 * to provide a valid \p loc_prev location. | |
| 284 * Then the chain will be prepended to the list. | |
| 285 * | |
| 286 * @param begin a pointer to the begin node pointer (if your list has one) | |
| 287 * @param end a pointer to the end node pointer (if your list has one) | |
| 288 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) | |
| 289 * @param loc_next the location of a \c next pointer within your node struct (required) | |
| 290 * @param node the node after which to insert (\c NULL to prepend the chain to the list) | |
| 291 * @param insert_begin a pointer to the first node of the chain that shall be inserted | |
| 292 * @param insert_end a pointer to the last node of the chain (or NULL if the last node shall be determined) | |
| 293 */ | |
| 294 void cx_linked_list_insert_chain( | |
| 295 void **begin, | |
| 296 void **end, | |
| 297 ptrdiff_t loc_prev, | |
| 298 ptrdiff_t loc_next, | |
| 299 void *node, | |
| 300 void *insert_begin, | |
| 301 void *insert_end | |
| 302 ) __attribute__((__nonnull__(6))); | |
| 185 | 303 |
| 186 /** | 304 /** |
| 187 * Removes a node from the linked list. | 305 * Removes a node from the linked list. |
| 188 * | 306 * |
| 189 * If the node to remove is the begin (resp. end) node of the list and if \p begin (resp. \p end) | 307 * If the node to remove is the begin (resp. end) node of the list and if \p begin (resp. \p end) |
| 200 * @param end a pointer to the end node pointer (optional) | 318 * @param end a pointer to the end node pointer (optional) |
| 201 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) | 319 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) |
| 202 * @param loc_next the location of a \c next pointer within your node struct (required) | 320 * @param loc_next the location of a \c next pointer within your node struct (required) |
| 203 * @param node the node to remove | 321 * @param node the node to remove |
| 204 */ | 322 */ |
| 205 void cx_linked_list_remove(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node) | 323 void cx_linked_list_remove( |
| 206 __attribute__((__nonnull__(5))); | 324 void **begin, |
| 325 void **end, | |
| 326 ptrdiff_t loc_prev, | |
| 327 ptrdiff_t loc_next, | |
| 328 void *node | |
| 329 ) __attribute__((__nonnull__(5))); | |
| 207 | 330 |
| 208 | 331 |
| 209 /** | 332 /** |
| 210 * Determines the size of a linked list starting with \p node. | 333 * Determines the size of a linked list starting with \p node. |
| 211 * @param node the first node | 334 * @param node the first node |
| 212 * @param loc_next the location of the \c next pointer within the node struct | 335 * @param loc_next the location of the \c next pointer within the node struct |
| 213 * @return the size of the list or zero if \p node is \c NULL | 336 * @return the size of the list or zero if \p node is \c NULL |
| 214 */ | 337 */ |
| 215 size_t cx_linked_list_size(void *node, ptrdiff_t loc_next); | 338 size_t cx_linked_list_size( |
| 339 void *node, | |
| 340 ptrdiff_t loc_next | |
| 341 ); | |
| 216 | 342 |
| 217 /** | 343 /** |
| 218 * Sorts a linked list based on a comparison function. | 344 * Sorts a linked list based on a comparison function. |
| 219 * | 345 * |
| 220 * This function can work with linked lists of the following structures: | 346 * This function can work with linked lists of the following structures: |
| 243 * @param loc_data the location of the \c data pointer within your node struct | 369 * @param loc_data the location of the \c data pointer within your node struct |
| 244 * @param follow_ptr \c false if the pointer denoted by \p loc_data shall be passed to the \p cmp_func. | 370 * @param follow_ptr \c false if the pointer denoted by \p loc_data shall be passed to the \p cmp_func. |
| 245 * If \c true, the data at \p loc_data is assumed to be a pointer, dereferenced, and then passed to \p cmp_func. | 371 * If \c true, the data at \p loc_data is assumed to be a pointer, dereferenced, and then passed to \p cmp_func. |
| 246 * @param cmp_func the compare function defining the sort order | 372 * @param cmp_func the compare function defining the sort order |
| 247 */ | 373 */ |
| 248 void cx_linked_list_sort(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, | 374 void cx_linked_list_sort( |
| 249 ptrdiff_t loc_data, int follow_ptr, CxListComparator cmp_func) | 375 void **begin, |
| 250 __attribute__((__nonnull__(1, 7))); | 376 void **end, |
| 251 | 377 ptrdiff_t loc_prev, |
| 378 ptrdiff_t loc_next, | |
| 379 ptrdiff_t loc_data, | |
| 380 int follow_ptr, | |
| 381 CxListComparator cmp_func | |
| 382 ) __attribute__((__nonnull__(1, 7))); | |
| 252 | 383 |
| 253 /** | 384 /** |
| 254 * Reverses the order of the nodes in a linked list. | 385 * Reverses the order of the nodes in a linked list. |
| 255 * | 386 * |
| 256 * @param begin a pointer to the begin node pointer (required) | 387 * @param begin a pointer to the begin node pointer (required) |
| 257 * @param end a pointer to the end node pointer (optional) | 388 * @param end a pointer to the end node pointer (optional) |
| 258 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) | 389 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one) |
| 259 * @param loc_next the location of a \c next pointer within your node struct (required) | 390 * @param loc_next the location of a \c next pointer within your node struct (required) |
| 260 */ | 391 */ |
| 261 void cx_linked_list_reverse(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next) | 392 void cx_linked_list_reverse( |
| 262 __attribute__((__nonnull__(1))); | 393 void **begin, |
| 394 void **end, | |
| 395 ptrdiff_t loc_prev, | |
| 396 ptrdiff_t loc_next | |
| 397 ) __attribute__((__nonnull__(1))); | |
| 263 | 398 |
| 264 #ifdef __cplusplus | 399 #ifdef __cplusplus |
| 265 } /* extern "C" */ | 400 } /* extern "C" */ |
| 266 #endif | 401 #endif |
| 267 | 402 |
