ucw/slists.h

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