src/cx/linked_list.h

Sun, 22 Dec 2024 21:42:16 +0100

author
Mike Becker <universe@uap-core.de>
date
Sun, 22 Dec 2024 21:42:16 +0100
changeset 1045
468c868cc8a8
parent 993
b642eca4b956
permissions
-rw-r--r--

add attributes to string to number conversion functions

issue #532

398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
1 /*
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
3 *
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
4 * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
5 *
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
6 * Redistribution and use in source and binary forms, with or without
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
7 * modification, are permitted provided that the following conditions are met:
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
8 *
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
9 * 1. Redistributions of source code must retain the above copyright
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
10 * notice, this list of conditions and the following disclaimer.
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
11 *
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
12 * 2. Redistributions in binary form must reproduce the above copyright
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
13 * notice, this list of conditions and the following disclaimer in the
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
14 * documentation and/or other materials provided with the distribution.
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
15 *
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
26 * POSSIBILITY OF SUCH DAMAGE.
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
27 */
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
28 /**
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
29 * \file linked_list.h
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
30 * \brief Linked list implementation.
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
31 * \details Also provides several low-level functions for custom linked list implementations.
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
32 * \author Mike Becker
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
33 * \author Olaf Wintermann
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
34 * \copyright 2-Clause BSD License
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
35 */
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
36
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
37 #ifndef UCX_LINKED_LIST_H
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
38 #define UCX_LINKED_LIST_H
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
39
484
9e6900b1cf9d add common.h include to all other header files
Mike Becker <universe@uap-core.de>
parents: 481
diff changeset
40 #include "common.h"
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
41 #include "list.h"
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
42
415
067aa769796a fix missing extern "C"
Mike Becker <universe@uap-core.de>
parents: 412
diff changeset
43 #ifdef __cplusplus
067aa769796a fix missing extern "C"
Mike Becker <universe@uap-core.de>
parents: 412
diff changeset
44 extern "C" {
067aa769796a fix missing extern "C"
Mike Becker <universe@uap-core.de>
parents: 412
diff changeset
45 #endif
067aa769796a fix missing extern "C"
Mike Becker <universe@uap-core.de>
parents: 412
diff changeset
46
466
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 456
diff changeset
47 /**
807
c8d692131b1e remove flags to disable SBO in tests - fix #343 fix #358
Mike Becker <universe@uap-core.de>
parents: 764
diff changeset
48 * The maximum item size that uses SBO swap instead of relinking.
647
2e6e9d9f2159 implement swap function for list elements - fixes #218
Mike Becker <universe@uap-core.de>
parents: 639
diff changeset
49 */
926
8fdd8d78c14b fix several survivors of east-const and some missing consts
Mike Becker <universe@uap-core.de>
parents: 919
diff changeset
50 extern const unsigned cx_linked_list_swap_sbo_size;
647
2e6e9d9f2159 implement swap function for list elements - fixes #218
Mike Becker <universe@uap-core.de>
parents: 639
diff changeset
51
2e6e9d9f2159 implement swap function for list elements - fixes #218
Mike Becker <universe@uap-core.de>
parents: 639
diff changeset
52 /**
855
35bcb3216c0d fix inconsistent use of item_size and elem_size
Mike Becker <universe@uap-core.de>
parents: 807
diff changeset
53 * Allocates a linked list for storing elements with \p elem_size bytes each.
466
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 456
diff changeset
54 *
855
35bcb3216c0d fix inconsistent use of item_size and elem_size
Mike Becker <universe@uap-core.de>
parents: 807
diff changeset
55 * If \p elem_size is CX_STORE_POINTERS, the created list will be created as if
763
741a2040fa33 make cx_cmp_ptr default comparator for pointer lists - relates to #340
Mike Becker <universe@uap-core.de>
parents: 759
diff changeset
56 * cxListStorePointers() was called immediately after creation and the compare
741a2040fa33 make cx_cmp_ptr default comparator for pointer lists - relates to #340
Mike Becker <universe@uap-core.de>
parents: 759
diff changeset
57 * function will be automatically set to cx_cmp_ptr(), if none is given.
669
dce9b8450656 add docs for CX_STORE_POINTERS and remove cxHashMapCreateForPointers()
Mike Becker <universe@uap-core.de>
parents: 662
diff changeset
58 *
466
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 456
diff changeset
59 * @param allocator the allocator for allocating the list nodes
989
8aa57a7fecc4 improve consistency for allocator arguments - fixes #485
Mike Becker <universe@uap-core.de>
parents: 985
diff changeset
60 * (if \c NULL, a default stdlib allocator will be used)
466
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 456
diff changeset
61 * @param comparator the comparator for the elements
763
741a2040fa33 make cx_cmp_ptr default comparator for pointer lists - relates to #340
Mike Becker <universe@uap-core.de>
parents: 759
diff changeset
62 * (if \c NULL, and the list is not storing pointers, sort and find
741a2040fa33 make cx_cmp_ptr default comparator for pointer lists - relates to #340
Mike Becker <universe@uap-core.de>
parents: 759
diff changeset
63 * functions will not work)
855
35bcb3216c0d fix inconsistent use of item_size and elem_size
Mike Becker <universe@uap-core.de>
parents: 807
diff changeset
64 * @param elem_size the size of each element in bytes
466
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 456
diff changeset
65 * @return the created list
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 456
diff changeset
66 */
985
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
67 cx_attr_nodiscard
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
68 cx_attr_malloc
993
b642eca4b956 make names of destroy and free functions consistent - fixes #484
Mike Becker <universe@uap-core.de>
parents: 989
diff changeset
69 cx_attr_dealloc(cxListFree, 1)
500
eb9e7bd40a8e do not hide pointers behind typedefs
Mike Becker <universe@uap-core.de>
parents: 489
diff changeset
70 CxList *cxLinkedListCreate(
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 879
diff changeset
71 const CxAllocator *allocator,
677
b09aae58bba4 refactoring of collections to make use of destructors in map implementations
Mike Becker <universe@uap-core.de>
parents: 670
diff changeset
72 cx_compare_func comparator,
855
35bcb3216c0d fix inconsistent use of item_size and elem_size
Mike Becker <universe@uap-core.de>
parents: 807
diff changeset
73 size_t elem_size
670
4ad8ea3aee49 allow NULL for allocator and comparator
Mike Becker <universe@uap-core.de>
parents: 669
diff changeset
74 );
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
75
466
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 456
diff changeset
76 /**
855
35bcb3216c0d fix inconsistent use of item_size and elem_size
Mike Becker <universe@uap-core.de>
parents: 807
diff changeset
77 * Allocates a linked list for storing elements with \p elem_size bytes each.
662
d0d95740071b add simple functions for creating lists
Mike Becker <universe@uap-core.de>
parents: 647
diff changeset
78 *
d0d95740071b add simple functions for creating lists
Mike Becker <universe@uap-core.de>
parents: 647
diff changeset
79 * The list will use cxDefaultAllocator and no comparator function. If you want
d0d95740071b add simple functions for creating lists
Mike Becker <universe@uap-core.de>
parents: 647
diff changeset
80 * to call functions that need a comparator, you must either set one immediately
d0d95740071b add simple functions for creating lists
Mike Becker <universe@uap-core.de>
parents: 647
diff changeset
81 * after list creation or use cxLinkedListCreate().
d0d95740071b add simple functions for creating lists
Mike Becker <universe@uap-core.de>
parents: 647
diff changeset
82 *
855
35bcb3216c0d fix inconsistent use of item_size and elem_size
Mike Becker <universe@uap-core.de>
parents: 807
diff changeset
83 * If \p elem_size is CX_STORE_POINTERS, the created list will be created as if
763
741a2040fa33 make cx_cmp_ptr default comparator for pointer lists - relates to #340
Mike Becker <universe@uap-core.de>
parents: 759
diff changeset
84 * cxListStorePointers() was called immediately after creation and the compare
741a2040fa33 make cx_cmp_ptr default comparator for pointer lists - relates to #340
Mike Becker <universe@uap-core.de>
parents: 759
diff changeset
85 * function will be automatically set to cx_cmp_ptr().
669
dce9b8450656 add docs for CX_STORE_POINTERS and remove cxHashMapCreateForPointers()
Mike Becker <universe@uap-core.de>
parents: 662
diff changeset
86 *
855
35bcb3216c0d fix inconsistent use of item_size and elem_size
Mike Becker <universe@uap-core.de>
parents: 807
diff changeset
87 * @param elem_size the size of each element in bytes
662
d0d95740071b add simple functions for creating lists
Mike Becker <universe@uap-core.de>
parents: 647
diff changeset
88 * @return the created list
d0d95740071b add simple functions for creating lists
Mike Becker <universe@uap-core.de>
parents: 647
diff changeset
89 */
855
35bcb3216c0d fix inconsistent use of item_size and elem_size
Mike Becker <universe@uap-core.de>
parents: 807
diff changeset
90 #define cxLinkedListCreateSimple(elem_size) \
35bcb3216c0d fix inconsistent use of item_size and elem_size
Mike Becker <universe@uap-core.de>
parents: 807
diff changeset
91 cxLinkedListCreate(NULL, NULL, elem_size)
662
d0d95740071b add simple functions for creating lists
Mike Becker <universe@uap-core.de>
parents: 647
diff changeset
92
d0d95740071b add simple functions for creating lists
Mike Becker <universe@uap-core.de>
parents: 647
diff changeset
93 /**
438
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
94 * Finds the node at a certain index.
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
95 *
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
96 * This function can be used to start at an arbitrary position within the list.
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
97 * If the search index is large than the start index, \p loc_advance must denote
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
98 * the location of some sort of \c next pointer (i.e. a pointer to the next node).
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
99 * But it is also possible that the search index is smaller than the start index
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
100 * (e.g. in cases where traversing a list backwards is faster) in which case
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
101 * \p loc_advance must denote the location of some sort of \c prev pointer
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
102 * (i.e. a pointer to the previous node).
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
103 *
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
104 * @param start a pointer to the start node
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
105 * @param start_index the start index
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
106 * @param loc_advance the location of the pointer to advance
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
107 * @param index the search index
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
108 * @return the node found at the specified index
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
109 */
985
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
110 cx_attr_nonnull
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
111 cx_attr_nodiscard
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
112 void *cx_linked_list_at(
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 879
diff changeset
113 const void *start,
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
114 size_t start_index,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
115 ptrdiff_t loc_advance,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
116 size_t index
891
49d8cff6f0ee make all function attributes leading - fixes #425
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
117 );
438
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
118
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
119 /**
480
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
120 * Finds the index of an element within a linked list.
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
121 *
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
122 * @param start a pointer to the start node
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
123 * @param loc_advance the location of the pointer to advance
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
124 * @param loc_data the location of the \c data pointer within your node struct
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
125 * @param cmp_func a compare function to compare \p elem against the node data
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
126 * @param elem a pointer to the element to find
699
35b2b99ee523 make list find return a negative value when elem not found
Mike Becker <universe@uap-core.de>
parents: 677
diff changeset
127 * @return the index of the element or a negative value if it could not be found
480
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
128 */
985
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
129 cx_attr_nonnull
699
35b2b99ee523 make list find return a negative value when elem not found
Mike Becker <universe@uap-core.de>
parents: 677
diff changeset
130 ssize_t cx_linked_list_find(
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 879
diff changeset
131 const void *start,
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
132 ptrdiff_t loc_advance,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
133 ptrdiff_t loc_data,
677
b09aae58bba4 refactoring of collections to make use of destructors in map implementations
Mike Becker <universe@uap-core.de>
parents: 670
diff changeset
134 cx_compare_func cmp_func,
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 879
diff changeset
135 const void *elem
891
49d8cff6f0ee make all function attributes leading - fixes #425
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
136 );
480
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
137
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
138 /**
764
ccbdbd088455 add cxListFindRemove and cx_linked_list_find_node
Mike Becker <universe@uap-core.de>
parents: 763
diff changeset
139 * Finds the node containing an element within a linked list.
ccbdbd088455 add cxListFindRemove and cx_linked_list_find_node
Mike Becker <universe@uap-core.de>
parents: 763
diff changeset
140 *
ccbdbd088455 add cxListFindRemove and cx_linked_list_find_node
Mike Becker <universe@uap-core.de>
parents: 763
diff changeset
141 * @param result a pointer to the memory where the node pointer (or \c NULL if the element
ccbdbd088455 add cxListFindRemove and cx_linked_list_find_node
Mike Becker <universe@uap-core.de>
parents: 763
diff changeset
142 * could not be found) shall be stored to
ccbdbd088455 add cxListFindRemove and cx_linked_list_find_node
Mike Becker <universe@uap-core.de>
parents: 763
diff changeset
143 * @param start a pointer to the start node
ccbdbd088455 add cxListFindRemove and cx_linked_list_find_node
Mike Becker <universe@uap-core.de>
parents: 763
diff changeset
144 * @param loc_advance the location of the pointer to advance
ccbdbd088455 add cxListFindRemove and cx_linked_list_find_node
Mike Becker <universe@uap-core.de>
parents: 763
diff changeset
145 * @param loc_data the location of the \c data pointer within your node struct
ccbdbd088455 add cxListFindRemove and cx_linked_list_find_node
Mike Becker <universe@uap-core.de>
parents: 763
diff changeset
146 * @param cmp_func a compare function to compare \p elem against the node data
ccbdbd088455 add cxListFindRemove and cx_linked_list_find_node
Mike Becker <universe@uap-core.de>
parents: 763
diff changeset
147 * @param elem a pointer to the element to find
ccbdbd088455 add cxListFindRemove and cx_linked_list_find_node
Mike Becker <universe@uap-core.de>
parents: 763
diff changeset
148 * @return the index of the element or a negative value if it could not be found
ccbdbd088455 add cxListFindRemove and cx_linked_list_find_node
Mike Becker <universe@uap-core.de>
parents: 763
diff changeset
149 */
985
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
150 cx_attr_nonnull
764
ccbdbd088455 add cxListFindRemove and cx_linked_list_find_node
Mike Becker <universe@uap-core.de>
parents: 763
diff changeset
151 ssize_t cx_linked_list_find_node(
ccbdbd088455 add cxListFindRemove and cx_linked_list_find_node
Mike Becker <universe@uap-core.de>
parents: 763
diff changeset
152 void **result,
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 879
diff changeset
153 const void *start,
764
ccbdbd088455 add cxListFindRemove and cx_linked_list_find_node
Mike Becker <universe@uap-core.de>
parents: 763
diff changeset
154 ptrdiff_t loc_advance,
ccbdbd088455 add cxListFindRemove and cx_linked_list_find_node
Mike Becker <universe@uap-core.de>
parents: 763
diff changeset
155 ptrdiff_t loc_data,
ccbdbd088455 add cxListFindRemove and cx_linked_list_find_node
Mike Becker <universe@uap-core.de>
parents: 763
diff changeset
156 cx_compare_func cmp_func,
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 879
diff changeset
157 const void *elem
891
49d8cff6f0ee make all function attributes leading - fixes #425
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
158 );
764
ccbdbd088455 add cxListFindRemove and cx_linked_list_find_node
Mike Becker <universe@uap-core.de>
parents: 763
diff changeset
159
ccbdbd088455 add cxListFindRemove and cx_linked_list_find_node
Mike Becker <universe@uap-core.de>
parents: 763
diff changeset
160 /**
475
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
161 * Finds the first node in a linked list.
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
162 *
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
163 * The function starts with the pointer denoted by \p node and traverses the list
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
164 * along a prev pointer whose location within the node struct is
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
165 * denoted by \p loc_prev.
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
166 *
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
167 * @param node a pointer to a node in the list
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
168 * @param loc_prev the location of the \c prev pointer
485
6a86ad3d8c03 use same doxygen style in all files
Mike Becker <universe@uap-core.de>
parents: 484
diff changeset
169 * @return a pointer to the first node
475
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
170 */
985
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
171 cx_attr_nonnull
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
172 cx_attr_returns_nonnull
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
173 void *cx_linked_list_first(
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 879
diff changeset
174 const void *node,
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
175 ptrdiff_t loc_prev
891
49d8cff6f0ee make all function attributes leading - fixes #425
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
176 );
475
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
177
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
178 /**
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
179 * Finds the last node in a linked list.
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
180 *
475
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
181 * The function starts with the pointer denoted by \p node and traverses the list
456
227c2eabbef8 change cx_linked_list_last() and add a test for it
Mike Becker <universe@uap-core.de>
parents: 453
diff changeset
182 * along a next pointer whose location within the node struct is
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
183 * denoted by \p loc_next.
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
184 *
475
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
185 * @param node a pointer to a node in the list
456
227c2eabbef8 change cx_linked_list_last() and add a test for it
Mike Becker <universe@uap-core.de>
parents: 453
diff changeset
186 * @param loc_next the location of the \c next pointer
478
599770bb6314 add more nonnull attributes
Mike Becker <universe@uap-core.de>
parents: 477
diff changeset
187 * @return a pointer to the last node
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
188 */
985
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
189 cx_attr_nonnull
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
190 cx_attr_returns_nonnull
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
191 void *cx_linked_list_last(
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 879
diff changeset
192 const void *node,
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
193 ptrdiff_t loc_next
891
49d8cff6f0ee make all function attributes leading - fixes #425
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
194 );
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
195
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
196 /**
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
197 * Finds the predecessor of a node in case it is not linked.
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
198 *
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
199 * \remark If \p node is not contained in the list starting with \p begin, the behavior is undefined.
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
200 *
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
201 * @param begin the node where to start the search
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
202 * @param loc_next the location of the \c next pointer
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
203 * @param node the successor of the node to find
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
204 * @return the node or \c NULL if \p node has no predecessor
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
205 */
985
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
206 cx_attr_nonnull
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
207 void *cx_linked_list_prev(
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 879
diff changeset
208 const void *begin,
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
209 ptrdiff_t loc_next,
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 879
diff changeset
210 const void *node
891
49d8cff6f0ee make all function attributes leading - fixes #425
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
211 );
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
212
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
213 /**
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
214 * Adds a new node to a linked list.
475
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
215 * The node must not be part of any list already.
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
216 *
478
599770bb6314 add more nonnull attributes
Mike Becker <universe@uap-core.de>
parents: 477
diff changeset
217 * \remark One of the pointers \p begin or \p end may be \c NULL, but not both.
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
218 *
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
219 * @param begin a pointer to the begin node pointer (if your list has one)
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
220 * @param end a pointer to the end node pointer (if your list has one)
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
221 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
222 * @param loc_next the location of a \c next pointer within your node struct (required)
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
223 * @param new_node a pointer to the node that shall be appended
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
224 */
985
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
225 cx_attr_nonnull_arg(5)
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
226 void cx_linked_list_add(
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
227 void **begin,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
228 void **end,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
229 ptrdiff_t loc_prev,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
230 ptrdiff_t loc_next,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
231 void *new_node
891
49d8cff6f0ee make all function attributes leading - fixes #425
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
232 );
406
9cbea761fbf7 adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents: 402
diff changeset
233
468
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
234 /**
475
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
235 * Prepends a new node to a linked list.
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
236 * The node must not be part of any list already.
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
237 *
478
599770bb6314 add more nonnull attributes
Mike Becker <universe@uap-core.de>
parents: 477
diff changeset
238 * \remark One of the pointers \p begin or \p end may be \c NULL, but not both.
475
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
239 *
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
240 * @param begin a pointer to the begin node pointer (if your list has one)
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
241 * @param end a pointer to the end node pointer (if your list has one)
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
242 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
243 * @param loc_next the location of a \c next pointer within your node struct (required)
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
244 * @param new_node a pointer to the node that shall be prepended
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
245 */
985
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
246 cx_attr_nonnull_arg(5)
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
247 void cx_linked_list_prepend(
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
248 void **begin,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
249 void **end,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
250 ptrdiff_t loc_prev,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
251 ptrdiff_t loc_next,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
252 void *new_node
891
49d8cff6f0ee make all function attributes leading - fixes #425
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
253 );
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
254
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
255 /**
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
256 * Links two nodes.
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
257 *
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
258 * @param left the new predecessor of \p right
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
259 * @param right the new successor of \p left
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
260 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
261 * @param loc_next the location of a \c next pointer within your node struct (required)
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
262 */
985
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
263 cx_attr_nonnull
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
264 void cx_linked_list_link(
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
265 void *left,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
266 void *right,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
267 ptrdiff_t loc_prev,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
268 ptrdiff_t loc_next
891
49d8cff6f0ee make all function attributes leading - fixes #425
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
269 );
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
270
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
271 /**
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
272 * Unlinks two nodes.
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
273 *
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
274 * If right is not the successor of left, the behavior is undefined.
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
275 *
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
276 * @param left the predecessor of \p right
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
277 * @param right the successor of \p left
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
278 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
279 * @param loc_next the location of a \c next pointer within your node struct (required)
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
280 */
985
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
281 cx_attr_nonnull
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
282 void cx_linked_list_unlink(
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
283 void *left,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
284 void *right,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
285 ptrdiff_t loc_prev,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
286 ptrdiff_t loc_next
891
49d8cff6f0ee make all function attributes leading - fixes #425
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
287 );
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
288
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
289 /**
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
290 * Inserts a new node after a given node of a linked list.
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
291 * The new node must not be part of any list already.
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
292 *
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
293 * \note If you specify \c NULL as the \p node to insert after, this function needs either the \p begin or
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
294 * the \p end pointer to determine the start of the list. Then the new node will be prepended to the list.
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
295 *
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
296 * @param begin a pointer to the begin node pointer (if your list has one)
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
297 * @param end a pointer to the end node pointer (if your list has one)
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
298 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
299 * @param loc_next the location of a \c next pointer within your node struct (required)
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
300 * @param node the node after which to insert (\c NULL if you want to prepend the node to the list)
878
1c1ee61c01f9 fix typo in documentation
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
301 * @param new_node a pointer to the node that shall be inserted
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
302 */
985
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
303 cx_attr_nonnull_arg(6)
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
304 void cx_linked_list_insert(
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
305 void **begin,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
306 void **end,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
307 ptrdiff_t loc_prev,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
308 ptrdiff_t loc_next,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
309 void *node,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
310 void *new_node
891
49d8cff6f0ee make all function attributes leading - fixes #425
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
311 );
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
312
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
313 /**
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
314 * Inserts a chain of nodes after a given node of a linked list.
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
315 * The chain must not be part of any list already.
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
316 *
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
317 * If you do not explicitly specify the end of the chain, it will be determined by traversing
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
318 * the \c next pointer.
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
319 *
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
320 * \note If you specify \c NULL as the \p node to insert after, this function needs either the \p begin or
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
321 * the \p end pointer to determine the start of the list. If only the \p end pointer is specified, you also need
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
322 * to provide a valid \p loc_prev location.
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
323 * Then the chain will be prepended to the list.
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
324 *
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
325 * @param begin a pointer to the begin node pointer (if your list has one)
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
326 * @param end a pointer to the end node pointer (if your list has one)
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
327 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
328 * @param loc_next the location of a \c next pointer within your node struct (required)
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
329 * @param node the node after which to insert (\c NULL to prepend the chain to the list)
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
330 * @param insert_begin a pointer to the first node of the chain that shall be inserted
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
331 * @param insert_end a pointer to the last node of the chain (or NULL if the last node shall be determined)
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
332 */
985
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
333 cx_attr_nonnull_arg(6)
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
334 void cx_linked_list_insert_chain(
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
335 void **begin,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
336 void **end,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
337 ptrdiff_t loc_prev,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
338 ptrdiff_t loc_next,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
339 void *node,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
340 void *insert_begin,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
341 void *insert_end
891
49d8cff6f0ee make all function attributes leading - fixes #425
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
342 );
475
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
343
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
344 /**
879
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
345 * Inserts a node into a sorted linked list.
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
346 * The new node must not be part of any list already.
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
347 *
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
348 * If the list starting with the node pointed to by \p begin is not sorted
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
349 * already, the behavior is undefined.
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
350 *
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
351 * @param begin a pointer to the begin node pointer (required)
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
352 * @param end a pointer to the end node pointer (if your list has one)
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
353 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
354 * @param loc_next the location of a \c next pointer within your node struct (required)
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
355 * @param new_node a pointer to the node that shall be inserted
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
356 * @param cmp_func a compare function that will receive the node pointers
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
357 */
985
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
358 cx_attr_nonnull_arg(1, 5, 6)
879
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
359 void cx_linked_list_insert_sorted(
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
360 void **begin,
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
361 void **end,
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
362 ptrdiff_t loc_prev,
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
363 ptrdiff_t loc_next,
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
364 void *new_node,
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
365 cx_compare_func cmp_func
891
49d8cff6f0ee make all function attributes leading - fixes #425
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
366 );
879
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
367
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
368 /**
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
369 * Inserts a chain of nodes into a sorted linked list.
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
370 * The chain must not be part of any list already.
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
371 *
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
372 * If either the list starting with the node pointed to by \p begin or the list
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
373 * starting with \p insert_begin is not sorted, the behavior is undefined.
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
374 *
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
375 * \attention In contrast to cx_linked_list_insert_chain(), the source chain
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
376 * will be broken and inserted into the target list so that the resulting list
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
377 * will be sorted according to \p cmp_func. That means, each node in the source
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
378 * chain may be re-linked with nodes from the target list.
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
379 *
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
380 * @param begin a pointer to the begin node pointer (required)
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
381 * @param end a pointer to the end node pointer (if your list has one)
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
382 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
383 * @param loc_next the location of a \c next pointer within your node struct (required)
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
384 * @param insert_begin a pointer to the first node of the chain that shall be inserted
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
385 * @param cmp_func a compare function that will receive the node pointers
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
386 */
985
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
387 cx_attr_nonnull_arg(1, 5, 6)
879
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
388 void cx_linked_list_insert_sorted_chain(
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
389 void **begin,
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
390 void **end,
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
391 ptrdiff_t loc_prev,
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
392 ptrdiff_t loc_next,
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
393 void *insert_begin,
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
394 cx_compare_func cmp_func
891
49d8cff6f0ee make all function attributes leading - fixes #425
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
395 );
879
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
396
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
397 /**
919
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
398 * Removes a chain of nodes from the linked list.
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
399 *
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
400 * If one of the nodes to remove is the begin (resp. end) node of the list and if \p begin (resp. \p end)
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
401 * addresses are provided, the pointers are adjusted accordingly.
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
402 *
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
403 * The following combinations of arguments are valid (more arguments are optional):
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
404 * \li \p loc_next and \p loc_prev (ancestor node is determined by using the prev pointer, overall O(1) performance)
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
405 * \li \p loc_next and \p begin (ancestor node is determined by list traversal, overall O(n) performance)
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
406 *
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
407 * \remark The \c next and \c prev pointers of the removed node are not cleared by this function and may still be used
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
408 * to traverse to a former adjacent node in the list, or within the chain.
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
409 *
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
410 * @param begin a pointer to the begin node pointer (optional)
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
411 * @param end a pointer to the end node pointer (optional)
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
412 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
413 * @param loc_next the location of a \c next pointer within your node struct (required)
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
414 * @param node the start node of the chain
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
415 * @param num the number of nodes to remove
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
416 * @return the actual number of nodes that were removed (may be less when the list did not have enough nodes)
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
417 */
985
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
418 cx_attr_nonnull_arg(5)
919
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
419 size_t cx_linked_list_remove_chain(
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
420 void **begin,
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
421 void **end,
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
422 ptrdiff_t loc_prev,
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
423 ptrdiff_t loc_next,
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
424 void *node,
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
425 size_t num
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
426 );
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
427
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
428 /**
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
429 * Removes a node from the linked list.
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
430 *
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
431 * If the node to remove is the begin (resp. end) node of the list and if \p begin (resp. \p end)
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
432 * addresses are provided, the pointers are adjusted accordingly.
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
433 *
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
434 * The following combinations of arguments are valid (more arguments are optional):
477
73a93c7a56ae add more explicit documentation to cx_linked_list_remove()
Mike Becker <universe@uap-core.de>
parents: 476
diff changeset
435 * \li \p loc_next and \p loc_prev (ancestor node is determined by using the prev pointer, overall O(1) performance)
73a93c7a56ae add more explicit documentation to cx_linked_list_remove()
Mike Becker <universe@uap-core.de>
parents: 476
diff changeset
436 * \li \p loc_next and \p begin (ancestor node is determined by list traversal, overall O(n) performance)
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
437 *
476
60ff4561dc04 change contract of cx_linked_list_remove()
Mike Becker <universe@uap-core.de>
parents: 475
diff changeset
438 * \remark The \c next and \c prev pointers of the removed node are not cleared by this function and may still be used
60ff4561dc04 change contract of cx_linked_list_remove()
Mike Becker <universe@uap-core.de>
parents: 475
diff changeset
439 * to traverse to a former adjacent node in the list.
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
440 *
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
441 * @param begin a pointer to the begin node pointer (optional)
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
442 * @param end a pointer to the end node pointer (optional)
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
443 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
444 * @param loc_next the location of a \c next pointer within your node struct (required)
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
445 * @param node the node to remove
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
446 */
985
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
447 cx_attr_nonnull_arg(5)
919
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
448 static inline void cx_linked_list_remove(
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
449 void **begin,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
450 void **end,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
451 ptrdiff_t loc_prev,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
452 ptrdiff_t loc_next,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
453 void *node
919
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
454 ) {
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
455 cx_linked_list_remove_chain(begin, end, loc_prev, loc_next, node, 1);
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
456 }
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
457
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
458 /**
468
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
459 * Determines the size of a linked list starting with \p node.
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
460 * @param node the first node
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
461 * @param loc_next the location of the \c next pointer within the node struct
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
462 * @return the size of the list or zero if \p node is \c NULL
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
463 */
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
464 size_t cx_linked_list_size(
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 879
diff changeset
465 const void *node,
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
466 ptrdiff_t loc_next
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
467 );
468
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
468
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
469 /**
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
470 * Sorts a linked list based on a comparison function.
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
471 *
639
309e8b08c60e temporarily remove pointer lists - see #234
Mike Becker <universe@uap-core.de>
parents: 629
diff changeset
472 * This function can work with linked lists of the following structure:
468
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
473 * \code
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
474 * typedef struct node node;
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
475 * struct node {
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
476 * node* prev;
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
477 * node* next;
639
309e8b08c60e temporarily remove pointer lists - see #234
Mike Becker <universe@uap-core.de>
parents: 629
diff changeset
478 * my_payload data;
468
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
479 * }
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
480 * \endcode
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
481 *
476
60ff4561dc04 change contract of cx_linked_list_remove()
Mike Becker <universe@uap-core.de>
parents: 475
diff changeset
482 * @note This is a recursive function with at most logarithmic recursion depth.
60ff4561dc04 change contract of cx_linked_list_remove()
Mike Becker <universe@uap-core.de>
parents: 475
diff changeset
483 *
468
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
484 * @param begin a pointer to the begin node pointer (required)
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
485 * @param end a pointer to the end node pointer (optional)
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
486 * @param loc_prev the location of a \c prev pointer within your node struct (negative if not present)
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
487 * @param loc_next the location of a \c next pointer within your node struct (required)
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
488 * @param loc_data the location of the \c data pointer within your node struct
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
489 * @param cmp_func the compare function defining the sort order
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
490 */
985
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
491 cx_attr_nonnull_arg(1, 6)
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
492 void cx_linked_list_sort(
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
493 void **begin,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
494 void **end,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
495 ptrdiff_t loc_prev,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
496 ptrdiff_t loc_next,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
497 ptrdiff_t loc_data,
677
b09aae58bba4 refactoring of collections to make use of destructors in map implementations
Mike Becker <universe@uap-core.de>
parents: 670
diff changeset
498 cx_compare_func cmp_func
891
49d8cff6f0ee make all function attributes leading - fixes #425
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
499 );
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
500
486
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 485
diff changeset
501
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 485
diff changeset
502 /**
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 485
diff changeset
503 * Compares two lists element wise.
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 485
diff changeset
504 *
488
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 487
diff changeset
505 * \note Both list must have the same structure.
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 487
diff changeset
506 *
486
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 485
diff changeset
507 * @param begin_left the begin of the left list (\c NULL denotes an empty list)
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 485
diff changeset
508 * @param begin_right the begin of the right list (\c NULL denotes an empty list)
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 485
diff changeset
509 * @param loc_advance the location of the pointer to advance
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 485
diff changeset
510 * @param loc_data the location of the \c data pointer within your node struct
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 485
diff changeset
511 * @param cmp_func the function to compare the elements
552
4373c2a90066 #178 fix that lists of different kind cannot be compared
Mike Becker <universe@uap-core.de>
parents: 528
diff changeset
512 * @return the first non-zero result of invoking \p cmp_func or: negative if the left list is smaller than the
4373c2a90066 #178 fix that lists of different kind cannot be compared
Mike Becker <universe@uap-core.de>
parents: 528
diff changeset
513 * right list, positive if the left list is larger than the right list, zero if both lists are equal.
486
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 485
diff changeset
514 */
985
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
515 cx_attr_nonnull_arg(5)
486
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 485
diff changeset
516 int cx_linked_list_compare(
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 879
diff changeset
517 const void *begin_left,
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 879
diff changeset
518 const void *begin_right,
486
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 485
diff changeset
519 ptrdiff_t loc_advance,
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 485
diff changeset
520 ptrdiff_t loc_data,
677
b09aae58bba4 refactoring of collections to make use of destructors in map implementations
Mike Becker <universe@uap-core.de>
parents: 670
diff changeset
521 cx_compare_func cmp_func
891
49d8cff6f0ee make all function attributes leading - fixes #425
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
522 );
486
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 485
diff changeset
523
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
524 /**
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
525 * Reverses the order of the nodes in a linked list.
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
526 *
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
527 * @param begin a pointer to the begin node pointer (required)
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
528 * @param end a pointer to the end node pointer (optional)
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
529 * @param loc_prev the location of a \c prev pointer within your node struct (negative if your struct does not have one)
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
530 * @param loc_next the location of a \c next pointer within your node struct (required)
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
531 */
985
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
532 cx_attr_nonnull_arg(1)
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
533 void cx_linked_list_reverse(
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
534 void **begin,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
535 void **end,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
536 ptrdiff_t loc_prev,
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
537 ptrdiff_t loc_next
891
49d8cff6f0ee make all function attributes leading - fixes #425
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
538 );
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
539
415
067aa769796a fix missing extern "C"
Mike Becker <universe@uap-core.de>
parents: 412
diff changeset
540 #ifdef __cplusplus
628
1e2be40f0cb5 use //-style single line comments everywhere
Mike Becker <universe@uap-core.de>
parents: 552
diff changeset
541 } // extern "C"
415
067aa769796a fix missing extern "C"
Mike Becker <universe@uap-core.de>
parents: 412
diff changeset
542 #endif
067aa769796a fix missing extern "C"
Mike Becker <universe@uap-core.de>
parents: 412
diff changeset
543
628
1e2be40f0cb5 use //-style single line comments everywhere
Mike Becker <universe@uap-core.de>
parents: 552
diff changeset
544 #endif // UCX_LINKED_LIST_H

mercurial