tllist

tllist is a Typed Linked List C header file only library implemented using pre-processor macros.

1. Description
2. Usage
   1. Declaring a variable
   2. Adding items - basic
   3. List length
   4. Accessing items
   5. Iterating
   6. Removing items - basic
   7. Adding items - advanced
   8. Removing items - advanced
   9. Freeing
3. Integrating
   1. Installing
   2. Meson
4. API
   1. Cheat sheet

Description

Most C implementations of linked list are untyped. That is, their data carriers are typically void *. This is error prone since your compiler will not be able to help you correct your mistakes (oh, was it a pointer-to-a-pointer... I thought it was just a pointer...).

tllist addresses this by using pre-processor macros to implement dynamic types, where the data carrier is typed to whatever you want; both primitive data types are supported as well as aggregated ones such as structs, enums and unions.

Being a double-linked list, most operations are constant in time (including pushing and popping both to/from front and back).

The memory overhead is fairly small; each item carries, besides its data, a prev and next pointer (i.e. a constant 16 byte overhead per item on 64-bit architectures).

The list itself has two head and tail pointers, plus a length variable (typically 8 bytes on 64-bit architectures) to make list length lookup constant in time.

Thus, assuming 64-bit pointers (and a 64-bit size_t type), the total overhead is 3*8 + n*2*8 bytes.

Usage

Declaring a variable

1. Declare a variable

   /* Declare a variable using an anonymous type */ tll(int) an_integer_list = tll_init(); 

2. Typedef

   /* First typedef the list type */ typedef tll(int) an_integer_list_t; /* Then declare a variable using that typedef */ an_integer_list_t an_integer_list = tll_init(); 

Adding items - basic

Use tll_push_back() or tll_push_front() to add elements to the back or front of the list.

tll_push_back(an_integer_list, 4711); tll_push_front(an_integer_list, 1234); 

List length

tll_length() returns the length (number of items) in a list.

tll_push_back(an_integer_list, 1234); tll_push_back(an_integer_list, 5678); printf("length: %zu\n", tll_length(an_integer_list)); 

Outputs:

length: 2 

Accessing items

For the front and back items, you can use tll_front() and tll_back() respectively. For any other item in the list, you need to iterate the list and find the item yourself.

tll_push_back(an_integer_list, 1234); tll_push_back(an_integer_list, 5555); tll_push_back(an_integer_list, 6789); printf("front: %d\n", tll_front(an_integer_list)); printf("back: %d\n", tll_back(an_integer_list)); 

Outputs:

front: 1234 back: 6789 

Iterating

You can iterate the list either forward or backwards, using tll_foreach() and tll_rforeach() respectively.

The it variable should be treated as an opaque iterator type, where it->item is the item.

In reality, it is simply a pointer to the linked list entry, and since tllist is a header-only implementation, you do have access to e.g. the next/prev pointers. There should not be any need to access anything except item however.

Note that it can be named anything.

tll_push_back(an_integer_list, 1); tll_push_back(an_integer_list, 2); tll_foreach(an_integer_list, it) { printf("forward: %d\n", it->item); } tll_rforeach(an_integer_list, it) { printf("reverse: %d\n", it->item); } 

Outputs:

forward: 1 forward: 2 reverse: 2 reverse: 1 

Removing items - basic

tll_pop_front() and tll_pop_back() removes the front/back item and returns it.

tll_push_back(an_integer_list, 1234); tll_push_back(an_integer_list, 5678); printf("front: %d\n", tll_pop_front(an_integer_list)); printf("back: %d\n", tll_pop_back(an_integer_list)); printf("length: %zu\n", tll_length(an_integer_list)); 

Outputs:

front: 1234 back: 5678 length: 0 

Adding items - advanced

Given an iterator, you can insert new items before or after that iterator, using tll_insert_before() and tll_insert_after().

tll_foreach(an_integer_list, it) { if (it->item == 1234) { tll_insert_before(an_integer_list, it, 7777); break; } } 

Q: Why do I have to pass both the list and the iterator to tll_insert_before()?

A: If not, each element in the list would have to contain a pointer to the owning list, which would significantly increase the overhead.

Removing items - advanced

Similar to how you can add items while iterating a list, you can also remove them.

Note that the *foreach() functions are safe in this regard - it is perfectly OK to remove the "current" item.

tll_foreach(an_integer_list, it) { if (it->item.delete_me) tll_remove(an_integer_list, it); } 

To make it slightly easier to handle cases where the item itself must be free:d as well, there is also tll_remove_and_free(). It works just like tll_remove(), but takes an additional argument; a callback that will be called for each item.

tll(int *) int_p_list = tll_init(); int *a = malloc(sizeof(*a)); int *b = malloc(sizeof(*b)); *a = 1234; *b = 5678; tll_push_back(int_p_list, a); tll_push_back(int_p_list, b); tll_foreach(int_p_list, it) { tll_remove_and_free(int_p_list, it, free); } 

Freeing

To remove all items, use tll_free(), or tll_free_and_free(). Conceptually, these just do:

tll_foreach(an_integer_list, it) { tll_remove(an_integer_list, it); } 

Note that there is no need to call tll_free() on an empty (tll_length(list) == 0) list.

Integrating

The easiest way may be to simply copy tllist.h into your project. But see sections below for other ways.

Installing

tllist can be installed as a system library. You can then use pkg-config --cflags tllist to get the compiler flags needed to set the include path.

If you are running Arch Linux, there's a bundled PKGBUILD you can use.

Meson

You can use tllist as a subproject. In your main project's meson.build, to something like:

tllist = subproject('tllist').get_variable('tllist') executable('you-executable', ..., dependencies: [tllist]) 

Or, if tllist has been installed as a system library, a regular

tllist = dependency('tllist') 

will suffice. Optionally, you can combine the two; search for a system library first, and fallback to a subproject:

tllist = dependency('tllist', version: '>=1.0.0', fallback: ['tllist', 'tllist']) 

API

Cheat sheet

Function	Description	Context	Complexity
list = tll_init()	initialize a new tllist variable to an empty list	Variable init	O(1)
tll_length(list)	returns the length (number of items) of a list		O(1)
tll_push_front(list, item)	inserts item at the beginning of the list		O(1)
tll_push_back(list, item)	inserts item at the end of the list		O(1)
tll_front(list)	returns the first item in the list		O(1)
tll_back(list)	returns the last item in the list		O(1)
tll_pop_front(list)	removes and returns the first item in the list		O(1)
tll_pop_back(list)	removes and returns the last item in the list		O(1)
tll_foreach(list, it)	iterates the list from the beginning to the end		O(n)
tll_rforeach(list, it)	iterates the list from the end to the beginning		O(n)
tll_insert_before(list, it, item)	inserts item before it.	tll_(r)foreach()	O(1)
tll_insert_after(list, it, item)	inserts item after it.	tll_(r)foreach()	O(1)
tll_remove(list, it)	removes it from the list.	tll_(r)foreach()	O(1)
tll_remove_and_free(list, it, cb)	removes it from the list, and calls cb(it->item).	tll_(r)foreach()	O(1)
tll_free(list)	removes all items from the list		O(n)
tll_free_and_free(list, cb)	removes all items from the list, and calls cb(it->item) for each item.		O(n)
tll_sort(list, cmp)	sort the list according to the result of cmp(item1, item2)		O(n log(n))