1# tllist 2 3**tllist** is a **T**yped **L**inked **L**ist C header file only 4library implemented using pre-processor macros. 5 6[![Packaging status](https://repology.org/badge/vertical-allrepos/tllist.svg)](https://repology.org/project/tllist/versions) 7 81. [Description](#description) 91. [Usage](#usage) 10 1. [Declaring a variable](#declaring-a-variable) 11 1. [Adding items - basic](#adding-items-basic) 12 1. [List length](#list-length) 13 1. [Accessing items](#accessing-items) 14 1. [Iterating](#iterating) 15 1. [Removing items - basic](#removing-items-basic) 16 1. [Adding items - advanced](#adding-items-advanced) 17 1. [Removing items - advanced](#removing-items-advanced) 18 1. [Freeing](#freeing) 191. [Integrating](#integrating) 20 1. [Installing](#installing) 21 1. [Meson](#meson) 221. [API](#api) 23 1. [Cheat sheet](#cheat-sheet) 24 25 26## Description 27 28Most C implementations of linked list are untyped. That is, their data 29carriers are typically `void *`. This is error prone since your 30compiler will not be able to help you correct your mistakes (_oh, was 31it a pointer-to-a-pointer... I thought it was just a pointer..._). 32 33**tllist** addresses this by using pre-processor macros to implement 34dynamic types, where the data carrier is typed to whatever you want; 35both **primitive** data types are supported as well as aggregated ones 36such as **structs**, **enums** and **unions**. 37 38Being a double-linked list, most operations are constant in time 39(including pushing and popping both to/from front and back). 40 41The memory overhead is fairly small; each item carries, besides its 42data, a _prev_ and _next_ pointer (i.e. a constant 16 byte overhead 43per item on 64-bit architectures). 44 45The list itself has two _head_ and _tail_ pointers, plus a _length_ 46variable (typically 8 bytes on 64-bit architectures) to make list 47length lookup constant in time. 48 49Thus, assuming 64-bit pointers (and a 64-bit `size_t` type), the total 50overhead is `3*8 + n*2*8` bytes. 51 52 53## Usage 54 55### Declaring a variable 56 571. **Declare a variable** 58 59 ```c 60 /* Declare a variable using an anonymous type */ 61 tll(int) an_integer_list = tll_init(); 62 ``` 63 64 652. **Typedef** 66 67 ```c 68 /* First typedef the list type */ 69 typedef tll(int) an_integer_list_t; 70 71 /* Then declare a variable using that typedef */ 72 an_integer_list_t an_integer_list = tll_init(); 73 ``` 74 75### Adding items - basic 76 77Use `tll_push_back()` or `tll_push_front()` to add elements to the 78back or front of the list. 79 80```c 81tll_push_back(an_integer_list, 4711); 82tll_push_front(an_integer_list, 1234); 83``` 84 85 86### List length 87 88`tll_length()` returns the length (number of items) in a list. 89 90```c 91tll_push_back(an_integer_list, 1234); 92tll_push_back(an_integer_list, 5678); 93printf("length: %zu\n", tll_length(an_integer_list)); 94``` 95 96Outputs: 97 98 length: 2 99 100 101### Accessing items 102 103For the front and back items, you can use `tll_front()` and 104`tll_back()` respectively. For any other item in the list, you need to 105iterate the list and find the item yourself. 106 107```c 108tll_push_back(an_integer_list, 1234); 109tll_push_back(an_integer_list, 5555); 110tll_push_back(an_integer_list, 6789); 111 112printf("front: %d\n", tll_front(an_integer_list)); 113printf("back: %d\n", tll_back(an_integer_list)); 114``` 115 116Outputs: 117 118 front: 1234 119 back: 6789 120 121 122### Iterating 123 124You can iterate the list either forward or backwards, using 125`tll_foreach()` and `tll_rforeach()` respectively. 126 127The `it` variable should be treated as an opaque iterator type, where 128`it->item` is the item. 129 130In reality, it is simply a pointer to the linked list entry, and since 131tllist is a header-only implementation, you do have access to e.g. the 132next/prev pointers. There should not be any need to access anything 133except `item` however. 134 135Note that `it` can be named anything. 136 137```c 138tll_push_back(an_integer_list, 1); 139tll_push_back(an_integer_list, 2); 140 141tll_foreach(an_integer_list, it) { 142 printf("forward: %d\n", it->item); 143} 144 145tll_rforeach(an_integer_list, it) { 146 printf("reverse: %d\n", it->item); 147} 148``` 149 150Outputs: 151 152 forward: 1 153 forward: 2 154 reverse: 2 155 reverse: 1 156 157 158### Removing items - basic 159 160`tll_pop_front()` and `tll_pop_back()` removes the front/back item and 161returns it. 162 163```c 164tll_push_back(an_integer_list, 1234); 165tll_push_back(an_integer_list, 5678); 166 167printf("front: %d\n", tll_pop_front(an_integer_list)); 168printf("back: %d\n", tll_pop_back(an_integer_list)); 169printf("length: %zu\n", tll_length(an_integer_list)); 170``` 171 172Outputs: 173 174 front: 1234 175 back: 5678 176 length: 0 177 178 179### Adding items - advanced 180 181Given an iterator, you can insert new items before or after that 182iterator, using `tll_insert_before()` and `tll_insert_after()`. 183 184```c 185tll_foreach(an_integer_list, it) { 186 if (it->item == 1234) { 187 tll_insert_before(an_integer_list, it, 7777); 188 break; 189 } 190} 191``` 192 193Q: Why do I have to pass **both** the _list_ and the _iterator_ to 194 `tll_insert_before()`? 195 196A: If not, **each** element in the list would have to contain a 197 pointer to the owning list, which would significantly increase the 198 overhead. 199 200 201### Removing items - advanced 202 203Similar to how you can add items while iterating a list, you can also 204remove them. 205 206Note that the `*foreach()` functions are **safe** in this regard - it 207is perfectly OK to remove the "current" item. 208 209```c 210tll_foreach(an_integer_list, it) { 211 if (it->item.delete_me) 212 tll_remove(an_integer_list, it); 213} 214``` 215 216To make it slightly easier to handle cases where the item _itself_ 217must be free:d as well, there is also `tll_remove_and_free()`. It 218works just like `tll_remove()`, but takes an additional argument; a 219callback that will be called for each item. 220 221```c 222tll(int *) int_p_list = tll_init(); 223 224int *a = malloc(sizeof(*a)); 225int *b = malloc(sizeof(*b)); 226 227*a = 1234; 228*b = 5678; 229 230tll_push_back(int_p_list, a); 231tll_push_back(int_p_list, b); 232 233tll_foreach(int_p_list, it) { 234 tll_remove_and_free(int_p_list, it, free); 235} 236``` 237 238 239### Freeing 240 241To remove **all** items, use `tll_free()`, or 242`tll_free_and_free()`. Conceptually, these just do: 243 244```c 245tll_foreach(an_integer_list, it) { 246 tll_remove(an_integer_list, it); 247} 248``` 249 250Note that there is no need to call `tll_free()` on an empty 251(`tll_length(list) == 0`) list. 252 253 254## Integrating 255 256The easiest way may be to simply copy `tllist.h` into your 257project. But see sections below for other ways. 258 259 260### Installing 261 262tllist can be installed as a system library. You can then use 263`pkg-config --cflags tllist` to get the compiler flags needed to set 264the include path. 265 266If you are running Arch Linux, there's a bundled [PKGBUILD](PKGBUILD) 267you can use. 268 269 270### Meson 271 272You can use tllist as a subproject. In your main project's 273`meson.build`, to something like: 274 275```meson 276tllist = subproject('tllist').get_variable('tllist') 277executable('you-executable', ..., dependencies: [tllist]) 278``` 279 280Or, if tllist has been installed as a system library, a regular 281 282```meson 283tllist = dependency('tllist') 284``` 285 286will suffice. Optionally, you can combine the two; search for a system 287library first, and fallback to a subproject: 288 289```meson 290tllist = dependency('tllist', version: '>=1.0.0', fallback: ['tllist', 'tllist']) 291``` 292 293 294## API 295 296### Cheat sheet 297 298| Function | Description | Context | Complexity | 299|-------------------------------------|-------------------------------------------------------|--------------------|-----------:| 300| `list = tll_init()` | initialize a new tllist variable to an empty list | Variable init | O(1) | 301| `tll_length(list)` | returns the length (number of items) of a list | | O(1) | 302| `tll_push_front(list, item)` | inserts _item_ at the beginning of the list | | O(1) | 303| `tll_push_back(list, item)` | inserts _item_ at the end of the list | | O(1) | 304| `tll_front(list)` | returns the first item in the list | | O(1) | 305| `tll_back(list)` | returns the last item in the list | | O(1) | 306| `tll_pop_front(list)` | removes and returns the first item in the list | | O(1) | 307| `tll_pop_back(list)` | removes and returns the last item in the list | | O(1) | 308| `tll_foreach(list, it)` | iterates the list from the beginning to the end | | O(n) | 309| `tll_rforeach(list, it)` | iterates the list from the end to the beginning | | O(n) | 310| `tll_insert_before(list, it, item)` | inserts _item_ before _it_. | `tll_(r)foreach()` | O(1) | 311| `tll_insert_after(list, it, item)` | inserts _item_ after _it_. | `tll_(r)foreach()` | O(1) | 312| `tll_remove(list, it)` | removes _it_ from the list. | `tll_(r)foreach()` | O(1) | 313| `tll_remove_and_free(list, it, cb)` | removes _it_ from the list, and calls `cb(it->item)`. | `tll_(r)foreach()` | O(1) | 314| `tll_free(list)` | removes **all** items from the list | | O(n) | 315| `tll_free_and_free(list, cb)` | removes **all** items from the list, and calls `cb(it->item)` for each item. | | O(n) | 316