2 * Sherlock Library -- Linked Lists
4 * (c) 1997--1999 Martin Mares <mj@ucw.cz>
7 #ifndef _SHERLOCK_LISTS_H
8 #define _SHERLOCK_LISTS_H
11 * I admit the list structure is very tricky and also somewhat awkward,
12 * but it's both efficient and easy to manipulate once one understands the
13 * basic trick: The list head always contains two synthetic nodes which are
14 * always present in the list: the head and the tail. But as the `next'
15 * entry of the tail and the `prev' entry of the head are both NULL, the
16 * nodes can overlap each other:
19 * null head_node.prev tail_node.next
24 struct node *next, *prev;
27 typedef struct list { /* In fact two overlayed nodes */
28 struct node *head, *null, *tail;
32 #define HEAD(list) ((void *)((list).head))
33 #define TAIL(list) ((void *)((list).tail))
34 #define WALK_LIST(n,list) for(n=HEAD(list);(NODE (n))->next; \
35 n=(void *)((NODE (n))->next))
36 #define DO_FOR_ALL(n,list) WALK_LIST(n,list)
37 #define WALK_LIST_DELSAFE(n,nxt,list) \
38 for(n=HEAD(list); nxt=(void *)((NODE (n))->next); n=(void *) nxt)
39 #define WALK_LIST_BACKWARDS(n,list) for(n=TAIL(list);(NODE (n))->prev; \
40 n=(void *)((NODE (n))->prev))
41 #define WALK_LIST_BACKWARDS_DELSAFE(n,prv,list) \
42 for(n=TAIL(list); prv=(void *)((NODE (n))->prev); n=(void *) prv)
44 #define EMPTY_LIST(list) (!(list).head->next)
46 void add_tail(list *, node *);
47 void add_head(list *, node *);
48 void rem_node(node *);
49 void add_tail_list(list *, list *);
50 void init_list(list *);
51 void insert_node(node *, node *);
53 #if !defined(_SHERLOCK_LISTS_C) && defined(__GNUC__)
54 #define LIST_INLINE extern inline
55 #include "lib/lists.c"