ucw/clists.h

   1 /*
   2  *      UCW Library -- Circular Linked Lists
   3  *
   4  *      (c) 2003--2010 Martin Mares <mj@ucw.cz>
   5  *      (c) 2017 Pavel Charvat <pchar@ucw.cz>
   6  *
   7  *      This software may be freely distributed and used according to the terms
   8  *      of the GNU Lesser General Public License.
   9  */
  10
  11 #ifndef _UCW_CLISTS_H
  12 #define _UCW_CLISTS_H
  13
  14 /**
  15  * Common header for list nodes.
  16  **/
  17 typedef struct cnode {
  18   struct cnode *next, *prev;
  19 } cnode;
  20
  21 /**
  22  * Circular doubly linked list.
  23  **/
  24 typedef struct clist {
  25   struct cnode head;
  26 } clist;
  27
  28 /**
  29  * Initialize a new circular linked list. Must be called before any other function.
  30  **/
  31 static inline void clist_init(clist *l)
  32 {
  33   cnode *head = &l->head;
  34   head->next = head->prev = head;
  35 }
  36
  37 /**
  38  * Return the first node on @l or NULL if @l is empty.
  39  **/
  40 static inline void *clist_head(clist *l)
  41 {
  42   return (l->head.next != &l->head) ? l->head.next : NULL;
  43 }
  44
  45 /**
  46  * Return the last node on @l or NULL if @l is empty.
  47  **/
  48 static inline void *clist_tail(clist *l)
  49 {
  50   return (l->head.prev != &l->head) ? l->head.prev : NULL;
  51 }
  52
  53 /**
  54  * Find the next node to @n or NULL if @n is the last one.
  55  **/
  56 static inline void *clist_next(clist *l, cnode *n)
  57 {
  58   return (n->next != &l->head) ? (void *) n->next : NULL;
  59 }
  60
  61 /**
  62  * Find the previous node to @n or NULL if @n is the first one.
  63  **/
  64 static inline void *clist_prev(clist *l, cnode *n)
  65 {
  66   return (n->prev != &l->head) ? (void *) n->prev : NULL;
  67 }
  68
  69 /**
  70  * Return a non-zero value iff @l is empty.
  71  **/
  72 static inline int clist_empty(clist *l)
  73 {
  74   return (l->head.next == &l->head);
  75 }
  76
  77 /**
  78  * 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.
  79  * The list should not be changed during this loop command.
  80  **/
  81 #define CLIST_WALK(n,list) for(n=(void*)(list).head.next; (cnode*)(n) != &(list).head; n=(void*)((cnode*)(n))->next)
  82
  83 /**
  84  * Same as @CLIST_WALK(), but allows removal of the current node. This macro requires one more variable to store some temporary pointers.
  85  **/
  86 #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)
  87
  88 /**
  89  * Same as @CLIST_WALK(), but it defines the variable for the current node in place. @type should be a pointer type.
  90  **/
  91 #define CLIST_FOR_EACH(type,n,list) for(type n=(void*)(list).head.next; (cnode*)(n) != &(list).head; n=(void*)((cnode*)(n))->next)
  92
  93 /**
  94  * 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.
  95  **/
  96 #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)
  97
  98 /**
  99  * Reversed version of @CLIST_FOR_EACH().
 100  **/
 101 #define CLIST_FOR_EACH_BACKWARDS(type,n,list) for(type n=(void*)(list).head.prev; (cnode*)(n) != &(list).head; n=(void*)((cnode*)(n))->prev)
 102
 103 /**
 104  * Insert a new node just after the node @after. To insert at the head of the list, use @clist_add_head() instead.
 105  **/
 106 static inline void clist_insert_after(cnode *what, cnode *after)
 107 {
 108   cnode *before = after->next;
 109   what->next = before;
 110   what->prev = after;
 111   before->prev = what;
 112   after->next = what;
 113 }
 114
 115 /**
 116  * Insert a new node just before the node @before. To insert at the tail of the list, use @clist_add_tail() instead.
 117  **/
 118 static inline void clist_insert_before(cnode *what, cnode *before)
 119 {
 120   cnode *after = before->prev;
 121   what->next = before;
 122   what->prev = after;
 123   before->prev = what;
 124   after->next = what;
 125 }
 126
 127 /**
 128  * Insert a new node in front of all other nodes.
 129  **/
 130 static inline void clist_add_head(clist *l, cnode *n)
 131 {
 132   clist_insert_after(n, &l->head);
 133 }
 134
 135 /**
 136  * Insert a new node after all other nodes.
 137  **/
 138 static inline void clist_add_tail(clist *l, cnode *n)
 139 {
 140   clist_insert_before(n, &l->head);
 141 }
 142
 143 /**
 144  * Remove node @n.
 145  **/
 146 static inline void clist_remove(cnode *n)
 147 {
 148   cnode *before = n->prev;
 149   cnode *after = n->next;
 150   before->next = after;
 151   after->prev = before;
 152 }
 153
 154 /**
 155  * Remove the first node in @l, if it exists. Return the pointer to that node or NULL.
 156  **/
 157 static inline void *clist_remove_head(clist *l)
 158 {
 159   cnode *n = clist_head(l);
 160   if (n)
 161     clist_remove(n);
 162   return n;
 163 }
 164
 165 /**
 166  * Remove the last node in @l, if it exists. Return the pointer to that node or NULL.
 167  **/
 168 static inline void *clist_remove_tail(clist *l)
 169 {
 170   cnode *n = clist_tail(l);
 171   if (n)
 172     clist_remove(n);
 173   return n;
 174 }
 175
 176 /**
 177  * Merge two lists by inserting the list @what just after the node @after in a different list.
 178  * The first list is then cleared.
 179  **/
 180 static inline void clist_insert_list_after(clist *what, cnode *after)
 181 {
 182   if (!clist_empty(what))
 183     {
 184       cnode *w = &what->head;
 185       w->prev->next = after->next;
 186       after->next->prev = w->prev;
 187       w->next->prev = after;
 188       after->next = w->next;
 189       clist_init(what);
 190     }
 191 }
 192
 193 /**
 194  * Merge two lists by inserting the list @what in front of all other nodes in a different list @l.
 195  * The first list is then cleared.
 196  **/
 197 static inline void clist_add_list_head(clist *l, clist *what)
 198 {
 199   clist_insert_list_after(what, &l->head);
 200 }
 201
 202 /**
 203  * Merge two lists by inserting the list @what after all other nodes in a different list @l.
 204  * The first list is then cleared.
 205  **/
 206 static inline void clist_add_list_tail(clist *l, clist *what)
 207 {
 208   clist_insert_list_after(what, l->head.prev);
 209 }
 210
 211 /**
 212  * Move all items from a source list to a destination list. The source list
 213  * becomes empty, the original contents of the destination list are destroyed.
 214  **/
 215 static inline void clist_move(clist *to, clist *from)
 216 {
 217   clist_init(to);
 218   clist_insert_list_after(from, &to->head);
 219   clist_init(from);
 220 }
 221
 222 /**
 223  * Compute the number of nodes in @l. Beware of linear time complexity.
 224  **/
 225 static inline uint clist_size(clist *l)
 226 {
 227   uint i = 0;
 228   CLIST_FOR_EACH(cnode *, n, *l)
 229     i++;
 230   return i;
 231 }
 232
 233 /**
 234  * Remove a node @n and mark it as unlinked by setting the previous and next pointers to NULL.
 235  **/
 236 static inline void clist_unlink(cnode *n)
 237 {
 238   clist_remove(n);
 239   n->prev = n->next = NULL;
 240 }
 241
 242 /**
 243  * Remove the first node on @l and mark it as unlinked.
 244  * Return the pointer to that node or NULL.
 245  **/
 246 static inline void *clist_unlink_head(clist *l)
 247 {
 248   cnode *n = clist_head(l);
 249   if (n)
 250     clist_unlink(n);
 251   return n;
 252 }
 253
 254 /**
 255  * Remove the last node on @l and mark it as unlinked.
 256  * Return the pointer to that node or NULL.
 257  **/
 258 static inline void *clist_unlink_tail(clist *l)
 259 {
 260   cnode *n = clist_tail(l);
 261   if (n)
 262     clist_unlink(n);
 263   return n;
 264 }
 265
 266 /**
 267  * Check if a node is linked a list. Unlinked nodes are recognized by having their
 268  * previous and next pointers equal to NULL. Returns 0 or 1.
 269  *
 270  * Nodes initialized to all zeroes are unlinked, inserting a node anywhere in a list
 271  * makes it linked. Normal removal functions like @clist_remove() do not mark nodes
 272  * as unlinked, you need to call @clist_unlink() instead.
 273  **/
 274 static inline int clist_is_linked(cnode *n)
 275 {
 276   return !!n->next;
 277 }
 278
 279 #endif