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()`. 68 69## Iterate 70 71To iterate over a list: first get the head entry and then iterate over the 72nodes as long there is a next. Each node has an *element* associated with it, 73the custom pointer you stored there. Usually a struct pointer or similar. 74 75 struct Curl_llist_node *iter; 76 77 /* get the first entry of the 'barlist' */ 78 iter = Curl_llist_head(&barlist); 79 80 while(iter) { 81 /* extract the element pointer from the node */ 82 struct foobar *elem = Curl_node_elem(iter); 83 84 /* advance to the next node in the list */ 85 iter = Curl_node_next(iter); 86 } 87 88# Function overview 89 90## `Curl_llist_init` 91 92~~~c 93void Curl_llist_init(struct Curl_llist *list, Curl_llist_dtor dtor); 94~~~ 95 96Initializes the `list`. The argument `dtor` is NULL or a function pointer that 97gets called when list nodes are removed from this list. 98 99The function is infallible. 100 101~~~c 102typedef void (*Curl_llist_dtor)(void *user, void *elem); 103~~~ 104 105`dtor` is called with two arguments: `user` and `elem`. The first being the 106`user` pointer passed in to `Curl_llist_remove()`or `Curl_llist_destroy()` and 107the second is the `elem` pointer associated with removed node. The pointer 108that `Curl_node_elem()` would have returned for that node. 109 110## `Curl_llist_destroy` 111 112~~~c 113void Curl_llist_destroy(struct Curl_llist *list, void *user); 114~~~ 115 116This removes all nodes from the `list`. This leaves the list in a cleared 117state. 118 119The function is infallible. 120 121## `Curl_llist_append` 122 123~~~c 124void Curl_llist_append(struct Curl_llist *list, 125 const void *elem, struct Curl_llist_node *node); 126~~~ 127 128Adds `node` last in the `list` with a custom pointer to `elem`. 129 130The function is infallible. 131 132## `Curl_llist_insert_next` 133 134~~~c 135void Curl_llist_insert_next(struct Curl_llist *list, 136 struct Curl_llist_node *node, 137 const void *elem, 138 struct Curl_llist_node *node); 139~~~ 140 141Adds `node` to the `list` with a custom pointer to `elem` immediately after 142the previous list `node`. 143 144The function is infallible. 145 146## `Curl_llist_head` 147 148~~~c 149struct Curl_llist_node *Curl_llist_head(struct Curl_llist *list); 150~~~ 151 152Returns a pointer to the first node of the `list`, or a NULL if empty. 153 154## `Curl_node_uremove` 155 156~~~c 157void Curl_node_uremove(struct Curl_llist_node *node, void *user); 158~~~ 159 160Removes the `node` the list it was previously added to. Passes the `user` 161pointer to the list's destructor function if one was setup. 162 163The function is infallible. 164 165## `Curl_node_remove` 166 167~~~c 168void Curl_node_remove(struct Curl_llist_node *node); 169~~~ 170 171Removes the `node` the list it was previously added to. Passes a NULL pointer 172to the list's destructor function if one was setup. 173 174The function is infallible. 175 176## `Curl_node_elem` 177 178~~~c 179void *Curl_node_elem(struct Curl_llist_node *node); 180~~~ 181 182Given a list node, this function returns the associated element. 183 184## `Curl_node_next` 185 186~~~c 187struct Curl_llist_node *Curl_node_next(struct Curl_llist_node *node); 188~~~ 189 190Given a list node, this function returns the next node in the list. 191
