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