Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (2.51 KB)

1 58ef912c Martin Mares
/*
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 a2d01907 Martin Mares
/*
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 58ef912c Martin Mares
typedef struct node {
26
  struct node *next, *prev;
27
} node;
28
29 54bb032d Jan Moskyto Matejka
typedef union list {                        /* In fact two overlayed nodes */
30
  struct {                                /* Head node */
31
    struct node head_node;
32
    void *head_padding;
33
  };
34
  struct {                                /* Tail node */
35
    void *tail_padding;
36
    struct node tail_node;
37
  };
38
  struct {                                /* Split to separate pointers */
39
    struct node *head;
40
    struct node *null;
41
    struct node *tail;
42
  };
43 58ef912c Martin Mares
} list;
44
45 54bb032d Jan Moskyto Matejka
46 58ef912c Martin Mares
#define NODE (node *)
47
#define HEAD(list) ((void *)((list).head))
48
#define TAIL(list) ((void *)((list).tail))
49 d5356072 Ondrej Zajicek
#define NODE_NEXT(n) ((void *)((NODE (n))->next))
50 fc06fb62 Ondrej Zajicek
#define NODE_VALID(n) ((NODE (n))->next)
51
#define WALK_LIST(n,list) for(n=HEAD(list); NODE_VALID(n); n=NODE_NEXT(n))
52 0c791f87 Ondrej Zajicek
#define WALK_LIST2(n,nn,list,pos) \
53
  for(nn=(list).head; NODE_VALID(nn) && (n=SKIP_BACK(typeof(*n),pos,nn)); nn=nn->next)
54 d92882be Martin Mares
#define WALK_LIST_DELSAFE(n,nxt,list) \
55 f4a60a9b Ondrej Zajicek (work)
  for(n=HEAD(list); nxt=NODE_NEXT(n); n=(void *) nxt)
56
#define WALK_LIST2_DELSAFE(n,nn,nxt,list,pos) \
57
  for(nn=HEAD(list); (nxt=nn->next) && (n=SKIP_BACK(typeof(*n),pos,nn)); nn=nxt)
58
59 b933281e Ondrej Zajicek
/* WALK_LIST_FIRST supposes that called code removes each processed node */
60
#define WALK_LIST_FIRST(n,list) \
61
     while(n=HEAD(list), (NODE (n))->next)
62 b6628a8c Martin Mares
#define WALK_LIST_BACKWARDS(n,list) for(n=TAIL(list);(NODE (n))->prev; \
63
                                n=(void *)((NODE (n))->prev))
64
#define WALK_LIST_BACKWARDS_DELSAFE(n,prv,list) \
65
     for(n=TAIL(list); prv=(void *)((NODE (n))->prev); n=(void *) prv)
66 aea2dcab Pavel Machek
67 58ef912c Martin Mares
#define EMPTY_LIST(list) (!(list).head->next)
68
69 85a3639d Pavel Tvrdik
70
#ifndef _BIRD_LISTS_C_
71
#define LIST_INLINE static inline
72
#include "lib/lists.c"
73
#undef LIST_INLINE
74
75
#else /* _BIRD_LISTS_C_ */
76
#define LIST_INLINE
77 58ef912c Martin Mares
void add_tail(list *, node *);
78
void add_head(list *, node *);
79
void rem_node(node *);
80
void add_tail_list(list *, list *);
81
void init_list(list *);
82
void insert_node(node *, node *);
83 d15b0b0a Ondrej Zajicek (work)
uint list_length(list *);
84 58ef912c Martin Mares
#endif
85
86
#endif