da4f3a79d9ebea846d93ad8de44daa99418da97f
[xonotic/darkplaces.git] / com_list.h
1 /*
2 Copyright (C) 2020-2021 David Knapp (Cloudwalk)
3
4 This program is free software; you can redistribute it and/or
5 modify it under the terms of the GNU General Public License
6 as published by the Free Software Foundation; either version 2
7 of the License, or (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
12
13 See the GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program; if not, write to the Free Software
17 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
18
19 */
20
21 // com_list.h - generic doubly linked list interface, adapted from Linux list.h
22
23 #ifndef LIST_H
24 #define LIST_H
25
26 #include <stddef.h>
27 #include "qtypes.h"
28 #include "qdefs.h"
29
30 typedef struct llist_s
31 {
32         struct llist_s *prev;
33         struct llist_s *next;
34 } llist_t;
35
36 #define LIST_HEAD_INIT(name) { &(name), &(name) }
37
38 #define LIST_HEAD(name) \
39         struct llist_s name = LIST_HEAD_INIT(name)
40
41 /*
42  * Get the struct for this entry
43  */
44 #define List_Entry(ptr, type, member) ContainerOf(ptr, type, member)
45
46 /*
47  * Get the first element from a list
48  * The list is expected to not be empty
49  */
50 #define List_First_Entry(ptr, type, member) List_Entry((ptr)->next, type, member)
51
52 /*
53  * Get the last element from the list
54  * The list is expected to not be empty
55  */
56 #define List_Last_Entry(ptr, type, member) List_Entry((ptr)->prev, type, member)
57
58 /*
59  * Get the first element from the list, but return NULL if it's empty
60  */
61 #define List_First_Entry_Or_Null(ptr, type, member) ({ \
62         struct llist_s *head__ = (ptr); \
63         struct llist_s *pos__ = head__->next; \
64         pos__ != head__ ? List_Entry(pos__, type, member) : NULL; \
65 })
66
67 /*
68  * Get the next element in the list
69  */
70 #define List_Next_Entry(pos, member) \
71         List_Entry((pos)->member.next, Q_typeof(*(pos)), member)
72
73 /*
74  * Get the prev element in the list
75  */
76 #define List_Prev_Entry(pos, member) \
77         List_Entry((pos)->member.prev, Q_typeof(*(pos)), member)
78
79 /*
80  * Iterate over a list
81  */
82 #define List_For_Each(pos, head) \
83         for (pos = (head)->next; pos != (head); pos = pos->next)
84
85 /*
86  * Continue iteration over a list, after the current position
87  */
88 #define List_For_Each_Continue(pos, head) \
89         for (pos = pos->next; pos != (head); pos = pos->next)
90
91 /*
92  * Iterate over a list backwards
93  */
94 #define List_For_Each_Prev(pos, head) \
95         for (pos = (head)->prev; pos != (head); pos = pos->prev)
96
97 /*
98  * Iterate over a list, safe against removal of list entry
99  */
100 #define List_For_Each_Safe(pos, n, head) \
101         for (pos = (head)->next, n = pos->next; pos != (head); \
102              pos = n, n = pos->next)
103 /*
104  * Iterate over a list backwards, safe against removal of list entry
105  */
106 #define List_For_Each_Prev_Safe(pos, n, head) \
107         for (pos = (head)->prev, n = pos->prev; \
108              pos != (head); \
109              pos = n, n = pos->prev)
110 /*
111  * Test if the entry points to the head of the list
112  */
113 #define List_Entry_Is_Head(pos, head, member) \
114         (&pos->member == (head))
115
116 /*
117  * Iterate over a list of a given type
118  */
119 #define List_For_Each_Entry(pos, head, member) \
120         for (pos = List_Last_Entry(head, Q_typeof(*pos), member); \
121              !List_Entry_Is_Head(pos, head, member); \
122              pos = List_Prev_Entry(pos, member))
123
124 /*
125  * Iterate over a list of a given type backwards
126  */
127 #define List_For_Each_Prev_Entry(pos, head, member) \
128         for (pos = List_Last_Entry(head, Q_typeof(*pos), member); \
129              !List_Entry_Is_Head(pos, head, member); \
130              pos = List_Prev_Entry(pos, member))
131
132 /*
133  * Prepares a pos entry for use as a start point in List_For_Each_Entry_Continue()
134  */
135 #define List_Prepare_Entry(pos, head, member) \
136         ((pos) ? : List_Entry(head, Q_typeof(*pos), member))
137
138 /*
139  * Continue iteration over a list of a given type, after the current position
140  */
141 #define List_For_Each_Entry_Continue(pos, head, member) \
142         for (pos = List_Next_Entry(pos, member); \
143              !List_Entry_Is_Head(pos, head, member); \
144              pos = List_Next_Entry(pos, member))
145
146 /*
147  * Continue iteration over a list of a given type backwards, after the current position
148  */
149 #define List_For_Each_Prev_Entry_Continue(pos, head, member) \
150         for (pos = List_Prev_Entry(pos, member); \
151              !List_Entry_Is_Head(pos, head, member); \
152              pos = List_Prev_Entry(pos, member))
153
154 /*
155  * Continue iteration over a list of a given type, from the current position
156  */
157 #define List_For_Each_Entry_From(pos, head, member) \
158         for (; !List_Entry_Is_Head(pos, head, member); \
159              pos = List_Next_Entry(pos, member))
160
161 /*
162  * Continue iteration over a list of a given type backwards, from the current position
163  */
164 #define List_For_Each_Prev_Entry_From(pos, head, member) \
165         for (; !List_Entry_Is_Head(pos, head, member); \
166              pos = List_Prev_Entry(pos, member))
167
168 /*
169  * Iterate over a list of a given type, safe against removal of list entry
170  */
171 #define List_For_Each_Entry_Safe(pos, n, head, member) \
172         for (pos = List_First_Entry(head, Q_typeof(*pos), member), \
173              n = List_Next_Entry(pos, member); \
174              !List_Entry_Is_Head(pos, head, member); \
175              pos = n, n = List_Next_Entry(n, member))
176 /*
177  * Continue iteration over a list of a given type, after the current position, safe against removal of list entry
178  */
179 #define List_For_Each_Entry_Safe_Continue(pos, n, head, member) \
180         for (pos = List_Next_Entry(pos, member), \
181              n = List_Next_Entry(pos, member); \
182              !List_Entry_Is_Head(pos, head, member); \
183              pos = n, n = List_Next_Entry(n, member))
184
185 /*
186  * Continue iteration over a list of a given type, from the current position, safe against removal of list entry
187  */
188 #define List_For_Each_Entry_Safe_From(pos, n, head, member) \
189         for (n = List_Next_Entry(pos, member); \
190              !List_Entry_Is_Head(pos, head, member); \
191              pos = n, n = List_Next_Entry(n, member))
192
193
194 /*
195  * Iterate over a list of a given type backwards, safe against removal of list entry
196  */
197 #define List_For_Each_Prev_Entry_Safe(pos, n, head, member) \
198         for (pos = List_Last_Entry(head, Q_typeof(*pos), member), \
199              n = List_Prev_Entry(pos, member); \
200              !List_Entry_Is_Head(pos, head, member); \
201              pos = n, n = List_Prev_Entry(n, member))
202
203 /*
204  * Reset a stale List_For_Each_Entry_Safe loop
205  */
206 #define List_Safe_Reset_Next(pos, n, member) \
207                 n = List_Next_Entry(pos, member)
208
209 static inline qbool List_Is_Empty(const llist_t *list)
210 {
211         return list->next == list;
212 }
213
214 /*
215  * Creates a new linked list. Initializes the head to point to itself.
216  * If it's a list header, the result is an empty list.
217  */
218 static inline void List_Create(llist_t *list)
219 {
220         list->next = list->prev = NULL;
221 }
222
223 /*
224  * Insert a node between two known nodes.
225  * 
226  * Only use when prev and next are known.
227  */
228 static inline void __List_Add(llist_t *node, llist_t *prev, llist_t *next)
229 {
230         next->prev = node;
231         node->next = next;
232         node->prev = prev;
233         prev->next = node;
234 }
235
236 /*
237  * Insert a node immediately after head.
238  */
239 static inline void List_Add(llist_t *node, llist_t *head)
240 {
241         __List_Add(node, head, head->next);
242 }
243
244 /*
245  * Insert a node immediately before head.
246  */
247 static inline void List_Add_Tail(llist_t *node, llist_t *head)
248 {
249         __List_Add(node, head->prev, head);
250 }
251
252 /*
253  * Bridge prev and next together, when removing the parent of them.
254  */
255 static inline void __List_Delete(llist_t *prev, llist_t *next)
256 {
257         next->prev = prev;
258         prev->next = next;
259 }
260
261 /*
262  * Redundant?
263  */
264 static inline void __List_Delete_Node(llist_t *node)
265 {
266         __List_Delete(node->prev, node->next);
267 }
268
269 /*
270  * Removes a node from its list. Sets its pointers to NULL.
271  */
272 static inline void List_Delete(llist_t *node)
273 {
274         __List_Delete_Node(node);
275         node->next = node->prev = NULL;
276 }
277
278 /*
279  * Removes a node from its list. Reinitialize it.
280  */
281 static inline void List_Delete_Init(llist_t *node)
282 {
283         __List_Delete_Node(node);
284         node->next = node->prev = node;
285 }
286
287 /*
288  * Replace old with new. Old is overwritten if empty.
289  */
290 static inline void List_Replace(llist_t *old, llist_t *_new)
291 {
292         _new->next = old->next;
293         _new->next->prev = _new;
294         _new->prev = old->prev;
295         _new->prev->next = _new;
296         old->next = old->prev = old;
297 }
298
299 /*
300  * Replace old with new. Initialize old.
301  * Old is overwritten if empty.
302  */
303 static inline void List_Replace_Init(llist_t *old, llist_t *_new)
304 {
305         List_Replace(old, _new);
306         List_Create(old);
307 }
308
309 /*
310  * Swap node1 with node2 in place.
311  */
312 static inline void List_Swap(llist_t *node1, llist_t *node2)
313 {
314         llist_t *pos = node2->prev;
315         List_Delete_Init(node2);
316         List_Replace(node1, node2);
317         if(pos == node1)
318                 pos = node2;
319         List_Add(node1, pos);
320 }
321
322 /*
323  * Delete list from its... list, then insert after head.
324  */
325 static inline void List_Move(llist_t *list, llist_t *head)
326 {
327         __List_Delete_Node(list);
328         List_Add(list, head);
329 }
330
331 /*
332  * Delete list from its... list, then insert before head.
333  */
334 static inline void List_Move_Tail(llist_t *list, llist_t *head)
335 {
336         __List_Delete_Node(list);
337         List_Add_Tail(list, head);
338 }
339
340 /*
341  * Move the first node of a range of nodes immediately after head.
342  * All three parameters must belong to the same list.
343  */
344
345 static inline void List_Bulk_Move_Tail(llist_t *head, llist_t *first, llist_t *last)
346 {
347         first->prev->next = last->next;
348         last->next->prev = first->prev;
349
350         head->prev->next = first;
351         first->prev = head->prev;
352
353         last->next = head;
354         head->prev = last;
355 }
356
357 /*
358  * Shift the head to the right (like rotating a wheel counterclockwise).
359  * The node immediately to the right becomes the new head.
360  */
361 static inline void List_Rotate_Left(llist_t *head)
362 {
363         llist_t *first;
364
365         if (!List_Is_Empty(head))
366         {
367                 first = head->next;
368                 List_Move_Tail(first, head);
369         }
370 }
371
372 /*
373  * Make list the new head.
374  */
375 static inline void List_Rotate_To_Front(llist_t *list, llist_t *head)
376 {
377         List_Move_Tail(head, list);
378 }
379
380 /*
381  * Concatenate two lists. The head of list will be discarded.
382  */
383 static inline void __List_Splice(const llist_t *list, llist_t *prev, llist_t *next)
384 {
385         llist_t *first = list->next;
386         llist_t *last = list->prev;
387
388         first->prev = prev;
389         prev->next = first;
390
391         last->next = next;
392         next->prev = last;
393 }
394
395 /*
396  * Concatenate two lists. The first node of list will be inserted after head.
397  */
398 static inline void List_Splice(const llist_t *list, llist_t *head)
399 {
400         if(!List_Is_Empty(list))
401                 __List_Splice(list, head, head->next);
402 }
403
404 /*
405  * Concatenate two lists. The tail of list will be inserted before head.
406  */
407 static inline void List_Splice_Tail(const llist_t *list, llist_t *head)
408 {
409         if (!List_Is_Empty(list))
410                 __List_Splice(list, head->prev, head);
411 }
412
413 static inline qbool List_Is_First(llist_t *list, llist_t *start)
414 {
415         return list->prev == start;
416 }
417
418 static inline qbool List_Is_Last(llist_t *list, llist_t *start)
419 {
420         return list->next == start;
421 }
422
423 #endif