1<!-- 2Copyright (C) Daniel Stenberg, <daniel@haxx.se>, et al. 3 4SPDX-License-Identifier: curl 5--> 6 7# `llist` - linked lists 8 9 #include "llist.h" 10 11This is the internal module for linked lists. The API is designed to be 12flexible but also to avoid dynamic memory allocation. 13 14None of the involved structs should be accessed using struct fields (outside 15of `llist.c`). Use the functions. 16 17## Setup and shutdown 18 19`struct Curl_llist` is the struct holding a single linked list. It needs to be 20initialized with a call to `Curl_llist_init()` before it can be used 21 22To clean up a list, call `Curl_llist_destroy()`. Since the linked lists 23themselves do not allocate memory, it can also be fine to just *not* clean up 24the list. 25 26## Add a node 27 28There are two functions for adding a node to a linked list: 29 301. Add it last in the list with `Curl_llist_append` 312. Add it after a specific existing node with `Curl_llist_insert_next` 32 33When a node is added to a list, it stores an associated custom pointer to 34anything you like and you provide a pointer to a `struct Curl_llist_node` 35struct in which it stores and updates pointers. If you intend to add the same 36struct to multiple lists concurrently, you need to have one `struct 37Curl_llist_node` for each list. 38 39Add a node to a list with `Curl_llist_append(list, elem, node)`. Where 40 41- `list`: points to a `struct Curl_llist` 42- `elem`: points to what you want added to the list 43- `node`: is a pointer to a `struct Curl_llist_node`. Data storage for this 44 node. 45 46Example: to add a `struct foobar` to a linked list. Add a node struct within 47it: 48 49 struct foobar { 50 char *random; 51 struct Curl_llist_node storage; /* can be anywhere in the struct */ 52 char *data; 53 }; 54 55 struct Curl_llist barlist; /* the list for foobar entries */ 56 struct foobar entries[10]; 57 58 Curl_llist_init(&barlist, NULL); 59 60 /* add the first struct to the list */ 61 Curl_llist_append(&barlist, &entries[0], &entries[0].storage); 62 63See also `Curl_llist_insert_next`. 64 65## Remove a node 66 67Remove a node again from a list by calling `Curl_llist_remove()`. This 68will destroy the node's `elem` (e.g. calling a registered free function). 69 70To remove a node without destroying it's `elem`, use 71`Curl_node_take_elem()` which returns the `elem` pointer and 72removes the node from the list. The caller then owns this pointer 73and has to take care of it. 74 75## Iterate 76 77To iterate over a list: first get the head entry and then iterate over the 78nodes as long there is a next. Each node has an *element* associated with it, 79the custom pointer you stored there. Usually a struct pointer or similar. 80 81 struct Curl_llist_node *iter; 82 83 /* get the first entry of the 'barlist' */ 84 iter = Curl_llist_head(&barlist); 85 86 while(iter) { 87 /* extract the element pointer from the node */ 88 struct foobar *elem = Curl_node_elem(iter); 89 90 /* advance to the next node in the list */ 91 iter = Curl_node_next(iter); 92 } 93 94# Function overview 95 96## `Curl_llist_init` 97 98~~~c 99void Curl_llist_init(struct Curl_llist *list, Curl_llist_dtor dtor); 100~~~ 101 102Initializes the `list`. The argument `dtor` is NULL or a function pointer that 103gets called when list nodes are removed from this list. 104 105The function is infallible. 106 107~~~c 108typedef void (*Curl_llist_dtor)(void *user, void *elem); 109~~~ 110 111`dtor` is called with two arguments: `user` and `elem`. The first being the 112`user` pointer passed in to `Curl_llist_remove()`or `Curl_llist_destroy()` and 113the second is the `elem` pointer associated with removed node. The pointer 114that `Curl_node_elem()` would have returned for that node. 115 116## `Curl_llist_destroy` 117 118~~~c 119void Curl_llist_destroy(struct Curl_llist *list, void *user); 120~~~ 121 122This removes all nodes from the `list`. This leaves the list in a cleared 123state. 124 125The function is infallible. 126 127## `Curl_llist_append` 128 129~~~c 130void Curl_llist_append(struct Curl_llist *list, 131 const void *elem, struct Curl_llist_node *node); 132~~~ 133 134Adds `node` last in the `list` with a custom pointer to `elem`. 135 136The function is infallible. 137 138## `Curl_llist_insert_next` 139 140~~~c 141void Curl_llist_insert_next(struct Curl_llist *list, 142 struct Curl_llist_node *node, 143 const void *elem, 144 struct Curl_llist_node *node); 145~~~ 146 147Adds `node` to the `list` with a custom pointer to `elem` immediately after 148the previous list `node`. 149 150The function is infallible. 151 152## `Curl_llist_head` 153 154~~~c 155struct Curl_llist_node *Curl_llist_head(struct Curl_llist *list); 156~~~ 157 158Returns a pointer to the first node of the `list`, or a NULL if empty. 159 160## `Curl_node_uremove` 161 162~~~c 163void Curl_node_uremove(struct Curl_llist_node *node, void *user); 164~~~ 165 166Removes the `node` the list it was previously added to. Passes the `user` 167pointer to the list's destructor function if one was setup. 168 169The function is infallible. 170 171## `Curl_node_remove` 172 173~~~c 174void Curl_node_remove(struct Curl_llist_node *node); 175~~~ 176 177Removes the `node` the list it was previously added to. Passes a NULL pointer 178to the list's destructor function if one was setup. 179 180The function is infallible. 181 182## `Curl_node_elem` 183 184~~~c 185void *Curl_node_elem(struct Curl_llist_node *node); 186~~~ 187 188Given a list node, this function returns the associated element. 189 190## `Curl_node_next` 191 192~~~c 193struct Curl_llist_node *Curl_node_next(struct Curl_llist_node *node); 194~~~ 195 196Given a list node, this function returns the next node in the list. 197
