Rev 4251 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
3254 | Serge | 1 | /* |
2 | * Copyright © 2010-2012 Intel Corporation |
||
3 | * Copyright © 2010 Francisco Jerez |
||
4 | * |
||
5 | * Permission is hereby granted, free of charge, to any person obtaining a |
||
6 | * copy of this software and associated documentation files (the "Software"), |
||
7 | * to deal in the Software without restriction, including without limitation |
||
8 | * the rights to use, copy, modify, merge, publish, distribute, sublicense, |
||
9 | * and/or sell copies of the Software, and to permit persons to whom the |
||
10 | * Software is furnished to do so, subject to the following conditions: |
||
11 | * |
||
12 | * The above copyright notice and this permission notice (including the next |
||
13 | * paragraph) shall be included in all copies or substantial portions of the |
||
14 | * Software. |
||
15 | * |
||
16 | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
||
17 | * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
||
18 | * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL |
||
19 | * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
||
20 | * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING |
||
21 | * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS |
||
22 | * IN THE SOFTWARE. |
||
23 | * |
||
24 | */ |
||
25 | |||
26 | #ifndef _INTEL_LIST_H_ |
||
27 | #define _INTEL_LIST_H_ |
||
28 | |||
29 | #include |
||
30 | |||
31 | /** |
||
32 | * @file Classic doubly-link circular list implementation. |
||
33 | * For real usage examples of the linked list, see the file test/list.c |
||
34 | * |
||
35 | * Example: |
||
36 | * We need to keep a list of struct foo in the parent struct bar, i.e. what |
||
37 | * we want is something like this. |
||
38 | * |
||
39 | * struct bar { |
||
40 | * ... |
||
41 | * struct foo *list_of_foos; -----> struct foo {}, struct foo {}, struct foo{} |
||
42 | * ... |
||
43 | * } |
||
44 | * |
||
45 | * We need one list head in bar and a list element in all list_of_foos (both are of |
||
46 | * data type 'struct list'). |
||
47 | * |
||
48 | * struct bar { |
||
49 | * ... |
||
50 | * struct list list_of_foos; |
||
51 | * ... |
||
52 | * } |
||
53 | * |
||
54 | * struct foo { |
||
55 | * ... |
||
56 | * struct list entry; |
||
57 | * ... |
||
58 | * } |
||
59 | * |
||
60 | * Now we initialize the list head: |
||
61 | * |
||
62 | * struct bar bar; |
||
63 | * ... |
||
64 | * list_init(&bar.list_of_foos); |
||
65 | * |
||
66 | * Then we create the first element and add it to this list: |
||
67 | * |
||
68 | * struct foo *foo = malloc(...); |
||
69 | * .... |
||
70 | * list_add(&foo->entry, &bar.list_of_foos); |
||
71 | * |
||
72 | * Repeat the above for each element you want to add to the list. Deleting |
||
73 | * works with the element itself. |
||
74 | * list_del(&foo->entry); |
||
75 | * free(foo); |
||
76 | * |
||
77 | * Note: calling list_del(&bar.list_of_foos) will set bar.list_of_foos to an empty |
||
78 | * list again. |
||
79 | * |
||
80 | * Looping through the list requires a 'struct foo' as iterator and the |
||
81 | * name of the field the subnodes use. |
||
82 | * |
||
83 | * struct foo *iterator; |
||
84 | * list_for_each_entry(iterator, &bar.list_of_foos, entry) { |
||
85 | * if (iterator->something == ...) |
||
86 | * ... |
||
87 | * } |
||
88 | * |
||
89 | * Note: You must not call list_del() on the iterator if you continue the |
||
90 | * loop. You need to run the safe for-each loop instead: |
||
91 | * |
||
92 | * struct foo *iterator, *next; |
||
93 | * list_for_each_entry_safe(iterator, next, &bar.list_of_foos, entry) { |
||
94 | * if (...) |
||
95 | * list_del(&iterator->entry); |
||
96 | * } |
||
97 | * |
||
98 | */ |
||
99 | |||
100 | /** |
||
101 | * The linkage struct for list nodes. This struct must be part of your |
||
102 | * to-be-linked struct. struct list is required for both the head of the |
||
103 | * list and for each list node. |
||
104 | * |
||
105 | * Position and name of the struct list field is irrelevant. |
||
106 | * There are no requirements that elements of a list are of the same type. |
||
107 | * There are no requirements for a list head, any struct list can be a list |
||
108 | * head. |
||
109 | */ |
||
4251 | Serge | 110 | |
3254 | Serge | 111 | struct list { |
112 | struct list *next, *prev; |
||
113 | }; |
||
114 | |||
115 | /** |
||
116 | * Initialize the list as an empty list. |
||
117 | * |
||
118 | * Example: |
||
119 | * list_init(&bar->list_of_foos); |
||
120 | * |
||
121 | * @param The list to initialized. |
||
122 | */ |
||
123 | static void |
||
124 | list_init(struct list *list) |
||
125 | { |
||
126 | list->next = list->prev = list; |
||
127 | } |
||
128 | |||
129 | static inline void |
||
130 | __list_add(struct list *entry, |
||
131 | struct list *prev, |
||
132 | struct list *next) |
||
133 | { |
||
134 | next->prev = entry; |
||
135 | entry->next = next; |
||
136 | entry->prev = prev; |
||
137 | prev->next = entry; |
||
138 | } |
||
139 | |||
140 | /** |
||
141 | * Insert a new element after the given list head. The new element does not |
||
142 | * need to be initialised as empty list. |
||
143 | * The list changes from: |
||
144 | * head → some element → ... |
||
145 | * to |
||
146 | * head → new element → older element → ... |
||
147 | * |
||
148 | * Example: |
||
149 | * struct foo *newfoo = malloc(...); |
||
150 | * list_add(&newfoo->entry, &bar->list_of_foos); |
||
151 | * |
||
152 | * @param entry The new element to prepend to the list. |
||
153 | * @param head The existing list. |
||
154 | */ |
||
155 | static inline void |
||
156 | list_add(struct list *entry, struct list *head) |
||
157 | { |
||
158 | __list_add(entry, head, head->next); |
||
159 | } |
||
160 | |||
161 | static inline void |
||
162 | list_add_tail(struct list *entry, struct list *head) |
||
163 | { |
||
164 | __list_add(entry, head->prev, head); |
||
165 | } |
||
166 | |||
167 | static inline void list_replace(struct list *old, |
||
168 | struct list *new) |
||
169 | { |
||
170 | new->next = old->next; |
||
171 | new->next->prev = new; |
||
172 | new->prev = old->prev; |
||
173 | new->prev->next = new; |
||
174 | } |
||
175 | |||
176 | #define list_last_entry(ptr, type, member) \ |
||
177 | list_entry((ptr)->prev, type, member) |
||
178 | |||
179 | #define list_for_each(pos, head) \ |
||
180 | for (pos = (head)->next; pos != (head); pos = pos->next) |
||
181 | |||
182 | /** |
||
183 | * Append a new element to the end of the list given with this list head. |
||
184 | * |
||
185 | * The list changes from: |
||
186 | * head → some element → ... → lastelement |
||
187 | * to |
||
188 | * head → some element → ... → lastelement → new element |
||
189 | * |
||
190 | * Example: |
||
191 | * struct foo *newfoo = malloc(...); |
||
192 | * list_append(&newfoo->entry, &bar->list_of_foos); |
||
193 | * |
||
194 | * @param entry The new element to prepend to the list. |
||
195 | * @param head The existing list. |
||
196 | */ |
||
197 | static inline void |
||
198 | list_append(struct list *entry, struct list *head) |
||
199 | { |
||
200 | __list_add(entry, head->prev, head); |
||
201 | } |
||
202 | |||
203 | |||
204 | static inline void |
||
205 | __list_del(struct list *prev, struct list *next) |
||
206 | { |
||
207 | assert(next->prev == prev->next); |
||
208 | next->prev = prev; |
||
209 | prev->next = next; |
||
210 | } |
||
211 | |||
212 | static inline void |
||
213 | _list_del(struct list *entry) |
||
214 | { |
||
215 | assert(entry->prev->next == entry); |
||
216 | assert(entry->next->prev == entry); |
||
217 | __list_del(entry->prev, entry->next); |
||
218 | } |
||
219 | |||
220 | /** |
||
221 | * Remove the element from the list it is in. Using this function will reset |
||
222 | * the pointers to/from this element so it is removed from the list. It does |
||
223 | * NOT free the element itself or manipulate it otherwise. |
||
224 | * |
||
225 | * Using list_del on a pure list head (like in the example at the top of |
||
226 | * this file) will NOT remove the first element from |
||
227 | * the list but rather reset the list as empty list. |
||
228 | * |
||
229 | * Example: |
||
230 | * list_del(&foo->entry); |
||
231 | * |
||
232 | * @param entry The element to remove. |
||
233 | */ |
||
234 | static inline void |
||
235 | list_del(struct list *entry) |
||
236 | { |
||
237 | _list_del(entry); |
||
238 | list_init(entry); |
||
239 | } |
||
240 | |||
241 | static inline void list_move(struct list *list, struct list *head) |
||
242 | { |
||
243 | if (list->prev != head) { |
||
244 | _list_del(list); |
||
245 | list_add(list, head); |
||
246 | } |
||
247 | } |
||
248 | |||
249 | static inline void list_move_tail(struct list *list, struct list *head) |
||
250 | { |
||
251 | _list_del(list); |
||
252 | list_add_tail(list, head); |
||
253 | } |
||
254 | |||
255 | /** |
||
256 | * Check if the list is empty. |
||
257 | * |
||
258 | * Example: |
||
259 | * list_is_empty(&bar->list_of_foos); |
||
260 | * |
||
261 | * @return True if the list contains one or more elements or False otherwise. |
||
262 | */ |
||
263 | static inline bool |
||
264 | list_is_empty(struct list *head) |
||
265 | { |
||
266 | return head->next == head; |
||
267 | } |
||
268 | |||
269 | /** |
||
270 | * Alias of container_of |
||
271 | */ |
||
272 | #define list_entry(ptr, type, member) \ |
||
273 | container_of(ptr, type, member) |
||
274 | |||
275 | /** |
||
276 | * Retrieve the first list entry for the given list pointer. |
||
277 | * |
||
278 | * Example: |
||
279 | * struct foo *first; |
||
280 | * first = list_first_entry(&bar->list_of_foos, struct foo, list_of_foos); |
||
281 | * |
||
282 | * @param ptr The list head |
||
283 | * @param type Data type of the list element to retrieve |
||
284 | * @param member Member name of the struct list field in the list element. |
||
285 | * @return A pointer to the first list element. |
||
286 | */ |
||
287 | #define list_first_entry(ptr, type, member) \ |
||
288 | list_entry((ptr)->next, type, member) |
||
289 | |||
290 | /** |
||
291 | * Retrieve the last list entry for the given listpointer. |
||
292 | * |
||
293 | * Example: |
||
294 | * struct foo *first; |
||
295 | * first = list_last_entry(&bar->list_of_foos, struct foo, list_of_foos); |
||
296 | * |
||
297 | * @param ptr The list head |
||
298 | * @param type Data type of the list element to retrieve |
||
299 | * @param member Member name of the struct list field in the list element. |
||
300 | * @return A pointer to the last list element. |
||
301 | */ |
||
302 | #define list_last_entry(ptr, type, member) \ |
||
303 | list_entry((ptr)->prev, type, member) |
||
304 | |||
305 | #define __container_of(ptr, sample, member) \ |
||
306 | (void *)((char *)(ptr) \ |
||
307 | - ((char *)&(sample)->member - (char *)(sample))) |
||
308 | /** |
||
309 | * Loop through the list given by head and set pos to struct in the list. |
||
310 | * |
||
311 | * Example: |
||
312 | * struct foo *iterator; |
||
313 | * list_for_each_entry(iterator, &bar->list_of_foos, entry) { |
||
314 | * [modify iterator] |
||
315 | * } |
||
316 | * |
||
317 | * This macro is not safe for node deletion. Use list_for_each_entry_safe |
||
318 | * instead. |
||
319 | * |
||
320 | * @param pos Iterator variable of the type of the list elements. |
||
321 | * @param head List head |
||
322 | * @param member Member name of the struct list in the list elements. |
||
323 | * |
||
324 | */ |
||
325 | #define list_for_each_entry(pos, head, member) \ |
||
326 | for (pos = __container_of((head)->next, pos, member); \ |
||
327 | &pos->member != (head); \ |
||
328 | pos = __container_of(pos->member.next, pos, member)) |
||
329 | |||
330 | #define list_for_each_entry_reverse(pos, head, member) \ |
||
331 | for (pos = __container_of((head)->prev, pos, member); \ |
||
332 | &pos->member != (head); \ |
||
333 | pos = __container_of(pos->member.prev, pos, member)) |
||
334 | |||
335 | /** |
||
336 | * Loop through the list, keeping a backup pointer to the element. This |
||
337 | * macro allows for the deletion of a list element while looping through the |
||
338 | * list. |
||
339 | * |
||
340 | * See list_for_each_entry for more details. |
||
341 | */ |
||
342 | #define list_for_each_entry_safe(pos, tmp, head, member) \ |
||
343 | for (pos = __container_of((head)->next, pos, member), \ |
||
344 | tmp = __container_of(pos->member.next, pos, member); \ |
||
345 | &pos->member != (head); \ |
||
346 | pos = tmp, tmp = __container_of(pos->member.next, tmp, member)) |
||
347 | |||
348 | |||
349 | #undef container_of |
||
350 | #define container_of(ptr, type, member) \ |
||
351 | ((type *)((char *)(ptr) - (char *) &((type *)0)->member)) |
||
352 | |||
353 | #endif /* _INTEL_LIST_H_ */ |
||
354 |