Doubly linked lists

[Aaron Digulla <digulla wi-pc44 fh-konstanz de>]

Hello,

I just had a look on how you implement doubly linked lists and I have
a comment. The AmigaOS contains functions for doubly linked lists which
have some very interesting properties:

- All functions always only copy pointers. There are no if's.
- You don't have to allocate memory to modify the list.
- You can remove a node from a list without the list pointer.

The only drawback is that it uses some magic in the list header. Here
is how it is used:

    struct List
    {
	struct Node * head, * tail, * tailpred;
    };

    struct Node
    {
	struct Node * next, * pred;
    };

When you want to add some object to a list, then the object must
be defined like this:

    struct Object
    {
	struct Node node;
    }

The code to add an object looks like this:

    void AddHead (struct List * list, struct Node * node)
    {
	node->next = list->head;
	node->pred = (struct Node *)&(list->head);
	list->head->pred = node;
	list->head = node;
    }

To remove one:

    void Remove (struct Node * node)
    {
	node->pred->next = node->next;
	node->next->pred = node->pred;
    }

As you can see, you never need to check anything or traverse the list. It
works because the list header are *two* nodes which were merged. The first
node is "head, tail" and the second is "tail, tailpred".

The pred pointer in the first node of the list points to the "head, tail"
node in the list header and the next pointer in the last node points to
"tail, tailpred". The pointer head points to the first node of the list,
tail is *always* NULL and tailpred points to the last node the user added
to the list (that's why it is called tailpred: The last node in the list is
"tail, tailpred" and not what the user appended to the list).

Because of this, the code is very fast (it can be compiled into only a few
asm instructions, eg. the code to remove a node is only 4 instructions).

The only drawback is that it makes assumptions about how the compiler
places and aligns pointers but I think one can assume that this code will
run on any CPU. There is no reason to believe that the compiler must
place the third pointer in the list header at some strange offset (ie.
that (&tail - &head) != (&tailpred - &tail)).

What do you think ? Should I write a module for glib which uses this ?

--
Dipl. Inf. (FH) Aaron "Optimizer" Digulla     Assistent im BIKS Labor, FB WI
"(to) optimize: Make a program faster by      FH Konstanz, Brauneggerstr. 55
improving the algorithms rather than by       Tel:+49-7531-206-514
buying a faster machine."                     EMail: digulla@fh-konstanz.de