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