lib/lists.h

   1 /*
   2  *      Sherlock Library -- Linked Lists
   3  *
   4  *      (c) 1997--1999 Martin Mares <mj@ucw.cz>
   5  */
   6
   7 #ifndef _SHERLOCK_LISTS_H
   8 #define _SHERLOCK_LISTS_H
   9
  10 /*
  11  * I admit the list structure is very tricky and also somewhat awkward,
  12  * but it's both efficient and easy to manipulate once one understands the
  13  * basic trick: The list head always contains two synthetic nodes which are
  14  * always present in the list: the head and the tail. But as the `next'
  15  * entry of the tail and the `prev' entry of the head are both NULL, the
  16  * nodes can overlap each other:
  17  *
  18  *     head    head_node.next
  19  *     null    head_node.prev  tail_node.next
  20  *     tail                    tail_node.prev
  21  */
  22
  23 typedef struct node {
  24   struct node *next, *prev;
  25 } node;
  26
  27 typedef struct list {                   /* In fact two overlayed nodes */
  28   struct node *head, *null, *tail;
  29 } list;
  30
  31 #define NODE (node *)
  32 #define HEAD(list) ((void *)((list).head))
  33 #define TAIL(list) ((void *)((list).tail))
  34 #define WALK_LIST(n,list) for(n=HEAD(list);(NODE (n))->next; \
  35                                 n=(void *)((NODE (n))->next))
  36 #define DO_FOR_ALL(n,list) WALK_LIST(n,list)
  37 #define WALK_LIST_DELSAFE(n,nxt,list) \
  38      for(n=HEAD(list); nxt=(void *)((NODE (n))->next); n=(void *) nxt)
  39 #define WALK_LIST_BACKWARDS(n,list) for(n=TAIL(list);(NODE (n))->prev; \
  40                                 n=(void *)((NODE (n))->prev))
  41 #define WALK_LIST_BACKWARDS_DELSAFE(n,prv,list) \
  42      for(n=TAIL(list); prv=(void *)((NODE (n))->prev); n=(void *) prv)
  43
  44 #define EMPTY_LIST(list) (!(list).head->next)
  45
  46 void add_tail(list *, node *);
  47 void add_head(list *, node *);
  48 void rem_node(node *);
  49 void add_tail_list(list *, list *);
  50 void init_list(list *);
  51 void insert_node(node *, node *);
  52
  53 #if !defined(_SHERLOCK_LISTS_C) && defined(__GNUC__)
  54 #define LIST_INLINE extern inline
  55 #include "lib/lists.c"
  56 #undef LIST_INLINE
  57 #else
  58 #define LIST_INLINE
  59 #endif
  60
  61 #endif