Return to lists.h CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird / lib

bird 1.6.3

    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: /* WALK_LIST_FIRST supposes that called code removes each processed node */
   57: #define WALK_LIST_FIRST(n,list) \
   58:      while(n=HEAD(list), (NODE (n))->next)
   59: #define WALK_LIST_BACKWARDS(n,list) for(n=TAIL(list);(NODE (n))->prev; \
   60: 				n=(void *)((NODE (n))->prev))
   61: #define WALK_LIST_BACKWARDS_DELSAFE(n,prv,list) \
   62:      for(n=TAIL(list); prv=(void *)((NODE (n))->prev); n=(void *) prv)
   63: 
   64: #define EMPTY_LIST(list) (!(list).head->next)
   65: 
   66: 
   67: #ifndef _BIRD_LISTS_C_
   68: #define LIST_INLINE static inline
   69: #include "lib/lists.c"
   70: #undef LIST_INLINE
   71: 
   72: #else /* _BIRD_LISTS_C_ */
   73: #define LIST_INLINE
   74: void add_tail(list *, node *);
   75: void add_head(list *, node *);
   76: void rem_node(node *);
   77: void add_tail_list(list *, list *);
   78: void init_list(list *);
   79: void insert_node(node *, node *);
   80: #endif
   81: 
   82: #endif