common/llist.h

   1
   2 #ifndef _LLIST_H
   3 #define _LLIST_H
   4
   5 // this file provides macros which implement common operations on linked lists.
   6 // this saves a little bit of thinking and helps prevent bugs caused by
   7 // forgetting one of the steps.
   8
   9 // call them giving them the node to work on and the names of the fields
  10 // for next, prev, first and last nodes.
  11
  12 // add a node to the end of a linked list
  13 #define LL_ADD_END(O, PREV, NEXT, FIRST, LAST)  \
  14 {       \
  15         if (LAST)       \
  16                 LAST->NEXT = O; \
  17         else    \
  18                 FIRST = O;      \
  19         \
  20         O->PREV = LAST; \
  21         O->NEXT = NULL; \
  22         LAST = O;       \
  23 }
  24
  25 // add a node at the start of a linked list
  26 #define LL_ADD_BEGIN(O, PREV, NEXT, FIRST, LAST)        \
  27 {       \
  28         O->NEXT = FIRST;        \
  29         O->PREV = NULL; \
  30         \
  31         if (FIRST)      \
  32                 FIRST->PREV = O;        \
  33         else    \
  34                 FIRST = LAST = O;       \
  35 }
  36
  37 // insert a node just before another node
  38 #define LL_INSERT_BEFORE(O, BEHIND, PREV, NEXT, FIRST, LAST)    \
  39 {       \
  40         if (BEHIND == FIRST)    \
  41                 FIRST = O;      \
  42         else    \
  43                 BEHIND->PREV->NEXT = O; \
  44         \
  45         O->NEXT = BEHIND;       \
  46         O->PREV = BEHIND->PREV; \
  47         BEHIND->PREV = O;       \
  48 }
  49
  50 // insert a node just after another node
  51 #define LL_INSERT_AFTER(O, AFTER, PREV, NEXT, FIRST, LAST)      \
  52 {       \
  53         if (AFTER == LAST)      \
  54                 LAST = O;       \
  55         else    \
  56                 AFTER->NEXT->PREV = O;  \
  57         \
  58         O->NEXT = AFTER->NEXT;  \
  59         O->PREV = AFTER;        \
  60         AFTER->NEXT = O;        \
  61 }
  62
  63 // remove a node from a linked list
  64 #define LL_REMOVE(O, PREV, NEXT, FIRST, LAST)   \
  65 {       \
  66         if (O == FIRST) \
  67                 FIRST = FIRST->NEXT;    \
  68         else if (O->PREV)       \
  69                 O->PREV->NEXT = O->NEXT;        \
  70         \
  71         if (O == LAST)  \
  72                 LAST = LAST->PREV;      \
  73         else if (O->NEXT)       \
  74                 O->NEXT->PREV = O->PREV;        \
  75 }
  76
  77 // debug function
  78 #define LL_DUMP_LIST(START, PREV, NEXT, NODETYPE)       \
  79 {       \
  80         stat("LL_DUMP_LIST from %s using %s", #START, #NEXT);   \
  81         \
  82         NODETYPE *n = START;    \
  83         int iter = 0;   \
  84         while(n)        \
  85         {       \
  86                 stat("%d: %08x   P:%08x  N:%08x", iter++, n, n->PREV, n->NEXT); \
  87                 n = n->NEXT;    \
  88         }       \
  89 }
  90
  91
  92 #endif
  93
  94