2 * UCW Library -- Single-Linked Lists
4 * (c) 2005 Martin Mares <mj@ucw.cz>
6 * This software may be freely distributed and used according to the terms
7 * of the GNU Lesser General Public License.
14 * Common header for list nodes.
16 typedef struct snode {
23 typedef struct slist {
24 struct snode head, *last;
28 * Initialize a new single-linked list. Must be called before any other function.
30 static inline void slist_init(slist *l)
32 l->head.next = l->last = NULL;
36 * Return the first node of @l or NULL if @l is empty.
38 static inline void *slist_head(slist *l)
44 * Return the last node of @l or NULL if @l is empty.
46 static inline void *slist_tail(slist *l)
52 * Find the next node to @n or NULL if @n is the last one.
54 static inline void *slist_next(snode *n)
60 * Return a non-zero value iff @l is empty.
62 static inline int slist_empty(slist *l)
68 * Insert a new node in front of all other nodes.
70 static inline void slist_add_head(slist *l, snode *n)
72 n->next = l->head.next;
79 * Insert a new node after all other nodes.
81 static inline void slist_add_tail(slist *l, snode *n)
92 * Insert a new node just after the node @after. To insert a new head, use @slist_add_head() instead.
94 static inline void slist_insert_after(slist *l, snode *what, snode *after)
96 what->next = after->next;
103 * Quickly remove the node next to @after. The node may not exist.
105 static inline void slist_remove_after(slist *l, snode *after)
107 snode *n = after->next;
110 after->next = n->next;
112 l->last = (after == &l->head) ? NULL : after;
117 * Remove the first node in @l. The list can be empty.
119 static inline void slist_remove_head(slist *l)
121 slist_remove_after(l, &l->head);
126 #define SLIST_WALK(n,list) for(n=(void*)(list).head.next; (n); (n)=(void*)((snode*)(n))->next)
127 #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)))
128 #define SLIST_FOR_EACH(type,n,list) for(type n=(void*)(list).head.next; n; n=(void*)((snode*)(n))->next)
130 /* Non-trivial functions */
133 * Find the previous node to @n or NULL if @n is the first one. Beware linear time complexity.
135 void *slist_prev(slist *l, snode *n);
138 * Insert a new node just before the node @before. To insert a new tail, use @slist_add_tail(). Beware linear time complexity.
140 void slist_insert_before(slist *l, snode *what, snode *before);
143 * Remove node @n. Beware linear time complexity.
145 void slist_remove(slist *l, snode *n);
148 * Remove the last node in @l. The list can be empty.
150 static inline void slist_remove_tail(slist *l)
152 slist_remove(l, l->last);
156 * Compute the number of nodes in @l. Beware linear time complexity.
158 static inline uns slist_size(slist *l)
161 SLIST_FOR_EACH(snode *, n, *l)