The other day I needed a linked list for the umpteenth time, and instead of going with the old (data, next) pairs, I decided I wanted something a bit more efficient, like an [unrolled linked list][http://en.wikipedia.org/wiki/Unrolled_linked_list “Wikipedia”). This also provided a good opportunity to use the CuTest unit testing framework and do some test-first development.

The result is rather nice, testing actually found a small bug, despite the fact that I was sure can do linked lists in my sleep, and I was so pleased with the performance characteristics (better cache efficiency and far fewer allocations) that I replaced all the lists in Eressea with it.

Code Sample

1
2
3
4
5
6
7
8
9
10
11
12
13
14

quicklist *q, *ql = 0;
int i;
// insert element at index:
ql_insert(ql, 0, foo);
ql_insert(ql, 0, bar);
assert(ql_get(ql, 1)==foo);
assert(ql_length(ql)==2);
// push element at end, get indexed element:
ql_push(ql, baz);
assert(ql_get(ql, 2)==baz);
// iterate over list:
for (q=ql,i=0;q;ql_advance(&ql, &i, 1)) {
    printf("%p ", ql_get(q, i));
}

The code is on github for you to use as you please.