Statistics
| Branch: | Revision:

iof-bird-daemon / lib / lists.h @ b933281e

History | View | Annotate | Download (1.91 KB)

1
/*
2
 *        BIRD Library -- Linked Lists
3
 *
4
 *        (c) 1998 Martin Mares <mj@ucw.cz>
5
 *
6
 *        Can be freely distributed and used under the terms of the GNU GPL.
7
 */
8

    
9
#ifndef _BIRD_LISTS_H_
10
#define _BIRD_LISTS_H_
11

    
12
/*
13
 * I admit the list structure is very tricky and also somewhat awkward,
14
 * but it's both efficient and easy to manipulate once one understands the
15
 * basic trick: The list head always contains two synthetic nodes which are
16
 * always present in the list: the head and the tail. But as the `next'
17
 * entry of the tail and the `prev' entry of the head are both NULL, the
18
 * nodes can overlap each other:
19
 *
20
 *     head    head_node.next
21
 *     null    head_node.prev  tail_node.next
22
 *     tail                    tail_node.prev
23
 */
24

    
25
typedef struct node {
26
  struct node *next, *prev;
27
} node;
28

    
29
typedef struct list {                        /* In fact two overlayed nodes */
30
  struct node *head, *null, *tail;
31
} list;
32

    
33
#define NODE (node *)
34
#define HEAD(list) ((void *)((list).head))
35
#define TAIL(list) ((void *)((list).tail))
36
#define WALK_LIST(n,list) for(n=HEAD(list);(NODE (n))->next; \
37
                                n=(void *)((NODE (n))->next))
38
#define WALK_LIST_DELSAFE(n,nxt,list) \
39
     for(n=HEAD(list); nxt=(void *)((NODE (n))->next); n=(void *) nxt)
40
/* WALK_LIST_FIRST supposes that called code removes each processed node */
41
#define WALK_LIST_FIRST(n,list) \
42
     while(n=HEAD(list), (NODE (n))->next)
43
#define WALK_LIST_BACKWARDS(n,list) for(n=TAIL(list);(NODE (n))->prev; \
44
                                n=(void *)((NODE (n))->prev))
45
#define WALK_LIST_BACKWARDS_DELSAFE(n,prv,list) \
46
     for(n=TAIL(list); prv=(void *)((NODE (n))->prev); n=(void *) prv)
47

    
48
#define EMPTY_LIST(list) (!(list).head->next)
49

    
50
void add_tail(list *, node *);
51
void add_head(list *, node *);
52
void rem_node(node *);
53
void add_tail_list(list *, list *);
54
void init_list(list *);
55
void insert_node(node *, node *);
56

    
57
#ifndef _BIRD_LISTS_C_
58
#define LIST_INLINE extern inline
59
#include "lib/lists.c"
60
#undef LIST_INLINE
61
#else
62
#define LIST_INLINE
63
#endif
64

    
65
#endif