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   snode *n = slist_head(l);
 122   if (n)
 123     slist_remove_after(l, &l->head);
 124   return n;
 125 }
 126
 127 /* Loops */
 128
 129 /**
 130  * 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.
 131  * The list should not be changed during this loop command.
 132  **/
 133 #define SLIST_WALK(n,list) for(n=(void*)(list).head.next; (n); (n)=(void*)((snode*)(n))->next)
 134
 135 /**
 136  * 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()).
 137  **/
 138 #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)))
 139
 140 /**
 141  * Same as @SLIST_WALK(), but it defines the variable for the current node in place. @type should be a pointer type.
 142  **/
 143 #define SLIST_FOR_EACH(type,n,list) for(type n=(void*)(list).head.next; n; n=(void*)((snode*)(n))->next)
 144
 145 /* Non-trivial functions */
 146
 147 /**
 148  * Find the previous node to @n or NULL if @n is the first one. Beware linear time complexity.
 149  **/
 150 void *slist_prev(slist *l, snode *n);
 151
 152 /**
 153  * Insert a new node just before the node @before. To insert a new tail, use @slist_add_tail(). Beware linear time complexity.
 154  **/
 155 void slist_insert_before(slist *l, snode *what, snode *before);
 156
 157 /**
 158  * Remove node @n. Beware linear time complexity.
 159  **/
 160 void slist_remove(slist *l, snode *n);
 161
 162 /**
 163  * Remove the last node in @l. The list can be empty.
 164  **/
 165 static inline void slist_remove_tail(slist *l)
 166 {
 167   slist_remove(l, l->last);
 168 }
 169
 170 /**
 171  * Compute the number of nodes in @l. Beware linear time complexity.
 172  **/
 173 static inline uns slist_size(slist *l)
 174 {
 175   uns i = 0;
 176   SLIST_FOR_EACH(snode *, n, *l)
 177     i++;
 178   return i;
 179 }
 180
 181 #endif