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