lib/lists.h

   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 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 } list;
  44
  45
  46 #define NODE (node *)
  47 #define HEAD(list) ((void *)((list).head))
  48 #define TAIL(list) ((void *)((list).tail))
  49 #define NODE_NEXT(n) ((void *)((NODE (n))->next))
  50 #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 #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 #define WALK_LIST_DELSAFE(n,nxt,list) \
  55   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 /* 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 #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
  67 #define EMPTY_LIST(list) (!(list).head->next)
  68
  69
  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 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 uint list_length(list *);
  84 #endif
  85
  86 #endif