Reducing head node size for a doubly linked list in C

list.md

Reducing head node size for a doubly linked list in C

Disadvantages of using head node pointer

A way to define generic linked list is something like this, retrieving derived structure using offsetof defined in stddef.h:

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

To iterate all nodes in a list, we need to know the first ( head ) node. So if we define a head node pointer,

struct list* head = NULL;

following two disadvantages need to be considered.

• Special case must be considered when a linked list is empty, checking the pointer is not NULL.
• Such pointer is required to delete the first node (aka head node, node pointed by head node pointer).

As an example for the second disadvantage, consider the case to delete a node from a hash table consists of multiple head node pointers:

struct list* head[BUCKETS];

How can we know the head node pointer of the list which contains the node to be deleted? Additional information like bucket index or reference to head pointer takes more storage. Or calculating hash function to get bucket index is sometimes quite expensive.

Head node clears disadvantages but head node size can be another issue.

Head node can be defined like this :

struct list head = { NULL, NULL };

• The first disadvantage is cleared because &head is always not NULL.
• The second is also cleared because &head never changes before discarding the whole list.

Circular list can be used if we don't want to check validity of prev and next pointers:

struct list head = { &head, &head };

All O.K. but head node size can be an issue for an array of lists which has many items, like a hash data structure. If head node is used instead of head node pointer, twice storage is needed for buckets.

struct list hash[BUCKETS];

To avoid this, Linux kernel defines hlist structures.

struct hlist_head {
    struct hlist_node *first;
};

struct hlist_node {
    struct hlist_node *next, **pprev;
};

This structure basically uses head node pointer, so the first disadvantage mentioned above exposed in hlist_add_head. Refer to kernel code, https://github.com/torvalds/linux/blob/master/include/linux/list.h

if (first)
		first->pprev = &n->next;

By the way, pprev will clear the second disadvantage of using head node pointer, because it can store pointer of first in hlist_head structure.

But these structures are not compatible to generic linked list structure, so additional function set is needed to support hlist. So I suggest alternative method to define a structure compatible to both singly and doubly linked lists.

Generic linked list structure compatible to both singly and doubly linked lists

_List structure defined in https://github.com/orionids/Orion/blob/master/coral/def.h looks like this :

struct _List {
    struct _List* link;
};

It is generic singly linked list. To define doubly linked list in a derived structure, array of _List is used :

struct _MyList {
    ...
    struct _List list[2]; // doubly linked list
    ...
};

For struct _List* node,

• Next node can be accessed like : node[0].link or node->link
• Previous node can be accessed like : node[1].link

Without nonstandard pointer casting between structures, above _List structure can represent both singly and doubly linked list. Based on this concept, listAdd and listCut implemented in https://github.com/orionids/Orion/blob/master/coralsrc/list.c

And listAddCircularNode and listCutCircularNode reduce pointer validity checks for circular linked lists. For small systems, these functions need not to be defined because listAdd and listCut can replace them.

Reducing head node size for a doubly linked list

To reduce head node size for a hash table, head node for singly linked list can be used. By this head node pointer is not needed when deleting a node, like hlist in Linux kernel.

struct _List hash[BUCKETS];

Because _List structure is compatible to both singly and doubly linked lists, &hash[i] can be an argument for doubly linked list functions if (&hash[i])[1].link is not accessed in them :

• hash[i].link must be set to NULL initially, so listAdd and listCut will never access (&hash[i])[1].link
• Or hash[i].link can be hash + i ( circular node ) so circular list functions can be used with slight modification for listCutCircularNode. To avoid invalid access, dummy argument is propery supplied. ( Not implemented in Coral library )

This is newly adopted linked list implementation in Coral library( component of Orion project ).

Wow!!