A C header file only implementation of a typed linked list.
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
Daniel Eklöf 42d6830b42
meson: use meson.override_dependency() - requires meson >= 0.54
1 month ago
.gitignore PKGBUILD: initial 6 months ago
.gitlab-ci.yml ci: initial CI 6 months ago
LICENSE license: MIT 6 months ago
PKGBUILD meson: use meson.override_dependency() - requires meson >= 0.54 1 month ago
README.md README: let's see if codeberg parses this 5 months ago
meson.build meson: use meson.override_dependency() - requires meson >= 0.54 1 month ago
test.c test: add a super-basic unittest 6 months ago
tllist.h import tllist.h 6 months ago

README.md

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();
    
  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.

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)