xref: /aosp_15_r20/external/curl/docs/internals/LLIST.md (revision 6236dae45794135f37c4eb022389c904c8b0090d)
1*6236dae4SAndroid Build Coastguard Worker<!--
2*6236dae4SAndroid Build Coastguard WorkerCopyright (C) Daniel Stenberg, <[email protected]>, et al.
3*6236dae4SAndroid Build Coastguard Worker
4*6236dae4SAndroid Build Coastguard WorkerSPDX-License-Identifier: curl
5*6236dae4SAndroid Build Coastguard Worker-->
6*6236dae4SAndroid Build Coastguard Worker
7*6236dae4SAndroid Build Coastguard Worker# `llist` - linked lists
8*6236dae4SAndroid Build Coastguard Worker
9*6236dae4SAndroid Build Coastguard Worker    #include "llist.h"
10*6236dae4SAndroid Build Coastguard Worker
11*6236dae4SAndroid Build Coastguard WorkerThis is the internal module for linked lists. The API is designed to be
12*6236dae4SAndroid Build Coastguard Workerflexible but also to avoid dynamic memory allocation.
13*6236dae4SAndroid Build Coastguard Worker
14*6236dae4SAndroid Build Coastguard WorkerNone of the involved structs should be accessed using struct fields (outside
15*6236dae4SAndroid Build Coastguard Workerof `llist.c`). Use the functions.
16*6236dae4SAndroid Build Coastguard Worker
17*6236dae4SAndroid Build Coastguard Worker## Setup and shutdown
18*6236dae4SAndroid Build Coastguard Worker
19*6236dae4SAndroid Build Coastguard Worker`struct Curl_llist` is the struct holding a single linked list. It needs to be
20*6236dae4SAndroid Build Coastguard Workerinitialized with a call to `Curl_llist_init()` before it can be used
21*6236dae4SAndroid Build Coastguard Worker
22*6236dae4SAndroid Build Coastguard WorkerTo clean up a list, call `Curl_llist_destroy()`. Since the linked lists
23*6236dae4SAndroid Build Coastguard Workerthemselves do not allocate memory, it can also be fine to just *not* clean up
24*6236dae4SAndroid Build Coastguard Workerthe list.
25*6236dae4SAndroid Build Coastguard Worker
26*6236dae4SAndroid Build Coastguard Worker## Add a node
27*6236dae4SAndroid Build Coastguard Worker
28*6236dae4SAndroid Build Coastguard WorkerThere are two functions for adding a node to a linked list:
29*6236dae4SAndroid Build Coastguard Worker
30*6236dae4SAndroid Build Coastguard Worker1. Add it last in the list with `Curl_llist_append`
31*6236dae4SAndroid Build Coastguard Worker2. Add it after a specific existing node with `Curl_llist_insert_next`
32*6236dae4SAndroid Build Coastguard Worker
33*6236dae4SAndroid Build Coastguard WorkerWhen a node is added to a list, it stores an associated custom pointer to
34*6236dae4SAndroid Build Coastguard Workeranything you like and you provide a pointer to a `struct Curl_llist_node`
35*6236dae4SAndroid Build Coastguard Workerstruct in which it stores and updates pointers. If you intend to add the same
36*6236dae4SAndroid Build Coastguard Workerstruct to multiple lists concurrently, you need to have one `struct
37*6236dae4SAndroid Build Coastguard WorkerCurl_llist_node` for each list.
38*6236dae4SAndroid Build Coastguard Worker
39*6236dae4SAndroid Build Coastguard WorkerAdd a node to a list with `Curl_llist_append(list, elem, node)`. Where
40*6236dae4SAndroid Build Coastguard Worker
41*6236dae4SAndroid Build Coastguard Worker- `list`: points to a `struct Curl_llist`
42*6236dae4SAndroid Build Coastguard Worker- `elem`: points to what you want added to the list
43*6236dae4SAndroid Build Coastguard Worker- `node`: is a pointer to a `struct Curl_llist_node`. Data storage for this
44*6236dae4SAndroid Build Coastguard Worker  node.
45*6236dae4SAndroid Build Coastguard Worker
46*6236dae4SAndroid Build Coastguard WorkerExample: to add a `struct foobar` to a linked list. Add a node struct within
47*6236dae4SAndroid Build Coastguard Workerit:
48*6236dae4SAndroid Build Coastguard Worker
49*6236dae4SAndroid Build Coastguard Worker    struct foobar {
50*6236dae4SAndroid Build Coastguard Worker       char *random;
51*6236dae4SAndroid Build Coastguard Worker       struct Curl_llist_node storage; /* can be anywhere in the struct */
52*6236dae4SAndroid Build Coastguard Worker       char *data;
53*6236dae4SAndroid Build Coastguard Worker    };
54*6236dae4SAndroid Build Coastguard Worker
55*6236dae4SAndroid Build Coastguard Worker    struct Curl_llist barlist; /* the list for foobar entries */
56*6236dae4SAndroid Build Coastguard Worker    struct foobar entries[10];
57*6236dae4SAndroid Build Coastguard Worker
58*6236dae4SAndroid Build Coastguard Worker    Curl_llist_init(&barlist, NULL);
59*6236dae4SAndroid Build Coastguard Worker
60*6236dae4SAndroid Build Coastguard Worker    /* add the first struct to the list */
61*6236dae4SAndroid Build Coastguard Worker    Curl_llist_append(&barlist, &entries[0], &entries[0].storage);
62*6236dae4SAndroid Build Coastguard Worker
63*6236dae4SAndroid Build Coastguard WorkerSee also `Curl_llist_insert_next`.
64*6236dae4SAndroid Build Coastguard Worker
65*6236dae4SAndroid Build Coastguard Worker## Remove a node
66*6236dae4SAndroid Build Coastguard Worker
67*6236dae4SAndroid Build Coastguard WorkerRemove a node again from a list by calling `Curl_llist_remove()`.
68*6236dae4SAndroid Build Coastguard Worker
69*6236dae4SAndroid Build Coastguard Worker## Iterate
70*6236dae4SAndroid Build Coastguard Worker
71*6236dae4SAndroid Build Coastguard WorkerTo iterate over a list: first get the head entry and then iterate over the
72*6236dae4SAndroid Build Coastguard Workernodes as long there is a next. Each node has an *element* associated with it,
73*6236dae4SAndroid Build Coastguard Workerthe custom pointer you stored there. Usually a struct pointer or similar.
74*6236dae4SAndroid Build Coastguard Worker
75*6236dae4SAndroid Build Coastguard Worker     struct Curl_llist_node *iter;
76*6236dae4SAndroid Build Coastguard Worker
77*6236dae4SAndroid Build Coastguard Worker     /* get the first entry of the 'barlist' */
78*6236dae4SAndroid Build Coastguard Worker     iter = Curl_llist_head(&barlist);
79*6236dae4SAndroid Build Coastguard Worker
80*6236dae4SAndroid Build Coastguard Worker     while(iter) {
81*6236dae4SAndroid Build Coastguard Worker       /* extract the element pointer from the node */
82*6236dae4SAndroid Build Coastguard Worker       struct foobar *elem = Curl_node_elem(iter);
83*6236dae4SAndroid Build Coastguard Worker
84*6236dae4SAndroid Build Coastguard Worker       /* advance to the next node in the list */
85*6236dae4SAndroid Build Coastguard Worker       iter = Curl_node_next(iter);
86*6236dae4SAndroid Build Coastguard Worker     }
87*6236dae4SAndroid Build Coastguard Worker
88*6236dae4SAndroid Build Coastguard Worker# Function overview
89*6236dae4SAndroid Build Coastguard Worker
90*6236dae4SAndroid Build Coastguard Worker## `Curl_llist_init`
91*6236dae4SAndroid Build Coastguard Worker
92*6236dae4SAndroid Build Coastguard Worker~~~c
93*6236dae4SAndroid Build Coastguard Workervoid Curl_llist_init(struct Curl_llist *list, Curl_llist_dtor dtor);
94*6236dae4SAndroid Build Coastguard Worker~~~
95*6236dae4SAndroid Build Coastguard Worker
96*6236dae4SAndroid Build Coastguard WorkerInitializes the `list`. The argument `dtor` is NULL or a function pointer that
97*6236dae4SAndroid Build Coastguard Workergets called when list nodes are removed from this list.
98*6236dae4SAndroid Build Coastguard Worker
99*6236dae4SAndroid Build Coastguard WorkerThe function is infallible.
100*6236dae4SAndroid Build Coastguard Worker
101*6236dae4SAndroid Build Coastguard Worker~~~c
102*6236dae4SAndroid Build Coastguard Workertypedef void (*Curl_llist_dtor)(void *user, void *elem);
103*6236dae4SAndroid Build Coastguard Worker~~~
104*6236dae4SAndroid Build Coastguard Worker
105*6236dae4SAndroid Build Coastguard Worker`dtor` is called with two arguments: `user` and `elem`. The first being the
106*6236dae4SAndroid Build Coastguard Worker`user` pointer passed in to `Curl_llist_remove()`or `Curl_llist_destroy()` and
107*6236dae4SAndroid Build Coastguard Workerthe second is the `elem` pointer associated with removed node. The pointer
108*6236dae4SAndroid Build Coastguard Workerthat `Curl_node_elem()` would have returned for that node.
109*6236dae4SAndroid Build Coastguard Worker
110*6236dae4SAndroid Build Coastguard Worker## `Curl_llist_destroy`
111*6236dae4SAndroid Build Coastguard Worker
112*6236dae4SAndroid Build Coastguard Worker~~~c
113*6236dae4SAndroid Build Coastguard Workervoid Curl_llist_destroy(struct Curl_llist *list, void *user);
114*6236dae4SAndroid Build Coastguard Worker~~~
115*6236dae4SAndroid Build Coastguard Worker
116*6236dae4SAndroid Build Coastguard WorkerThis removes all nodes from the `list`. This leaves the list in a cleared
117*6236dae4SAndroid Build Coastguard Workerstate.
118*6236dae4SAndroid Build Coastguard Worker
119*6236dae4SAndroid Build Coastguard WorkerThe function is infallible.
120*6236dae4SAndroid Build Coastguard Worker
121*6236dae4SAndroid Build Coastguard Worker## `Curl_llist_append`
122*6236dae4SAndroid Build Coastguard Worker
123*6236dae4SAndroid Build Coastguard Worker~~~c
124*6236dae4SAndroid Build Coastguard Workervoid Curl_llist_append(struct Curl_llist *list,
125*6236dae4SAndroid Build Coastguard Worker                       const void *elem, struct Curl_llist_node *node);
126*6236dae4SAndroid Build Coastguard Worker~~~
127*6236dae4SAndroid Build Coastguard Worker
128*6236dae4SAndroid Build Coastguard WorkerAdds `node` last in the `list` with a custom pointer to `elem`.
129*6236dae4SAndroid Build Coastguard Worker
130*6236dae4SAndroid Build Coastguard WorkerThe function is infallible.
131*6236dae4SAndroid Build Coastguard Worker
132*6236dae4SAndroid Build Coastguard Worker## `Curl_llist_insert_next`
133*6236dae4SAndroid Build Coastguard Worker
134*6236dae4SAndroid Build Coastguard Worker~~~c
135*6236dae4SAndroid Build Coastguard Workervoid Curl_llist_insert_next(struct Curl_llist *list,
136*6236dae4SAndroid Build Coastguard Worker                            struct Curl_llist_node *node,
137*6236dae4SAndroid Build Coastguard Worker                            const void *elem,
138*6236dae4SAndroid Build Coastguard Worker                            struct Curl_llist_node *node);
139*6236dae4SAndroid Build Coastguard Worker~~~
140*6236dae4SAndroid Build Coastguard Worker
141*6236dae4SAndroid Build Coastguard WorkerAdds `node` to the `list` with a custom pointer to `elem` immediately after
142*6236dae4SAndroid Build Coastguard Workerthe previous list `node`.
143*6236dae4SAndroid Build Coastguard Worker
144*6236dae4SAndroid Build Coastguard WorkerThe function is infallible.
145*6236dae4SAndroid Build Coastguard Worker
146*6236dae4SAndroid Build Coastguard Worker## `Curl_llist_head`
147*6236dae4SAndroid Build Coastguard Worker
148*6236dae4SAndroid Build Coastguard Worker~~~c
149*6236dae4SAndroid Build Coastguard Workerstruct Curl_llist_node *Curl_llist_head(struct Curl_llist *list);
150*6236dae4SAndroid Build Coastguard Worker~~~
151*6236dae4SAndroid Build Coastguard Worker
152*6236dae4SAndroid Build Coastguard WorkerReturns a pointer to the first node of the `list`, or a NULL if empty.
153*6236dae4SAndroid Build Coastguard Worker
154*6236dae4SAndroid Build Coastguard Worker## `Curl_node_uremove`
155*6236dae4SAndroid Build Coastguard Worker
156*6236dae4SAndroid Build Coastguard Worker~~~c
157*6236dae4SAndroid Build Coastguard Workervoid Curl_node_uremove(struct Curl_llist_node *node, void *user);
158*6236dae4SAndroid Build Coastguard Worker~~~
159*6236dae4SAndroid Build Coastguard Worker
160*6236dae4SAndroid Build Coastguard WorkerRemoves the `node` the list it was previously added to. Passes the `user`
161*6236dae4SAndroid Build Coastguard Workerpointer to the list's destructor function if one was setup.
162*6236dae4SAndroid Build Coastguard Worker
163*6236dae4SAndroid Build Coastguard WorkerThe function is infallible.
164*6236dae4SAndroid Build Coastguard Worker
165*6236dae4SAndroid Build Coastguard Worker## `Curl_node_remove`
166*6236dae4SAndroid Build Coastguard Worker
167*6236dae4SAndroid Build Coastguard Worker~~~c
168*6236dae4SAndroid Build Coastguard Workervoid Curl_node_remove(struct Curl_llist_node *node);
169*6236dae4SAndroid Build Coastguard Worker~~~
170*6236dae4SAndroid Build Coastguard Worker
171*6236dae4SAndroid Build Coastguard WorkerRemoves the `node` the list it was previously added to. Passes a NULL pointer
172*6236dae4SAndroid Build Coastguard Workerto the list's destructor function if one was setup.
173*6236dae4SAndroid Build Coastguard Worker
174*6236dae4SAndroid Build Coastguard WorkerThe function is infallible.
175*6236dae4SAndroid Build Coastguard Worker
176*6236dae4SAndroid Build Coastguard Worker## `Curl_node_elem`
177*6236dae4SAndroid Build Coastguard Worker
178*6236dae4SAndroid Build Coastguard Worker~~~c
179*6236dae4SAndroid Build Coastguard Workervoid *Curl_node_elem(struct Curl_llist_node *node);
180*6236dae4SAndroid Build Coastguard Worker~~~
181*6236dae4SAndroid Build Coastguard Worker
182*6236dae4SAndroid Build Coastguard WorkerGiven a list node, this function returns the associated element.
183*6236dae4SAndroid Build Coastguard Worker
184*6236dae4SAndroid Build Coastguard Worker## `Curl_node_next`
185*6236dae4SAndroid Build Coastguard Worker
186*6236dae4SAndroid Build Coastguard Worker~~~c
187*6236dae4SAndroid Build Coastguard Workerstruct Curl_llist_node *Curl_node_next(struct Curl_llist_node *node);
188*6236dae4SAndroid Build Coastguard Worker~~~
189*6236dae4SAndroid Build Coastguard Worker
190*6236dae4SAndroid Build Coastguard WorkerGiven a list node, this function returns the next node in the list.
191