#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