ucw/clists.h

   1 /*
   2  *      UCW Library -- Circular Linked Lists
   3  *
   4  *      (c) 2003--2010 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  * Circular doubly 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 /**
  77  * Loop over all nodes in the @list and perform the next C statement on them. The current node is stored in @n which must be defined before as pointer to any type.
  78  * The list should not be changed during this loop command.
  79  **/
  80 #define CLIST_WALK(n,list) for(n=(void*)(list).head.next; (cnode*)(n) != &(list).head; n=(void*)((cnode*)(n))->next)
  81
  82 /**
  83  * Same as @CLIST_WALK(), but allows removal of the current node. This macro requires one more variable to store some temporary pointers.
  84  **/
  85 #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)
  86
  87 /**
  88  * Same as @CLIST_WALK(), but it defines the variable for the current node in place. @type should be a pointer type.
  89  **/
  90 #define CLIST_FOR_EACH(type,n,list) for(type n=(void*)(list).head.next; (cnode*)(n) != &(list).head; n=(void*)((cnode*)(n))->next)
  91
  92 /**
  93  * Same as @CLIST_WALK_DELSAFE(), but it defines the variable for the current node in place. @type should be a pointer type. The temporary variable must be still known before.
  94  **/
  95 #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)
  96
  97 /**
  98  * Reversed version of @CLIST_FOR_EACH().
  99  **/
 100 #define CLIST_FOR_EACH_BACKWARDS(type,n,list) for(type n=(void*)(list).head.prev; (cnode*)(n) != &(list).head; n=(void*)((cnode*)(n))->prev)
 101
 102 /**
 103  * Insert a new node just after the node @after. To insert at the head of the list, use @clist_add_head() instead.
 104  **/
 105 static inline void clist_insert_after(cnode *what, cnode *after)
 106 {
 107   cnode *before = after->next;
 108   what->next = before;
 109   what->prev = after;
 110   before->prev = what;
 111   after->next = what;
 112 }
 113
 114 /**
 115  * Insert a new node just before the node @before. To insert at the tail of the list, use @clist_add_tail() instead.
 116  **/
 117 static inline void clist_insert_before(cnode *what, cnode *before)
 118 {
 119   cnode *after = before->prev;
 120   what->next = before;
 121   what->prev = after;
 122   before->prev = what;
 123   after->next = what;
 124 }
 125
 126 /**
 127  * Insert a new node in front of all other nodes.
 128  **/
 129 static inline void clist_add_head(clist *l, cnode *n)
 130 {
 131   clist_insert_after(n, &l->head);
 132 }
 133
 134 /**
 135  * Insert a new node after all other nodes.
 136  **/
 137 static inline void clist_add_tail(clist *l, cnode *n)
 138 {
 139   clist_insert_before(n, &l->head);
 140 }
 141
 142 /**
 143  * Remove node @n.
 144  **/
 145 static inline void clist_remove(cnode *n)
 146 {
 147   cnode *before = n->prev;
 148   cnode *after = n->next;
 149   before->next = after;
 150   after->prev = before;
 151 }
 152
 153 /**
 154  * Remove the first node in @l, if it exists. Return the pointer to that node or NULL.
 155  **/
 156 static inline void *clist_remove_head(clist *l)
 157 {
 158   cnode *n = clist_head(l);
 159   if (n)
 160     clist_remove(n);
 161   return n;
 162 }
 163
 164 /**
 165  * Remove the last node in @l, if it exists. Return the pointer to that node or NULL.
 166  **/
 167 static inline void *clist_remove_tail(clist *l)
 168 {
 169   cnode *n = clist_tail(l);
 170   if (n)
 171     clist_remove(n);
 172   return n;
 173 }
 174
 175 /**
 176  * Merge two lists by inserting the list @what just after the node @after in a different list.
 177  * The first list is then cleared.
 178  **/
 179 static inline void clist_insert_list_after(clist *what, cnode *after)
 180 {
 181   if (!clist_empty(what))
 182     {
 183       cnode *w = &what->head;
 184       w->prev->next = after->next;
 185       after->next->prev = w->prev;
 186       w->next->prev = after;
 187       after->next = w->next;
 188       clist_init(what);
 189     }
 190 }
 191
 192 /**
 193  * Move all items from a source list to a destination list. The source list
 194  * becomes empty, the original contents of the destination list are destroyed.
 195  **/
 196 static inline void clist_move(clist *to, clist *from)
 197 {
 198   clist_init(to);
 199   clist_insert_list_after(from, &to->head);
 200   clist_init(from);
 201 }
 202
 203 /**
 204  * Compute the number of nodes in @l. Beware of linear time complexity.
 205  **/
 206 static inline uns clist_size(clist *l)
 207 {
 208   uns i = 0;
 209   CLIST_FOR_EACH(cnode *, n, *l)
 210     i++;
 211   return i;
 212 }
 213
 214 /**
 215  * Remove a node @n and mark it as unlinked by setting the previous and next pointers to NULL.
 216  **/
 217 static inline void clist_unlink(cnode *n)
 218 {
 219   clist_remove(n);
 220   n->prev = n->next = NULL;
 221 }
 222
 223 /**
 224  * Remove the first node on @l and mark it as unlinked.
 225  * Return the pointer to that node or NULL.
 226  **/
 227 static inline void *clist_unlink_head(clist *l)
 228 {
 229   cnode *n = clist_head(l);
 230   if (n)
 231     clist_unlink(n);
 232   return n;
 233 }
 234
 235 /**
 236  * Remove the last node on @l and mark it as unlinked.
 237  * Return the pointer to that node or NULL.
 238  **/
 239 static inline void *clist_unlink_tail(clist *l)
 240 {
 241   cnode *n = clist_tail(l);
 242   if (n)
 243     clist_unlink(n);
 244   return n;
 245 }
 246
 247 /**
 248  * Check if a node is linked a list. Unlinked nodes are recognized by having their
 249  * previous and next pointers equal to NULL. Returns 0 or 1.
 250  *
 251  * Nodes initialized to all zeroes are unlinked, inserting a node anywhere in a list
 252  * makes it linked. Normal removal functions like clist_remove() do not mark nodes
 253  * as unlinked, you need to call clist_unlink() instead.
 254  **/
 255 static inline int clist_is_linked(cnode *n)
 256 {
 257   return !!n->next;
 258 }
 259
 260 #endif