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 |