ucw/slists.h

   1 /*
   2  *      UCW Library -- Single-Linked Lists
   3  *
   4  *      (c) 2005 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_SLISTS_H
  12 #define _UCW_SLISTS_H
  13
  14 #ifdef CONFIG_UCW_CLEAN_ABI
  15 #define slist_insert_before ucw_slist_insert_before
  16 #define slist_prev ucw_slist_prev
  17 #define slist_remove ucw_slist_remove
  18 #endif
  19
  20 /**
  21  * Common header for list nodes.
  22  **/
  23 typedef struct snode {
  24   struct snode *next;
  25 } snode;
  26
  27 /**
  28  * Single-linked list.
  29  **/
  30 typedef struct slist {
  31   struct snode head, *last;
  32 } slist;
  33
  34 /**
  35  * Initialize a new single-linked list. Must be called before any other function.
  36  **/
  37 static inline void slist_init(slist *l)
  38 {
  39   l->head.next = l->last = NULL;
  40 }
  41
  42 /**
  43  * Return the first node of @l or NULL if @l is empty.
  44  **/
  45 static inline void *slist_head(slist *l)
  46 {
  47   return l->head.next;
  48 }
  49
  50 /**
  51  * Return the last node of @l or NULL if @l is empty.
  52  **/
  53 static inline void *slist_tail(slist *l)
  54 {
  55   return l->last;
  56 }
  57
  58 /**
  59  * Find the next node to @n or NULL if @n is the last one.
  60  **/
  61 static inline void *slist_next(snode *n)
  62 {
  63   return n->next;
  64 }
  65
  66 /**
  67  * Return a non-zero value iff @l is empty.
  68  **/
  69 static inline int slist_empty(slist *l)
  70 {
  71   return !l->head.next;
  72 }
  73
  74 /**
  75  * Insert a new node in front of all other nodes.
  76  **/
  77 static inline void slist_add_head(slist *l, snode *n)
  78 {
  79   n->next = l->head.next;
  80   l->head.next = n;
  81   if (!l->last)
  82     l->last = n;
  83 }
  84
  85 /**
  86  * Insert a new node after all other nodes.
  87  **/
  88 static inline void slist_add_tail(slist *l, snode *n)
  89 {
  90   if (l->last)
  91     l->last->next = n;
  92   else
  93     l->head.next = n;
  94   n->next = NULL;
  95   l->last = n;
  96 }
  97
  98 /**
  99  * Insert a new node just after the node @after. To insert a new head, use @slist_add_head() instead.
 100  **/
 101 static inline void slist_insert_after(slist *l, snode *what, snode *after)
 102 {
 103   what->next = after->next;
 104   after->next = what;
 105   if (!what->next)
 106     l->last = what;
 107 }
 108
 109 /**
 110  * Quickly remove the node next to @after. The node may not exist.
 111  **/
 112 static inline void slist_remove_after(slist *l, snode *after)
 113 {
 114   snode *n = after->next;
 115   if (n)
 116     {
 117       after->next = n->next;
 118       if (l->last == n)
 119         l->last = (after == &l->head) ? NULL : after;
 120     }
 121 }
 122
 123 /**
 124  * Remove the first node in @l. The list can be empty.
 125  **/
 126 static inline void *slist_remove_head(slist *l)
 127 {
 128   snode *n = slist_head(l);
 129   if (n)
 130     slist_remove_after(l, &l->head);
 131   return n;
 132 }
 133
 134 /* Loops */
 135
 136 /**
 137  * 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.
 138  * The list should not be changed during this loop command.
 139  **/
 140 #define SLIST_WALK(n,list) for(n=(void*)(list).head.next; (n); (n)=(void*)((snode*)(n))->next)
 141
 142 /**
 143  * Same as @SLIST_WALK(), but allows removal of the current node. This macro requires one more variable to store the pointer to the previous node (useful for @slist_remove_after()).
 144  **/
 145 #define SLIST_WALK_DELSAFE(n,list,prev) for((prev)=(void*)&(list).head; (n)=(void*)((snode*)prev)->next; (prev)=(((snode*)(prev))->next==(snode*)(n) ? (void*)(n) : (void*)(prev)))
 146
 147 /**
 148  * Same as @SLIST_WALK(), but it defines the variable for the current node in place. @type should be a pointer type.
 149  **/
 150 #define SLIST_FOR_EACH(type,n,list) for(type n=(void*)(list).head.next; n; n=(void*)((snode*)(n))->next)
 151
 152 /* Non-trivial functions */
 153
 154 /**
 155  * Find the previous node to @n or NULL if @n is the first one. Beware linear time complexity.
 156  **/
 157 void *slist_prev(slist *l, snode *n);
 158
 159 /**
 160  * Insert a new node just before the node @before. To insert a new tail, use @slist_add_tail(). Beware linear time complexity.
 161  **/
 162 void slist_insert_before(slist *l, snode *what, snode *before);
 163
 164 /**
 165  * Remove node @n. Beware linear time complexity.
 166  **/
 167 void slist_remove(slist *l, snode *n);
 168
 169 /**
 170  * Remove the last node in @l. The list can be empty.
 171  **/
 172 static inline void slist_remove_tail(slist *l)
 173 {
 174   slist_remove(l, l->last);
 175 }
 176
 177 /**
 178  * Merge two lists by inserting the list @what in front of all other nodes in a different list @l.
 179  * The first list is then cleared.
 180  **/
 181 static inline void slist_add_list_head(slist *l, slist *what)
 182 {
 183   if (!slist_empty(what))
 184     {
 185       if (!slist_empty(l))
 186         what->last->next = l->head.next;
 187       else
 188         l->last = what->last;
 189       l->head.next = what->head.next;
 190       slist_init(what);
 191     }
 192 }
 193
 194 /**
 195  * Merge two lists by inserting the list @what after all other nodes in a different list @l.
 196  * The first list is then cleared.
 197  **/
 198 static inline void slist_add_list_tail(slist *l, slist *what)
 199 {
 200   if (!slist_empty(what))
 201     {
 202       if (!slist_empty(l))
 203         l->last->next = what->head.next;
 204       else
 205         l->head.next = what->head.next;
 206       l->last = what->last;
 207       slist_init(what);
 208     }
 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 slist_move(slist *to, slist *from)
 216 {
 217   to->head.next = from->head.next;
 218   to->last = from->last;
 219   slist_init(from);
 220 }
 221
 222 /**
 223  * Compute the number of nodes in @l. Beware linear time complexity.
 224  **/
 225 static inline uint slist_size(slist *l)
 226 {
 227   uint i = 0;
 228   SLIST_FOR_EACH(snode *, n, *l)
 229     i++;
 230   return i;
 231 }
 232
 233 #endif