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. This also provided a good opportunity to use the CuTest unit testing framework and do some test-first development.
The result is pretty 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:
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)); }
Code is on github. Use as you please.