Return to lists.h CVS log

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

Annotation of embedaddon/bird2/lib/lists.h, revision 1.1

1.1     ! misho       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