ucw/clists.h

   1 /*
   2  *      UCW Library -- Circular Linked Lists
   3  *
   4  *      (c) 2003--2007 Martin Mares <mj@ucw.cz>
   5  *
   6  *      This software may be freely distributed and used according to the terms
   7  *      of the GNU Lesser General Public License.
   8  */
   9
  10 #ifndef _UCW_CLISTS_H
  11 #define _UCW_CLISTS_H
  12
  13 /**
  14  * Common header for list nodes.
  15  **/
  16 typedef struct cnode {
  17   struct cnode *next, *prev;
  18 } cnode;
  19
  20 /**
  21  * Circilar linked list.
  22  **/
  23 typedef struct clist {
  24   struct cnode head;
  25 } clist;
  26
  27 /**
  28  * Initialize a new circular linked list. Must be called before any other function.
  29  **/
  30 static inline void clist_init(clist *l)
  31 {
  32   cnode *head = &l->head;
  33   head->next = head->prev = head;
  34 }
  35
  36 /**
  37  * Return the first node on @l or NULL if @l is empty.
  38  **/
  39 static inline void *clist_head(clist *l)
  40 {
  41   return (l->head.next != &l->head) ? l->head.next : NULL;
  42 }
  43
  44 /**
  45  * Return the last node on @l or NULL if @l is empty.
  46  **/
  47 static inline void *clist_tail(clist *l)
  48 {
  49   return (l->head.prev != &l->head) ? l->head.prev : NULL;
  50 }
  51
  52 /**
  53  * Find the next node to @n or NULL if @n is the last one.
  54  **/
  55 static inline void *clist_next(clist *l, cnode *n)
  56 {
  57   return (n->next != &l->head) ? (void *) n->next : NULL;
  58 }
  59
  60 /**
  61  * Find the previous node to @n or NULL if @n is the first one.
  62  **/
  63 static inline void *clist_prev(clist *l, cnode *n)
  64 {
  65   return (n->prev != &l->head) ? (void *) n->prev : NULL;
  66 }
  67
  68 /**
  69  * Return a non-zero value iff @l is empty.
  70  **/
  71 static inline int clist_empty(clist *l)
  72 {
  73   return (l->head.next == &l->head);
  74 }
  75
  76 #define CLIST_WALK(n,list) for(n=(void*)(list).head.next; (cnode*)(n) != &(list).head; n=(void*)((cnode*)(n))->next)
  77 #define CLIST_WALK_DELSAFE(n,list,tmp) for(n=(void*)(list).head.next; tmp=(void*)((cnode*)(n))->next, (cnode*)(n) != &(list).head; n=(void*)tmp)
  78 #define CLIST_FOR_EACH(type,n,list) for(type n=(void*)(list).head.next; (cnode*)(n) != &(list).head; n=(void*)((cnode*)(n))->next)
  79 #define CLIST_FOR_EACH_DELSAFE(type,n,list,tmp) for(type n=(void*)(list).head.next; tmp=(void*)((cnode*)(n))->next, (cnode*)(n) != &(list).head; n=(void*)tmp)
  80
  81 #define CLIST_FOR_EACH_BACKWARDS(type,n,list) for(type n=(void*)(list).head.prev; (cnode*)(n) != &(list).head; n=(void*)((cnode*)(n))->prev)
  82
  83 /**
  84  * Insert a new node just after the node @after. To insert a new head, use @clist_add_head() instead.
  85  **/
  86 static inline void clist_insert_after(cnode *what, cnode *after)
  87 {
  88   cnode *before = after->next;
  89   what->next = before;
  90   what->prev = after;
  91   before->prev = what;
  92   after->next = what;
  93 }
  94
  95 /**
  96  * Insert a new node just before the node @before. To insert a new tail, use @clist_add_tail() instead.
  97  **/
  98 static inline void clist_insert_before(cnode *what, cnode *before)
  99 {
 100   cnode *after = before->prev;
 101   what->next = before;
 102   what->prev = after;
 103   before->prev = what;
 104   after->next = what;
 105 }
 106
 107 /**
 108  * Insert a new node in front of all other nodes.
 109  **/
 110 static inline void clist_add_head(clist *l, cnode *n)
 111 {
 112   clist_insert_after(n, &l->head);
 113 }
 114
 115 /**
 116  * Insert a new node after all other nodes.
 117  **/
 118 static inline void clist_add_tail(clist *l, cnode *n)
 119 {
 120   clist_insert_before(n, &l->head);
 121 }
 122
 123 /**
 124  * Remove node @n.
 125  **/
 126 static inline void clist_remove(cnode *n)
 127 {
 128   cnode *before = n->prev;
 129   cnode *after = n->next;
 130   before->next = after;
 131   after->prev = before;
 132 }
 133
 134 /**
 135  * Remove the first node in @l. The list can be empty.
 136  **/
 137 static inline void *clist_remove_head(clist *l)
 138 {
 139   cnode *n = clist_head(l);
 140   if (n)
 141     clist_remove(n);
 142   return n;
 143 }
 144
 145 /**
 146  * Remove the last node in @l. The list can be empty.
 147  **/
 148 static inline void *clist_remove_tail(clist *l)
 149 {
 150   cnode *n = clist_tail(l);
 151   if (n)
 152     clist_remove(n);
 153   return n;
 154 }
 155
 156 /**
 157  * Merge two lists by inserting the list @what just after the node @after in a different list.
 158  * The first list is then cleared.
 159  **/
 160 static inline void clist_insert_list_after(clist *what, cnode *after)
 161 {
 162   if (!clist_empty(what))
 163     {
 164       cnode *w = &what->head;
 165       w->prev->next = after->next;
 166       after->next->prev = w->prev;
 167       w->next->prev = after;
 168       after->next = w->next;
 169       clist_init(what);
 170     }
 171 }
 172
 173 /**
 174  * Compute the number of nodes in @l. Beware linear time complexity.
 175  **/
 176 static inline uns clist_size(clist *l)
 177 {
 178   uns i = 0;
 179   CLIST_FOR_EACH(cnode *, n, *l)
 180     i++;
 181   return i;
 182 }
 183
 184 #endif