home contents changes options help

I created a new doubly-linked list needed for wire/libtile.c back in May. This is a generic list structure that may be used instead of GLIB GSList. See wire/dl_list.h.

A DL_list struct contains a head and tail pointer. Call DL_init to zero it. Place a DL_node as the first member of any type of struct you wish to place in a DL_list. That way you can cast freely between struct X and DL_node. (It is always legal to cast a C struct pointer to a pointer of its first member.) Nodes should be zeroed too, also with a call to DL_init.

Because DL_nodes are part of the data item being stored there is no separate malloc of the node itself. A DL_node is implicitly allocated with the data and a DL_list will hold any number of nodes/data without allocating more memory. A DL_list has no memory management to get wrong and can't leak. DL_list is pointer-based and does not allocate any memory. Unhooking a node does not deallocate anything.

DL_append and DL_remove are the primary functions to modify a DL_list. Nodes are added to the end by append. Removing a node unhooks it only. The DL_list contains head and tail DL_node pointers. Each DL_node contains prev and next pointers of type DL_node. The DL_list head->prev and tail->next members will always be zero. Once you have any DL_node you can walk either direction by following its prev and next DL_node members until you reach a null pointer. There are deliberately no iterators.

To avoid extra size and testing, I didn't implement anything I didn't use (such as DL_prepend) or wasn't absolutely necessary. Entire implementation is 135 lines of code. Written in C for compatibility. Would be trivial to wrap in C++.