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 53214954025 : WRITE_ONCE(list->next, list);
38 13508659408 : WRITE_ONCE(list->prev, list);
39 1137398292 : }
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 34523565013 : static inline void __list_add(struct list_head *new,
66 : struct list_head *prev,
67 : struct list_head *next)
68 : {
69 34523565013 : if (!__list_add_valid(new, prev, next))
70 : return;
71 :
72 34524947624 : next->prev = new;
73 34524947624 : new->next = next;
74 34524947624 : new->prev = prev;
75 34524947624 : 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 3056069327 : __list_add(new, head, head->next);
89 24677280 : }
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 30287565500 : __list_add(new, head->prev, head);
103 2920916017 : }
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 34860401962 : next->prev = prev;
115 34860401962 : WRITE_ONCE(prev->next, next);
116 34860401962 : }
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 34859244824 : static inline void __list_del_entry(struct list_head *entry)
133 : {
134 34859244824 : if (!__list_del_entry_valid(entry))
135 : return;
136 :
137 34860401962 : __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 2548817623 : __list_del_entry(entry);
149 2553053690 : entry->next = LIST_POISON1;
150 2548594753 : entry->prev = LIST_POISON2;
151 41708096 : }
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 94486993 : new->next = old->next;
164 94486993 : new->next->prev = new;
165 94486993 : new->prev = old->prev;
166 94486993 : 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 94486993 : list_replace(old, new);
180 94486993 : 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 29794873363 : __list_del_entry(entry);
207 29671643391 : INIT_LIST_HEAD(entry);
208 119781397 : }
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 911767487 : static inline void list_move(struct list_head *list, struct list_head *head)
216 : {
217 911767487 : __list_del_entry(list);
218 911767484 : list_add(list, head);
219 911767203 : }
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 416725187 : static inline void list_move_tail(struct list_head *list,
227 : struct list_head *head)
228 : {
229 416725187 : __list_del_entry(list);
230 416725395 : list_add_tail(list, head);
231 416725071 : }
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 : first->prev->next = last->next;
247 : last->next->prev = first->prev;
248 :
249 : head->prev->next = first;
250 : first->prev = head->prev;
251 :
252 : last->next = head;
253 : 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 5345125 : 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 70438961718 : 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 219775459 : __list_del_entry(entry);
309 219774887 : WRITE_ONCE(entry->prev, entry);
310 219774887 : 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 5094121224 : struct list_head *next = smp_load_acquire(&head->next);
329 5094537425 : return list_is_head(next, head) && (next == READ_ONCE(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 : if (!list_empty(head)) {
341 : 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 : 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 1090408 : 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 134889 : struct list_head *new_first = entry->next;
377 134889 : list->next = head->next;
378 134889 : list->next->prev = list;
379 134889 : list->prev = entry;
380 134889 : entry->next = list;
381 134889 : head->next = new_first;
382 134889 : new_first->prev = head;
383 134889 : }
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 134889 : static inline void list_cut_position(struct list_head *list,
400 : struct list_head *head, struct list_head *entry)
401 : {
402 134889 : if (list_empty(head))
403 : return;
404 155815 : if (list_is_singular(head) && !list_is_head(entry, head) && (entry != head->next))
405 : return;
406 134889 : if (list_is_head(entry, head))
407 0 : INIT_LIST_HEAD(list);
408 : else
409 134889 : __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 : if (head->next == entry) {
431 : INIT_LIST_HEAD(list);
432 : return;
433 : }
434 : list->next = head->next;
435 : list->next->prev = list;
436 : list->prev = entry->prev;
437 : list->prev->next = list;
438 : head->next = entry;
439 : 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 1140658973 : struct list_head *first = list->next;
447 1140658973 : struct list_head *last = list->prev;
448 :
449 1140658973 : first->prev = prev;
450 1140658973 : prev->next = first;
451 :
452 1140658973 : last->next = next;
453 1140658973 : next->prev = last;
454 57569084 : }
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 490675567 : if (!list_empty(list))
465 30138830 : __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 27797369 : if (!list_empty(list))
477 27430254 : __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 2297959357 : if (!list_empty(list)) {
491 1082477015 : __list_splice(list, head, head->next);
492 1082477015 : 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 612874 : if (!list_empty(list)) {
508 612874 : __list_splice(list, head->prev, head);
509 612874 : 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_next_entry_circular - get the next element in list
568 : * @pos: the type * to cursor.
569 : * @head: the list head to take the element from.
570 : * @member: the name of the list_head within the struct.
571 : *
572 : * Wraparound if pos is the last element (return the first element).
573 : * Note, that list is expected to be not empty.
574 : */
575 : #define list_next_entry_circular(pos, head, member) \
576 : (list_is_last(&(pos)->member, head) ? \
577 : list_first_entry(head, typeof(*(pos)), member) : list_next_entry(pos, member))
578 :
579 : /**
580 : * list_prev_entry - get the prev element in list
581 : * @pos: the type * to cursor
582 : * @member: the name of the list_head within the struct.
583 : */
584 : #define list_prev_entry(pos, member) \
585 : list_entry((pos)->member.prev, typeof(*(pos)), member)
586 :
587 : /**
588 : * list_prev_entry_circular - get the prev element in list
589 : * @pos: the type * to cursor.
590 : * @head: the list head to take the element from.
591 : * @member: the name of the list_head within the struct.
592 : *
593 : * Wraparound if pos is the first element (return the last element).
594 : * Note, that list is expected to be not empty.
595 : */
596 : #define list_prev_entry_circular(pos, head, member) \
597 : (list_is_first(&(pos)->member, head) ? \
598 : list_last_entry(head, typeof(*(pos)), member) : list_prev_entry(pos, member))
599 :
600 : /**
601 : * list_for_each - iterate over a list
602 : * @pos: the &struct list_head to use as a loop cursor.
603 : * @head: the head for your list.
604 : */
605 : #define list_for_each(pos, head) \
606 : for (pos = (head)->next; !list_is_head(pos, (head)); pos = pos->next)
607 :
608 : /**
609 : * list_for_each_rcu - Iterate over a list in an RCU-safe fashion
610 : * @pos: the &struct list_head to use as a loop cursor.
611 : * @head: the head for your list.
612 : */
613 : #define list_for_each_rcu(pos, head) \
614 : for (pos = rcu_dereference((head)->next); \
615 : !list_is_head(pos, (head)); \
616 : pos = rcu_dereference(pos->next))
617 :
618 : /**
619 : * list_for_each_continue - continue iteration over a list
620 : * @pos: the &struct list_head to use as a loop cursor.
621 : * @head: the head for your list.
622 : *
623 : * Continue to iterate over a list, continuing after the current position.
624 : */
625 : #define list_for_each_continue(pos, head) \
626 : for (pos = pos->next; !list_is_head(pos, (head)); pos = pos->next)
627 :
628 : /**
629 : * list_for_each_prev - iterate over a list backwards
630 : * @pos: the &struct list_head to use as a loop cursor.
631 : * @head: the head for your list.
632 : */
633 : #define list_for_each_prev(pos, head) \
634 : for (pos = (head)->prev; !list_is_head(pos, (head)); pos = pos->prev)
635 :
636 : /**
637 : * list_for_each_safe - iterate over a list safe against removal of list entry
638 : * @pos: the &struct list_head to use as a loop cursor.
639 : * @n: another &struct list_head to use as temporary storage
640 : * @head: the head for your list.
641 : */
642 : #define list_for_each_safe(pos, n, head) \
643 : for (pos = (head)->next, n = pos->next; \
644 : !list_is_head(pos, (head)); \
645 : pos = n, n = pos->next)
646 :
647 : /**
648 : * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
649 : * @pos: the &struct list_head to use as a loop cursor.
650 : * @n: another &struct list_head to use as temporary storage
651 : * @head: the head for your list.
652 : */
653 : #define list_for_each_prev_safe(pos, n, head) \
654 : for (pos = (head)->prev, n = pos->prev; \
655 : !list_is_head(pos, (head)); \
656 : pos = n, n = pos->prev)
657 :
658 : /**
659 : * list_count_nodes - count nodes in the list
660 : * @head: the head for your list.
661 : */
662 : static inline size_t list_count_nodes(struct list_head *head)
663 : {
664 : struct list_head *pos;
665 : size_t count = 0;
666 :
667 : list_for_each(pos, head)
668 : count++;
669 :
670 : return count;
671 : }
672 :
673 : /**
674 : * list_entry_is_head - test if the entry points to the head of the list
675 : * @pos: the type * to cursor
676 : * @head: the head for your list.
677 : * @member: the name of the list_head within the struct.
678 : */
679 : #define list_entry_is_head(pos, head, member) \
680 : (&pos->member == (head))
681 :
682 : /**
683 : * list_for_each_entry - iterate over list of given type
684 : * @pos: the type * to use as a loop cursor.
685 : * @head: the head for your list.
686 : * @member: the name of the list_head within the struct.
687 : */
688 : #define list_for_each_entry(pos, head, member) \
689 : for (pos = list_first_entry(head, typeof(*pos), member); \
690 : !list_entry_is_head(pos, head, member); \
691 : pos = list_next_entry(pos, member))
692 :
693 : /**
694 : * list_for_each_entry_reverse - iterate backwards over list of given type.
695 : * @pos: the type * to use as a loop cursor.
696 : * @head: the head for your list.
697 : * @member: the name of the list_head within the struct.
698 : */
699 : #define list_for_each_entry_reverse(pos, head, member) \
700 : for (pos = list_last_entry(head, typeof(*pos), member); \
701 : !list_entry_is_head(pos, head, member); \
702 : pos = list_prev_entry(pos, member))
703 :
704 : /**
705 : * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
706 : * @pos: the type * to use as a start point
707 : * @head: the head of the list
708 : * @member: the name of the list_head within the struct.
709 : *
710 : * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
711 : */
712 : #define list_prepare_entry(pos, head, member) \
713 : ((pos) ? : list_entry(head, typeof(*pos), member))
714 :
715 : /**
716 : * list_for_each_entry_continue - continue iteration over list of given type
717 : * @pos: the type * to use as a loop cursor.
718 : * @head: the head for your list.
719 : * @member: the name of the list_head within the struct.
720 : *
721 : * Continue to iterate over list of given type, continuing after
722 : * the current position.
723 : */
724 : #define list_for_each_entry_continue(pos, head, member) \
725 : for (pos = list_next_entry(pos, member); \
726 : !list_entry_is_head(pos, head, member); \
727 : pos = list_next_entry(pos, member))
728 :
729 : /**
730 : * list_for_each_entry_continue_reverse - iterate backwards from the given point
731 : * @pos: the type * to use as a loop cursor.
732 : * @head: the head for your list.
733 : * @member: the name of the list_head within the struct.
734 : *
735 : * Start to iterate over list of given type backwards, continuing after
736 : * the current position.
737 : */
738 : #define list_for_each_entry_continue_reverse(pos, head, member) \
739 : for (pos = list_prev_entry(pos, member); \
740 : !list_entry_is_head(pos, head, member); \
741 : pos = list_prev_entry(pos, member))
742 :
743 : /**
744 : * list_for_each_entry_from - iterate over list of given type from the current point
745 : * @pos: the type * to use as a loop cursor.
746 : * @head: the head for your list.
747 : * @member: the name of the list_head within the struct.
748 : *
749 : * Iterate over list of given type, continuing from current position.
750 : */
751 : #define list_for_each_entry_from(pos, head, member) \
752 : for (; !list_entry_is_head(pos, head, member); \
753 : pos = list_next_entry(pos, member))
754 :
755 : /**
756 : * list_for_each_entry_from_reverse - iterate backwards over list of given type
757 : * from the current point
758 : * @pos: the type * to use as a loop cursor.
759 : * @head: the head for your list.
760 : * @member: the name of the list_head within the struct.
761 : *
762 : * Iterate backwards over list of given type, continuing from current position.
763 : */
764 : #define list_for_each_entry_from_reverse(pos, head, member) \
765 : for (; !list_entry_is_head(pos, head, member); \
766 : pos = list_prev_entry(pos, member))
767 :
768 : /**
769 : * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
770 : * @pos: the type * to use as a loop cursor.
771 : * @n: another type * to use as temporary storage
772 : * @head: the head for your list.
773 : * @member: the name of the list_head within the struct.
774 : */
775 : #define list_for_each_entry_safe(pos, n, head, member) \
776 : for (pos = list_first_entry(head, typeof(*pos), member), \
777 : n = list_next_entry(pos, member); \
778 : !list_entry_is_head(pos, head, member); \
779 : pos = n, n = list_next_entry(n, member))
780 :
781 : /**
782 : * list_for_each_entry_safe_continue - continue list iteration safe against removal
783 : * @pos: the type * to use as a loop cursor.
784 : * @n: another type * to use as temporary storage
785 : * @head: the head for your list.
786 : * @member: the name of the list_head within the struct.
787 : *
788 : * Iterate over list of given type, continuing after current point,
789 : * safe against removal of list entry.
790 : */
791 : #define list_for_each_entry_safe_continue(pos, n, head, member) \
792 : for (pos = list_next_entry(pos, member), \
793 : n = list_next_entry(pos, member); \
794 : !list_entry_is_head(pos, head, member); \
795 : pos = n, n = list_next_entry(n, member))
796 :
797 : /**
798 : * list_for_each_entry_safe_from - iterate over list from current point safe against removal
799 : * @pos: the type * to use as a loop cursor.
800 : * @n: another type * to use as temporary storage
801 : * @head: the head for your list.
802 : * @member: the name of the list_head within the struct.
803 : *
804 : * Iterate over list of given type from current point, safe against
805 : * removal of list entry.
806 : */
807 : #define list_for_each_entry_safe_from(pos, n, head, member) \
808 : for (n = list_next_entry(pos, member); \
809 : !list_entry_is_head(pos, head, member); \
810 : pos = n, n = list_next_entry(n, member))
811 :
812 : /**
813 : * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal
814 : * @pos: the type * to use as a loop cursor.
815 : * @n: another type * to use as temporary storage
816 : * @head: the head for your list.
817 : * @member: the name of the list_head within the struct.
818 : *
819 : * Iterate backwards over list of given type, safe against removal
820 : * of list entry.
821 : */
822 : #define list_for_each_entry_safe_reverse(pos, n, head, member) \
823 : for (pos = list_last_entry(head, typeof(*pos), member), \
824 : n = list_prev_entry(pos, member); \
825 : !list_entry_is_head(pos, head, member); \
826 : pos = n, n = list_prev_entry(n, member))
827 :
828 : /**
829 : * list_safe_reset_next - reset a stale list_for_each_entry_safe loop
830 : * @pos: the loop cursor used in the list_for_each_entry_safe loop
831 : * @n: temporary storage used in list_for_each_entry_safe
832 : * @member: the name of the list_head within the struct.
833 : *
834 : * list_safe_reset_next is not safe to use in general if the list may be
835 : * modified concurrently (eg. the lock is dropped in the loop body). An
836 : * exception to this is if the cursor element (pos) is pinned in the list,
837 : * and list_safe_reset_next is called after re-taking the lock and before
838 : * completing the current iteration of the loop body.
839 : */
840 : #define list_safe_reset_next(pos, n, member) \
841 : n = list_next_entry(pos, member)
842 :
843 : /*
844 : * Double linked lists with a single pointer list head.
845 : * Mostly useful for hash tables where the two pointer list head is
846 : * too wasteful.
847 : * You lose the ability to access the tail in O(1).
848 : */
849 :
850 : #define HLIST_HEAD_INIT { .first = NULL }
851 : #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
852 : #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
853 : static inline void INIT_HLIST_NODE(struct hlist_node *h)
854 : {
855 2128582415 : h->next = NULL;
856 1043609146 : h->pprev = NULL;
857 252314035 : }
858 :
859 : /**
860 : * hlist_unhashed - Has node been removed from list and reinitialized?
861 : * @h: Node to be checked
862 : *
863 : * Not that not all removal functions will leave a node in unhashed
864 : * state. For example, hlist_nulls_del_init_rcu() does leave the
865 : * node in unhashed state, but hlist_nulls_del() does not.
866 : */
867 : static inline int hlist_unhashed(const struct hlist_node *h)
868 : {
869 30521799876 : return !h->pprev;
870 : }
871 :
872 : /**
873 : * hlist_unhashed_lockless - Version of hlist_unhashed for lockless use
874 : * @h: Node to be checked
875 : *
876 : * This variant of hlist_unhashed() must be used in lockless contexts
877 : * to avoid potential load-tearing. The READ_ONCE() is paired with the
878 : * various WRITE_ONCE() in hlist helpers that are defined below.
879 : */
880 : static inline int hlist_unhashed_lockless(const struct hlist_node *h)
881 : {
882 1558 : return !READ_ONCE(h->pprev);
883 : }
884 :
885 : /**
886 : * hlist_empty - Is the specified hlist_head structure an empty hlist?
887 : * @h: Structure to check.
888 : */
889 : static inline int hlist_empty(const struct hlist_head *h)
890 : {
891 321659901 : return !READ_ONCE(h->first);
892 : }
893 :
894 : static inline void __hlist_del(struct hlist_node *n)
895 : {
896 271350647 : struct hlist_node *next = n->next;
897 271350647 : struct hlist_node **pprev = n->pprev;
898 :
899 271350647 : WRITE_ONCE(*pprev, next);
900 263094656 : if (next)
901 26159382 : WRITE_ONCE(next->pprev, pprev);
902 : }
903 :
904 : /**
905 : * hlist_del - Delete the specified hlist_node from its list
906 : * @n: Node to delete.
907 : *
908 : * Note that this function leaves the node in hashed state. Use
909 : * hlist_del_init() or similar instead to unhash @n.
910 : */
911 : static inline void hlist_del(struct hlist_node *n)
912 : {
913 3098442 : __hlist_del(n);
914 3098442 : n->next = LIST_POISON1;
915 3098442 : n->pprev = LIST_POISON2;
916 : }
917 :
918 : /**
919 : * hlist_del_init - Delete the specified hlist_node from its list and initialize
920 : * @n: Node to delete.
921 : *
922 : * Note that this function leaves the node in unhashed state.
923 : */
924 : static inline void hlist_del_init(struct hlist_node *n)
925 : {
926 253218486 : if (!hlist_unhashed(n)) {
927 252314035 : __hlist_del(n);
928 252314035 : INIT_HLIST_NODE(n);
929 : }
930 : }
931 :
932 : /**
933 : * hlist_add_head - add a new entry at the beginning of the hlist
934 : * @n: new entry to be added
935 : * @h: hlist head to add it after
936 : *
937 : * Insert a new entry after the specified head.
938 : * This is good for implementing stacks.
939 : */
940 : static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
941 : {
942 255066210 : struct hlist_node *first = h->first;
943 255066210 : WRITE_ONCE(n->next, first);
944 255066184 : if (first)
945 18787223 : WRITE_ONCE(first->pprev, &n->next);
946 255066210 : WRITE_ONCE(h->first, n);
947 249654564 : WRITE_ONCE(n->pprev, &h->first);
948 2646300 : }
949 :
950 : /**
951 : * hlist_add_before - add a new entry before the one specified
952 : * @n: new entry to be added
953 : * @next: hlist node to add it before, which must be non-NULL
954 : */
955 : static inline void hlist_add_before(struct hlist_node *n,
956 : struct hlist_node *next)
957 : {
958 : WRITE_ONCE(n->pprev, next->pprev);
959 : WRITE_ONCE(n->next, next);
960 : WRITE_ONCE(next->pprev, &n->next);
961 : WRITE_ONCE(*(n->pprev), n);
962 : }
963 :
964 : /**
965 : * hlist_add_behind - add a new entry after the one specified
966 : * @n: new entry to be added
967 : * @prev: hlist node to add it after, which must be non-NULL
968 : */
969 : static inline void hlist_add_behind(struct hlist_node *n,
970 : struct hlist_node *prev)
971 : {
972 : WRITE_ONCE(n->next, prev->next);
973 : WRITE_ONCE(prev->next, n);
974 : WRITE_ONCE(n->pprev, &prev->next);
975 :
976 : if (n->next)
977 : WRITE_ONCE(n->next->pprev, &n->next);
978 : }
979 :
980 : /**
981 : * hlist_add_fake - create a fake hlist consisting of a single headless node
982 : * @n: Node to make a fake list out of
983 : *
984 : * This makes @n appear to be its own predecessor on a headless hlist.
985 : * The point of this is to allow things like hlist_del() to work correctly
986 : * in cases where there is no list.
987 : */
988 : static inline void hlist_add_fake(struct hlist_node *n)
989 : {
990 1087355288 : n->pprev = &n->next;
991 : }
992 :
993 : /**
994 : * hlist_fake: Is this node a fake hlist?
995 : * @h: Node to check for being a self-referential fake hlist.
996 : */
997 : static inline bool hlist_fake(struct hlist_node *h)
998 : {
999 1098486967 : return h->pprev == &h->next;
1000 : }
1001 :
1002 : /**
1003 : * hlist_is_singular_node - is node the only element of the specified hlist?
1004 : * @n: Node to check for singularity.
1005 : * @h: Header for potentially singular list.
1006 : *
1007 : * Check whether the node is the only node of the head without
1008 : * accessing head, thus avoiding unnecessary cache misses.
1009 : */
1010 : static inline bool
1011 : hlist_is_singular_node(struct hlist_node *n, struct hlist_head *h)
1012 : {
1013 : return !n->next && n->pprev == &h->first;
1014 : }
1015 :
1016 : /**
1017 : * hlist_move_list - Move an hlist
1018 : * @old: hlist_head for old list.
1019 : * @new: hlist_head for new list.
1020 : *
1021 : * Move a list from one list head to another. Fixup the pprev
1022 : * reference of the first entry if it exists.
1023 : */
1024 : static inline void hlist_move_list(struct hlist_head *old,
1025 : struct hlist_head *new)
1026 : {
1027 730678 : new->first = old->first;
1028 730678 : if (new->first)
1029 235001 : new->first->pprev = &new->first;
1030 730678 : old->first = NULL;
1031 : }
1032 :
1033 : #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
1034 :
1035 : #define hlist_for_each(pos, head) \
1036 : for (pos = (head)->first; pos ; pos = pos->next)
1037 :
1038 : #define hlist_for_each_safe(pos, n, head) \
1039 : for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
1040 : pos = n)
1041 :
1042 : #define hlist_entry_safe(ptr, type, member) \
1043 : ({ typeof(ptr) ____ptr = (ptr); \
1044 : ____ptr ? hlist_entry(____ptr, type, member) : NULL; \
1045 : })
1046 :
1047 : /**
1048 : * hlist_for_each_entry - iterate over list of given type
1049 : * @pos: the type * to use as a loop cursor.
1050 : * @head: the head for your list.
1051 : * @member: the name of the hlist_node within the struct.
1052 : */
1053 : #define hlist_for_each_entry(pos, head, member) \
1054 : for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\
1055 : pos; \
1056 : pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
1057 :
1058 : /**
1059 : * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
1060 : * @pos: the type * to use as a loop cursor.
1061 : * @member: the name of the hlist_node within the struct.
1062 : */
1063 : #define hlist_for_each_entry_continue(pos, member) \
1064 : for (pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member);\
1065 : pos; \
1066 : pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
1067 :
1068 : /**
1069 : * hlist_for_each_entry_from - iterate over a hlist continuing from current point
1070 : * @pos: the type * to use as a loop cursor.
1071 : * @member: the name of the hlist_node within the struct.
1072 : */
1073 : #define hlist_for_each_entry_from(pos, member) \
1074 : for (; pos; \
1075 : pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
1076 :
1077 : /**
1078 : * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
1079 : * @pos: the type * to use as a loop cursor.
1080 : * @n: a &struct hlist_node to use as temporary storage
1081 : * @head: the head for your list.
1082 : * @member: the name of the hlist_node within the struct.
1083 : */
1084 : #define hlist_for_each_entry_safe(pos, n, head, member) \
1085 : for (pos = hlist_entry_safe((head)->first, typeof(*pos), member);\
1086 : pos && ({ n = pos->member.next; 1; }); \
1087 : pos = hlist_entry_safe(n, typeof(*pos), member))
1088 :
1089 : #endif
|
