Debian Codegraph @

include/list.h

raw
1 #ifndef _LINUX_LIST_H
2 #define _LINUX_LIST_H
3
4 #include <stddef.h>
5
6 /*
7 * Casts a member of a structure out to the containing structure
8 * @param ptr the pointer to the member.
9 * @param type the type of the container struct this is embedded in.
10 * @param member the name of the member within the struct.
11 *
12 */
13 #define container_of(ptr, type, member) ({ \
14 const typeof( ((type *)0)->member ) *__mptr = (ptr); \
15 (type *)( (char *)__mptr - offsetof(type,member) );})
16
17 /*
18 * These are non-NULL pointers that will result in page faults
19 * under normal circumstances, used to verify that nobody uses
20 * non-initialized list entries.
21 */
22 #define LIST_POISON1 ((void *) 0x00100100)
23 #define LIST_POISON2 ((void *) 0x00200200)
24
25 /*
26 * Simple doubly linked list implementation.
27 *
28 * Some of the internal functions ("__xxx") are useful when
29 * manipulating whole lists rather than single entries, as
30 * sometimes we already know the next/prev entries and we can
31 * generate better code by using them directly rather than
32 * using the generic single-entry routines.
33 */
34
35 struct list_head {
36 struct list_head *next, *prev;
37 };
38
39 #define LIST_HEAD_INIT(name) { &(name), &(name) }
40
41 #define LIST_HEAD(name) \
42 struct list_head name = LIST_HEAD_INIT(name)
43
44 #define INIT_LIST_HEAD(ptr) do { \
45 (ptr)->next = (ptr); (ptr)->prev = (ptr); \
46 } while (0)
47
48 /*
49 * Insert a new entry between two known consecutive entries.
50 *
51 * This is only for internal list manipulation where we know
52 * the prev/next entries already!
53 */
54 static inline void __list_add(struct list_head *new,
55 struct list_head *prev,
56 struct list_head *next)
57 {
58 next->prev = new;
59 new->next = next;
60 new->prev = prev;
61 prev->next = new;
62 }
63
64 /**
65 * list_add - add a new entry
66 * @new: new entry to be added
67 * @head: list head to add it after
68 *
69 * Insert a new entry after the specified head.
70 * This is good for implementing stacks.
71 */
72 static inline void list_add(struct list_head *new, struct list_head *head)
73 {
74 __list_add(new, head, head->next);
75 }
76
77 /**
78 * list_add_tail - add a new entry
79 * @new: new entry to be added
80 * @head: list head to add it before
81 *
82 * Insert a new entry before the specified head.
83 * This is useful for implementing queues.
84 */
85 static inline void list_add_tail(struct list_head *new, struct list_head *head)
86 {
87 __list_add(new, head->prev, head);
88 }
89
90 /*
91 * Delete a list entry by making the prev/next entries
92 * point to each other.
93 *
94 * This is only for internal list manipulation where we know
95 * the prev/next entries already!
96 */
97 static inline void __list_del(struct list_head * prev, struct list_head * next)
98 {
99 next->prev = prev;
100 prev->next = next;
101 }
102
103 /**
104 * list_del - deletes entry from list.
105 * @entry: the element to delete from the list.
106 * Note: list_empty on entry does not return true after this, the entry is
107 * in an undefined state.
108 */
109 static inline void list_del(struct list_head *entry)
110 {
111 __list_del(entry->prev, entry->next);
112 entry->next = LIST_POISON1;
113 entry->prev = LIST_POISON2;
114 }
115
116 /**
117 * list_del_init - deletes entry from list and reinitialize it.
118 * @entry: the element to delete from the list.
119 */
120 static inline void list_del_init(struct list_head *entry)
121 {
122 __list_del(entry->prev, entry->next);
123 INIT_LIST_HEAD(entry);
124 }
125
126 /*
127 * list_move - delete from one list and add as another's head
128 * @list: the entry to move
129 * @head: the head that will precede our entry
130 */
131 static inline void list_move(struct list_head *list, struct list_head *head)
132 {
133 __list_del(list->prev, list->next);
134 list_add(list, head);
135 }
136
137 /**
138 * list_move_tail - delete from one list and add as another's tail
139 * @list: the entry to move
140 * @head: the head that will follow our entry
141 */
142 static inline void list_move_tail(struct list_head *list,
143 struct list_head *head)
144 {
145 __list_del(list->prev, list->next);
146 list_add_tail(list, head);
147 }
148
149 /**
150 * list_empty - tests whether a list is empty
151 * @head: the list to test.
152 */
153 static inline int list_empty(const struct list_head *head)
154 {
155 return head->next == head;
156 }
157
158 static inline void __list_splice(struct list_head *list,
159 struct list_head *head)
160 {
161 struct list_head *first = list->next;
162 struct list_head *last = list->prev;
163 struct list_head *at = head->next;
164
165 first->prev = head;
166 head->next = first;
167
168 last->next = at;
169 at->prev = last;
170 }
171
172 /**
173 * list_splice - join two lists
174 * @list: the new list to add.
175 * @head: the place to add it in the first list.
176 */
177 static inline void list_splice(struct list_head *list, struct list_head *head)
178 {
179 if (!list_empty(list))
180 __list_splice(list, head);
181 }
182
183 /**
184 * list_splice_init - join two lists and reinitialise the emptied list.
185 * @list: the new list to add.
186 * @head: the place to add it in the first list.
187 *
188 * The list at @list is reinitialised
189 */
190 static inline void list_splice_init(struct list_head *list,
191 struct list_head *head)
192 {
193 if (!list_empty(list)) {
194 __list_splice(list, head);
195 INIT_LIST_HEAD(list);
196 }
197 }
198
199 /**
200 * list_entry - get the struct for this entry
201 * @ptr: the &struct list_head pointer.
202 * @type: the type of the struct this is embedded in.
203 * @member: the name of the list_struct within the struct.
204 */
205 #define list_entry(ptr, type, member) \
206 container_of(ptr, type, member)
207
208 /**
209 * list_first_entry - get the first element from a list
210 * @ptr: the list head to take the element from.
211 * @type: the type of the struct this is embedded in.
212 * @member: the name of the list_head within the struct.
213 *
214 * Note, that list is expected to be not empty.
215 */
216 #define list_first_entry(ptr, type, member) \
217 list_entry((ptr)->next, type, member)
218
219 /**
220 * list_last_entry - get the last element from a list
221 * @ptr: the list head to take the element from.
222 * @type: the type of the struct this is embedded in.
223 * @member: the name of the list_head within the struct.
224 *
225 * Note, that list is expected to be not empty.
226 */
227 #define list_last_entry(ptr, type, member) \
228 list_entry((ptr)->prev, type, member)
229
230 /**
231 * list_next_entry - get the next element in list
232 * @pos: the type * to cursor
233 * @member: the name of the list_head within the struct.
234 */
235 #define list_next_entry(pos, member) \
236 list_entry((pos)->member.next, typeof(*(pos)), member)
237
238 /**
239 * list_prev_entry - get the prev element in list
240 * @pos: the type * to cursor
241 * @member: the name of the list_head within the struct.
242 */
243 #define list_prev_entry(pos, member) \
244 list_entry((pos)->member.prev, typeof(*(pos)), member)
245
246 /**
247 * list_for_each - iterate over a list
248 * @pos: the &struct list_head to use as a loop counter.
249 * @head: the head for your list.
250 */
251 #define list_for_each(pos, head) \
252 for (pos = (head)->next; pos != (head); pos = pos->next)
253
254 /**
255 * list_for_each_prev - iterate over a list in reverse
256 * @pos: the &struct list_head to use as a loop counter.
257 * @head: the head for your list.
258 */
259 #define list_for_each_prev(pos, head) \
260 for (pos = (head)->prev; pos != (head); pos = pos->prev)
261
262 /**
263 * list_for_each_safe - iterate over a list safe against removal of list entry
264 * @pos: the &struct list_head to use as a loop counter.
265 * @n: another &struct list_head to use as temporary storage
266 * @head: the head for your list.
267 */
268 #define list_for_each_safe(pos, n, head) \
269 for (pos = (head)->next, n = pos->next; pos != (head); \
270 pos = n, n = pos->next)
271
272 /**
273 * list_for_each_entry - iterate over list of given type
274 * @pos: the type * to use as a loop counter.
275 * @head: the head for your list.
276 * @member: the name of the list_struct within the struct.
277 */
278 #define list_for_each_entry(pos, head, member) \
279 for (pos = list_entry((head)->next, typeof(*pos), member); \
280 &pos->member != (head); \
281 pos = list_next_entry(pos, member))
282
283 /**
284 * list_for_each_entry_reverse - iterate backwards over list of given type.
285 * @pos: the type * to use as a loop counter.
286 * @head: the head for your list.
287 * @member: the name of the list_struct within the struct.
288 */
289 #define list_for_each_entry_reverse(pos, head, member) \
290 for (pos = list_last_entry(head, typeof(*pos), member); \
291 &pos->member != (head); \
292 pos = list_prev_entry(pos, member))
293
294 /**
295 * list_prepare_entry - prepare a pos entry for use as a start point in
296 * list_for_each_entry_continue
297 * @pos: the type * to use as a start point
298 * @head: the head of the list
299 * @member: the name of the list_struct within the struct.
300 */
301 #define list_prepare_entry(pos, head, member) \
302 ((pos) ? : list_entry(head, typeof(*pos), member))
303
304 /**
305 * list_for_each_entry_continue - iterate over list of given type
306 * continuing after existing point
307 * @pos: the type * to use as a loop counter.
308 * @head: the head for your list.
309 * @member: the name of the list_struct within the struct.
310 */
311 #define list_for_each_entry_continue(pos, head, member) \
312 for (pos = list_next_entry(pos, member); \
313 &pos->member != (head); \
314 pos = list_next_entry(pos, member))
315
316 /**
317 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
318 * @pos: the type * to use as a loop counter.
319 * @n: another type * to use as temporary storage
320 * @head: the head for your list.
321 * @member: the name of the list_struct within the struct.
322 */
323 #define list_for_each_entry_safe(pos, n, head, member) \
324 for (pos = list_first_entry(head, typeof(*pos), member), \
325 n = list_next_entry(pos, member); \
326 &pos->member != (head); \
327 pos = n, n = list_next_entry(n, member))
328
329 /**
330 * list_for_each_entry_safe_continue - iterate over list of given type
331 * continuing after existing point safe against removal of list entry
332 * @pos: the type * to use as a loop counter.
333 * @n: another type * to use as temporary storage
334 * @head: the head for your list.
335 * @member: the name of the list_struct within the struct.
336 */
337 #define list_for_each_entry_safe_continue(pos, n, head, member) \
338 for (pos = list_next_entry(pos, member), \
339 n = list_next_entry(pos, member); \
340 &pos->member != (head); \
341 pos = n, n = list_next_entry(n, member))
342
343 /**
344 * list_for_each_entry_safe_reverse - iterate backwards over list of given type safe against
345 * removal of list entry
346 * @pos: the type * to use as a loop counter.
347 * @n: another type * to use as temporary storage
348 * @head: the head for your list.
349 * @member: the name of the list_struct within the struct.
350 */
351 #define list_for_each_entry_safe_reverse(pos, n, head, member) \
352 for (pos = list_last_entry(head, typeof(*pos), member), \
353 n = list_prev_entry(pos, member); \
354 &pos->member != (head); \
355 pos = n, n = list_prev_entry(n, member))
356
357
358
359
360 /*
361 * Double linked lists with a single pointer list head.
362 * Mostly useful for hash tables where the two pointer list head is
363 * too wasteful.
364 * You lose the ability to access the tail in O(1).
365 */
366
367 struct hlist_head {
368 struct hlist_node *first;
369 };
370
371 struct hlist_node {
372 struct hlist_node *next, **pprev;
373 };
374
375 #define HLIST_HEAD_INIT { .first = NULL }
376 #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
377 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
378 #define INIT_HLIST_NODE(ptr) ((ptr)->next = NULL, (ptr)->pprev = NULL)
379
380 static inline int hlist_unhashed(const struct hlist_node *h)
381 {
382 return !h->pprev;
383 }
384
385 static inline int hlist_empty(const struct hlist_head *h)
386 {
387 return !h->first;
388 }
389
390 static inline void __hlist_del(struct hlist_node *n)
391 {
392 struct hlist_node *next = n->next;
393 struct hlist_node **pprev = n->pprev;
394 *pprev = next;
395 if (next)
396 next->pprev = pprev;
397 }
398
399 static inline void hlist_del(struct hlist_node *n)
400 {
401 __hlist_del(n);
402 n->next = LIST_POISON1;
403 n->pprev = LIST_POISON2;
404 }
405
406
407 static inline void hlist_del_init(struct hlist_node *n)
408 {
409 if (n->pprev) {
410 __hlist_del(n);
411 INIT_HLIST_NODE(n);
412 }
413 }
414
415 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
416 {
417 struct hlist_node *first = h->first;
418 n->next = first;
419 if (first)
420 first->pprev = &n->next;
421 h->first = n;
422 n->pprev = &h->first;
423 }
424
425
426
427 /* next must be != NULL */
428 static inline void hlist_add_before(struct hlist_node *n,
429 struct hlist_node *next)
430 {
431 n->pprev = next->pprev;
432 n->next = next;
433 next->pprev = &n->next;
434 *(n->pprev) = n;
435 }
436
437 static inline void hlist_add_after(struct hlist_node *n,
438 struct hlist_node *next)
439 {
440 next->next = n->next;
441 n->next = next;
442 next->pprev = &n->next;
443
444 if(next->next)
445 next->next->pprev = &next->next;
446 }
447
448
449
450 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
451
452 #define hlist_for_each(pos, head) \
453 for (pos = (head)->first; pos; pos = pos->next)
454
455 #define hlist_for_each_safe(pos, n, head) \
456 for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
457 pos = n)
458
459 #define hlist_entry_safe(ptr, type, member) \
460 ({ typeof(ptr) ____ptr = (ptr); \
461 ____ptr ? hlist_entry(____ptr, type, member) : NULL; \
462 })
463
464 /**
465 * hlist_for_each_entry - iterate over list of given type
466 * @tpos: the type * to use as a loop counter.
467 * @pos: the &struct hlist_node to use as a loop counter.
468 * @head: the head for your list.
469 * @member: the name of the hlist_node within the struct.
470 */
471 #define hlist_for_each_entry(pos, head, member) \
472 for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\
473 pos; \
474 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
475
476 /**
477 * hlist_for_each_entry_continue - iterate over a hlist continuing after existing point
478 * @tpos: the type * to use as a loop counter.
479 * @pos: the &struct hlist_node to use as a loop counter.
480 * @member: the name of the hlist_node within the struct.
481 */
482 #define hlist_for_each_entry_continue(pos, member) \
483 for (pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member);\
484 pos; \
485 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
486
487 /**
488 * hlist_for_each_entry_from - iterate over a hlist continuing from existing point
489 * @tpos: the type * to use as a loop counter.
490 * @pos: the &struct hlist_node to use as a loop counter.
491 * @member: the name of the hlist_node within the struct.
492 */
493 #define hlist_for_each_entry_from(pos, member) \
494 for (; pos; \
495 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
496
497 /**
498 * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
499 * @tpos: the type * to use as a loop counter.
500 * @pos: the &struct hlist_node to use as a loop counter.
501 * @n: another &struct hlist_node to use as temporary storage
502 * @head: the head for your list.
503 * @member: the name of the hlist_node within the struct.
504 */
505 #define hlist_for_each_entry_safe(tpos, pos, n, head, member) \
506 for (pos = hlist_entry_safe((head)->first, typeof(*pos), member);\
507 pos && ({ n = pos->next; 1; }) && \
508 pos = hlist_entry_safe(n, typeof(*pos), member))
509
510 #endif