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

#ifndef _BIRD_LISTS_H_
#define _BIRD_LISTS_H_

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

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

29 30 31 32 33 34 35 36 37 38 39 40 41 42
typedef union list {			/* In fact two overlayed nodes */
  struct {				/* Head node */
    struct node head_node;
    void *head_padding;
  };
  struct {				/* Tail node */
    void *tail_padding;
    struct node tail_node;
  };
  struct {				/* Split to separate pointers */
    struct node *head;
    struct node *null;
    struct node *tail;
  };
43 44
} list;

45

46 47 48
#define NODE (node *)
#define HEAD(list) ((void *)((list).head))
#define TAIL(list) ((void *)((list).tail))
49
#define NODE_NEXT(n) ((void *)((NODE (n))->next))
50 51
#define NODE_VALID(n) ((NODE (n))->next)
#define WALK_LIST(n,list) for(n=HEAD(list); NODE_VALID(n); n=NODE_NEXT(n))
52 53
#define WALK_LIST2(n,nn,list,pos) \
  for(nn=(list).head; NODE_VALID(nn) && (n=SKIP_BACK(typeof(*n),pos,nn)); nn=nn->next)
54
#define WALK_LIST_DELSAFE(n,nxt,list) \
55
     for(n=HEAD(list); nxt=NODE_NEXT(n); n=(void *) nxt)
56 57 58
/* WALK_LIST_FIRST supposes that called code removes each processed node */
#define WALK_LIST_FIRST(n,list) \
     while(n=HEAD(list), (NODE (n))->next)
59 60 61 62
#define WALK_LIST_BACKWARDS(n,list) for(n=TAIL(list);(NODE (n))->prev; \
				n=(void *)((NODE (n))->prev))
#define WALK_LIST_BACKWARDS_DELSAFE(n,prv,list) \
     for(n=TAIL(list); prv=(void *)((NODE (n))->prev); n=(void *) prv)
63

64 65
#define EMPTY_LIST(list) (!(list).head->next)

66 67 68 69 70 71 72 73

#ifndef _BIRD_LISTS_C_
#define LIST_INLINE static inline
#include "lib/lists.c"
#undef LIST_INLINE

#else /* _BIRD_LISTS_C_ */
#define LIST_INLINE
74 75 76 77 78 79 80 81 82
void add_tail(list *, node *);
void add_head(list *, node *);
void rem_node(node *);
void add_tail_list(list *, list *);
void init_list(list *);
void insert_node(node *, node *);
#endif

#endif