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