Line data Source code
1 : /* SPDX-License-Identifier: GPL-2.0 */
2 : #ifndef _LINUX_LIST_H
3 : #define _LINUX_LIST_H
4 :
5 : #include <linux/container_of.h>
6 : #include <linux/types.h>
7 : #include <linux/stddef.h>
8 : #include <linux/poison.h>
9 : #include <linux/const.h>
10 :
11 : #include <asm/barrier.h>
12 :
13 : /*
14 : * Circular doubly linked list implementation.
15 : *
16 : * Some of the internal functions ("__xxx") are useful when
17 : * manipulating whole lists rather than single entries, as
18 : * sometimes we already know the next/prev entries and we can
19 : * generate better code by using them directly rather than
20 : * using the generic single-entry routines.
21 : */
22 :
23 : #define LIST_HEAD_INIT(name) { &(name), &(name) }
24 :
25 : #define LIST_HEAD(name) \
26 : struct list_head name = LIST_HEAD_INIT(name)
27 :
28 : /**
29 : * INIT_LIST_HEAD - Initialize a list_head structure
30 : * @list: list_head structure to be initialized.
31 : *
32 : * Initializes the list_head to point to itself. If it is a list header,
33 : * the result is an empty list.
34 : */
35 : static inline void INIT_LIST_HEAD(struct list_head *list)
36 : {
37 295383 : WRITE_ONCE(list->next, list);
38 295381 : list->prev = list;
39 : }
40 :
41 : #ifdef CONFIG_DEBUG_LIST
42 : extern bool __list_add_valid(struct list_head *new,
43 : struct list_head *prev,
44 : struct list_head *next);
45 : extern bool __list_del_entry_valid(struct list_head *entry);
46 : #else
47 : static inline bool __list_add_valid(struct list_head *new,
48 : struct list_head *prev,
49 : struct list_head *next)
50 : {
51 : return true;
52 : }
53 : static inline bool __list_del_entry_valid(struct list_head *entry)
54 : {
55 : return true;
56 : }
57 : #endif
58 :
59 : /*
60 : * Insert a new entry between two known consecutive entries.
61 : *
62 : * This is only for internal list manipulation where we know
63 : * the prev/next entries already!
64 : */
65 : static inline void __list_add(struct list_head *new,
66 : struct list_head *prev,
67 : struct list_head *next)
68 : {
69 4484 : if (!__list_add_valid(new, prev, next))
70 : return;
71 :
72 4484 : next->prev = new;
73 4484 : new->next = next;
74 4484 : new->prev = prev;
75 4484 : WRITE_ONCE(prev->next, new);
76 : }
77 :
78 : /**
79 : * list_add - add a new entry
80 : * @new: new entry to be added
81 : * @head: list head to add it after
82 : *
83 : * Insert a new entry after the specified head.
84 : * This is good for implementing stacks.
85 : */
86 : static inline void list_add(struct list_head *new, struct list_head *head)
87 : {
88 1902 : __list_add(new, head, head->next);
89 : }
90 :
91 :
92 : /**
93 : * list_add_tail - add a new entry
94 : * @new: new entry to be added
95 : * @head: list head to add it before
96 : *
97 : * Insert a new entry before the specified head.
98 : * This is useful for implementing queues.
99 : */
100 : static inline void list_add_tail(struct list_head *new, struct list_head *head)
101 : {
102 7066 : __list_add(new, head->prev, head);
103 : }
104 :
105 : /*
106 : * Delete a list entry by making the prev/next entries
107 : * point to each other.
108 : *
109 : * This is only for internal list manipulation where we know
110 : * the prev/next entries already!
111 : */
112 : static inline void __list_del(struct list_head * prev, struct list_head * next)
113 : {
114 2916 : next->prev = prev;
115 2916 : WRITE_ONCE(prev->next, next);
116 : }
117 :
118 : /*
119 : * Delete a list entry and clear the 'prev' pointer.
120 : *
121 : * This is a special-purpose list clearing method used in the networking code
122 : * for lists allocated as per-cpu, where we don't want to incur the extra
123 : * WRITE_ONCE() overhead of a regular list_del_init(). The code that uses this
124 : * needs to check the node 'prev' pointer instead of calling list_empty().
125 : */
126 : static inline void __list_del_clearprev(struct list_head *entry)
127 : {
128 : __list_del(entry->prev, entry->next);
129 : entry->prev = NULL;
130 : }
131 :
132 : static inline void __list_del_entry(struct list_head *entry)
133 : {
134 2916 : if (!__list_del_entry_valid(entry))
135 : return;
136 :
137 2916 : __list_del(entry->prev, entry->next);
138 : }
139 :
140 : /**
141 : * list_del - deletes entry from list.
142 : * @entry: the element to delete from the list.
143 : * Note: list_empty() on entry does not return true after this, the entry is
144 : * in an undefined state.
145 : */
146 : static inline void list_del(struct list_head *entry)
147 : {
148 1582 : __list_del_entry(entry);
149 1582 : entry->next = LIST_POISON1;
150 1582 : entry->prev = LIST_POISON2;
151 : }
152 :
153 : /**
154 : * list_replace - replace old entry by new one
155 : * @old : the element to be replaced
156 : * @new : the new element to insert
157 : *
158 : * If @old was empty, it will be overwritten.
159 : */
160 : static inline void list_replace(struct list_head *old,
161 : struct list_head *new)
162 : {
163 0 : new->next = old->next;
164 0 : new->next->prev = new;
165 0 : new->prev = old->prev;
166 0 : new->prev->next = new;
167 : }
168 :
169 : /**
170 : * list_replace_init - replace old entry by new one and initialize the old one
171 : * @old : the element to be replaced
172 : * @new : the new element to insert
173 : *
174 : * If @old was empty, it will be overwritten.
175 : */
176 : static inline void list_replace_init(struct list_head *old,
177 : struct list_head *new)
178 : {
179 0 : list_replace(old, new);
180 0 : INIT_LIST_HEAD(old);
181 : }
182 :
183 : /**
184 : * list_swap - replace entry1 with entry2 and re-add entry1 at entry2's position
185 : * @entry1: the location to place entry2
186 : * @entry2: the location to place entry1
187 : */
188 : static inline void list_swap(struct list_head *entry1,
189 : struct list_head *entry2)
190 : {
191 : struct list_head *pos = entry2->prev;
192 :
193 : list_del(entry2);
194 : list_replace(entry1, entry2);
195 : if (pos == entry1)
196 : pos = entry2;
197 : list_add(entry1, pos);
198 : }
199 :
200 : /**
201 : * list_del_init - deletes entry from list and reinitialize it.
202 : * @entry: the element to delete from the list.
203 : */
204 : static inline void list_del_init(struct list_head *entry)
205 : {
206 1047 : __list_del_entry(entry);
207 1047 : INIT_LIST_HEAD(entry);
208 : }
209 :
210 : /**
211 : * list_move - delete from one list and add as another's head
212 : * @list: the entry to move
213 : * @head: the head that will precede our entry
214 : */
215 : static inline void list_move(struct list_head *list, struct list_head *head)
216 : {
217 1 : __list_del_entry(list);
218 1 : list_add(list, head);
219 : }
220 :
221 : /**
222 : * list_move_tail - delete from one list and add as another's tail
223 : * @list: the entry to move
224 : * @head: the head that will follow our entry
225 : */
226 : static inline void list_move_tail(struct list_head *list,
227 : struct list_head *head)
228 : {
229 7 : __list_del_entry(list);
230 7 : list_add_tail(list, head);
231 : }
232 :
233 : /**
234 : * list_bulk_move_tail - move a subsection of a list to its tail
235 : * @head: the head that will follow our entry
236 : * @first: first entry to move
237 : * @last: last entry to move, can be the same as first
238 : *
239 : * Move all entries between @first and including @last before @head.
240 : * All three entries must belong to the same linked list.
241 : */
242 : static inline void list_bulk_move_tail(struct list_head *head,
243 : struct list_head *first,
244 : struct list_head *last)
245 : {
246 0 : first->prev->next = last->next;
247 0 : last->next->prev = first->prev;
248 :
249 0 : head->prev->next = first;
250 0 : first->prev = head->prev;
251 :
252 0 : last->next = head;
253 0 : head->prev = last;
254 : }
255 :
256 : /**
257 : * list_is_first -- tests whether @list is the first entry in list @head
258 : * @list: the entry to test
259 : * @head: the head of the list
260 : */
261 : static inline int list_is_first(const struct list_head *list, const struct list_head *head)
262 : {
263 : return list->prev == head;
264 : }
265 :
266 : /**
267 : * list_is_last - tests whether @list is the last entry in list @head
268 : * @list: the entry to test
269 : * @head: the head of the list
270 : */
271 : static inline int list_is_last(const struct list_head *list, const struct list_head *head)
272 : {
273 : return list->next == head;
274 : }
275 :
276 : /**
277 : * list_is_head - tests whether @list is the list @head
278 : * @list: the entry to test
279 : * @head: the head of the list
280 : */
281 : static inline int list_is_head(const struct list_head *list, const struct list_head *head)
282 : {
283 : return list == head;
284 : }
285 :
286 : /**
287 : * list_empty - tests whether a list is empty
288 : * @head: the list to test.
289 : */
290 : static inline int list_empty(const struct list_head *head)
291 : {
292 5378 : return READ_ONCE(head->next) == head;
293 : }
294 :
295 : /**
296 : * list_del_init_careful - deletes entry from list and reinitialize it.
297 : * @entry: the element to delete from the list.
298 : *
299 : * This is the same as list_del_init(), except designed to be used
300 : * together with list_empty_careful() in a way to guarantee ordering
301 : * of other memory operations.
302 : *
303 : * Any memory operations done before a list_del_init_careful() are
304 : * guaranteed to be visible after a list_empty_careful() test.
305 : */
306 : static inline void list_del_init_careful(struct list_head *entry)
307 : {
308 0 : __list_del_entry(entry);
309 0 : entry->prev = entry;
310 0 : smp_store_release(&entry->next, entry);
311 : }
312 :
313 : /**
314 : * list_empty_careful - tests whether a list is empty and not being modified
315 : * @head: the list to test
316 : *
317 : * Description:
318 : * tests whether a list is empty _and_ checks that no other CPU might be
319 : * in the process of modifying either member (next or prev)
320 : *
321 : * NOTE: using list_empty_careful() without synchronization
322 : * can only be safe if the only activity that can happen
323 : * to the list entry is list_del_init(). Eg. it cannot be used
324 : * if another CPU could re-list_add() it.
325 : */
326 : static inline int list_empty_careful(const struct list_head *head)
327 : {
328 0 : struct list_head *next = smp_load_acquire(&head->next);
329 0 : return list_is_head(next, head) && (next == head->prev);
330 : }
331 :
332 : /**
333 : * list_rotate_left - rotate the list to the left
334 : * @head: the head of the list
335 : */
336 : static inline void list_rotate_left(struct list_head *head)
337 : {
338 : struct list_head *first;
339 :
340 0 : if (!list_empty(head)) {
341 0 : first = head->next;
342 : list_move_tail(first, head);
343 : }
344 : }
345 :
346 : /**
347 : * list_rotate_to_front() - Rotate list to specific item.
348 : * @list: The desired new front of the list.
349 : * @head: The head of the list.
350 : *
351 : * Rotates list so that @list becomes the new front of the list.
352 : */
353 : static inline void list_rotate_to_front(struct list_head *list,
354 : struct list_head *head)
355 : {
356 : /*
357 : * Deletes the list head from the list denoted by @head and
358 : * places it as the tail of @list, this effectively rotates the
359 : * list so that @list is at the front.
360 : */
361 0 : list_move_tail(head, list);
362 : }
363 :
364 : /**
365 : * list_is_singular - tests whether a list has just one entry.
366 : * @head: the list to test.
367 : */
368 : static inline int list_is_singular(const struct list_head *head)
369 : {
370 0 : return !list_empty(head) && (head->next == head->prev);
371 : }
372 :
373 : static inline void __list_cut_position(struct list_head *list,
374 : struct list_head *head, struct list_head *entry)
375 : {
376 0 : struct list_head *new_first = entry->next;
377 0 : list->next = head->next;
378 0 : list->next->prev = list;
379 0 : list->prev = entry;
380 0 : entry->next = list;
381 0 : head->next = new_first;
382 0 : new_first->prev = head;
383 : }
384 :
385 : /**
386 : * list_cut_position - cut a list into two
387 : * @list: a new list to add all removed entries
388 : * @head: a list with entries
389 : * @entry: an entry within head, could be the head itself
390 : * and if so we won't cut the list
391 : *
392 : * This helper moves the initial part of @head, up to and
393 : * including @entry, from @head to @list. You should
394 : * pass on @entry an element you know is on @head. @list
395 : * should be an empty list or a list you do not care about
396 : * losing its data.
397 : *
398 : */
399 0 : static inline void list_cut_position(struct list_head *list,
400 : struct list_head *head, struct list_head *entry)
401 : {
402 0 : if (list_empty(head))
403 : return;
404 0 : if (list_is_singular(head) && !list_is_head(entry, head) && (entry != head->next))
405 : return;
406 0 : if (list_is_head(entry, head))
407 : INIT_LIST_HEAD(list);
408 : else
409 : __list_cut_position(list, head, entry);
410 : }
411 :
412 : /**
413 : * list_cut_before - cut a list into two, before given entry
414 : * @list: a new list to add all removed entries
415 : * @head: a list with entries
416 : * @entry: an entry within head, could be the head itself
417 : *
418 : * This helper moves the initial part of @head, up to but
419 : * excluding @entry, from @head to @list. You should pass
420 : * in @entry an element you know is on @head. @list should
421 : * be an empty list or a list you do not care about losing
422 : * its data.
423 : * If @entry == @head, all entries on @head are moved to
424 : * @list.
425 : */
426 : static inline void list_cut_before(struct list_head *list,
427 : struct list_head *head,
428 : struct list_head *entry)
429 : {
430 0 : if (head->next == entry) {
431 : INIT_LIST_HEAD(list);
432 : return;
433 : }
434 0 : list->next = head->next;
435 0 : list->next->prev = list;
436 0 : list->prev = entry->prev;
437 0 : list->prev->next = list;
438 0 : head->next = entry;
439 0 : entry->prev = head;
440 : }
441 :
442 : static inline void __list_splice(const struct list_head *list,
443 : struct list_head *prev,
444 : struct list_head *next)
445 : {
446 0 : struct list_head *first = list->next;
447 0 : struct list_head *last = list->prev;
448 :
449 0 : first->prev = prev;
450 0 : prev->next = first;
451 :
452 0 : last->next = next;
453 0 : next->prev = last;
454 : }
455 :
456 : /**
457 : * list_splice - join two lists, this is designed for stacks
458 : * @list: the new list to add.
459 : * @head: the place to add it in the first list.
460 : */
461 : static inline void list_splice(const struct list_head *list,
462 : struct list_head *head)
463 : {
464 0 : if (!list_empty(list))
465 0 : __list_splice(list, head, head->next);
466 : }
467 :
468 : /**
469 : * list_splice_tail - join two lists, each list being a queue
470 : * @list: the new list to add.
471 : * @head: the place to add it in the first list.
472 : */
473 : static inline void list_splice_tail(struct list_head *list,
474 : struct list_head *head)
475 : {
476 0 : if (!list_empty(list))
477 0 : __list_splice(list, head->prev, head);
478 : }
479 :
480 : /**
481 : * list_splice_init - join two lists and reinitialise the emptied list.
482 : * @list: the new list to add.
483 : * @head: the place to add it in the first list.
484 : *
485 : * The list at @list is reinitialised
486 : */
487 : static inline void list_splice_init(struct list_head *list,
488 : struct list_head *head)
489 : {
490 0 : if (!list_empty(list)) {
491 0 : __list_splice(list, head, head->next);
492 : INIT_LIST_HEAD(list);
493 : }
494 : }
495 :
496 : /**
497 : * list_splice_tail_init - join two lists and reinitialise the emptied list
498 : * @list: the new list to add.
499 : * @head: the place to add it in the first list.
500 : *
501 : * Each of the lists is a queue.
502 : * The list at @list is reinitialised
503 : */
504 : static inline void list_splice_tail_init(struct list_head *list,
505 : struct list_head *head)
506 : {
507 2 : if (!list_empty(list)) {
508 0 : __list_splice(list, head->prev, head);
509 : INIT_LIST_HEAD(list);
510 : }
511 : }
512 :
513 : /**
514 : * list_entry - get the struct for this entry
515 : * @ptr: the &struct list_head pointer.
516 : * @type: the type of the struct this is embedded in.
517 : * @member: the name of the list_head within the struct.
518 : */
519 : #define list_entry(ptr, type, member) \
520 : container_of(ptr, type, member)
521 :
522 : /**
523 : * list_first_entry - get the first element from a list
524 : * @ptr: the list head to take the element from.
525 : * @type: the type of the struct this is embedded in.
526 : * @member: the name of the list_head within the struct.
527 : *
528 : * Note, that list is expected to be not empty.
529 : */
530 : #define list_first_entry(ptr, type, member) \
531 : list_entry((ptr)->next, type, member)
532 :
533 : /**
534 : * list_last_entry - get the last element from a list
535 : * @ptr: the list head to take the element from.
536 : * @type: the type of the struct this is embedded in.
537 : * @member: the name of the list_head within the struct.
538 : *
539 : * Note, that list is expected to be not empty.
540 : */
541 : #define list_last_entry(ptr, type, member) \
542 : list_entry((ptr)->prev, type, member)
543 :
544 : /**
545 : * list_first_entry_or_null - get the first element from a list
546 : * @ptr: the list head to take the element from.
547 : * @type: the type of the struct this is embedded in.
548 : * @member: the name of the list_head within the struct.
549 : *
550 : * Note that if the list is empty, it returns NULL.
551 : */
552 : #define list_first_entry_or_null(ptr, type, member) ({ \
553 : struct list_head *head__ = (ptr); \
554 : struct list_head *pos__ = READ_ONCE(head__->next); \
555 : pos__ != head__ ? list_entry(pos__, type, member) : NULL; \
556 : })
557 :
558 : /**
559 : * list_next_entry - get the next element in list
560 : * @pos: the type * to cursor
561 : * @member: the name of the list_head within the struct.
562 : */
563 : #define list_next_entry(pos, member) \
564 : list_entry((pos)->member.next, typeof(*(pos)), member)
565 :
566 : /**
567 : * list_prev_entry - get the prev element in list
568 : * @pos: the type * to cursor
569 : * @member: the name of the list_head within the struct.
570 : */
571 : #define list_prev_entry(pos, member) \
572 : list_entry((pos)->member.prev, typeof(*(pos)), member)
573 :
574 : /**
575 : * list_for_each - iterate over a list
576 : * @pos: the &struct list_head to use as a loop cursor.
577 : * @head: the head for your list.
578 : */
579 : #define list_for_each(pos, head) \
580 : for (pos = (head)->next; !list_is_head(pos, (head)); pos = pos->next)
581 :
582 : /**
583 : * list_for_each_continue - continue iteration over a list
584 : * @pos: the &struct list_head to use as a loop cursor.
585 : * @head: the head for your list.
586 : *
587 : * Continue to iterate over a list, continuing after the current position.
588 : */
589 : #define list_for_each_continue(pos, head) \
590 : for (pos = pos->next; !list_is_head(pos, (head)); pos = pos->next)
591 :
592 : /**
593 : * list_for_each_prev - iterate over a list backwards
594 : * @pos: the &struct list_head to use as a loop cursor.
595 : * @head: the head for your list.
596 : */
597 : #define list_for_each_prev(pos, head) \
598 : for (pos = (head)->prev; !list_is_head(pos, (head)); pos = pos->prev)
599 :
600 : /**
601 : * list_for_each_safe - iterate over a list safe against removal of list entry
602 : * @pos: the &struct list_head to use as a loop cursor.
603 : * @n: another &struct list_head to use as temporary storage
604 : * @head: the head for your list.
605 : */
606 : #define list_for_each_safe(pos, n, head) \
607 : for (pos = (head)->next, n = pos->next; \
608 : !list_is_head(pos, (head)); \
609 : pos = n, n = pos->next)
610 :
611 : /**
612 : * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
613 : * @pos: the &struct list_head to use as a loop cursor.
614 : * @n: another &struct list_head to use as temporary storage
615 : * @head: the head for your list.
616 : */
617 : #define list_for_each_prev_safe(pos, n, head) \
618 : for (pos = (head)->prev, n = pos->prev; \
619 : !list_is_head(pos, (head)); \
620 : pos = n, n = pos->prev)
621 :
622 : /**
623 : * list_entry_is_head - test if the entry points to the head of the list
624 : * @pos: the type * to cursor
625 : * @head: the head for your list.
626 : * @member: the name of the list_head within the struct.
627 : */
628 : #define list_entry_is_head(pos, head, member) \
629 : (&pos->member == (head))
630 :
631 : /**
632 : * list_for_each_entry - iterate over list of given type
633 : * @pos: the type * to use as a loop cursor.
634 : * @head: the head for your list.
635 : * @member: the name of the list_head within the struct.
636 : */
637 : #define list_for_each_entry(pos, head, member) \
638 : for (pos = list_first_entry(head, typeof(*pos), member); \
639 : !list_entry_is_head(pos, head, member); \
640 : pos = list_next_entry(pos, member))
641 :
642 : /**
643 : * list_for_each_entry_reverse - iterate backwards over list of given type.
644 : * @pos: the type * to use as a loop cursor.
645 : * @head: the head for your list.
646 : * @member: the name of the list_head within the struct.
647 : */
648 : #define list_for_each_entry_reverse(pos, head, member) \
649 : for (pos = list_last_entry(head, typeof(*pos), member); \
650 : !list_entry_is_head(pos, head, member); \
651 : pos = list_prev_entry(pos, member))
652 :
653 : /**
654 : * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
655 : * @pos: the type * to use as a start point
656 : * @head: the head of the list
657 : * @member: the name of the list_head within the struct.
658 : *
659 : * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
660 : */
661 : #define list_prepare_entry(pos, head, member) \
662 : ((pos) ? : list_entry(head, typeof(*pos), member))
663 :
664 : /**
665 : * list_for_each_entry_continue - continue iteration over list of given type
666 : * @pos: the type * to use as a loop cursor.
667 : * @head: the head for your list.
668 : * @member: the name of the list_head within the struct.
669 : *
670 : * Continue to iterate over list of given type, continuing after
671 : * the current position.
672 : */
673 : #define list_for_each_entry_continue(pos, head, member) \
674 : for (pos = list_next_entry(pos, member); \
675 : !list_entry_is_head(pos, head, member); \
676 : pos = list_next_entry(pos, member))
677 :
678 : /**
679 : * list_for_each_entry_continue_reverse - iterate backwards from the given point
680 : * @pos: the type * to use as a loop cursor.
681 : * @head: the head for your list.
682 : * @member: the name of the list_head within the struct.
683 : *
684 : * Start to iterate over list of given type backwards, continuing after
685 : * the current position.
686 : */
687 : #define list_for_each_entry_continue_reverse(pos, head, member) \
688 : for (pos = list_prev_entry(pos, member); \
689 : !list_entry_is_head(pos, head, member); \
690 : pos = list_prev_entry(pos, member))
691 :
692 : /**
693 : * list_for_each_entry_from - iterate over list of given type from the current point
694 : * @pos: the type * to use as a loop cursor.
695 : * @head: the head for your list.
696 : * @member: the name of the list_head within the struct.
697 : *
698 : * Iterate over list of given type, continuing from current position.
699 : */
700 : #define list_for_each_entry_from(pos, head, member) \
701 : for (; !list_entry_is_head(pos, head, member); \
702 : pos = list_next_entry(pos, member))
703 :
704 : /**
705 : * list_for_each_entry_from_reverse - iterate backwards over list of given type
706 : * from the current point
707 : * @pos: the type * to use as a loop cursor.
708 : * @head: the head for your list.
709 : * @member: the name of the list_head within the struct.
710 : *
711 : * Iterate backwards over list of given type, continuing from current position.
712 : */
713 : #define list_for_each_entry_from_reverse(pos, head, member) \
714 : for (; !list_entry_is_head(pos, head, member); \
715 : pos = list_prev_entry(pos, member))
716 :
717 : /**
718 : * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
719 : * @pos: the type * to use as a loop cursor.
720 : * @n: another type * to use as temporary storage
721 : * @head: the head for your list.
722 : * @member: the name of the list_head within the struct.
723 : */
724 : #define list_for_each_entry_safe(pos, n, head, member) \
725 : for (pos = list_first_entry(head, typeof(*pos), member), \
726 : n = list_next_entry(pos, member); \
727 : !list_entry_is_head(pos, head, member); \
728 : pos = n, n = list_next_entry(n, member))
729 :
730 : /**
731 : * list_for_each_entry_safe_continue - continue list iteration safe against removal
732 : * @pos: the type * to use as a loop cursor.
733 : * @n: another type * to use as temporary storage
734 : * @head: the head for your list.
735 : * @member: the name of the list_head within the struct.
736 : *
737 : * Iterate over list of given type, continuing after current point,
738 : * safe against removal of list entry.
739 : */
740 : #define list_for_each_entry_safe_continue(pos, n, head, member) \
741 : for (pos = list_next_entry(pos, member), \
742 : n = list_next_entry(pos, member); \
743 : !list_entry_is_head(pos, head, member); \
744 : pos = n, n = list_next_entry(n, member))
745 :
746 : /**
747 : * list_for_each_entry_safe_from - iterate over list from current point safe against removal
748 : * @pos: the type * to use as a loop cursor.
749 : * @n: another type * to use as temporary storage
750 : * @head: the head for your list.
751 : * @member: the name of the list_head within the struct.
752 : *
753 : * Iterate over list of given type from current point, safe against
754 : * removal of list entry.
755 : */
756 : #define list_for_each_entry_safe_from(pos, n, head, member) \
757 : for (n = list_next_entry(pos, member); \
758 : !list_entry_is_head(pos, head, member); \
759 : pos = n, n = list_next_entry(n, member))
760 :
761 : /**
762 : * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal
763 : * @pos: the type * to use as a loop cursor.
764 : * @n: another type * to use as temporary storage
765 : * @head: the head for your list.
766 : * @member: the name of the list_head within the struct.
767 : *
768 : * Iterate backwards over list of given type, safe against removal
769 : * of list entry.
770 : */
771 : #define list_for_each_entry_safe_reverse(pos, n, head, member) \
772 : for (pos = list_last_entry(head, typeof(*pos), member), \
773 : n = list_prev_entry(pos, member); \
774 : !list_entry_is_head(pos, head, member); \
775 : pos = n, n = list_prev_entry(n, member))
776 :
777 : /**
778 : * list_safe_reset_next - reset a stale list_for_each_entry_safe loop
779 : * @pos: the loop cursor used in the list_for_each_entry_safe loop
780 : * @n: temporary storage used in list_for_each_entry_safe
781 : * @member: the name of the list_head within the struct.
782 : *
783 : * list_safe_reset_next is not safe to use in general if the list may be
784 : * modified concurrently (eg. the lock is dropped in the loop body). An
785 : * exception to this is if the cursor element (pos) is pinned in the list,
786 : * and list_safe_reset_next is called after re-taking the lock and before
787 : * completing the current iteration of the loop body.
788 : */
789 : #define list_safe_reset_next(pos, n, member) \
790 : n = list_next_entry(pos, member)
791 :
792 : /*
793 : * Double linked lists with a single pointer list head.
794 : * Mostly useful for hash tables where the two pointer list head is
795 : * too wasteful.
796 : * You lose the ability to access the tail in O(1).
797 : */
798 :
799 : #define HLIST_HEAD_INIT { .first = NULL }
800 : #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
801 : #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
802 : static inline void INIT_HLIST_NODE(struct hlist_node *h)
803 : {
804 761 : h->next = NULL;
805 761 : h->pprev = NULL;
806 : }
807 :
808 : /**
809 : * hlist_unhashed - Has node been removed from list and reinitialized?
810 : * @h: Node to be checked
811 : *
812 : * Not that not all removal functions will leave a node in unhashed
813 : * state. For example, hlist_nulls_del_init_rcu() does leave the
814 : * node in unhashed state, but hlist_nulls_del() does not.
815 : */
816 : static inline int hlist_unhashed(const struct hlist_node *h)
817 : {
818 0 : return !h->pprev;
819 : }
820 :
821 : /**
822 : * hlist_unhashed_lockless - Version of hlist_unhashed for lockless use
823 : * @h: Node to be checked
824 : *
825 : * This variant of hlist_unhashed() must be used in lockless contexts
826 : * to avoid potential load-tearing. The READ_ONCE() is paired with the
827 : * various WRITE_ONCE() in hlist helpers that are defined below.
828 : */
829 : static inline int hlist_unhashed_lockless(const struct hlist_node *h)
830 : {
831 292 : return !READ_ONCE(h->pprev);
832 : }
833 :
834 : /**
835 : * hlist_empty - Is the specified hlist_head structure an empty hlist?
836 : * @h: Structure to check.
837 : */
838 : static inline int hlist_empty(const struct hlist_head *h)
839 : {
840 837 : return !READ_ONCE(h->first);
841 : }
842 :
843 : static inline void __hlist_del(struct hlist_node *n)
844 : {
845 580 : struct hlist_node *next = n->next;
846 580 : struct hlist_node **pprev = n->pprev;
847 :
848 580 : WRITE_ONCE(*pprev, next);
849 580 : if (next)
850 186 : WRITE_ONCE(next->pprev, pprev);
851 : }
852 :
853 : /**
854 : * hlist_del - Delete the specified hlist_node from its list
855 : * @n: Node to delete.
856 : *
857 : * Note that this function leaves the node in hashed state. Use
858 : * hlist_del_init() or similar instead to unhash @n.
859 : */
860 : static inline void hlist_del(struct hlist_node *n)
861 : {
862 0 : __hlist_del(n);
863 0 : n->next = LIST_POISON1;
864 0 : n->pprev = LIST_POISON2;
865 : }
866 :
867 : /**
868 : * hlist_del_init - Delete the specified hlist_node from its list and initialize
869 : * @n: Node to delete.
870 : *
871 : * Note that this function leaves the node in unhashed state.
872 : */
873 : static inline void hlist_del_init(struct hlist_node *n)
874 : {
875 113 : if (!hlist_unhashed(n)) {
876 113 : __hlist_del(n);
877 : INIT_HLIST_NODE(n);
878 : }
879 : }
880 :
881 : /**
882 : * hlist_add_head - add a new entry at the beginning of the hlist
883 : * @n: new entry to be added
884 : * @h: hlist head to add it after
885 : *
886 : * Insert a new entry after the specified head.
887 : * This is good for implementing stacks.
888 : */
889 : static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
890 : {
891 241 : struct hlist_node *first = h->first;
892 241 : WRITE_ONCE(n->next, first);
893 241 : if (first)
894 1 : WRITE_ONCE(first->pprev, &n->next);
895 241 : WRITE_ONCE(h->first, n);
896 241 : WRITE_ONCE(n->pprev, &h->first);
897 : }
898 :
899 : /**
900 : * hlist_add_before - add a new entry before the one specified
901 : * @n: new entry to be added
902 : * @next: hlist node to add it before, which must be non-NULL
903 : */
904 : static inline void hlist_add_before(struct hlist_node *n,
905 : struct hlist_node *next)
906 : {
907 : WRITE_ONCE(n->pprev, next->pprev);
908 : WRITE_ONCE(n->next, next);
909 : WRITE_ONCE(next->pprev, &n->next);
910 : WRITE_ONCE(*(n->pprev), n);
911 : }
912 :
913 : /**
914 : * hlist_add_behind - add a new entry after the one specified
915 : * @n: new entry to be added
916 : * @prev: hlist node to add it after, which must be non-NULL
917 : */
918 : static inline void hlist_add_behind(struct hlist_node *n,
919 : struct hlist_node *prev)
920 : {
921 : WRITE_ONCE(n->next, prev->next);
922 : WRITE_ONCE(prev->next, n);
923 : WRITE_ONCE(n->pprev, &prev->next);
924 :
925 : if (n->next)
926 : WRITE_ONCE(n->next->pprev, &n->next);
927 : }
928 :
929 : /**
930 : * hlist_add_fake - create a fake hlist consisting of a single headless node
931 : * @n: Node to make a fake list out of
932 : *
933 : * This makes @n appear to be its own predecessor on a headless hlist.
934 : * The point of this is to allow things like hlist_del() to work correctly
935 : * in cases where there is no list.
936 : */
937 : static inline void hlist_add_fake(struct hlist_node *n)
938 : {
939 : n->pprev = &n->next;
940 : }
941 :
942 : /**
943 : * hlist_fake: Is this node a fake hlist?
944 : * @h: Node to check for being a self-referential fake hlist.
945 : */
946 : static inline bool hlist_fake(struct hlist_node *h)
947 : {
948 0 : return h->pprev == &h->next;
949 : }
950 :
951 : /**
952 : * hlist_is_singular_node - is node the only element of the specified hlist?
953 : * @n: Node to check for singularity.
954 : * @h: Header for potentially singular list.
955 : *
956 : * Check whether the node is the only node of the head without
957 : * accessing head, thus avoiding unnecessary cache misses.
958 : */
959 : static inline bool
960 : hlist_is_singular_node(struct hlist_node *n, struct hlist_head *h)
961 : {
962 95 : return !n->next && n->pprev == &h->first;
963 : }
964 :
965 : /**
966 : * hlist_move_list - Move an hlist
967 : * @old: hlist_head for old list.
968 : * @new: hlist_head for new list.
969 : *
970 : * Move a list from one list head to another. Fixup the pprev
971 : * reference of the first entry if it exists.
972 : */
973 : static inline void hlist_move_list(struct hlist_head *old,
974 : struct hlist_head *new)
975 : {
976 0 : new->first = old->first;
977 0 : if (new->first)
978 0 : new->first->pprev = &new->first;
979 0 : old->first = NULL;
980 : }
981 :
982 : #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
983 :
984 : #define hlist_for_each(pos, head) \
985 : for (pos = (head)->first; pos ; pos = pos->next)
986 :
987 : #define hlist_for_each_safe(pos, n, head) \
988 : for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
989 : pos = n)
990 :
991 : #define hlist_entry_safe(ptr, type, member) \
992 : ({ typeof(ptr) ____ptr = (ptr); \
993 : ____ptr ? hlist_entry(____ptr, type, member) : NULL; \
994 : })
995 :
996 : /**
997 : * hlist_for_each_entry - iterate over list of given type
998 : * @pos: the type * to use as a loop cursor.
999 : * @head: the head for your list.
1000 : * @member: the name of the hlist_node within the struct.
1001 : */
1002 : #define hlist_for_each_entry(pos, head, member) \
1003 : for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\
1004 : pos; \
1005 : pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
1006 :
1007 : /**
1008 : * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
1009 : * @pos: the type * to use as a loop cursor.
1010 : * @member: the name of the hlist_node within the struct.
1011 : */
1012 : #define hlist_for_each_entry_continue(pos, member) \
1013 : for (pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member);\
1014 : pos; \
1015 : pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
1016 :
1017 : /**
1018 : * hlist_for_each_entry_from - iterate over a hlist continuing from current point
1019 : * @pos: the type * to use as a loop cursor.
1020 : * @member: the name of the hlist_node within the struct.
1021 : */
1022 : #define hlist_for_each_entry_from(pos, member) \
1023 : for (; pos; \
1024 : pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
1025 :
1026 : /**
1027 : * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
1028 : * @pos: the type * to use as a loop cursor.
1029 : * @n: a &struct hlist_node to use as temporary storage
1030 : * @head: the head for your list.
1031 : * @member: the name of the hlist_node within the struct.
1032 : */
1033 : #define hlist_for_each_entry_safe(pos, n, head, member) \
1034 : for (pos = hlist_entry_safe((head)->first, typeof(*pos), member);\
1035 : pos && ({ n = pos->member.next; 1; }); \
1036 : pos = hlist_entry_safe(n, typeof(*pos), member))
1037 :
1038 : #endif
|
