Add list_for_each_entry_safe.
[gpxe.git] / src / include / gpxe / list.h
1 #ifndef _GPXE_LIST_H
2 #define _GPXE_LIST_H
3
4 /** @file
5  *
6  * Linked lists
7  *
8  * This linked list handling code is based on the Linux kernel's
9  * list.h.
10  */
11
12 #include <stddef.h>
13
14 /*
15  * Simple doubly linked list implementation.
16  *
17  * Some of the internal functions ("__xxx") are useful when
18  * manipulating whole lists rather than single entries, as
19  * sometimes we already know the next/prev entries and we can
20  * generate better code by using them directly rather than
21  * using the generic single-entry routines.
22  */
23
24 struct list_head {
25         struct list_head *next;
26         struct list_head *prev;
27 };
28
29 #define LIST_HEAD_INIT( name ) { &(name), &(name) }
30
31 #define LIST_HEAD( name ) \
32         struct list_head name = LIST_HEAD_INIT ( name )
33
34 #define INIT_LIST_HEAD( ptr ) do { \
35         (ptr)->next = (ptr); (ptr)->prev = (ptr); \
36 } while ( 0 )
37
38 /*
39  * Insert a new entry between two known consecutive entries.
40  *
41  * This is only for internal list manipulation where we know
42  * the prev/next entries already!
43  */
44 static inline void __list_add ( struct list_head *new,
45                                 struct list_head *prev,
46                                 struct list_head *next ) {
47         next->prev = new;
48         new->next = next;
49         new->prev = prev;
50         prev->next = new;
51 }
52
53 /**
54  * Add a new entry to the head of a list
55  *
56  * @v new       New entry to be added
57  * @v head      List head to add it after
58  *
59  * Insert a new entry after the specified head.  This is good for
60  * implementing stacks.
61  */
62 static inline void list_add ( struct list_head *new, struct list_head *head ) {
63         __list_add ( new, head, head->next );
64 }
65
66 /**
67  * Add a new entry to the tail of a list
68  *
69  * @v new       New entry to be added
70  * @v head      List head to add it before
71  *
72  * Insert a new entry before the specified head.  This is useful for
73  * implementing queues.
74  */
75 static inline void list_add_tail ( struct list_head *new,
76                                    struct list_head *head ) {
77         __list_add ( new, head->prev, head );
78 }
79
80 /*
81  * Delete a list entry by making the prev/next entries
82  * point to each other.
83  *
84  * This is only for internal list manipulation where we know
85  * the prev/next entries already!
86  */
87 static inline void __list_del ( struct list_head * prev,
88                                 struct list_head * next ) {
89         next->prev = prev;
90         prev->next = next;
91 }
92
93 /**
94  * Delete an entry from a list
95  *
96  * @v entry     Element to delete from the list
97  *
98  * Note that list_empty() on entry does not return true after this;
99  * the entry is in an undefined state.
100  */
101 static inline void list_del ( struct list_head *entry ) {
102         __list_del ( entry->prev, entry->next );
103 }
104
105 /**
106  * Test whether a list is empty
107  *
108  * @v head      List to test.
109  */
110 static inline int list_empty ( const struct list_head *head ) {
111         return head->next == head;
112 }
113
114 /**
115  * Get the containing struct for this entry
116  *
117  * @v ptr       The struct list_head pointer
118  * @v type      The type of the struct this is embedded in
119  * @v member    The name of the list_struct within the struct
120  */
121 #define list_entry( ptr, type, member ) \
122         container_of ( ptr, type, member )
123
124 /**
125  * Iterate over a list
126  *
127  * @v pos       The &struct list_head to use as a loop counter
128  * @v head      The head for your list
129  */
130 #define list_for_each( pos, head ) \
131         for ( pos = (head)->next; pos != (head); pos = pos->next )
132
133 /**
134  * Iterate over entries in a list
135  *
136  * @v pos       The type * to use as a loop counter
137  * @v head      The head for your list
138  * @v member    The name of the list_struct within the struct
139  */
140 #define list_for_each_entry( pos, head, member )                              \
141         for ( pos = list_entry ( (head)->next, typeof ( *pos ), member );     \
142               &pos->member != (head);                                         \
143               pos = list_entry ( pos->member.next, typeof ( *pos ), member ) )
144
145 /**
146  * Iterate over entries in a list, safe against deletion of entries
147  *
148  * @v pos       The type * to use as a loop counter
149  * @v tmp       Another type * to use for temporary storage
150  * @v head      The head for your list
151  * @v member    The name of the list_struct within the struct
152  */
153 #define list_for_each_entry_safe( pos, tmp, head, member )                    \
154         for ( pos = list_entry ( (head)->next, typeof ( *pos ), member ),     \
155               tmp = list_entry ( pos->member.next, typeof ( *tmp ), member ); \
156               &pos->member != (head);                                         \
157               pos = tmp,                                                      \
158               tmp = list_entry ( tmp->member.next, typeof ( *tmp ), member ) )
159
160 #endif /* _GPXE_LIST_H */