0 #if !defined(LIST_H)
1 #define LIST_H
2
3 /*
4 * Doubly-linked list macros
5 */
6
7 /*
8 * Copyright 2006 Johan Veenhuizen
9 *
10 * Permission is hereby granted, free of charge, to any person obtaining a
11 * copy of this software and associated documentation files (the "Software"),
12 * to deal in the Software without restriction, including without limitation
13 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
14 * and/or sell copies of the Software, and to permit persons to whom the
15 * Software is furnished to do so, subject to the following conditions:
16 *
17 * The above copyright notice and this permission notice shall be included
18 * in all copies or substantial portions of the Software.
19 *
20 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
21 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
23 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
24 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
25 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
26 * DEALINGS IN THE SOFTWARE.
27 */
28
29 /*
30 * Doubly-linked list type
31 *
32 * Both lists and nodes of lists are of type LIST.
33 *
34 * Doubly-linked list macros
35 *
36 * LIST_DEFINE(listname)
37 * Define and initialize an empty list at load time.
38 *
39 * LIST_INIT([list | node])
40 * Initialize a list or node at run time.
41 *
42 * LIST_EMPTY(list)
43 * Test if list is empty.
44 *
45 * LIST_HEAD(list)
46 * Return the first element of list, or NULL if empty.
47 *
48 * LIST_TAIL(list)
49 * Return the last element of list, or NULL if empty.
50 *
51 * LIST_INSERT(list, node)
52 * Insert node somewhere in list (order not important).
53 *
54 * LIST_INSERT_HEAD(list, node)
55 * Insert node at the head of list.
56 *
57 * LIST_INSERT_TAIL(list, node)
58 * Insert node at the tail of list.
59 *
60 * LIST_INSERT_BEFORE(elem, node)
61 * Insert node before elem.
62 *
63 * LIST_INSERT_AFTER(elem, node)
64 * Insert node after elem.
65 *
66 * LIST_REMOVE(node)
67 * Remove node from its list.
68 *
69 * LIST_MEMBER(node)
70 * Test if node is a member of a list.
71 *
72 * LIST_ITEM(node, type, memb)
73 * Return the structure of the given type, containing
74 * node as member memb.
75 *
76 * LIST_FOREACH(node, list)
77 * Iterate over the nodes of list (for loop).
78 */
79
80 #include <stdio.h>
81
82 /* The exported LIST type. */
83 typedef struct listnode LIST;
84
85 /* The internal list type. Don't use this in code. */
86 struct listnode {
87 struct listnode *ln_prev, *ln_next;
88 };
89
90 /* Define and initialize an empty list at load time. */
91 #define LIST_DEFINE(name) LIST name = { &name, &name }
92
93 /* Initialize a list or list node at run time. */
94 #define LIST_INIT(lp) ((lp)->ln_prev = (lp)->ln_next = (lp))
95
96 /* Return the first node of list, or NULL if empty. */
97 #define LIST_HEAD(list) ((list)->ln_next == (list) ? NULL : (list)->ln_next)
98
99 /* Return the last node of list, or NULL if empty. */
100 #define LIST_TAIL(list) ((list)->ln_prev == (list) ? NULL : (list)->ln_prev)
101
102 /* Insert node before elem. */
103 #define LIST_INSERT_BEFORE(elem, node) do { \
104 (node)->ln_next = (elem); \
105 (node)->ln_prev = (elem)->ln_prev; \
106 (elem)->ln_prev->ln_next = (node); \
107 (elem)->ln_prev = (node); \
108 } while (0)
109
110 /* Insert node after elem. */
111 #define LIST_INSERT_AFTER(elem, node) do { \
112 (node)->ln_prev = (elem); \
113 (node)->ln_next = (elem)->ln_next; \
114 (elem)->ln_next->ln_prev = (node); \
115 (elem)->ln_next = (node); \
116 } while (0)
117
118 /* Insert node at the head of list. */
119 #define LIST_INSERT_HEAD(list, node) LIST_INSERT_AFTER((list), (node))
120
121 /* Insert node at the tail of list. */
122 #define LIST_INSERT_TAIL(list, node) LIST_INSERT_BEFORE((list), (node))
123
124 /* Use this when order is not important. */
125 #define LIST_INSERT(list, node) LIST_INSERT_TAIL((list), (node))
126
127 /* Delete node from its list. */
128 #define LIST_REMOVE(node) do { \
129 (node)->ln_prev->ln_next = (node)->ln_next; \
130 (node)->ln_next->ln_prev = (node)->ln_prev; \
131 LIST_INIT(node); \
132 } while (0)
133
134 /* Test if list if empty. */
135 #define LIST_EMPTY(list) ((list)->ln_next == (list))
136
137 /* Test if node is a member of a list. */
138 #define LIST_MEMBER(node) ((node)->ln_next != (node))
139
140 #define LIST_ITEM(node, type, memb) \
141 ((type *)((char *)(node) - (char *)&(((type *)0)->memb)))
142
143 #define LIST_FOREACH(node, list) \
144 for ((node) = (list)->ln_next; \
145 (node) != (list); \
146 (node) = (node)->ln_next)
147
148 #endif /* defined(LIST_H) */
149