1 /*****
2 *
3 * Copyright (C) 2005-2015 CS-SI. All Rights Reserved.
4 * Author: Yoann Vandoorselaere <yoann.v@prelude-ids.com>
5 *
6 * This file is part of the Prelude library.
7 *
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation; either version 2, or (at your option)
11 * any later version.
12 *
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License along
19 * with this program; if not, write to the Free Software Foundation, Inc.,
20 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
21 *
22 *****/
23
24 /*
25 * This is a blind rewrite of the kernel linked list handling code,
26 * done so that we can dual-license libprelude. The code still look
27 * pretty similar, but there is no way to write such list implementation
28 * in many different manner.
29 */
30
31 #ifndef HAVE_LIBPRELUDE_PRELUDE_LIST_H
32 #define HAVE_LIBPRELUDE_PRELUDE_LIST_H
33
34 #ifdef HAVE_CONFIG_H
35 # include "config.h"
36 #endif
37
38 #include "prelude-inttypes.h"
39
40 #ifdef __cplusplus
41 extern "C" {
42 #endif
43
44 #define PRELUDE_LIST(item) prelude_list_t (item) = { &(item), &(item) }
45
46
47 typedef struct prelude_list {
48 struct prelude_list *next;
49 struct prelude_list *prev;
50 } prelude_list_t;
51
52
53
__prelude_list_splice(const prelude_list_t * list,prelude_list_t * prev,prelude_list_t * next)54 static inline void __prelude_list_splice(const prelude_list_t *list, prelude_list_t *prev, prelude_list_t *next)
55 {
56 prelude_list_t *first = list->next, *last = list->prev;
57
58 first->prev = prev;
59 prev->next = first;
60
61 last->next = next;
62 next->prev = last;
63 }
64
65
66
__prelude_list_add(prelude_list_t * item,prelude_list_t * prev,prelude_list_t * next)67 static inline void __prelude_list_add(prelude_list_t *item, prelude_list_t *prev, prelude_list_t *next)
68 {
69 prev->next = item;
70 item->prev = prev;
71 item->next = next;
72 next->prev = item;
73 }
74
75
76 /**
77 * prelude_list_init:
78 * @item: Pointer to a #prelude_list_t object.
79 *
80 * Initialize @item. Note that this is only required if @item
81 * is the head of a list, but might also be useful in case you
82 * want to use prelude_list_del_init().
83 */
prelude_list_init(prelude_list_t * item)84 static inline void prelude_list_init(prelude_list_t *item)
85 {
86 item->next = item->prev = item;
87 }
88
89
90
91 /**
92 * prelude_list_is_empty:
93 * @item: Pointer to a #prelude_list_t object.
94 *
95 * Check whether @item is empty or not.
96 *
97 * Returns: TRUE if @item is empty, FALSE otherwise.
98 */
prelude_list_is_empty(prelude_list_t * item)99 static inline prelude_bool_t prelude_list_is_empty(prelude_list_t *item)
100 {
101 return (item->next == item) ? PRELUDE_BOOL_TRUE : PRELUDE_BOOL_FALSE;
102 }
103
104
105
106 /**
107 * prelude_list_splice_tail:
108 * @head: Pointer to a #prelude_list_t list.
109 * @list: Pointer to a #prelude_list_t object to add to @head.
110 *
111 * All item from list @list are added at the beginning of @head.
112 */
prelude_list_splice(prelude_list_t * head,prelude_list_t * list)113 static inline void prelude_list_splice(prelude_list_t *head, prelude_list_t *list)
114 {
115 if ( ! prelude_list_is_empty(list) )
116 __prelude_list_splice(list, head, head->next);
117 }
118
119
120
121 /**
122 * prelude_list_splice_tail:
123 * @head: Pointer to a #prelude_list_t list.
124 * @list: Pointer to a #prelude_list_t object to add to @head.
125 *
126 * All item from list @list are added at the end of @head.
127 */
prelude_list_splice_tail(prelude_list_t * head,prelude_list_t * list)128 static inline void prelude_list_splice_tail(prelude_list_t *head, prelude_list_t *list)
129 {
130 if ( ! prelude_list_is_empty(list) )
131 __prelude_list_splice(list, head->prev, head);
132 }
133
134
135
136 /**
137 * prelude_list_add:
138 * @head: Pointer to a #prelude_list_t list.
139 * @item: Pointer to a #prelude_list_t object to add to @head.
140 *
141 * Add @item at the beginning of @head list.
142 */
prelude_list_add(prelude_list_t * head,prelude_list_t * item)143 static inline void prelude_list_add(prelude_list_t *head, prelude_list_t *item)
144 {
145 __prelude_list_add(item, head, head->next);
146 }
147
148
149
150 /**
151 * prelude_list_add_tail:
152 * @head: Pointer to a #prelude_list_t list.
153 * @item: Pointer to a #prelude_list_t object to add to @head.
154 *
155 * Add @item at the tail of @head list.
156 */
prelude_list_add_tail(prelude_list_t * head,prelude_list_t * item)157 static inline void prelude_list_add_tail(prelude_list_t *head, prelude_list_t *item)
158 {
159 __prelude_list_add(item, head->prev, head);
160 }
161
162
163
164 /**
165 * prelude_list_del:
166 * @item: Pointer to a #prelude_list_t object.
167 *
168 * Delete @item from the list it is linked in.
169 */
prelude_list_del(prelude_list_t * item)170 static inline void prelude_list_del(prelude_list_t *item)
171 {
172 item->prev->next = item->next;
173 item->next->prev = item->prev;
174 }
175
176
177
178 /**
179 * prelude_list_del_init:
180 * @item: Pointer to a #prelude_list_t object.
181 *
182 * Delete @item from the list it is linked in, and reinitialize
183 * @item member so that the list can be considered as empty.
184 */
prelude_list_del_init(prelude_list_t * item)185 static inline void prelude_list_del_init(prelude_list_t *item)
186 {
187 item->prev->next = item->next;
188 item->next->prev = item->prev;
189 prelude_list_init(item);
190 }
191
192
193 /**
194 * prelude_list_entry:
195 * @item: Pointer to a #prelude_list_t object to retrieve the entry from.
196 * @type: Type of the entry to retrieve.
197 * @member: List member in @type used to link it to a list.
198 *
199 * Retrieve the entry of type @type from the #prelude_list_t object @tmp,
200 * using the item list member @member. Returns the entry associated with @item.
201 */
202 #define prelude_list_entry(item, type, member) \
203 (type *) ((unsigned long) item - (unsigned long) &((type *) 0)->member)
204
205
206
207 /**
208 * prelude_list_for_each:
209 * @list: Pointer to a #prelude_list_t list.
210 * @pos: Pointer to a #prelude_list_t object pointing to the current list member.
211 *
212 * Iterate through all @list entry. prelude_list_entry() can be used to retrieve
213 * and entry from the @pos pointer. It is not safe to call prelude_list_del() while
214 * iterating using this function, see prelude_list_for_each_safe().
215 */
216 #define prelude_list_for_each(list, pos) \
217 for ( (pos) = (list)->next; (pos) != (list); (pos) = (pos)->next )
218
219
220 /**
221 * prelude_list_for_each_safe:
222 * @list: Pointer to a #prelude_list_t list.
223 * @pos: Pointer to a #prelude_list_t object pointing to the current list member.
224 * @bkp: Pointer to a #prelude_list_t object pointing to the next list member.
225 *
226 * Iterate through all @list entry. prelude_list_entry() can be used to retrieve
227 * and entry from the @pos pointer. Calling prelude_list_del() while iterating the
228 * list is safe.
229 */
230 #define prelude_list_for_each_safe(list, pos, bkp) \
231 for ( (pos) = (list)->next, (bkp) = (pos)->next; (pos) != (list); (pos) = (bkp), (bkp) = (pos)->next )
232
233
234
235 /**
236 * prelude_list_for_each_reversed:
237 * @list: Pointer to a #prelude_list_t list.
238 * @pos: Pointer to a #prelude_list_t object pointing to the current list member.
239 *
240 * Iterate through all @list entry in reverse order. prelude_list_entry() can be
241 * used to retrieve and entry from the @pos pointer. It is not safe to call
242 * prelude_list_del() while iterating using this function, see
243 * prelude_list_for_each_reversed_safe().
244 */
245 #define prelude_list_for_each_reversed(list, pos) \
246 for ( (pos) = (list)->prev; (pos) != (list); (pos) = (pos)->prev )
247
248
249
250 /**
251 * prelude_list_for_each_reversed_safe:
252 * @list: Pointer to a #prelude_list_t list.
253 * @pos: Pointer to a #prelude_list_t object pointing to the current list member.
254 * @bkp: Pointer to a #prelude_list_t object pointing to the next list member.
255 *
256 * Iterate through all @list entry in reverse order. prelude_list_entry() can be used to retrieve
257 * and entry from the @pos pointer. Calling prelude_list_del() while iterating the
258 * list is safe.
259 */
260 #define prelude_list_for_each_reversed_safe(list, pos, bkp) \
261 for ( (pos) = (list)->prev, (bkp) = (pos)->prev; (pos) != (list); (pos) = (bkp), (bkp) = (pos)->prev )
262
263
264 /**
265 * prelude_list_for_each_continue:
266 * @list: Pointer to a #prelude_list_t list.
267 * @pos: Pointer to a #prelude_list_t object pointing to the current list member.
268 *
269 * Iterate through all @list entry starting from @pos if it is not NULL, or from
270 * the start of @list if it is. prelude_list_entry() can be used to retrieve
271 * and entry from the @pos pointer. Calling prelude_list_del() while iterating the
272 * list is not safe.
273 */
274 #define prelude_list_for_each_continue(list, pos) \
275 for ( (pos) = ((pos) == NULL) ? (list)->next : (pos)->next; (pos) != (list); (pos) = (pos)->next )
276
277
278 /**
279 * prelude_list_for_each_continue_safe:
280 * @list: Pointer to a #prelude_list_t list.
281 * @pos: Pointer to a #prelude_list_t object pointing to the current list member.
282 * @bkp: Pointer to a #prelude_list_t object pointing to the next list member.
283 *
284 * Iterate through all @list entry starting from @pos if it is not NULL, or from
285 * the start of @list if it is. prelude_list_entry() can be used to retrieve
286 * and entry from the @pos pointer. Calling prelude_list_del() while iterating the
287 * list is safe.
288 */
289 #define prelude_list_for_each_continue_safe(list, pos, bkp) \
290 for ( (pos) = ((bkp) == NULL) ? (list)->next : (bkp); (bkp) = (pos)->next, (pos) != (list); (pos) = (bkp) )
291
292
293
294 #define prelude_list_get_next(list, pos, class, member) \
295 pos ? \
296 ((pos)->member.next == (list)) ? NULL : \
297 prelude_list_entry((pos)->member.next, class, member) \
298 : \
299 ((list)->next == (list)) ? NULL : \
300 prelude_list_entry((list)->next, class, member)
301
302
303 #define prelude_list_get_next_safe(list, pos, bkp, class, member) \
304 pos ? \
305 (((pos) = bkp), \
306 ((bkp) = (! (bkp) || (bkp)->member.next == list) ? NULL : prelude_list_entry((pos)->member.next, class, member)), \
307 (pos)) \
308 : \
309 (((pos) = ((list)->next == list) ? NULL : prelude_list_entry((list)->next, class, member)), \
310 ((bkp) = (! (pos) ||(pos)->member.next == list ) ? NULL : prelude_list_entry((pos)->member.next, class, member)), \
311 (pos))
312
313
314 #ifdef __cplusplus
315 }
316 #endif
317
318 #endif
319