1fcb81303217f141b1f30084be2057a51f00321c
[olsrd.git] / src / common / list.h
1 /*
2  * PacketBB handler library (see RFC 5444)
3  * Copyright (c) 2010 Henning Rogge <henning.rogge@fkie.fraunhofer.de>
4  * All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions
8  * are met:
9  *
10  * * Redistributions of source code must retain the above copyright
11  *   notice, this list of conditions and the following disclaimer.
12  * * Redistributions in binary form must reproduce the above copyright
13  *   notice, this list of conditions and the following disclaimer in
14  *   the documentation and/or other materials provided with the
15  *   distribution.
16  * * Neither the name of olsr.org, olsrd nor the names of its
17  *   contributors may be used to endorse or promote products derived
18  *   from this software without specific prior written permission.
19  *
20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
23  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
24  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
25  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
26  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
27  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
28  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
30  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
31  * POSSIBILITY OF SUCH DAMAGE.
32  *
33  * Visit http://www.olsr.org/git for more information.
34  *
35  * If you find this software useful feel free to make a donation
36  * to the project. For more information see the website or contact
37  * the copyright holders.
38  */
39
40 #ifndef LIST_H_
41 #define LIST_H_
42
43 #include <stddef.h>
44 #include <stdbool.h>
45
46 #include "container_of.h"
47
48 /**
49  * this struct is used as list head and list elements.
50  * the list-nodes and the list-head contain two rings of
51  * pointers (one forward, one backward), the first/last node
52  * have a link to the head, no NULL element.
53  */
54 struct list_entity {
55   /**
56    * Pointer to next element in list or to list head if last element
57    */
58   struct list_entity *next;
59
60   /**
61    * Pointer to previous element in list or list head if first element
62    */
63   struct list_entity *prev;
64 };
65
66 /**
67  * initialize a list-head
68  * @param pointer to list-head
69  */
70 static inline void list_init_head(struct list_entity *head) {
71   head->next = head->prev = head;
72 }
73
74 /**
75  * initialize a list-node
76  * @param pointer to list-node
77  */
78 static inline void list_init_node(struct list_entity *entity) {
79   entity->next = entity->prev = NULL;
80 }
81
82 /**
83  * internal function to add a new node between two other nodes.
84  * @param prev node before the insertion point
85  * @param next node after the insertion point
86  * @param new node which will be added to the list between 'prev' and 'next'
87  */
88 static inline void __list_add(struct list_entity *prev, struct list_entity *next, struct list_entity *new) {
89   new->next = next;
90   new->prev = prev;
91   next->prev = new;
92   prev->next = new;
93 }
94
95 /**
96  * adds a node at the beginning of a list
97  * @param head pointer to list head
98  * @param new node which will be added to the list
99  */
100 static inline void list_add_head(struct list_entity *head, struct list_entity *new) {
101   __list_add(head, head->next, new);
102 }
103
104 /**
105  * adds a node at the end of a list
106  * @param head pointer to list head
107  * @param new node which will be added to the list
108  */
109 static inline void list_add_tail(struct list_entity *head, struct list_entity *new) {
110   __list_add(head->prev, head, new);
111 }
112
113 /**
114  * adds a node before another node
115  * @param before reference node in the list
116  * @param new node which will be added to the list
117  */
118 static inline void list_add_before(struct list_entity *before, struct list_entity *new) {
119   __list_add(before->prev, before, new);
120 }
121
122 /**
123  * adds a node after another node
124  * @param before reference node in the list
125  * @param new node which will be added to the list
126  */
127 static inline void list_add_after(struct list_entity *after, struct list_entity *new) {
128   __list_add(after, after->next, new);
129 }
130
131 /**
132  * internal function that removes the nodes between two other nodes.
133  * @param prev node before the removed part of the list
134  * @param next node after the removed part of the list
135  */
136 static inline void __list_remove(struct list_entity *prev, struct list_entity *next) {
137   prev->next = next;
138   next->prev = prev;
139 }
140
141 /**
142  * removes a node from a list and clears node pointers
143  * @param entity node to remove from the list
144  */
145 static inline void list_remove(struct list_entity *entity) {
146   __list_remove(entity->prev, entity->next);
147   entity->prev = entity->next = NULL;
148 }
149
150 /**
151  * checks if list is empty
152  * @param head pointer to list head
153  * @return true if list is empty, false otherwise
154  */
155 static inline bool list_is_empty(struct list_entity *head) {
156   return head->next == head && head->prev == head;
157 }
158
159 /**
160  * checks if node has been added to a list
161  * @param node pointer to node
162  * @return true if both pointers of the node are initialized,
163  *   false otherwise
164  */
165 static inline bool list_node_added(struct list_entity *node) {
166   return node->next != NULL && node->prev != NULL;
167 }
168
169 /**
170  * checks if a node is the first element of a list
171  * @param head pointer to list head
172  * @param entity pointer to node
173  * @return true if node is first element of list, false otherwise
174  */
175 static inline bool list_is_first(struct list_entity *head, struct list_entity *entity) {
176   return head->next == entity;
177 }
178
179 /**
180  * checks if node is the last element of a list
181  * @param head pointer to list head
182  * @param entity pointer to node
183  * @return true if node is last element of list, false otherwise
184  */
185 static inline bool list_is_last(struct list_entity *head, struct list_entity *entity) {
186   return head->prev == entity;
187 }
188
189 /**
190  * Merge two lists and clear the second head
191  * @param add_to head of the list which will contain all elements
192  * @param remove_from head of the list which elements will be added after the elements
193  *   of the first one
194  */
195 static inline void list_merge(struct list_entity *add_to, struct list_entity *remove_from) {
196   if (list_is_empty(remove_from)) {
197     return;
198   }
199
200   add_to->next->prev = remove_from->prev;
201   remove_from->prev->next = add_to->next;
202   add_to->next = remove_from->next;
203   remove_from->next->prev = add_to;
204
205   list_init_head(remove_from);
206 }
207
208 /**
209  * @param head pointer to list-head
210  * @param element pointer to a node element
211  *    (don't need to be initialized)
212  * @param list_member name of the list_entity element inside the
213  *    larger struct
214  * @return pointer to the first element of the list
215  *    (automatically converted to type 'element')
216  */
217 #define list_first_element(head, element, list_member) \
218     container_of((head)->next, typeof(*(element)), list_member)
219
220 /**
221  * @param head pointer to list-head
222  * @param element pointer to a node element
223  *    (don't need to be initialized)
224  * @param list_member name of the list_entity element inside the
225  *    larger struct
226  * @return pointer to the last element of the list
227  *    (automatically converted to type 'element')
228  */
229 #define list_last_element(head, element, list_member) \
230     container_of((head)->prev, typeof(*(element)), list_member)
231
232 /**
233  * This function must not be called for the last element of
234  * a list
235  *
236  * @param element pointer to a node of the list
237  * @param list_member name of the list_entity element inside the
238  *    larger struct
239  * @return pointer to the node after 'element'
240  *    (automatically converted to type 'element')
241  */
242 #define list_next_element(element, list_member) \
243   container_of((&(element)->list_member)->next, typeof(*(element)), list_member)
244
245 /**
246  * This function must not be called for the first element of
247  * a list
248  *
249  * @param element pointer to a node of the list
250  * @param list_member name of the list_entity element inside the
251  *    larger struct
252  * @return pointer to the node before 'element'
253  *    (automatically converted to type 'element')
254  */
255 #define list_prev_element(element, list_member) \
256   container_of((&(element)->list_member)->prev, typeof(*(element)), list_member)
257
258 /**
259  * internal macro that loops over a limited range of nodes
260  * @param first_entity first element of loop
261  * @param last_entity last element of loop
262  * @param element pointer to list element struct
263  * @param list_member name of list_entity within list element struct
264  * @param loop_ptr iteration list_entity pointer
265  */
266 #define __list_for_element_range(first_entity, last_entity, element, list_member, loop_ptr) \
267   for (loop_ptr = (first_entity), element = container_of(loop_ptr, typeof(*(element)), list_member); \
268        loop_ptr->prev != (last_entity); \
269        loop_ptr = loop_ptr->next, \
270          element = container_of(loop_ptr, typeof(*(element)), list_member))
271
272
273 /**
274  * internal macro that loops backward over a limited range of nodes
275  * @param first_entity first element of range (will be last returned by the loop)
276  * @param last_entity last element of range (will be first returned by the loop)
277  * @param element pointer to list element struct
278  * @param list_member name of list_entity within list element struct
279  * @param loop_ptr iteration list_entity pointer
280  */
281 #define __list_for_element_range_reverse(first_entity, last_entity, element, list_member, loop_ptr) \
282   for (loop_ptr = (last_entity), element = container_of(loop_ptr, typeof(*(element)), list_member); \
283        loop_ptr->next != (first_entity); \
284        loop_ptr = loop_ptr->prev, \
285          element = container_of(loop_ptr, typeof(*(element)), list_member))
286
287 /**
288  * Loop over all elements of a list, used similar to a for() command.
289  * This loop should not be used if elements are removed from the list during
290  * the loop.
291  *
292  * @param head pointer to list-head
293  * @param element pointer to a node of the list, this element will
294  *    contain the current node of the list during the loop
295  * @param list_member name of the list_entity element inside the
296  *    larger struct
297  * @param loop_ptr pointer to an list_entity which is used as the
298  *    internal iterator
299  */
300 #define list_for_each_element(head, element, list_member, loop_ptr) \
301   __list_for_element_range((head)->next, (head)->prev, element, list_member, loop_ptr)
302
303 /**
304  * Loop over all elements of a list backwards, used similar to a for() command.
305  * This loop should not be used if elements are removed from the list during
306  * the loop.
307  *
308  * @param head pointer to list-head
309  * @param element pointer to a node of the list, this element will
310  *    contain the current node of the list during the loop
311  * @param list_member name of the list_entity element inside the
312  *    larger struct
313  * @param loop_ptr pointer to an list_entity which is used as the
314  *    internal iterator
315  */
316 #define list_for_each_element_reverse(head, element, list_member, loop_ptr) \
317   __list_for_element_range_reverse((head)->next, (head)->prev, element, list_member, loop_ptr)
318
319 /**
320  * Loop over a block of elements of a list, used similar to a for() command.
321  * This loop should not be used if elements are removed from the list during
322  * the loop.
323  *
324  * @param first pointer to first element of loop
325  * @param last pointer to last element of loop
326  * @param element pointer to a node of the list, this element will
327  *    contain the current node of the list during the loop
328  * @param list_member name of the list_entity element inside the
329  *    larger struct
330  * @param loop_ptr pointer to an list_entity which is used as the
331  *    internal iterator
332  */
333 #define list_for_element_range(first, last, element, list_member, loop_ptr) \
334   __list_for_element_range(&(first)->list_member, &(last)->list_member, element, list_member, loop_ptr)
335
336 /**
337  * Loop over a block of elements of a list backwards, used similar to a for() command.
338  * This loop should not be used if elements are removed from the list during
339  * the loop.
340  *
341  * @param first pointer to first element of range
342  * @param last pointer to last element of range
343  * @param element pointer to a node of the list, this element will
344  *    contain the current node of the list during the loop
345  * @param list_member name of the list_entity element inside the
346  *    larger struct
347  * @param loop_ptr pointer to an list_entity which is used as the
348  *    internal iterator
349  */
350 #define list_for_element_range_reverse(first, last, element, list_member, loop_ptr) \
351   __list_for_element_range_reverse(&(first)->list_member, &(last)->list_member, element, list_member, loop_ptr)
352
353 /**
354  * Loop over a block of elements of a list, used similar to a for() command.
355  * This loop should not be used if elements are removed from the list during
356  * the loop.
357  * The loop runs from the element 'first' to the end of the list.
358  *
359  * @param head pointer to head of list
360  * @param first pointer to first element of loop
361  * @param element pointer to a node of the list, this element will
362  *    contain the current node of the list during the loop
363  * @param list_member name of the list_entity element inside the
364  *    larger struct
365  * @param loop_ptr pointer to an list_entity which is used as the
366  *    internal iterator
367  */
368 #define list_for_element_to_last(head, first, element, list_member, loop_ptr) \
369   __list_for_element_range(&(first)->list_member, (head)->prev, element, list_member, loop_ptr)
370
371 /**
372  * Loop over a block of elements of a list backwards, used similar to a for() command.
373  * This loop should not be used if elements are removed from the list during
374  * the loop.
375  * The loop runs from the end of the list to the element 'first'.
376  *
377  * @param head pointer to head of list
378  * @param first pointer to first element of loop
379  * @param element pointer to a node of the list, this element will
380  *    contain the current node of the list during the loop
381  * @param list_member name of the list_entity element inside the
382  *    larger struct
383  * @param loop_ptr pointer to an list_entity which is used as the
384  *    internal iterator
385  */
386 #define list_for_element_to_last_reverse(head, first, element, list_member, loop_ptr) \
387   __list_for_element_range_reverse(&(first)->list_member, (head)->prev, element, list_member, loop_ptr)
388
389 /**
390  * Loop over a block of elements of a list, used similar to a for() command.
391  * This loop should not be used if elements are removed from the list during
392  * the loop.
393  * The loop runs from the start of the list to the element 'last'.
394  *
395  * @param head pointer to head of list
396  * @param last pointer to last element of loop
397  * @param element pointer to a node of the list, this element will
398  *    contain the current node of the list during the loop
399  * @param list_member name of the list_entity element inside the
400  *    larger struct
401  * @param loop_ptr pointer to an list_entity which is used as the
402  *    internal iterator
403  */
404 #define list_for_first_to_element(head, last, element, list_member, loop_ptr) \
405   __list_for_element_range((head)->next, &(last)->list_member, element, list_member, loop_ptr)
406
407 /**
408  * Loop over a block of elements of a list backwards, used similar to a for() command.
409  * This loop should not be used if elements are removed from the list during
410  * the loop.
411  * The loop runs from the element 'last' to the start of the list.
412  *
413  * @param head pointer to head of list
414  * @param last pointer to last element of loop
415  * @param element pointer to a node of the list, this element will
416  *    contain the current node of the list during the loop
417  * @param list_member name of the list_entity element inside the
418  *    larger struct
419  * @param loop_ptr pointer to an list_entity which is used as the
420  *    internal iterator
421  */
422 #define list_for_first_to_element_reverse(head, last, element, list_member, loop_ptr) \
423   __list_for_element_range_reverse((head)->next, &(last)->list_member, element, list_member, loop_ptr)
424
425 /**
426  * Loop over all elements of a list, used similar to a for() command.
427  * This loop can be used if the current element might be removed from
428  * the list during the loop. Other elements should not be removed during
429  * the loop.
430  *
431  * @param head pointer to list-head
432  * @param element pointer to a node of the list, this element will
433  *    contain the current node of the list during the loop
434  * @param list_member name of the list_entity element inside the
435  *    larger struct
436  * @param loop_ptr pointer to an list_entity which is used as the
437  *    internal iterator for the loop
438  * @param safe_ptr pointer to an list_entity which is used to store
439  *    the next node during the loop
440  */
441 #define list_for_each_element_safe(head, element, list_member, loop_ptr, safe_ptr) \
442   for (loop_ptr = (head)->next, safe_ptr = loop_ptr->next, \
443          element = container_of(loop_ptr, typeof(*(element)), list_member); \
444        loop_ptr != head; \
445        loop_ptr = safe_ptr, safe_ptr = safe_ptr->next, \
446          element = container_of(loop_ptr, typeof(*(element)), list_member))
447
448 /**
449  * Loop over all elements of a list backwards, used similar to a for() command.
450  * This loop can be used if the current element might be removed from
451  * the list during the loop. Other elements should not be removed during
452  * the loop.
453  *
454  * @param head pointer to list-head
455  * @param element pointer to a node of the list, this element will
456  *    contain the current node of the list during the loop
457  * @param list_member name of the list_entity element inside the
458  *    larger struct
459  * @param loop_ptr pointer to an list_entity which is used as the
460  *    internal iterator for the loop
461  * @param safe_ptr pointer to an list_entity which is used to store
462  *    the next node during the loop
463  */
464 #define list_for_each_element_reverse_safe(head, element, list_member, loop_ptr, safe_ptr) \
465   for (loop_ptr = (head)->prev, safe_ptr = loop_ptr->prev, \
466          element = container_of(loop_ptr, typeof(*(element)), list_member); \
467        loop_ptr != head; \
468        loop_ptr = safe_ptr, safe_ptr = safe_ptr->prev, \
469          element = container_of(loop_ptr, typeof(*(element)), list_member))
470
471 #endif /* LIST_H_ */