src/cx/linked_list.h

Thu, 16 Oct 2025 19:57:47 +0200

author
Mike Becker <universe@uap-core.de>
date
Thu, 16 Oct 2025 19:57:47 +0200
changeset 1426
3a89b31f0724
parent 1424
563033aa998c
permissions
-rw-r--r--

clean up header files and adds support for comparing arbitrary strings with string.h functions

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 /**
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
29 * @file linked_list.h
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
30 * @brief Linked list implementation.
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
31 * @author Mike Becker
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
32 * @author Olaf Wintermann
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
33 * @copyright 2-Clause BSD License
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
34 */
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
35
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
36 #ifndef UCX_LINKED_LIST_H
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
37 #define UCX_LINKED_LIST_H
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
38
484
9e6900b1cf9d add common.h include to all other header files
Mike Becker <universe@uap-core.de>
parents: 481
diff changeset
39 #include "common.h"
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
40 #include "list.h"
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
41
415
067aa769796a fix missing extern "C"
Mike Becker <universe@uap-core.de>
parents: 412
diff changeset
42 #ifdef __cplusplus
067aa769796a fix missing extern "C"
Mike Becker <universe@uap-core.de>
parents: 412
diff changeset
43 extern "C" {
067aa769796a fix missing extern "C"
Mike Becker <universe@uap-core.de>
parents: 412
diff changeset
44 #endif
067aa769796a fix missing extern "C"
Mike Becker <universe@uap-core.de>
parents: 412
diff changeset
45
466
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 456
diff changeset
46 /**
1424
563033aa998c fixes tons of typos and grammar issues across the documentation - fixes #667
Mike Becker <universe@uap-core.de>
parents: 1423
diff changeset
47 * Metadata for a linked list.
1367
6b3d52dd176e change linked_list.c to allow custom data in nodes + implement cx_kv_list_set_key()
Mike Becker <universe@uap-core.de>
parents: 1318
diff changeset
48 */
6b3d52dd176e change linked_list.c to allow custom data in nodes + implement cx_kv_list_set_key()
Mike Becker <universe@uap-core.de>
parents: 1318
diff changeset
49 typedef struct cx_linked_list_s {
6b3d52dd176e change linked_list.c to allow custom data in nodes + implement cx_kv_list_set_key()
Mike Becker <universe@uap-core.de>
parents: 1318
diff changeset
50 /** Base members. */
6b3d52dd176e change linked_list.c to allow custom data in nodes + implement cx_kv_list_set_key()
Mike Becker <universe@uap-core.de>
parents: 1318
diff changeset
51 struct cx_list_s base;
6b3d52dd176e change linked_list.c to allow custom data in nodes + implement cx_kv_list_set_key()
Mike Becker <universe@uap-core.de>
parents: 1318
diff changeset
52 /**
6b3d52dd176e change linked_list.c to allow custom data in nodes + implement cx_kv_list_set_key()
Mike Becker <universe@uap-core.de>
parents: 1318
diff changeset
53 * Location of the prev pointer (mandatory).
6b3d52dd176e change linked_list.c to allow custom data in nodes + implement cx_kv_list_set_key()
Mike Becker <universe@uap-core.de>
parents: 1318
diff changeset
54 */
6b3d52dd176e change linked_list.c to allow custom data in nodes + implement cx_kv_list_set_key()
Mike Becker <universe@uap-core.de>
parents: 1318
diff changeset
55 off_t loc_prev;
6b3d52dd176e change linked_list.c to allow custom data in nodes + implement cx_kv_list_set_key()
Mike Becker <universe@uap-core.de>
parents: 1318
diff changeset
56 /**
6b3d52dd176e change linked_list.c to allow custom data in nodes + implement cx_kv_list_set_key()
Mike Becker <universe@uap-core.de>
parents: 1318
diff changeset
57 * Location of the next pointer (mandatory).
6b3d52dd176e change linked_list.c to allow custom data in nodes + implement cx_kv_list_set_key()
Mike Becker <universe@uap-core.de>
parents: 1318
diff changeset
58 */
6b3d52dd176e change linked_list.c to allow custom data in nodes + implement cx_kv_list_set_key()
Mike Becker <universe@uap-core.de>
parents: 1318
diff changeset
59 off_t loc_next;
6b3d52dd176e change linked_list.c to allow custom data in nodes + implement cx_kv_list_set_key()
Mike Becker <universe@uap-core.de>
parents: 1318
diff changeset
60 /**
6b3d52dd176e change linked_list.c to allow custom data in nodes + implement cx_kv_list_set_key()
Mike Becker <universe@uap-core.de>
parents: 1318
diff changeset
61 * Location of the payload (mandatory).
6b3d52dd176e change linked_list.c to allow custom data in nodes + implement cx_kv_list_set_key()
Mike Becker <universe@uap-core.de>
parents: 1318
diff changeset
62 */
6b3d52dd176e change linked_list.c to allow custom data in nodes + implement cx_kv_list_set_key()
Mike Becker <universe@uap-core.de>
parents: 1318
diff changeset
63 off_t loc_data;
6b3d52dd176e change linked_list.c to allow custom data in nodes + implement cx_kv_list_set_key()
Mike Becker <universe@uap-core.de>
parents: 1318
diff changeset
64 /**
6b3d52dd176e change linked_list.c to allow custom data in nodes + implement cx_kv_list_set_key()
Mike Becker <universe@uap-core.de>
parents: 1318
diff changeset
65 * Additional bytes to allocate @em behind the payload (e.g. for metadata).
6b3d52dd176e change linked_list.c to allow custom data in nodes + implement cx_kv_list_set_key()
Mike Becker <universe@uap-core.de>
parents: 1318
diff changeset
66 */
6b3d52dd176e change linked_list.c to allow custom data in nodes + implement cx_kv_list_set_key()
Mike Becker <universe@uap-core.de>
parents: 1318
diff changeset
67 size_t extra_data_len;
6b3d52dd176e change linked_list.c to allow custom data in nodes + implement cx_kv_list_set_key()
Mike Becker <universe@uap-core.de>
parents: 1318
diff changeset
68 /**
6b3d52dd176e change linked_list.c to allow custom data in nodes + implement cx_kv_list_set_key()
Mike Becker <universe@uap-core.de>
parents: 1318
diff changeset
69 * Pointer to the first node.
6b3d52dd176e change linked_list.c to allow custom data in nodes + implement cx_kv_list_set_key()
Mike Becker <universe@uap-core.de>
parents: 1318
diff changeset
70 */
6b3d52dd176e change linked_list.c to allow custom data in nodes + implement cx_kv_list_set_key()
Mike Becker <universe@uap-core.de>
parents: 1318
diff changeset
71 void *begin;
6b3d52dd176e change linked_list.c to allow custom data in nodes + implement cx_kv_list_set_key()
Mike Becker <universe@uap-core.de>
parents: 1318
diff changeset
72 /**
6b3d52dd176e change linked_list.c to allow custom data in nodes + implement cx_kv_list_set_key()
Mike Becker <universe@uap-core.de>
parents: 1318
diff changeset
73 * Pointer to the last node.
6b3d52dd176e change linked_list.c to allow custom data in nodes + implement cx_kv_list_set_key()
Mike Becker <universe@uap-core.de>
parents: 1318
diff changeset
74 */
6b3d52dd176e change linked_list.c to allow custom data in nodes + implement cx_kv_list_set_key()
Mike Becker <universe@uap-core.de>
parents: 1318
diff changeset
75 void *end;
6b3d52dd176e change linked_list.c to allow custom data in nodes + implement cx_kv_list_set_key()
Mike Becker <universe@uap-core.de>
parents: 1318
diff changeset
76 } cx_linked_list;
6b3d52dd176e change linked_list.c to allow custom data in nodes + implement cx_kv_list_set_key()
Mike Becker <universe@uap-core.de>
parents: 1318
diff changeset
77
6b3d52dd176e change linked_list.c to allow custom data in nodes + implement cx_kv_list_set_key()
Mike Becker <universe@uap-core.de>
parents: 1318
diff changeset
78 /**
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
79 * 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
80 *
1111
78eeeb950883 remove API for changing the store_pointer property after list creation
Mike Becker <universe@uap-core.de>
parents: 1100
diff changeset
81 * If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of
1424
563033aa998c fixes tons of typos and grammar issues across the documentation - fixes #667
Mike Becker <universe@uap-core.de>
parents: 1423
diff changeset
82 * copies of the added elements, and the compare function will be automatically set
563033aa998c fixes tons of typos and grammar issues across the documentation - fixes #667
Mike Becker <universe@uap-core.de>
parents: 1423
diff changeset
83 * 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
84 *
466
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 456
diff changeset
85 * @param allocator the allocator for allocating the list nodes
1318
12fa1d37fe48 allow changing the cxDefaultAllocator - resolves #669
Mike Becker <universe@uap-core.de>
parents: 1241
diff changeset
86 * (if @c NULL, the cxDefaultAllocator will be used)
466
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 456
diff changeset
87 * @param comparator the comparator for the elements
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
88 * (if @c NULL, and the list is not storing pointers, sort and find
763
741a2040fa33 make cx_cmp_ptr default comparator for pointer lists - relates to #340
Mike Becker <universe@uap-core.de>
parents: 759
diff changeset
89 * 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
90 * @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
91 * @return the created list
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 456
diff changeset
92 */
1426
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
93 cx_attr_nodiscard cx_attr_malloc cx_attr_dealloc(cxListFree, 1)
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
94 CX_EXPORT CxList *cxLinkedListCreate(const CxAllocator *allocator,
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
95 cx_compare_func comparator, size_t elem_size);
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
96
466
28bc3e10ac28 add special linked list implementation for storing pointers
Mike Becker <universe@uap-core.de>
parents: 456
diff changeset
97 /**
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
98 * 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
99 *
d0d95740071b add simple functions for creating lists
Mike Becker <universe@uap-core.de>
parents: 647
diff changeset
100 * 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
101 * 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
102 * after list creation or use cxLinkedListCreate().
d0d95740071b add simple functions for creating lists
Mike Becker <universe@uap-core.de>
parents: 647
diff changeset
103 *
1111
78eeeb950883 remove API for changing the store_pointer property after list creation
Mike Becker <universe@uap-core.de>
parents: 1100
diff changeset
104 * If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of
1424
563033aa998c fixes tons of typos and grammar issues across the documentation - fixes #667
Mike Becker <universe@uap-core.de>
parents: 1423
diff changeset
105 * copies of the added elements, and the compare function will be automatically set
1239
b4b1f15d1866 complete more than 80% of the list.h documentation
Mike Becker <universe@uap-core.de>
parents: 1180
diff changeset
106 * 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
107 *
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
108 * @param elem_size (@c size_t) the size of each element in bytes
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
109 * @return (@c CxList*) the created list
662
d0d95740071b add simple functions for creating lists
Mike Becker <universe@uap-core.de>
parents: 647
diff changeset
110 */
855
35bcb3216c0d fix inconsistent use of item_size and elem_size
Mike Becker <universe@uap-core.de>
parents: 807
diff changeset
111 #define cxLinkedListCreateSimple(elem_size) \
1426
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
112 cxLinkedListCreate(NULL, NULL, elem_size)
662
d0d95740071b add simple functions for creating lists
Mike Becker <universe@uap-core.de>
parents: 647
diff changeset
113
d0d95740071b add simple functions for creating lists
Mike Becker <universe@uap-core.de>
parents: 647
diff changeset
114 /**
438
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
115 * Finds the node at a certain index.
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
116 *
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
117 * This function can be used to start at an arbitrary position within the list.
1424
563033aa998c fixes tons of typos and grammar issues across the documentation - fixes #667
Mike Becker <universe@uap-core.de>
parents: 1423
diff changeset
118 * If the search index is larger than the start index, @p loc_advance must denote
563033aa998c fixes tons of typos and grammar issues across the documentation - fixes #667
Mike Becker <universe@uap-core.de>
parents: 1423
diff changeset
119 * the location of a @c next pointer (i.e., a pointer to the next node).
438
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
120 * But it is also possible that the search index is smaller than the start index
1424
563033aa998c fixes tons of typos and grammar issues across the documentation - fixes #667
Mike Becker <universe@uap-core.de>
parents: 1423
diff changeset
121 * (e.g., in cases where traversing a list backwards is faster).
563033aa998c fixes tons of typos and grammar issues across the documentation - fixes #667
Mike Becker <universe@uap-core.de>
parents: 1423
diff changeset
122 * In that case @p loc_advance must denote the location of a @c prev pointer
563033aa998c fixes tons of typos and grammar issues across the documentation - fixes #667
Mike Becker <universe@uap-core.de>
parents: 1423
diff changeset
123 * (i.e., a pointer to the previous node).
438
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
124 *
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
125 * @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
126 * @param start_index the start index
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
127 * @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
128 * @param index the search index
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
129 * @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
130 */
1426
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
131 cx_attr_nonnull cx_attr_nodiscard
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
132 CX_EXPORT void *cx_linked_list_at(const void *start,size_t start_index,
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
133 ptrdiff_t loc_advance, size_t index);
438
cd3069757010 add function cx_linked_list_at()
Mike Becker <universe@uap-core.de>
parents: 415
diff changeset
134
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
135 /**
1162
e3bb67b72d33 remove dependency to ssize_t - fixes #552
Mike Becker <universe@uap-core.de>
parents: 1113
diff changeset
136 * Finds the node containing an element within a linked list.
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 * @param start a pointer to the start node
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
139 * @param loc_advance the location of the pointer to advance
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
140 * @param loc_data the location of the @c data pointer within your node struct
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
141 * @param cmp_func a compare function to compare @p elem against the node data
480
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
142 * @param elem a pointer to the element to find
1162
e3bb67b72d33 remove dependency to ssize_t - fixes #552
Mike Becker <universe@uap-core.de>
parents: 1113
diff changeset
143 * @param found_index an optional pointer where the index of the found node
e3bb67b72d33 remove dependency to ssize_t - fixes #552
Mike Becker <universe@uap-core.de>
parents: 1113
diff changeset
144 * (given that @p start has index 0) is stored
1374
4dceda670b05 fix documentation of return value of cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 1367
diff changeset
145 * @return a pointer to the found node or @c NULL if no matching node was found
480
e3be53a3354f add cx_linked_list_find()
Mike Becker <universe@uap-core.de>
parents: 478
diff changeset
146 */
1162
e3bb67b72d33 remove dependency to ssize_t - fixes #552
Mike Becker <universe@uap-core.de>
parents: 1113
diff changeset
147 cx_attr_nonnull_arg(1, 4, 5)
1426
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
148 CX_EXPORT void *cx_linked_list_find(const void *start, ptrdiff_t loc_advance,
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
149 ptrdiff_t loc_data, cx_compare_func cmp_func, const void *elem,
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
150 size_t *found_index);
764
ccbdbd088455 add cxListFindRemove and cx_linked_list_find_node
Mike Becker <universe@uap-core.de>
parents: 763
diff changeset
151
ccbdbd088455 add cxListFindRemove and cx_linked_list_find_node
Mike Becker <universe@uap-core.de>
parents: 763
diff changeset
152 /**
475
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
153 * 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
154 *
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
155 * The function starts with the pointer denoted by @p node and traverses the list
475
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
156 * along a prev pointer whose location within the node struct is
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
157 * denoted by @p loc_prev.
475
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
158 *
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
159 * @param node a pointer to a node in the list
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
160 * @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
161 * @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
162 */
1426
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
163 cx_attr_nonnull cx_attr_returns_nonnull
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
164 CX_EXPORT void *cx_linked_list_first(const void *node, ptrdiff_t loc_prev);
475
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
165
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
166 /**
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
167 * 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
168 *
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
169 * 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
170 * along a next pointer whose location within the node struct is
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
171 * denoted by @p loc_next.
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
172 *
475
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
173 * @param node a pointer to a node in the list
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
174 * @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
175 * @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
176 */
1426
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
177 cx_attr_nonnull cx_attr_returns_nonnull
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
178 CX_EXPORT void *cx_linked_list_last(const void *node, ptrdiff_t loc_next);
398
8d506ed6c1c0 adds first draft for linked list implementation
Mike Becker <universe@uap-core.de>
parents:
diff changeset
179
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
180 /**
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
181 * 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
182 *
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
183 * @remark If @p node is not contained in the list starting with @p begin, the behavior is undefined.
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
184 *
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
185 * @param begin the node where to start the search
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
186 * @param loc_next the location of the @c next pointer
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
187 * @param node the successor of the node to find
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
188 * @return the node or @c NULL if @p node has no predecessor
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
189 */
985
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
190 cx_attr_nonnull
1426
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
191 CX_EXPORT void *cx_linked_list_prev(const void *begin, ptrdiff_t loc_next, const void *node);
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
192
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
193 /**
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
194 * Adds a new node to a linked list.
1424
563033aa998c fixes tons of typos and grammar issues across the documentation - fixes #667
Mike Becker <universe@uap-core.de>
parents: 1423
diff changeset
195 * The node must not be part of any list yet.
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
196 *
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
197 * @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
198 *
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
199 * @param begin a pointer to the beginning node pointer (if your list has one)
453
bb144d08cd44 add some documentation and changes some signatures
Mike Becker <universe@uap-core.de>
parents: 438
diff changeset
200 * @param end a pointer to the end node pointer (if your list has one)
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
201 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
202 * @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
203 * @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
204 */
985
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
205 cx_attr_nonnull_arg(5)
1426
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
206 CX_EXPORT void cx_linked_list_add(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node);
406
9cbea761fbf7 adds cxLinkedListWrap and cxLinkedListRecalculateSize
Mike Becker <universe@uap-core.de>
parents: 402
diff changeset
207
468
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
208 /**
475
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
209 * Prepends a new node to a linked list.
1424
563033aa998c fixes tons of typos and grammar issues across the documentation - fixes #667
Mike Becker <universe@uap-core.de>
parents: 1423
diff changeset
210 * The node must not be part of any list yet.
475
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
211 *
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
212 * @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
213 *
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
214 * @param begin a pointer to the beginning node pointer (if your list has one)
475
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
215 * @param end a pointer to the end node pointer (if your list has one)
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
216 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
217 * @param loc_next the location of a @c next pointer within your node struct (required)
475
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
218 * @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
219 */
985
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
220 cx_attr_nonnull_arg(5)
1426
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
221 CX_EXPORT void cx_linked_list_prepend(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node);
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
222
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
223 /**
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
224 * Links two nodes.
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
225 *
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
226 * @param left the new predecessor of @p right
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
227 * @param right the new successor of @p left
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
228 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
229 * @param loc_next the location of a @c next pointer within your node struct (required)
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
230 */
985
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
231 cx_attr_nonnull
1426
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
232 CX_EXPORT void cx_linked_list_link(void *left, void *right, ptrdiff_t loc_prev, ptrdiff_t loc_next);
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
233
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
234 /**
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
235 * Unlinks two nodes.
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
236 *
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
237 * 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
238 *
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
239 * @param left the predecessor of @p right
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
240 * @param right the successor of @p left
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
241 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
242 * @param loc_next the location of a @c next pointer within your node struct (required)
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
243 */
985
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
244 cx_attr_nonnull
1426
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
245 CX_EXPORT void cx_linked_list_unlink(void *left, void *right, ptrdiff_t loc_prev, ptrdiff_t loc_next);
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
246
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
247 /**
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
248 * Inserts a new node after a given node of a linked list.
1424
563033aa998c fixes tons of typos and grammar issues across the documentation - fixes #667
Mike Becker <universe@uap-core.de>
parents: 1423
diff changeset
249 * The new node must not be part of any list yet.
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
250 *
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
251 * @note If you specify @c NULL as the @p node to insert after, this function needs either the @p begin or
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
252 * the @p end pointer to determine the start of the list. Then the new node will be prepended to the list.
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
253 *
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
254 * @param begin a pointer to the beginning node pointer (if your list has one)
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
255 * @param end a pointer to the end node pointer (if your list has one)
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
256 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
257 * @param loc_next the location of a @c next pointer within your node struct (required)
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
258 * @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
259 * @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
260 */
985
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
261 cx_attr_nonnull_arg(6)
1426
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
262 CX_EXPORT void cx_linked_list_insert(void **begin, void **end,
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
263 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node, void *new_node);
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
264
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
265 /**
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
266 * Inserts a chain of nodes after a given node of a linked list.
1424
563033aa998c fixes tons of typos and grammar issues across the documentation - fixes #667
Mike Becker <universe@uap-core.de>
parents: 1423
diff changeset
267 * The chain must not be part of any list yet.
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
268 *
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
269 * If you do not explicitly specify the end of the chain, it will be determined by traversing
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
270 * the @c next pointer.
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
271 *
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
272 * @note If you specify @c NULL as the @p node to insert after, this function needs either the @p begin or
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
273 * the @p end pointer to determine the start of the list. If only the @p end pointer is specified, you also need
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
274 * to provide a valid @p loc_prev location.
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
275 * 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
276 *
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
277 * @param begin a pointer to the beginning node pointer (if your list has one)
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
278 * @param end a pointer to the end node pointer (if your list has one)
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
279 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
280 * @param loc_next the location of a @c next pointer within your node struct (required)
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
281 * @param node the node after which to insert (@c NULL to prepend the chain to the list)
481
eef025d82a34 add several new linked list functions
Mike Becker <universe@uap-core.de>
parents: 480
diff changeset
282 * @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
283 * @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
284 */
985
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
285 cx_attr_nonnull_arg(6)
1426
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
286 CX_EXPORT void cx_linked_list_insert_chain(void **begin, void **end,
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
287 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node, void *insert_begin, void *insert_end);
475
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
288
31bf97fdbf71 add cx_linked_list_first() + cx_linked_list_prepend()
Mike Becker <universe@uap-core.de>
parents: 473
diff changeset
289 /**
879
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
290 * Inserts a node into a sorted linked list.
1424
563033aa998c fixes tons of typos and grammar issues across the documentation - fixes #667
Mike Becker <universe@uap-core.de>
parents: 1423
diff changeset
291 * The new node must not be part of any list yet.
879
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
292 *
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
293 * If the list starting with the node pointed to by @p begin is not sorted
879
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
294 * 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
295 *
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
296 * @param begin a pointer to the beginning node pointer (required)
879
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
297 * @param end a pointer to the end node pointer (if your list has one)
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
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)
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
299 * @param loc_next the location of a @c next pointer within your node struct (required)
879
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
300 * @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
301 * @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
302 */
985
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
303 cx_attr_nonnull_arg(1, 5, 6)
1426
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
304 CX_EXPORT void cx_linked_list_insert_sorted(void **begin, void **end,
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
305 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node, cx_compare_func cmp_func);
879
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
306
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
307 /**
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
308 * Inserts a chain of nodes into a sorted linked list.
1419
e46406fd1b3c add functions to insert elements into lists/arrays without duplicates - resolves #557
Mike Becker <universe@uap-core.de>
parents: 1374
diff changeset
309 * The chain must not be part of any list yet.
879
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
310 *
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
311 * If either the list starting with the node pointed to by @p begin or the list
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
312 * starting with @p insert_begin is not sorted, the behavior is undefined.
879
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
313 *
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
314 * @attention In contrast to cx_linked_list_insert_chain(), the source chain
879
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
315 * will be broken and inserted into the target list so that the resulting list
1424
563033aa998c fixes tons of typos and grammar issues across the documentation - fixes #667
Mike Becker <universe@uap-core.de>
parents: 1423
diff changeset
316 * will be sorted according to @p cmp_func. That means each node in the source
879
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
317 * 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
318 *
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
319 * @param begin a pointer to the beginning node pointer (required)
879
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
320 * @param end a pointer to the end node pointer (if your list has one)
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
321 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
322 * @param loc_next the location of a @c next pointer within your node struct (required)
879
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
323 * @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
324 * @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
325 */
985
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
326 cx_attr_nonnull_arg(1, 5, 6)
1426
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
327 CX_EXPORT void cx_linked_list_insert_sorted_chain(void **begin, void **end,
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
328 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *insert_begin, cx_compare_func cmp_func);
879
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
329
9c24a4eb5ac9 implement optimized sorted insert for linked lists - resolves #415
Mike Becker <universe@uap-core.de>
parents: 878
diff changeset
330 /**
1419
e46406fd1b3c add functions to insert elements into lists/arrays without duplicates - resolves #557
Mike Becker <universe@uap-core.de>
parents: 1374
diff changeset
331 * Inserts a node into a sorted linked list if no other node with the same value already exists.
e46406fd1b3c add functions to insert elements into lists/arrays without duplicates - resolves #557
Mike Becker <universe@uap-core.de>
parents: 1374
diff changeset
332 * The new node must not be part of any list yet.
e46406fd1b3c add functions to insert elements into lists/arrays without duplicates - resolves #557
Mike Becker <universe@uap-core.de>
parents: 1374
diff changeset
333 *
e46406fd1b3c add functions to insert elements into lists/arrays without duplicates - resolves #557
Mike Becker <universe@uap-core.de>
parents: 1374
diff changeset
334 * If the list starting with the node pointed to by @p begin is not sorted
e46406fd1b3c add functions to insert elements into lists/arrays without duplicates - resolves #557
Mike Becker <universe@uap-core.de>
parents: 1374
diff changeset
335 * already, the behavior is undefined.
e46406fd1b3c add functions to insert elements into lists/arrays without duplicates - resolves #557
Mike Becker <universe@uap-core.de>
parents: 1374
diff changeset
336 *
e46406fd1b3c add functions to insert elements into lists/arrays without duplicates - resolves #557
Mike Becker <universe@uap-core.de>
parents: 1374
diff changeset
337 * @param begin a pointer to the beginning node pointer (required)
e46406fd1b3c add functions to insert elements into lists/arrays without duplicates - resolves #557
Mike Becker <universe@uap-core.de>
parents: 1374
diff changeset
338 * @param end a pointer to the end node pointer (if your list has one)
e46406fd1b3c add functions to insert elements into lists/arrays without duplicates - resolves #557
Mike Becker <universe@uap-core.de>
parents: 1374
diff changeset
339 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
e46406fd1b3c add functions to insert elements into lists/arrays without duplicates - resolves #557
Mike Becker <universe@uap-core.de>
parents: 1374
diff changeset
340 * @param loc_next the location of a @c next pointer within your node struct (required)
e46406fd1b3c add functions to insert elements into lists/arrays without duplicates - resolves #557
Mike Becker <universe@uap-core.de>
parents: 1374
diff changeset
341 * @param new_node a pointer to the node that shall be inserted
e46406fd1b3c add functions to insert elements into lists/arrays without duplicates - resolves #557
Mike Becker <universe@uap-core.de>
parents: 1374
diff changeset
342 * @param cmp_func a compare function that will receive the node pointers
e46406fd1b3c add functions to insert elements into lists/arrays without duplicates - resolves #557
Mike Becker <universe@uap-core.de>
parents: 1374
diff changeset
343 * @retval zero when the node was inserted
e46406fd1b3c add functions to insert elements into lists/arrays without duplicates - resolves #557
Mike Becker <universe@uap-core.de>
parents: 1374
diff changeset
344 * @retval non-zero when a node with the same value already exists
e46406fd1b3c add functions to insert elements into lists/arrays without duplicates - resolves #557
Mike Becker <universe@uap-core.de>
parents: 1374
diff changeset
345 */
e46406fd1b3c add functions to insert elements into lists/arrays without duplicates - resolves #557
Mike Becker <universe@uap-core.de>
parents: 1374
diff changeset
346 cx_attr_nonnull_arg(1, 5, 6)
1426
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
347 CX_EXPORT int cx_linked_list_insert_unique(void **begin, void **end,
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
348 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node, cx_compare_func cmp_func);
1419
e46406fd1b3c add functions to insert elements into lists/arrays without duplicates - resolves #557
Mike Becker <universe@uap-core.de>
parents: 1374
diff changeset
349
e46406fd1b3c add functions to insert elements into lists/arrays without duplicates - resolves #557
Mike Becker <universe@uap-core.de>
parents: 1374
diff changeset
350 /**
e46406fd1b3c add functions to insert elements into lists/arrays without duplicates - resolves #557
Mike Becker <universe@uap-core.de>
parents: 1374
diff changeset
351 * Inserts a chain of nodes into a sorted linked list, avoiding duplicates.
e46406fd1b3c add functions to insert elements into lists/arrays without duplicates - resolves #557
Mike Becker <universe@uap-core.de>
parents: 1374
diff changeset
352 * The chain must not be part of any list yet.
e46406fd1b3c add functions to insert elements into lists/arrays without duplicates - resolves #557
Mike Becker <universe@uap-core.de>
parents: 1374
diff changeset
353 *
e46406fd1b3c add functions to insert elements into lists/arrays without duplicates - resolves #557
Mike Becker <universe@uap-core.de>
parents: 1374
diff changeset
354 * If either the list starting with the node pointed to by @p begin or the list
e46406fd1b3c add functions to insert elements into lists/arrays without duplicates - resolves #557
Mike Becker <universe@uap-core.de>
parents: 1374
diff changeset
355 * starting with @p insert_begin is not sorted, the behavior is undefined.
e46406fd1b3c add functions to insert elements into lists/arrays without duplicates - resolves #557
Mike Becker <universe@uap-core.de>
parents: 1374
diff changeset
356 *
e46406fd1b3c add functions to insert elements into lists/arrays without duplicates - resolves #557
Mike Becker <universe@uap-core.de>
parents: 1374
diff changeset
357 * @attention In contrast to cx_linked_list_insert_sorted(), not all nodes of the
e46406fd1b3c add functions to insert elements into lists/arrays without duplicates - resolves #557
Mike Becker <universe@uap-core.de>
parents: 1374
diff changeset
358 * chain might be added. This function returns a new chain consisting of all the duplicates.
e46406fd1b3c add functions to insert elements into lists/arrays without duplicates - resolves #557
Mike Becker <universe@uap-core.de>
parents: 1374
diff changeset
359 *
e46406fd1b3c add functions to insert elements into lists/arrays without duplicates - resolves #557
Mike Becker <universe@uap-core.de>
parents: 1374
diff changeset
360 * @param begin a pointer to the beginning node pointer (required)
e46406fd1b3c add functions to insert elements into lists/arrays without duplicates - resolves #557
Mike Becker <universe@uap-core.de>
parents: 1374
diff changeset
361 * @param end a pointer to the end node pointer (if your list has one)
e46406fd1b3c add functions to insert elements into lists/arrays without duplicates - resolves #557
Mike Becker <universe@uap-core.de>
parents: 1374
diff changeset
362 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
e46406fd1b3c add functions to insert elements into lists/arrays without duplicates - resolves #557
Mike Becker <universe@uap-core.de>
parents: 1374
diff changeset
363 * @param loc_next the location of a @c next pointer within your node struct (required)
e46406fd1b3c add functions to insert elements into lists/arrays without duplicates - resolves #557
Mike Becker <universe@uap-core.de>
parents: 1374
diff changeset
364 * @param insert_begin a pointer to the first node of the chain that shall be inserted
e46406fd1b3c add functions to insert elements into lists/arrays without duplicates - resolves #557
Mike Becker <universe@uap-core.de>
parents: 1374
diff changeset
365 * @param cmp_func a compare function that will receive the node pointers
1423
9a72258446cd fixes various bugs related to skipping duplicates in insert_unique - relates to #557
Mike Becker <universe@uap-core.de>
parents: 1419
diff changeset
366 * @return a pointer to a new chain with all duplicates that were not inserted (or @c NULL when there were no duplicates)
1419
e46406fd1b3c add functions to insert elements into lists/arrays without duplicates - resolves #557
Mike Becker <universe@uap-core.de>
parents: 1374
diff changeset
367 */
1426
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
368 cx_attr_nonnull_arg(1, 5, 6) cx_attr_nodiscard
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
369 CX_EXPORT void *cx_linked_list_insert_unique_chain(void **begin, void **end,
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
370 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *insert_begin, cx_compare_func cmp_func);
1419
e46406fd1b3c add functions to insert elements into lists/arrays without duplicates - resolves #557
Mike Becker <universe@uap-core.de>
parents: 1374
diff changeset
371
e46406fd1b3c add functions to insert elements into lists/arrays without duplicates - resolves #557
Mike Becker <universe@uap-core.de>
parents: 1374
diff changeset
372 /**
919
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
373 * 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
374 *
1424
563033aa998c fixes tons of typos and grammar issues across the documentation - fixes #667
Mike Becker <universe@uap-core.de>
parents: 1423
diff changeset
375 * If one of the nodes to remove is the beginning (resp. end) node of the list, and if @p begin (resp. @p end)
919
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
376 * 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
377 *
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
378 * The following combinations of arguments are valid (more arguments are optional):
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
379 * @li @p loc_next and @p loc_prev (ancestor node is determined by using the prev pointer, overall O(1) performance)
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
380 * @li @p loc_next and @p begin (ancestor node is determined by list traversal, overall O(n) performance)
919
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
381 *
1241
ebcc08023c33 complete linked_list.h docu
Mike Becker <universe@uap-core.de>
parents: 1239
diff changeset
382 * @remark The @c next and @c prev pointers of the removed chain are not cleared by this function and may still be used
919
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
383 * 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
384 *
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
385 * @param begin a pointer to the beginning node pointer (optional)
919
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
386 * @param end a pointer to the end node pointer (optional)
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
387 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
388 * @param loc_next the location of a @c next pointer within your node struct (required)
919
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
389 * @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
390 * @param num the number of nodes to remove
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
391 * @return the actual number of nodes that were removed (can be less when the list did not have enough nodes)
919
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
392 */
985
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
393 cx_attr_nonnull_arg(5)
1426
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
394 CX_EXPORT size_t cx_linked_list_remove_chain(void **begin, void **end,
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
395 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node, size_t num);
919
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
396
75da57d4634e add possibility to remove arrays of data and retrieve removed data
Mike Becker <universe@uap-core.de>
parents: 891
diff changeset
397 /**
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
398 * 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
399 *
1424
563033aa998c fixes tons of typos and grammar issues across the documentation - fixes #667
Mike Becker <universe@uap-core.de>
parents: 1423
diff changeset
400 * If the node to remove is the beginning (resp. end) node of the list, and if @p begin (resp. @p end)
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
401 * 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
402 *
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
403 * The following combinations of arguments are valid (more arguments are optional):
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
404 * @li @p loc_next and @p loc_prev (ancestor node is determined by using the prev pointer, overall O(1) performance)
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
405 * @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
406 *
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
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
476
60ff4561dc04 change contract of cx_linked_list_remove()
Mike Becker <universe@uap-core.de>
parents: 475
diff changeset
408 * 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
409 *
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
410 * @param begin a pointer to the beginning node pointer (optional)
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
411 * @param end a pointer to the end node pointer (optional)
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
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)
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
413 * @param loc_next the location of a @c next pointer within your node struct (required)
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
414 * @param node the node to remove
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
415 */
985
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
416 cx_attr_nonnull_arg(5)
1426
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
417 CX_EXPORT void cx_linked_list_remove(void **begin, void **end,
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
418 ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node);
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
419
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
420 /**
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
421 * Determines the size of a linked list starting with @p node.
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
422 *
468
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
423 * @param node the first node
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
424 * @param loc_next the location of the @c next pointer within the node struct
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
425 * @return the size of the list or zero if @p node is @c NULL
468
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
426 */
1180
4c3a69b9723a add support for building windows DLLs - resolves #582
Mike Becker <universe@uap-core.de>
parents: 1162
diff changeset
427 cx_attr_nodiscard
1426
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
428 CX_EXPORT size_t cx_linked_list_size(const void *node, ptrdiff_t loc_next);
468
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
429
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
430 /**
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
431 * 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
432 *
639
309e8b08c60e temporarily remove pointer lists - see #234
Mike Becker <universe@uap-core.de>
parents: 629
diff changeset
433 * This function can work with linked lists of the following structure:
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
434 * @code
468
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
435 * typedef struct node node;
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
436 * struct node {
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
437 * node* prev;
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
438 * node* next;
639
309e8b08c60e temporarily remove pointer lists - see #234
Mike Becker <universe@uap-core.de>
parents: 629
diff changeset
439 * my_payload data;
468
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
440 * }
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
441 * @endcode
468
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
442 *
476
60ff4561dc04 change contract of cx_linked_list_remove()
Mike Becker <universe@uap-core.de>
parents: 475
diff changeset
443 * @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
444 *
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
445 * @param begin a pointer to the beginning node pointer (required)
468
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
446 * @param end a pointer to the end node pointer (optional)
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
447 * @param loc_prev the location of a @c prev pointer within your node struct (negative if not present)
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
448 * @param loc_next the location of a @c next pointer within your node struct (required)
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
449 * @param loc_data the location of the @c data pointer within your node struct
468
75ae1dccd101 add cx_linked_list_sort()
Mike Becker <universe@uap-core.de>
parents: 467
diff changeset
450 * @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
451 */
985
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
452 cx_attr_nonnull_arg(1, 6)
1426
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
453 CX_EXPORT void cx_linked_list_sort(void **begin, void **end,
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
454 ptrdiff_t loc_prev, ptrdiff_t loc_next, ptrdiff_t loc_data, cx_compare_func cmp_func);
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
455
486
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 485
diff changeset
456
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 485
diff changeset
457 /**
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 485
diff changeset
458 * 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
459 *
1424
563033aa998c fixes tons of typos and grammar issues across the documentation - fixes #667
Mike Becker <universe@uap-core.de>
parents: 1423
diff changeset
460 * @attention Both lists must have the same structure.
488
9138acaa494b add cxLinkedListFromArray() and cxListCompare()
Mike Becker <universe@uap-core.de>
parents: 487
diff changeset
461 *
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
462 * @param begin_left the beginning of the left list (@c NULL denotes an empty list)
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
463 * @param begin_right the beginning of the right list (@c NULL denotes an empty list)
486
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 485
diff changeset
464 * @param loc_advance the location of the pointer to advance
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
465 * @param loc_data the location of the @c data pointer within your node struct
486
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 485
diff changeset
466 * @param cmp_func the function to compare the elements
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
467 * @return the first non-zero result of invoking @p cmp_func or: negative if the left list is smaller than the
552
4373c2a90066 #178 fix that lists of different kind cannot be compared
Mike Becker <universe@uap-core.de>
parents: 528
diff changeset
468 * 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
469 */
985
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
470 cx_attr_nonnull_arg(5)
1426
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
471 CX_EXPORT int cx_linked_list_compare(const void *begin_left, const void *begin_right,
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
472 ptrdiff_t loc_advance, ptrdiff_t loc_data, cx_compare_func cmp_func);
486
d7ca126eab7f add cx_linked_list_compare() and simplifies some tests
Mike Becker <universe@uap-core.de>
parents: 485
diff changeset
473
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
474 /**
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
475 * 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
476 *
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
477 * @param begin a pointer to the beginning node pointer (required)
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
478 * @param end a pointer to the end node pointer (optional)
1100
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
479 * @param loc_prev the location of a @c prev pointer within your node struct (negative if your struct does not have one)
2ca6fa71e55e refine docs for linked_list.h - issue #548
Mike Becker <universe@uap-core.de>
parents: 993
diff changeset
480 * @param loc_next the location of a @c next pointer within your node struct (required)
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
481 */
985
68754c7de906 major refactoring of attributes
Mike Becker <universe@uap-core.de>
parents: 926
diff changeset
482 cx_attr_nonnull_arg(1)
1426
3a89b31f0724 clean up header files and adds support for comparing arbitrary strings with string.h functions
Mike Becker <universe@uap-core.de>
parents: 1424
diff changeset
483 CX_EXPORT void cx_linked_list_reverse(void **begin, void **end, ptrdiff_t loc_prev, ptrdiff_t loc_next);
473
1bd4b8c28722 add cx_linked_list_{prev, remove, reverse}
Mike Becker <universe@uap-core.de>
parents: 468
diff changeset
484
415
067aa769796a fix missing extern "C"
Mike Becker <universe@uap-core.de>
parents: 412
diff changeset
485 #ifdef __cplusplus
628
1e2be40f0cb5 use //-style single line comments everywhere
Mike Becker <universe@uap-core.de>
parents: 552
diff changeset
486 } // extern "C"
415
067aa769796a fix missing extern "C"
Mike Becker <universe@uap-core.de>
parents: 412
diff changeset
487 #endif
067aa769796a fix missing extern "C"
Mike Becker <universe@uap-core.de>
parents: 412
diff changeset
488
628
1e2be40f0cb5 use //-style single line comments everywhere
Mike Becker <universe@uap-core.de>
parents: 552
diff changeset
489 #endif // UCX_LINKED_LIST_H

mercurial