Doubly Linked Lists in C

Doubly linked lists are a very useful data-structure. You can add and remove elements, and scan forwards and backwards all in constant time. This makes a list a useful "container" that can contain a group of things that may or may not need to be ordered. The question becomes what is the best way to make one in C?

The obvious way to create a doubly linked list is to add two pointers to a struct containing the data you wish to insert into the list. Something like:

struct foo {
	struct foo *next;
	struct foo *prev;
	
	int data;
	int some_more_data;
};

This can work quite well. It is obviously flexible enough to handle the task. (You can even have more than one pair of pointers, allowing the data to exist in more than one list at a time.) The problem is that open-coding is error-prone. Every list operation on foo will have to be reimplemented, and this introduces the chance for bugs.

Another way to construct a doubly linked list is to make the container generic. We can use a void * pointer to point to the data. Such an implementation might look like:

struct list {
	struct list *next;
	struct list *prev;
	void *data;
};

Since every user can have the same implementation, the above removes the code duplication problem. However, it suffers from some limitations compared to the original method. The first problem is that objects can only belong to one list at a time. (Depending on the organization of the program, this may or may not be an issue.) A second problem is inefficiency. To add an object to the list we now need to do a memory allocation. The extra overhead can be quite significant. Finally, the use of void * pointers isn't type-safe. The wrong kind of object might be accidentally added to the list, and the compiler can't warn us about that bug.

Fortunately, others have run into this issue, and there are solutions that are both type-safe, fast, and generic. However, we will need to investigate some macro magic to explore how they work. The first such implementation is due to the *BSD system, existing within the queue.h header. Within that header are multiple methods, but the most generic is the TAILQ set of macros. These define a macro to construct a generic list:

#define	TAILQ_HEAD(name, type, qual)\
struct name {\
	qual type *tqh_first;		/* first element */\
	qual type *qual *tqh_last;	/* addr of last next element */\
}

Given a name for the new structure and a type, it constructs a struct definition for the head of the list. List entries have a similar definition by macro:

#define	TAILQ_ENTRY(type, qual)\
struct {\
	qual type *tqe_next;		/* next element */\
	qual type *qual *tqe_prev;	/* address of previous next element */\
}

To use the above, you invoke the macro from within the struct definition for your data:

struct foo {
	TAILQ_ENTRY(struct foo, ) my_list;
	int data;
	int more_data;
};

The header then contains other macros that allow insertion, deletion, and iteration through the list. For example, the code to remove an element looks like:

#define	TAILQ_REMOVE(head, elm, field) \
do {\
	if (((elm)->field.tqe_next) != NULL)\
		(elm)->field.tqe_next->field.tqe_prev =\
			(elm)->field.tqe_prev;\
	else\
		(head)->tqh_last = (elm)->field.tqe_prev;\
	*(elm)->field.tqe_prev = (elm)->field.tqe_next;\
} while (0)

The above is wrapped in a do-while(0) loop so that it acts like a single statement. This is to avoid dangling-else problems with if statements. The rest of the code is quite simple. It checks to see that the element is not last and if it is, it updates the list head structure instead of a previous element. The rest is just simple pointer operations to elide the unwanted element. Since every list uses the same embedded structure, the same operations to access tqe_next, and tqe_prev always work. You just need to remember to pass in the right "field" that corresponds to the wanted list. In the case of lists of type struct foo above, we would need to use 'my_list'.

The above works, but is slightly inefficient. Note how the list end needs to be treated separately via the if statement? If the list is circular, then all the insertion and removal operations are simplified. The *BSD header has a corresponding CIRCLEQ set of macros that do this. However, the Linux kernel developers have taken that idea further with their struct list_head based implementation.

If you look within the Linux kernel source code, there is a header that implements a generic doubly linked list at include/linux/list.h. It is somewhat "cleaner" than the BSD implementation since there is only one structure ever defined, the list_head:

struct list_head {
	struct list_head *next, *prev;
};

You just include a field of this type within your data if you want to include it in a list:

struct foo {
	int data;
	struct list_head my_list;
	int some_more_data;
};

The problem here is how can it work? The list_head structures point to each other... but how can you move from a pointer to a list_head, which could be at any offset in the data, to a pointer to the data itself? The Linux kernel does this via the container_of() macro, which in turn uses the rarely used offsetof() feature of the C standard. Offsetof(), when given a type, and a member of that type, will return the byte offset of that member from the start of the type. With that information, you can do a small amount of pointer arithmetic to shift from a pointer to a contained member to a pointer to the containing object.

In the kernel container_of() is implemented as:

#define container_of(ptr, type, member) ({\
	const typeof( ((type *)0)->member ) *__mptr = (ptr);\
	(type *)( (char *)__mptr - offsetof(type,member) );})

The first line is just there for type-checking. We want to make sure that the pointer passed in is really a pointer that has the type of &(type.member). The second line just converts that pointer to (char *) so we can use the byte-sized offset. The final cast returns us to the correct type.

The list code then uses a simple wrapper called "list_entry" to go from pointers to entries, to pointers to elements:

#define list_entry(ptr, type, member) \
	container_of(ptr, type, member)

Finally, iterator macros can be constructed that use list_entry to get the elements one at a time. An example is list_for_each_entry(), which allows the user to iterate over the whole list:

#define list_for_each_entry(pos, head, member)\
	for (pos = list_entry((head)->next, typeof(*pos), member);\
		&pos->member != (head);\
		pos = list_entry(pos->member.next, typeof(*pos), member))

Just like the TAILQ macros, we need to give the list member (field) so that the right list is iterated over.

The above techniques are quite interesting... but can perhaps be improved. The first problem is that many of the macros need to give the data structure member or field, and if not, deal directly with the "confusing" list_head's instead. Another problem is that these lists aren't quite as type safe as they could be. Very little prevents the wrong kind of list_head from being used. You can put things of different type in the same list, and then accidentally iterate over them. If the offsets of the list_head fields are different, then data corruption will be the result.

Fortunately, these issues can be overcome at the cost of making the list head more like the *BSD TAILQ technique. We would like to store the type of the list elements, and also the numeric value of the field offset within the list head structure. This sounds impossible, but with gcc extensions we can actually get this to work. The magic definition looks like:

struct dlist {
	struct dlist *next;
	struct dlist *prev;
};

#define DECLARE_DLIST(head_type, type, field)\
union head_type {\
    struct dlist list;\
    union {\
        char (*offset)[offsetof(type, field)];\
        type *t;\
    } *data;\
}

We use a generic definition like struct list_head, but this time called struct dlist. However, we also require the user to declare the head to be a separate type. This new type is a little weird, it is a union between a struct dlist, combined with a pointer to some extra data. The "data" pointer will never actually be read from or stored to... it just is a sneaky way for us to store some information within the type. We store the offset of the field for the list, together with the type of the elements of the list. These two pieces of information can be extracted via the macros:

#define DLIST_OFFSET(head) sizeof(*(head)->data->offset)
#define DLIST_TYPE(head) typeof((head)->data->t)

Note that the sizeof() intrinsic, together with the gcc extension typeof() intrinsic both don't actually evaluate their arguments. They just use type information, so the data pointer isn't actually followed. You can use this method to "store" arbitrary types and unsigned long integers within another type. Provided the original type is the same size or larger than a pointer, there is no runtime overhead cost. We deliberately make the data pointer an unnamed union to prevent aliasing issues. This is because we don't want potential compiler optimizations impacted by this trick.

The above means that we can convert between pointers to list elements and entries without having to pass the 'field', provided we have a way to access the type of the list head. Since many list operations need the list head anyway, this can be a huge win for simplifying the user interface to the list data-structure. Macros that do this are:

#define DLIST_ELEM(head, list) \
    ((DLIST_TYPE(head)) ((char *)(list) - DLIST_OFFSET(head)))

#define DLIST_FIELD(head, elem) \
    ((struct dlist *) ((char *)(elem) + DLIST_OFFSET(head)))

(In this case we don't do the nice extra type-checking that the Linux kernel does, but it could be easily added. One way to do this might be:

#define BUILD_BUG_IF_ZERO(P)\
    sizeof(char[-(int) !(P)])

#define DLIST_CHECK_TYPES(head, elem)\
    BUILD_BUG_IF_ZERO(__builtin_types_compatible_p(DLIST_TYPE(head),\
         typeof(elem)))

This checks to see if elem is really the type of the things stored in the list pointed to by head.

We can create "unsafe" iterators for our generic list:

#define DLIST_NEXT_(elem, field) \
        container_of((elem)->field.next, typeof(*(elem)), field)

#define DLIST_PREV_(elem, field) \
        container_of((elem)->field.prev, typeof(*(elem)), field)

#define DLIST_FIRST_(head) DLIST_ELEM((head), (head)->list.next)
#define DLIST_LAST_(head) DLIST_ELEM((head), (head)->list.prev)

These aren't quite right because they might try to interpret the list head structure as an element if we iterate off of the end of the list. To avoid that, we need to know if the list is empty:

#define DLIST_EMPTY(head) ((head)->list.next == &(head)->list)

Or, if we are either the first or last element, and iterating the wrong way:

#define DLIST_FIRST(head)\
    (DLIST_EMPTY(head) ? NULL : DLIST_FIRST_(head))
#define DLIST_LAST(head)\
    (DLIST_EMPTY(head) ? NULL : DLIST_LAST_(head))
	
#define DLIST_SAFE(head, list)\
    ((list) == &(head)->list) ? NULL : DLIST_ELEM((head), (list))
	
#define DLIST_NEXT(head, elem) \
    (DLIST_CHECK_TYPES(head, elem),\
        DLIST_SAFE((head), DLIST_FIELD((head), (elem))->next))
#define DLIST_PREV(head, elem) \
    (DLIST_CHECK_TYPES(head, elem),\
        DLIST_SAFE((head), DLIST_FIELD((head), (elem))->prev))

The other code to insert and remove elements is very similar to the list_head method. However, we can use some of the previously introduced infrastructure to improve the list iterators. Basically, we can avoid having to pass in the field, and instead calculate it from the type of the list head. Code that does this for forward and reverse iteration looks like:

#define DLIST_LOOP_NEXT(var, head)\
	DLIST_ELEM((head), DLIST_FIELD((head), (var))->next)
#define DLIST_LOOP_PREV(var, head)\
	DLIST_ELEM((head), DLIST_FIELD((head), (var))->prev)

#define DLIST_FOREACH(var, head)\
	for ((var) = DLIST_ELEM((head), (head)->list.next);\
    	DLIST_FIELD((head), (var)) != &(head)->list;\
		(var) = DLIST_LOOP_NEXT((var), (head)))

#define DLIST_FOREACH_REVERSE(var, head)\
	for ((var) = DLIST_ELEM((head), (head)->list.prev);\
    	DLIST_FIELD((head), (var)) != &(head)->list;\
		(var) = DLIST_LOOP_PREV((var), (head)))

Finally, it is possible to improve the "safe" iterator, that still works if the current element is deleted. The original list_head version requires that the user pass in a temporary variable to store the next iteration in. However, it is possible to construct our own variable to use. A way to do this is to use the fact that a for loop in C99 allows variable declarations within the for-loop parenthesis. Unfortunately, a simple loop doesn't quite do what we want, but it is possible to fix that with a couple of if statements and a goto:

#ifndef CONCAT
#define CONCAT1(x,y)  x ## y
#define CONCAT(x,y)   CONCAT1(x,y)
#endif

#define DLIST_FOREACH_SAFE(var, head)\
if (1) {\
    goto CONCAT(dlist_entry_, __LINE__);\
} else for (typeof(var) CONCAT(t_, __LINE__);;)\
    if (1) {\
        break;\
    } else\
    CONCAT(dlist_entry_, __LINE__):\
    for ((var) = DLIST_ELEM((head), (head)->list.next),\
		CONCAT(t_, __LINE__) = DLIST_LOOP_NEXT((var), (head));\
		DLIST_FIELD((head), (var)) != &(head)->list;\
		(var) = CONCAT(t_, __LINE__),\
		CONCAT(t_, __LINE__) = DLIST_LOOP_NEXT((var), (head)))

The resulting macros, whilst much more complex to write, are much much simpler to use. The result is very type safe, and the resulting object code is identical to the list_head method. The trick of storing information within the container type can also be used with other data structures. Quite a bit of the power of C++ templates can actually be used in C this way.

Comments

MF said...

dear god...

David Rankin said...

This is an excellent discussion of generic iterator use in c very similar to a question I posted to stackoverflow recently: http://stackoverflow.com/questions/22798715/c-linked-list-is-it-possible-to-create-a-payload-independent-iterator-function

The huge benefit provided is reducing code duplication when working with multiple similar linked lists within an application. Thanks for taking the time to collect this information. I'll work on a functional implementation. If you have a standard test bit of code, it would really be useful if you provided a link on this page. (some of us slower types learn best by example ;)

EricJ said...

In Windows this intrusive list is the LIST_ENTRY, having members Flink and Blink.
There are macros to initialize, add to head or tail, and remove.
Before Windows NT this approach was used in VAX VMS.
One advantage is no operations have conditional branches.
The only disadvantage I have found is lack of type information when debugging.
http://msdn.microsoft.com/en-us/library/windows/hardware/ff554296(v=vs.85).aspx

said...

Enter your comments here

damn god said...

the explain is fine but coding technique is just horrible, I'm suffering here to understand your code. AND WHAT DA HELL THIS CAPTHCA ? 10 CHARECTER CAPTCHA ? WHY ?

Anonymous said...

This is just horrible and over engineered. I would never chose these kind of implementation.

said...

To the person above, you probably are not creating libraries that need to ensure things are safe. Depending on the application, I agree this may be too much. The aim, is to be as generic as possible but be safe.

Aanandhan said...

thanks jia for the code#include<stdio.h>// Example of Function Overloadingvoid mptliuly(void *ptr, int s, int mul_with){ int *ptr2Int; float *ptr2Float; if(s == 0){ ptr2Int = (int *)ptr; (*ptr2Int) = (*ptr2Int) * (mul_with); } else if(s==1) { ptr2Float = (float *)ptr; (*ptr2Float) = (*ptr2Float) * (mul_with); } }int main() { int p = 10; float q = 30.0; mptliuly(&p, 0, 10); //Second argument 0 represents int and third argument is a constant to mptliuly with mptliuly(&q, 1, 20); //Second argument 1 represents float printf("%d\n", p); printf("%f\n", q); }

hmijail said...

Really interesting article, but an example showing how your macros end up making the code look like would make it so much more complete. (And even better comparing it against code using TAILQ and linux/list.h...)

Enter the 10 characters above here

Enter your comments here
Name

• Lockless
• Articles
• Doubly Linked Lists in C