Allow for static initialisation.
[libeze] / ez-list.h
1 /* ez-list.h: Double-linked list implementation (aka 'exec lists')
2
3    Copyright (C) 2010,2019 Michael Zucchi
4
5    This program is free software: you can redistribute it and/or
6    modify it under the terms of the GNU Lesser General Public License
7    as published by the Free Software Foundation, either version 3 of
8    the License, or (at your option) any later version.
9
10    This program is distributed in the hope that it will be useful,
11    but WITHOUT ANY WARRANTY; without even the implied warranty of
12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13    GNU General Public License for more details.
14
15    You should have received a copy of the GNU Lesser General Public
16    License along with this program. If not, see
17    <http://www.gnu.org/licenses/>.
18 */
19 #ifndef _EZ_LIST_H
20 #define _EZ_LIST_H
21
22 #include <ez-node.h>
23
24 /**
25  * ez-list is a low-level double-linked list implementation that works
26  * without memory allocation.  
27  *
28  * o Adding to or removing from either end is an O(1) operation.
29  * o Removing any given node is an O(1) operation.
30  * o Nodes can only belong to a single list at any given time.
31  * o No operations can fail.
32  * o No pointers are checked.
33  * o The list is not thread-safe.
34  *
35  * All list functions are implemented as inline functions.
36  *
37  * This is how to iterate all elements in forward order:
38
39         struct list_item {
40                 struct ez_node ln;
41                 // item data
42         }
43
44         struct list list = EZ_INIT_LIST(list);
45
46         struct list_item *work = ez_list_head(list);
47         struct list_item *next = ez_list_succ(list);
48
49         while (next) {
50
51                 // operate on 'work'.
52                 // ez_node_remove() may be called here
53
54                 succ = next;
55                 next = ez_list_succ(list);
56         }
57
58  * For reverse order simply use ez_list_tail() and ez_node_pred().
59  *
60  * Functions use untyped pointers for nodes for convenience but they
61  * must start with struct ez_node.
62  *
63  * Historical note: this is a re-implementation of Amiga's kernel
64  * minimal lists.  A minor change is that functions take and return
65  * untyped nodes.
66  */
67
68 typedef struct ez_list ez_list;
69
70
71 /**
72  * A list header.
73  *
74  * This represents two overlapping nodes which share a common pointer.
75  * It must be initialised using ez_list_init() or EZ_INIT_LIST()
76  * before use.
77  *
78  * tail is always NULL.
79  *
80  * The pointers are volatile to avoid aliasing issues with C99+.
81  */
82 struct ez_list {
83         struct ez_node * volatile head;
84         struct ez_node * volatile tail;
85         struct ez_node * volatile tail_pred;
86 };
87
88 /**
89  * Initialise a list statically.
90  *
91  * struct ez_list list = EZ_INIT_LIST(list);
92  */
93 #define EZ_INIT_LIST(l) { (struct ez_node *)&(l).tail, (void *)0, (struct ez_node *)&l }
94
95 /**
96  * Initialise a list at runtime.
97  * 
98  */
99 static __inline__ void ez_list_init(struct ez_list *l) {
100         l->head = (struct ez_node *)&l->tail;
101         l->tail = (struct ez_node *)0L;
102         l->tail_pred = (struct ez_node *)&l->head;
103 }
104
105 /**
106  * Add a node to the head of the list.
107  */
108 static __inline__ void ez_list_addhead(struct ez_list *l, void *np) {
109         struct ez_node *n = np, *head = l->head;
110
111         n->u.list.succ = head;
112         n->u.list.pred = (struct ez_node *)&l->head;
113         head->u.list.pred = n;
114         l->head = n;
115 }
116
117 /**
118  * Add a node to the tail of the list.
119  */
120 static __inline__ void ez_list_addtail(struct ez_list *l, void *np) {
121         struct ez_node *n = np, *tail_pred = l->tail_pred;
122
123         n->u.list.pred = tail_pred;
124         n->u.list.succ = (struct ez_node *)&l->tail;
125         tail_pred->u.list.succ = n;
126         l->tail_pred = n;
127 }
128
129 /**
130  * Remove a node from a list.
131  *
132  * The node must already belong to a list.
133  *
134  * This performs a software memory barrier after
135  * write do workaround aliasing issues with gcc.
136  */
137 static __inline__ void ez_node_remove(void *np) {
138         struct ez_node *n = np, *pred = n->u.list.pred, *succ = n->u.list.succ;
139         
140         pred->u.list.succ = succ;
141         succ->u.list.pred = pred;
142 }
143
144 /**
145  * Remove a node from the head of the list.
146  *
147  * @return the head node, or NULL if the list is empty.
148  */
149 static __inline__ void *ez_list_remhead(struct ez_list *l) {
150         struct ez_node *n = l->head;
151         struct ez_node *s = n->u.list.succ;
152
153         if (s) {
154                 s->u.list.pred = (struct ez_node *)&l->head;
155                 l->head = s;
156                 return n;
157         } else
158                 return 0L;
159 }
160
161 /**
162  * Remove a node from the tail of the list.
163  *
164  * @return the tail node, or NULL if the list is empty.
165  */
166 static __inline__ void *ez_list_remtail(struct ez_list *l) {
167         struct ez_node *n = l->tail_pred;
168         struct ez_node *p = n->u.list.pred;
169
170         if (p) {
171                 p->u.list.succ = (struct ez_node *)&l->tail;
172                 l->tail_pred = p;
173                 return n;
174         } else
175                 return 0L;
176 }
177
178 /**
179  * Insert a node after a given node.
180  *
181  * @param l list.
182  * @param n node to insert.
183  * @param p node that is already present in list, or NULL (insert after head).
184  */
185 static __inline__ void ez_list_insert_after(struct ez_list *l, void *n, void *p) {
186         struct ez_node *nn = n;
187         struct ez_node *pp = p ? p : (struct ez_node *)&l->head;
188         struct ez_node *succ = pp->u.list.succ;
189
190         nn->u.list.succ = succ;
191         nn->u.list.pred = pp;
192         succ->u.list.pred = nn;
193         pp->u.list.succ = nn;
194 }
195
196 /**
197  * Insert a node before a given node.
198  *
199  * @param l list.
200  * @param n node to insert.
201  * @param p node that is already present in list, or NULL (insert before tail).
202  */
203 static __inline__ void ez_list_insert(struct ez_list *l, void *n, void *p) {
204         struct ez_node *nn = n;
205         struct ez_node *pp = p ? p : (struct ez_node *)&l->tail;
206         struct ez_node *pred = pp->u.list.pred;
207         
208         nn->u.list.succ = pp;
209         nn->u.list.pred = pred;
210         pred->u.list.succ = nn;
211         pp->u.list.pred = nn;
212 }
213
214 /**
215  * Find the length of the list.
216  *
217  * This is an O(n) operation, use ez_list_empty() to check for empty
218  * lists.
219  */
220 static __inline__ int ez_list_size(struct ez_list *l) {
221         struct ez_node *w, *n;
222         int size = 0;
223
224         for (w = l->head, n = w->u.list.succ; n; w = n, n = n->u.list.succ)
225                 size += 1;
226
227         return size;
228 }
229
230 /**
231  * Check if the list is empty.
232  *
233  * @param returns true (1) if the list is empty.
234  */
235 static __inline__ int ez_list_empty(struct ez_list *l) {
236         return l->tail_pred == (struct ez_node *)l;
237 }
238
239 /**
240  * Retrieve the successor to the head node (the first user node).
241  */
242 static __inline__ void *ez_list_head(struct ez_list *l) {
243         return (void *)l->head;
244 }
245
246 /**
247  * Retrieve the predecessor of the tail node (the last user node).
248  */
249 static __inline__ void *ez_list_tail(struct ez_list *l) {
250         return (void *)l->tail_pred;
251 }
252
253 /* This is important for -Os. */
254 static void ez_list_init(struct ez_list *l) __attribute__ ((always_inline));
255 static void ez_list_addhead(struct ez_list *l, void *np) __attribute__ ((always_inline));
256 static void ez_list_addtail(struct ez_list *l, void *np) __attribute__ ((always_inline));
257 static void ez_node_remove(void *np) __attribute__ ((always_inline));
258 static void *ez_list_remhead(struct ez_list *l) __attribute__ ((always_inline));
259 static void *ez_list_remtail(struct ez_list *l) __attribute__ ((always_inline));
260 static void ez_list_insert_after(struct ez_list *l, void *n, void *p) __attribute__ ((always_inline));
261 static void ez_list_insert(struct ez_list *l, void *n, void *p) __attribute__ ((always_inline));
262 static int ez_list_empty(struct ez_list *l) __attribute__ ((always_inline));
263 static void *ez_list_head(struct ez_list *l) __attribute__ ((always_inline));
264 static void *ez_list_tail(struct ez_list *l) __attribute__ ((always_inline));
265  
266 #endif