yambar/subprojects/tllist

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. 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 pointer-to-a-pointer... I though 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();
   

3. Named struct

   /* First declare named struct */
   tll(int, an_integer_list);
   
   /* Then declare a variable using that named struct */
   struct an_integer_list 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(). These are just convenience functions and calling these are equivalent to:

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.

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])

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)