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