com_list: Fix spacing. No code changes
[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 /*
105  * Iterate over a list backwards, safe against removal of list entry
106  */
107 #define List_For_Each_Prev_Safe(pos, n, head) \
108         for (pos = (head)->prev, n = pos->prev; \
109              pos != (head); \
110              pos = n, n = pos->prev)
111
112 /*
113  * Test if the entry points to the head of the list
114  */
115 #define List_Entry_Is_Head(pos, head, member) \
116         (&pos->member == (head))
117
118 /*
119  * Iterate over a list of a given type
120  */
121 #define List_For_Each_Entry(pos, head, member) \
122         for (pos = List_First_Entry(head, Q_typeof(*pos), member); \
123              !List_Entry_Is_Head(pos, head, member); \
124              pos = List_Next_Entry(pos, member))
125
126 /*
127  * Iterate over a list of a given type backwards
128  */
129 #define List_For_Each_Prev_Entry(pos, head, member) \
130         for (pos = List_Last_Entry(head, Q_typeof(*pos), member); \
131              !List_Entry_Is_Head(pos, head, member); \
132              pos = List_Prev_Entry(pos, member))
133
134 /*
135  * Prepares a pos entry for use as a start point in List_For_Each_Entry_Continue()
136  */
137 #define List_Prepare_Entry(pos, head, member) \
138         ((pos) ? : List_Entry(head, Q_typeof(*pos), member))
139
140 /*
141  * Continue iteration over a list of a given type, after the current position
142  */
143 #define List_For_Each_Entry_Continue(pos, head, member) \
144         for (pos = List_Next_Entry(pos, member); \
145              !List_Entry_Is_Head(pos, head, member); \
146              pos = List_Next_Entry(pos, member))
147
148 /*
149  * Continue iteration over a list of a given type backwards, after the current position
150  */
151 #define List_For_Each_Prev_Entry_Continue(pos, head, member) \
152         for (pos = List_Prev_Entry(pos, member); \
153              !List_Entry_Is_Head(pos, head, member); \
154              pos = List_Prev_Entry(pos, member))
155
156 /*
157  * Continue iteration over a list of a given type, from the current position
158  */
159 #define List_For_Each_Entry_From(pos, head, member) \
160         for (; !List_Entry_Is_Head(pos, head, member); \
161              pos = List_Next_Entry(pos, member))
162
163 /*
164  * Continue iteration over a list of a given type backwards, from the current position
165  */
166 #define List_For_Each_Prev_Entry_From(pos, head, member) \
167         for (; !List_Entry_Is_Head(pos, head, member); \
168              pos = List_Prev_Entry(pos, member))
169
170 /*
171  * Iterate over a list of a given type, safe against removal of list entry
172  */
173 #define List_For_Each_Entry_Safe(pos, n, head, member) \
174         for (pos = List_First_Entry(head, Q_typeof(*pos), member), \
175              n = List_Next_Entry(pos, member); \
176              !List_Entry_Is_Head(pos, head, member); \
177              pos = n, n = List_Next_Entry(n, member))
178
179 /*
180  * Continue iteration over a list of a given type, after the current position, safe against removal of list entry
181  */
182 #define List_For_Each_Entry_Safe_Continue(pos, n, head, member) \
183         for (pos = List_Next_Entry(pos, member), \
184              n = List_Next_Entry(pos, member); \
185              !List_Entry_Is_Head(pos, head, member); \
186              pos = n, n = List_Next_Entry(n, member))
187
188 /*
189  * Continue iteration over a list of a given type, from the current position, safe against removal of list entry
190  */
191 #define List_For_Each_Entry_Safe_From(pos, n, head, member) \
192         for (n = List_Next_Entry(pos, member); \
193              !List_Entry_Is_Head(pos, head, member); \
194              pos = n, n = List_Next_Entry(n, member))
195
196 /*
197  * Iterate over a list of a given type backwards, safe against removal of list entry
198  */
199 #define List_For_Each_Prev_Entry_Safe(pos, n, head, member) \
200         for (pos = List_Last_Entry(head, Q_typeof(*pos), member), \
201              n = List_Prev_Entry(pos, member); \
202              !List_Entry_Is_Head(pos, head, member); \
203              pos = n, n = List_Prev_Entry(n, member))
204
205 /*
206  * Reset a stale List_For_Each_Entry_Safe loop
207  */
208 #define List_Safe_Reset_Next(pos, n, member) \
209                 n = List_Next_Entry(pos, member)
210
211 static inline qbool List_Is_Empty(const llist_t *list)
212 {
213         return list->next == list;
214 }
215
216 /*
217  * Creates a new linked list. Initializes the head to point to itself.
218  * If it's a list header, the result is an empty list.
219  */
220 static inline void List_Create(llist_t *list)
221 {
222         list->next = list->prev = NULL;
223 }
224
225 /*
226  * Insert a node between two known nodes.
227  * 
228  * Only use when prev and next are known.
229  */
230 static inline void __List_Add(llist_t *node, llist_t *prev, llist_t *next)
231 {
232         next->prev = node;
233         node->next = next;
234         node->prev = prev;
235         prev->next = node;
236 }
237
238 /*
239  * Insert a node immediately after head.
240  */
241 static inline void List_Add(llist_t *node, llist_t *head)
242 {
243         __List_Add(node, head, head->next);
244 }
245
246 /*
247  * Insert a node immediately before head.
248  */
249 static inline void List_Add_Tail(llist_t *node, llist_t *head)
250 {
251         __List_Add(node, head->prev, head);
252 }
253
254 /*
255  * Bridge prev and next together, when removing the parent of them.
256  */
257 static inline void __List_Delete(llist_t *prev, llist_t *next)
258 {
259         next->prev = prev;
260         prev->next = next;
261 }
262
263 /*
264  * Redundant?
265  */
266 static inline void __List_Delete_Node(llist_t *node)
267 {
268         __List_Delete(node->prev, node->next);
269 }
270
271 /*
272  * Removes a node from its list. Sets its pointers to NULL.
273  */
274 static inline void List_Delete(llist_t *node)
275 {
276         __List_Delete_Node(node);
277         node->next = node->prev = NULL;
278 }
279
280 /*
281  * Removes a node from its list. Reinitialize it.
282  */
283 static inline void List_Delete_Init(llist_t *node)
284 {
285         __List_Delete_Node(node);
286         node->next = node->prev = node;
287 }
288
289 /*
290  * Replace old with new. Old is overwritten if empty.
291  */
292 static inline void List_Replace(llist_t *old, llist_t *_new)
293 {
294         _new->next = old->next;
295         _new->next->prev = _new;
296         _new->prev = old->prev;
297         _new->prev->next = _new;
298         old->next = old->prev = old;
299 }
300
301 /*
302  * Replace old with new. Initialize old.
303  * Old is overwritten if empty.
304  */
305 static inline void List_Replace_Init(llist_t *old, llist_t *_new)
306 {
307         List_Replace(old, _new);
308         List_Create(old);
309 }
310
311 /*
312  * Swap node1 with node2 in place.
313  */
314 static inline void List_Swap(llist_t *node1, llist_t *node2)
315 {
316         llist_t *pos = node2->prev;
317         List_Delete_Init(node2);
318         List_Replace(node1, node2);
319         if(pos == node1)
320                 pos = node2;
321         List_Add(node1, pos);
322 }
323
324 /*
325  * Delete list from its... list, then insert after head.
326  */
327 static inline void List_Move(llist_t *list, llist_t *head)
328 {
329         __List_Delete_Node(list);
330         List_Add(list, head);
331 }
332
333 /*
334  * Delete list from its... list, then insert before head.
335  */
336 static inline void List_Move_Tail(llist_t *list, llist_t *head)
337 {
338         __List_Delete_Node(list);
339         List_Add_Tail(list, head);
340 }
341
342 /*
343  * Move the first node of a range of nodes immediately after head.
344  * All three parameters must belong to the same list.
345  */
346
347 static inline void List_Bulk_Move_Tail(llist_t *head, llist_t *first, llist_t *last)
348 {
349         first->prev->next = last->next;
350         last->next->prev = first->prev;
351
352         head->prev->next = first;
353         first->prev = head->prev;
354
355         last->next = head;
356         head->prev = last;
357 }
358
359 /*
360  * Shift the head to the right (like rotating a wheel counterclockwise).
361  * The node immediately to the right becomes the new head.
362  */
363 static inline void List_Rotate_Left(llist_t *head)
364 {
365         llist_t *first;
366
367         if (!List_Is_Empty(head))
368         {
369                 first = head->next;
370                 List_Move_Tail(first, head);
371         }
372 }
373
374 /*
375  * Make list the new head.
376  */
377 static inline void List_Rotate_To_Front(llist_t *list, llist_t *head)
378 {
379         List_Move_Tail(head, list);
380 }
381
382 /*
383  * Concatenate two lists. The head of list will be discarded.
384  */
385 static inline void __List_Splice(const llist_t *list, llist_t *prev, llist_t *next)
386 {
387         llist_t *first = list->next;
388         llist_t *last = list->prev;
389
390         first->prev = prev;
391         prev->next = first;
392
393         last->next = next;
394         next->prev = last;
395 }
396
397 /*
398  * Concatenate two lists. The first node of list will be inserted after head.
399  */
400 static inline void List_Splice(const llist_t *list, llist_t *head)
401 {
402         if(!List_Is_Empty(list))
403                 __List_Splice(list, head, head->next);
404 }
405
406 /*
407  * Concatenate two lists. The tail of list will be inserted before head.
408  */
409 static inline void List_Splice_Tail(const llist_t *list, llist_t *head)
410 {
411         if (!List_Is_Empty(list))
412                 __List_Splice(list, head->prev, head);
413 }
414
415 static inline qbool List_Is_First(llist_t *list, llist_t *start)
416 {
417         return list->prev == start;
418 }
419
420 static inline qbool List_Is_Last(llist_t *list, llist_t *start)
421 {
422         return list->next == start;
423 }
424
425 #endif