Branch data 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 : : * Simple 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 : 90044 : static inline void INIT_LIST_HEAD(struct list_head *list)
27 : : {
28 : 291924076 : WRITE_ONCE(list->next, list);
29 : 313955239 : list->prev = list;
30 : 90044 : }
31 : :
32 : : #ifdef CONFIG_DEBUG_LIST
33 : : extern bool __list_add_valid(struct list_head *new,
34 : : struct list_head *prev,
35 : : struct list_head *next);
36 : : extern bool __list_del_entry_valid(struct list_head *entry);
37 : : #else
38 : : static inline bool __list_add_valid(struct list_head *new,
39 : : struct list_head *prev,
40 : : struct list_head *next)
41 : : {
42 : : return true;
43 : : }
44 : : static inline bool __list_del_entry_valid(struct list_head *entry)
45 : : {
46 : : return true;
47 : : }
48 : : #endif
49 : :
50 : : /*
51 : : * Insert a new entry between two known consecutive entries.
52 : : *
53 : : * This is only for internal list manipulation where we know
54 : : * the prev/next entries already!
55 : : */
56 : : static inline void __list_add(struct list_head *new,
57 : : struct list_head *prev,
58 : : struct list_head *next)
59 : : {
60 : : if (!__list_add_valid(new, prev, next))
61 : : return;
62 : :
63 : 241360377 : next->prev = new;
64 : 241360377 : new->next = next;
65 : 241360377 : new->prev = prev;
66 : 237132693 : WRITE_ONCE(prev->next, new);
67 : : }
68 : :
69 : : /**
70 : : * list_add - add a new entry
71 : : * @new: new entry to be added
72 : : * @head: list head to add it after
73 : : *
74 : : * Insert a new entry after the specified head.
75 : : * This is good for implementing stacks.
76 : : */
77 : 33392779 : static inline void list_add(struct list_head *new, struct list_head *head)
78 : : {
79 : 182833747 : __list_add(new, head, head->next);
80 : 33392779 : }
81 : :
82 : :
83 : : /**
84 : : * list_add_tail - add a new entry
85 : : * @new: new entry to be added
86 : : * @head: list head to add it before
87 : : *
88 : : * Insert a new entry before the specified head.
89 : : * This is useful for implementing queues.
90 : : */
91 : 0 : static inline void list_add_tail(struct list_head *new, struct list_head *head)
92 : : {
93 : 58092461 : __list_add(new, head->prev, head);
94 : 0 : }
95 : :
96 : : /*
97 : : * Delete a list entry by making the prev/next entries
98 : : * point to each other.
99 : : *
100 : : * This is only for internal list manipulation where we know
101 : : * the prev/next entries already!
102 : : */
103 : 5129 : static inline void __list_del(struct list_head * prev, struct list_head * next)
104 : : {
105 : 184743263 : next->prev = prev;
106 : 184743263 : WRITE_ONCE(prev->next, next);
107 : 5129 : }
108 : :
109 : : /*
110 : : * Delete a list entry and clear the 'prev' pointer.
111 : : *
112 : : * This is a special-purpose list clearing method used in the networking code
113 : : * for lists allocated as per-cpu, where we don't want to incur the extra
114 : : * WRITE_ONCE() overhead of a regular list_del_init(). The code that uses this
115 : : * needs to check the node 'prev' pointer instead of calling list_empty().
116 : : */
117 : : static inline void __list_del_clearprev(struct list_head *entry)
118 : : {
119 : 0 : __list_del(entry->prev, entry->next);
120 : 0 : entry->prev = NULL;
121 : : }
122 : :
123 : : /**
124 : : * list_del - deletes entry from list.
125 : : * @entry: the element to delete from the list.
126 : : * Note: list_empty() on entry does not return true after this, the entry is
127 : : * in an undefined state.
128 : : */
129 : : static inline void __list_del_entry(struct list_head *entry)
130 : : {
131 : : if (!__list_del_entry_valid(entry))
132 : : return;
133 : :
134 : 184738134 : __list_del(entry->prev, entry->next);
135 : : }
136 : :
137 : 22340655 : static inline void list_del(struct list_head *entry)
138 : : {
139 : : __list_del_entry(entry);
140 : 136451112 : entry->next = LIST_POISON1;
141 : 136451112 : entry->prev = LIST_POISON2;
142 : 22340655 : }
143 : :
144 : : /**
145 : : * list_replace - replace old entry by new one
146 : : * @old : the element to be replaced
147 : : * @new : the new element to insert
148 : : *
149 : : * If @old was empty, it will be overwritten.
150 : : */
151 : : static inline void list_replace(struct list_head *old,
152 : : struct list_head *new)
153 : : {
154 : 1178805 : new->next = old->next;
155 : 1178805 : new->next->prev = new;
156 : 1178805 : new->prev = old->prev;
157 : 1178805 : new->prev->next = new;
158 : : }
159 : :
160 : : static inline void list_replace_init(struct list_head *old,
161 : : struct list_head *new)
162 : : {
163 : : list_replace(old, new);
164 : : INIT_LIST_HEAD(old);
165 : : }
166 : :
167 : : /**
168 : : * list_swap - replace entry1 with entry2 and re-add entry1 at entry2's position
169 : : * @entry1: the location to place entry2
170 : : * @entry2: the location to place entry1
171 : : */
172 : : static inline void list_swap(struct list_head *entry1,
173 : : struct list_head *entry2)
174 : : {
175 : : struct list_head *pos = entry2->prev;
176 : :
177 : : list_del(entry2);
178 : : list_replace(entry1, entry2);
179 : : if (pos == entry1)
180 : : pos = entry2;
181 : : list_add(entry1, pos);
182 : : }
183 : :
184 : : /**
185 : : * list_del_init - deletes entry from list and reinitialize it.
186 : : * @entry: the element to delete from the list.
187 : : */
188 : : static inline void list_del_init(struct list_head *entry)
189 : : {
190 : : __list_del_entry(entry);
191 : : INIT_LIST_HEAD(entry);
192 : : }
193 : :
194 : : /**
195 : : * list_move - delete from one list and add as another's head
196 : : * @list: the entry to move
197 : : * @head: the head that will precede our entry
198 : : */
199 : : static inline void list_move(struct list_head *list, struct list_head *head)
200 : : {
201 : : __list_del_entry(list);
202 : : list_add(list, head);
203 : : }
204 : :
205 : : /**
206 : : * list_move_tail - delete from one list and add as another's tail
207 : : * @list: the entry to move
208 : : * @head: the head that will follow our entry
209 : : */
210 : : static inline void list_move_tail(struct list_head *list,
211 : : struct list_head *head)
212 : : {
213 : : __list_del_entry(list);
214 : : list_add_tail(list, head);
215 : : }
216 : :
217 : : /**
218 : : * list_bulk_move_tail - move a subsection of a list to its tail
219 : : * @head: the head that will follow our entry
220 : : * @first: first entry to move
221 : : * @last: last entry to move, can be the same as first
222 : : *
223 : : * Move all entries between @first and including @last before @head.
224 : : * All three entries must belong to the same linked list.
225 : : */
226 : : static inline void list_bulk_move_tail(struct list_head *head,
227 : : struct list_head *first,
228 : : struct list_head *last)
229 : : {
230 : : first->prev->next = last->next;
231 : : last->next->prev = first->prev;
232 : :
233 : : head->prev->next = first;
234 : : first->prev = head->prev;
235 : :
236 : : last->next = head;
237 : : head->prev = last;
238 : : }
239 : :
240 : : /**
241 : : * list_is_first -- tests whether @list is the first entry in list @head
242 : : * @list: the entry to test
243 : : * @head: the head of the list
244 : : */
245 : : static inline int list_is_first(const struct list_head *list,
246 : : const struct list_head *head)
247 : : {
248 : 0 : return list->prev == head;
249 : : }
250 : :
251 : : /**
252 : : * list_is_last - tests whether @list is the last entry in list @head
253 : : * @list: the entry to test
254 : : * @head: the head of the list
255 : : */
256 : : static inline int list_is_last(const struct list_head *list,
257 : : const struct list_head *head)
258 : : {
259 : 0 : return list->next == head;
260 : : }
261 : :
262 : : /**
263 : : * list_empty - tests whether a list is empty
264 : : * @head: the list to test.
265 : : */
266 : 5129 : static inline int list_empty(const struct list_head *head)
267 : : {
268 : 200063059 : return READ_ONCE(head->next) == head;
269 : : }
270 : :
271 : : /**
272 : : * list_empty_careful - tests whether a list is empty and not being modified
273 : : * @head: the list to test
274 : : *
275 : : * Description:
276 : : * tests whether a list is empty _and_ checks that no other CPU might be
277 : : * in the process of modifying either member (next or prev)
278 : : *
279 : : * NOTE: using list_empty_careful() without synchronization
280 : : * can only be safe if the only activity that can happen
281 : : * to the list entry is list_del_init(). Eg. it cannot be used
282 : : * if another CPU could re-list_add() it.
283 : : */
284 : : static inline int list_empty_careful(const struct list_head *head)
285 : : {
286 : 18558780 : struct list_head *next = head->next;
287 [ + + + + : 18558780 : return (next == head) && (next == head->prev);
+ + + + +
+ + + + +
- + + + -
+ # # # #
# # # # ]
288 : : }
289 : :
290 : : /**
291 : : * list_rotate_left - rotate the list to the left
292 : : * @head: the head of the list
293 : : */
294 : : static inline void list_rotate_left(struct list_head *head)
295 : : {
296 : : struct list_head *first;
297 : :
298 : : if (!list_empty(head)) {
299 : : first = head->next;
300 : : list_move_tail(first, head);
301 : : }
302 : : }
303 : :
304 : : /**
305 : : * list_rotate_to_front() - Rotate list to specific item.
306 : : * @list: The desired new front of the list.
307 : : * @head: The head of the list.
308 : : *
309 : : * Rotates list so that @list becomes the new front of the list.
310 : : */
311 : : static inline void list_rotate_to_front(struct list_head *list,
312 : : struct list_head *head)
313 : : {
314 : : /*
315 : : * Deletes the list head from the list denoted by @head and
316 : : * places it as the tail of @list, this effectively rotates the
317 : : * list so that @list is at the front.
318 : : */
319 : : list_move_tail(head, list);
320 : : }
321 : :
322 : : /**
323 : : * list_is_singular - tests whether a list has just one entry.
324 : : * @head: the list to test.
325 : : */
326 : : static inline int list_is_singular(const struct list_head *head)
327 : : {
328 [ + - + + : 2265843 : return !list_empty(head) && (head->next == head->prev);
+ + + + +
+ + + ]
329 : : }
330 : :
331 : : static inline void __list_cut_position(struct list_head *list,
332 : : struct list_head *head, struct list_head *entry)
333 : : {
334 : 1075 : struct list_head *new_first = entry->next;
335 : 1075 : list->next = head->next;
336 : 1075 : list->next->prev = list;
337 : 1075 : list->prev = entry;
338 : 1075 : entry->next = list;
339 : 1075 : head->next = new_first;
340 : 1075 : new_first->prev = head;
341 : : }
342 : :
343 : : /**
344 : : * list_cut_position - cut a list into two
345 : : * @list: a new list to add all removed entries
346 : : * @head: a list with entries
347 : : * @entry: an entry within head, could be the head itself
348 : : * and if so we won't cut the list
349 : : *
350 : : * This helper moves the initial part of @head, up to and
351 : : * including @entry, from @head to @list. You should
352 : : * pass on @entry an element you know is on @head. @list
353 : : * should be an empty list or a list you do not care about
354 : : * losing its data.
355 : : *
356 : : */
357 : 1075 : static inline void list_cut_position(struct list_head *list,
358 : : struct list_head *head, struct list_head *entry)
359 : : {
360 [ + - ]: 1075 : if (list_empty(head))
361 : : return;
362 [ + + - + ]: 1701 : if (list_is_singular(head) &&
363 [ # # ]: 626 : (head->next != entry && head != entry))
364 : : return;
365 [ - + ]: 1075 : if (entry == head)
366 : : INIT_LIST_HEAD(list);
367 : : else
368 : : __list_cut_position(list, head, entry);
369 : : }
370 : :
371 : : /**
372 : : * list_cut_before - cut a list into two, before given entry
373 : : * @list: a new list to add all removed entries
374 : : * @head: a list with entries
375 : : * @entry: an entry within head, could be the head itself
376 : : *
377 : : * This helper moves the initial part of @head, up to but
378 : : * excluding @entry, from @head to @list. You should pass
379 : : * in @entry an element you know is on @head. @list should
380 : : * be an empty list or a list you do not care about losing
381 : : * its data.
382 : : * If @entry == @head, all entries on @head are moved to
383 : : * @list.
384 : : */
385 : : static inline void list_cut_before(struct list_head *list,
386 : : struct list_head *head,
387 : : struct list_head *entry)
388 : : {
389 [ # # ]: 0 : if (head->next == entry) {
390 : : INIT_LIST_HEAD(list);
391 : : return;
392 : : }
393 : 0 : list->next = head->next;
394 : 0 : list->next->prev = list;
395 : 0 : list->prev = entry->prev;
396 : 0 : list->prev->next = list;
397 : 0 : head->next = entry;
398 : 0 : entry->prev = head;
399 : : }
400 : :
401 : : static inline void __list_splice(const struct list_head *list,
402 : : struct list_head *prev,
403 : : struct list_head *next)
404 : : {
405 : 5042596 : struct list_head *first = list->next;
406 : 5056693 : struct list_head *last = list->prev;
407 : :
408 : 5056693 : first->prev = prev;
409 : 5056693 : prev->next = first;
410 : :
411 : 5056693 : last->next = next;
412 : 5056693 : next->prev = last;
413 : : }
414 : :
415 : : /**
416 : : * list_splice - join two lists, this is designed for stacks
417 : : * @list: the new list to add.
418 : : * @head: the place to add it in the first list.
419 : : */
420 : : static inline void list_splice(const struct list_head *list,
421 : : struct list_head *head)
422 : : {
423 [ + + # # : 2084963 : if (!list_empty(list))
# # - + -
+ ]
424 : 22758 : __list_splice(list, head, head->next);
425 : : }
426 : :
427 : : /**
428 : : * list_splice_tail - join two lists, each list being a queue
429 : : * @list: the new list to add.
430 : : * @head: the place to add it in the first list.
431 : : */
432 : : static inline void list_splice_tail(struct list_head *list,
433 : : struct list_head *head)
434 : : {
435 [ - + # # ]: 836 : if (!list_empty(list))
436 : 0 : __list_splice(list, head->prev, head);
437 : : }
438 : :
439 : : /**
440 : : * list_splice_init - join two lists and reinitialise the emptied list.
441 : : * @list: the new list to add.
442 : : * @head: the place to add it in the first list.
443 : : *
444 : : * The list at @list is reinitialised
445 : : */
446 : : static inline void list_splice_init(struct list_head *list,
447 : : struct list_head *head)
448 : : {
449 [ + + + + : 2876906 : if (!list_empty(list)) {
# # # # #
# # # #
# ]
450 : 2091567 : __list_splice(list, head, head->next);
451 : : INIT_LIST_HEAD(list);
452 : : }
453 : : }
454 : :
455 : : /**
456 : : * list_splice_tail_init - join two lists and reinitialise the emptied list
457 : : * @list: the new list to add.
458 : : * @head: the place to add it in the first list.
459 : : *
460 : : * Each of the lists is a queue.
461 : : * The list at @list is reinitialised
462 : : */
463 : : static inline void list_splice_tail_init(struct list_head *list,
464 : : struct list_head *head)
465 : : {
466 [ + + + + : 2431101 : if (!list_empty(list)) {
+ + - + -
+ ]
467 : 2252742 : __list_splice(list, head->prev, head);
468 : : INIT_LIST_HEAD(list);
469 : : }
470 : : }
471 : :
472 : : /**
473 : : * list_entry - get the struct for this entry
474 : : * @ptr: the &struct list_head pointer.
475 : : * @type: the type of the struct this is embedded in.
476 : : * @member: the name of the list_head within the struct.
477 : : */
478 : : #define list_entry(ptr, type, member) \
479 : : container_of(ptr, type, member)
480 : :
481 : : /**
482 : : * list_first_entry - get the first element from a list
483 : : * @ptr: the list head to take the element from.
484 : : * @type: the type of the struct this is embedded in.
485 : : * @member: the name of the list_head within the struct.
486 : : *
487 : : * Note, that list is expected to be not empty.
488 : : */
489 : : #define list_first_entry(ptr, type, member) \
490 : : list_entry((ptr)->next, type, member)
491 : :
492 : : /**
493 : : * list_last_entry - get the last element from a list
494 : : * @ptr: the list head to take the element from.
495 : : * @type: the type of the struct this is embedded in.
496 : : * @member: the name of the list_head within the struct.
497 : : *
498 : : * Note, that list is expected to be not empty.
499 : : */
500 : : #define list_last_entry(ptr, type, member) \
501 : : list_entry((ptr)->prev, type, member)
502 : :
503 : : /**
504 : : * list_first_entry_or_null - get the first element from a list
505 : : * @ptr: the list head to take the element from.
506 : : * @type: the type of the struct this is embedded in.
507 : : * @member: the name of the list_head within the struct.
508 : : *
509 : : * Note that if the list is empty, it returns NULL.
510 : : */
511 : : #define list_first_entry_or_null(ptr, type, member) ({ \
512 : : struct list_head *head__ = (ptr); \
513 : : struct list_head *pos__ = READ_ONCE(head__->next); \
514 : : pos__ != head__ ? list_entry(pos__, type, member) : NULL; \
515 : : })
516 : :
517 : : /**
518 : : * list_next_entry - get the next element in list
519 : : * @pos: the type * to cursor
520 : : * @member: the name of the list_head within the struct.
521 : : */
522 : : #define list_next_entry(pos, member) \
523 : : list_entry((pos)->member.next, typeof(*(pos)), member)
524 : :
525 : : /**
526 : : * list_prev_entry - get the prev element in list
527 : : * @pos: the type * to cursor
528 : : * @member: the name of the list_head within the struct.
529 : : */
530 : : #define list_prev_entry(pos, member) \
531 : : list_entry((pos)->member.prev, typeof(*(pos)), member)
532 : :
533 : : /**
534 : : * list_for_each - iterate over a list
535 : : * @pos: the &struct list_head to use as a loop cursor.
536 : : * @head: the head for your list.
537 : : */
538 : : #define list_for_each(pos, head) \
539 : : for (pos = (head)->next; pos != (head); pos = pos->next)
540 : :
541 : : /**
542 : : * list_for_each_prev - iterate over a list backwards
543 : : * @pos: the &struct list_head to use as a loop cursor.
544 : : * @head: the head for your list.
545 : : */
546 : : #define list_for_each_prev(pos, head) \
547 : : for (pos = (head)->prev; pos != (head); pos = pos->prev)
548 : :
549 : : /**
550 : : * list_for_each_safe - iterate over a list safe against removal of list entry
551 : : * @pos: the &struct list_head to use as a loop cursor.
552 : : * @n: another &struct list_head to use as temporary storage
553 : : * @head: the head for your list.
554 : : */
555 : : #define list_for_each_safe(pos, n, head) \
556 : : for (pos = (head)->next, n = pos->next; pos != (head); \
557 : : pos = n, n = pos->next)
558 : :
559 : : /**
560 : : * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
561 : : * @pos: the &struct list_head to use as a loop cursor.
562 : : * @n: another &struct list_head to use as temporary storage
563 : : * @head: the head for your list.
564 : : */
565 : : #define list_for_each_prev_safe(pos, n, head) \
566 : : for (pos = (head)->prev, n = pos->prev; \
567 : : pos != (head); \
568 : : pos = n, n = pos->prev)
569 : :
570 : : /**
571 : : * list_for_each_entry - iterate over list of given type
572 : : * @pos: the type * to use as a loop cursor.
573 : : * @head: the head for your list.
574 : : * @member: the name of the list_head within the struct.
575 : : */
576 : : #define list_for_each_entry(pos, head, member) \
577 : : for (pos = list_first_entry(head, typeof(*pos), member); \
578 : : &pos->member != (head); \
579 : : pos = list_next_entry(pos, member))
580 : :
581 : : /**
582 : : * list_for_each_entry_reverse - iterate backwards over list of given type.
583 : : * @pos: the type * to use as a loop cursor.
584 : : * @head: the head for your list.
585 : : * @member: the name of the list_head within the struct.
586 : : */
587 : : #define list_for_each_entry_reverse(pos, head, member) \
588 : : for (pos = list_last_entry(head, typeof(*pos), member); \
589 : : &pos->member != (head); \
590 : : pos = list_prev_entry(pos, member))
591 : :
592 : : /**
593 : : * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
594 : : * @pos: the type * to use as a start point
595 : : * @head: the head of the list
596 : : * @member: the name of the list_head within the struct.
597 : : *
598 : : * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
599 : : */
600 : : #define list_prepare_entry(pos, head, member) \
601 : : ((pos) ? : list_entry(head, typeof(*pos), member))
602 : :
603 : : /**
604 : : * list_for_each_entry_continue - continue iteration over list of given type
605 : : * @pos: the type * to use as a loop cursor.
606 : : * @head: the head for your list.
607 : : * @member: the name of the list_head within the struct.
608 : : *
609 : : * Continue to iterate over list of given type, continuing after
610 : : * the current position.
611 : : */
612 : : #define list_for_each_entry_continue(pos, head, member) \
613 : : for (pos = list_next_entry(pos, member); \
614 : : &pos->member != (head); \
615 : : pos = list_next_entry(pos, member))
616 : :
617 : : /**
618 : : * list_for_each_entry_continue_reverse - iterate backwards from the given point
619 : : * @pos: the type * to use as a loop cursor.
620 : : * @head: the head for your list.
621 : : * @member: the name of the list_head within the struct.
622 : : *
623 : : * Start to iterate over list of given type backwards, continuing after
624 : : * the current position.
625 : : */
626 : : #define list_for_each_entry_continue_reverse(pos, head, member) \
627 : : for (pos = list_prev_entry(pos, member); \
628 : : &pos->member != (head); \
629 : : pos = list_prev_entry(pos, member))
630 : :
631 : : /**
632 : : * list_for_each_entry_from - iterate over list of given type from the current point
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 : : * Iterate over list of given type, continuing from current position.
638 : : */
639 : : #define list_for_each_entry_from(pos, head, member) \
640 : : for (; &pos->member != (head); \
641 : : pos = list_next_entry(pos, member))
642 : :
643 : : /**
644 : : * list_for_each_entry_from_reverse - iterate backwards over list of given type
645 : : * from the current point
646 : : * @pos: the type * to use as a loop cursor.
647 : : * @head: the head for your list.
648 : : * @member: the name of the list_head within the struct.
649 : : *
650 : : * Iterate backwards over list of given type, continuing from current position.
651 : : */
652 : : #define list_for_each_entry_from_reverse(pos, head, member) \
653 : : for (; &pos->member != (head); \
654 : : pos = list_prev_entry(pos, member))
655 : :
656 : : /**
657 : : * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
658 : : * @pos: the type * to use as a loop cursor.
659 : : * @n: another type * to use as temporary storage
660 : : * @head: the head for your list.
661 : : * @member: the name of the list_head within the struct.
662 : : */
663 : : #define list_for_each_entry_safe(pos, n, head, member) \
664 : : for (pos = list_first_entry(head, typeof(*pos), member), \
665 : : n = list_next_entry(pos, member); \
666 : : &pos->member != (head); \
667 : : pos = n, n = list_next_entry(n, member))
668 : :
669 : : /**
670 : : * list_for_each_entry_safe_continue - continue list iteration safe against removal
671 : : * @pos: the type * to use as a loop cursor.
672 : : * @n: another type * to use as temporary storage
673 : : * @head: the head for your list.
674 : : * @member: the name of the list_head within the struct.
675 : : *
676 : : * Iterate over list of given type, continuing after current point,
677 : : * safe against removal of list entry.
678 : : */
679 : : #define list_for_each_entry_safe_continue(pos, n, head, member) \
680 : : for (pos = list_next_entry(pos, member), \
681 : : n = list_next_entry(pos, member); \
682 : : &pos->member != (head); \
683 : : pos = n, n = list_next_entry(n, member))
684 : :
685 : : /**
686 : : * list_for_each_entry_safe_from - iterate over list from current point safe against removal
687 : : * @pos: the type * to use as a loop cursor.
688 : : * @n: another type * to use as temporary storage
689 : : * @head: the head for your list.
690 : : * @member: the name of the list_head within the struct.
691 : : *
692 : : * Iterate over list of given type from current point, safe against
693 : : * removal of list entry.
694 : : */
695 : : #define list_for_each_entry_safe_from(pos, n, head, member) \
696 : : for (n = list_next_entry(pos, member); \
697 : : &pos->member != (head); \
698 : : pos = n, n = list_next_entry(n, member))
699 : :
700 : : /**
701 : : * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal
702 : : * @pos: the type * to use as a loop cursor.
703 : : * @n: another type * to use as temporary storage
704 : : * @head: the head for your list.
705 : : * @member: the name of the list_head within the struct.
706 : : *
707 : : * Iterate backwards over list of given type, safe against removal
708 : : * of list entry.
709 : : */
710 : : #define list_for_each_entry_safe_reverse(pos, n, head, member) \
711 : : for (pos = list_last_entry(head, typeof(*pos), member), \
712 : : n = list_prev_entry(pos, member); \
713 : : &pos->member != (head); \
714 : : pos = n, n = list_prev_entry(n, member))
715 : :
716 : : /**
717 : : * list_safe_reset_next - reset a stale list_for_each_entry_safe loop
718 : : * @pos: the loop cursor used in the list_for_each_entry_safe loop
719 : : * @n: temporary storage used in list_for_each_entry_safe
720 : : * @member: the name of the list_head within the struct.
721 : : *
722 : : * list_safe_reset_next is not safe to use in general if the list may be
723 : : * modified concurrently (eg. the lock is dropped in the loop body). An
724 : : * exception to this is if the cursor element (pos) is pinned in the list,
725 : : * and list_safe_reset_next is called after re-taking the lock and before
726 : : * completing the current iteration of the loop body.
727 : : */
728 : : #define list_safe_reset_next(pos, n, member) \
729 : : n = list_next_entry(pos, member)
730 : :
731 : : /*
732 : : * Double linked lists with a single pointer list head.
733 : : * Mostly useful for hash tables where the two pointer list head is
734 : : * too wasteful.
735 : : * You lose the ability to access the tail in O(1).
736 : : */
737 : :
738 : : #define HLIST_HEAD_INIT { .first = NULL }
739 : : #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
740 : : #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
741 : : static inline void INIT_HLIST_NODE(struct hlist_node *h)
742 : : {
743 : 34191158 : h->next = NULL;
744 : 34191158 : h->pprev = NULL;
745 : : }
746 : :
747 : 0 : static inline int hlist_unhashed(const struct hlist_node *h)
748 : : {
749 : 18901663 : return !h->pprev;
750 : : }
751 : :
752 : : static inline int hlist_empty(const struct hlist_head *h)
753 : : {
754 [ # # # # ]: 3950918 : return !READ_ONCE(h->first);
755 : : }
756 : :
757 : : static inline void __hlist_del(struct hlist_node *n)
758 : : {
759 : 9273170 : struct hlist_node *next = n->next;
760 : 2655592 : struct hlist_node **pprev = n->pprev;
761 : :
762 : 9277359 : WRITE_ONCE(*pprev, next);
763 [ + + + + : 9277359 : if (next)
+ + # # #
# + + + +
+ + # # #
# ]
764 : 526362 : next->pprev = pprev;
765 : : }
766 : :
767 : : static inline void hlist_del(struct hlist_node *n)
768 : : {
769 : : __hlist_del(n);
770 : 11980 : n->next = LIST_POISON1;
771 : 11980 : n->pprev = LIST_POISON2;
772 : : }
773 : :
774 : : static inline void hlist_del_init(struct hlist_node *n)
775 : : {
776 [ + + + - : 6455010 : if (!hlist_unhashed(n)) {
+ + ]
777 : : __hlist_del(n);
778 : : INIT_HLIST_NODE(n);
779 : : }
780 : : }
781 : :
782 : : static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
783 : : {
784 : 14656580 : struct hlist_node *first = h->first;
785 : 14659064 : n->next = first;
786 [ + + + + : 14657615 : if (first)
+ + + + +
+ # # #
# ]
787 : 541337 : first->pprev = &n->next;
788 : 14658857 : WRITE_ONCE(h->first, n);
789 : 14659064 : n->pprev = &h->first;
790 : : }
791 : :
792 : : /* next must be != NULL */
793 : : static inline void hlist_add_before(struct hlist_node *n,
794 : : struct hlist_node *next)
795 : : {
796 : : n->pprev = next->pprev;
797 : : n->next = next;
798 : : next->pprev = &n->next;
799 : : WRITE_ONCE(*(n->pprev), n);
800 : : }
801 : :
802 : : static inline void hlist_add_behind(struct hlist_node *n,
803 : : struct hlist_node *prev)
804 : : {
805 : : n->next = prev->next;
806 : : prev->next = n;
807 : : n->pprev = &prev->next;
808 : :
809 : : if (n->next)
810 : : n->next->pprev = &n->next;
811 : : }
812 : :
813 : : /* after that we'll appear to be on some hlist and hlist_del will work */
814 : : static inline void hlist_add_fake(struct hlist_node *n)
815 : : {
816 : : n->pprev = &n->next;
817 : : }
818 : :
819 : : static inline bool hlist_fake(struct hlist_node *h)
820 : : {
821 : 215871 : return h->pprev == &h->next;
822 : : }
823 : :
824 : : /*
825 : : * Check whether the node is the only node of the head without
826 : : * accessing head:
827 : : */
828 : : static inline bool
829 : : hlist_is_singular_node(struct hlist_node *n, struct hlist_head *h)
830 : : {
831 [ + + + + ]: 1413291 : return !n->next && n->pprev == &h->first;
832 : : }
833 : :
834 : : /*
835 : : * Move a list from one list head to another. Fixup the pprev
836 : : * reference of the first entry if it exists.
837 : : */
838 : : static inline void hlist_move_list(struct hlist_head *old,
839 : : struct hlist_head *new)
840 : : {
841 : 550656 : new->first = old->first;
842 [ + + ]: 550656 : if (new->first)
843 : 535856 : new->first->pprev = &new->first;
844 : 550656 : old->first = NULL;
845 : : }
846 : :
847 : : #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
848 : :
849 : : #define hlist_for_each(pos, head) \
850 : : for (pos = (head)->first; pos ; pos = pos->next)
851 : :
852 : : #define hlist_for_each_safe(pos, n, head) \
853 : : for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
854 : : pos = n)
855 : :
856 : : #define hlist_entry_safe(ptr, type, member) \
857 : : ({ typeof(ptr) ____ptr = (ptr); \
858 : : ____ptr ? hlist_entry(____ptr, type, member) : NULL; \
859 : : })
860 : :
861 : : /**
862 : : * hlist_for_each_entry - iterate over list of given type
863 : : * @pos: the type * to use as a loop cursor.
864 : : * @head: the head for your list.
865 : : * @member: the name of the hlist_node within the struct.
866 : : */
867 : : #define hlist_for_each_entry(pos, head, member) \
868 : : for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\
869 : : pos; \
870 : : pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
871 : :
872 : : /**
873 : : * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
874 : : * @pos: the type * to use as a loop cursor.
875 : : * @member: the name of the hlist_node within the struct.
876 : : */
877 : : #define hlist_for_each_entry_continue(pos, member) \
878 : : for (pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member);\
879 : : pos; \
880 : : pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
881 : :
882 : : /**
883 : : * hlist_for_each_entry_from - iterate over a hlist continuing from current point
884 : : * @pos: the type * to use as a loop cursor.
885 : : * @member: the name of the hlist_node within the struct.
886 : : */
887 : : #define hlist_for_each_entry_from(pos, member) \
888 : : for (; pos; \
889 : : pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
890 : :
891 : : /**
892 : : * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
893 : : * @pos: the type * to use as a loop cursor.
894 : : * @n: another &struct hlist_node to use as temporary storage
895 : : * @head: the head for your list.
896 : : * @member: the name of the hlist_node within the struct.
897 : : */
898 : : #define hlist_for_each_entry_safe(pos, n, head, member) \
899 : : for (pos = hlist_entry_safe((head)->first, typeof(*pos), member);\
900 : : pos && ({ n = pos->member.next; 1; }); \
901 : : pos = hlist_entry_safe(n, typeof(*pos), member))
902 : :
903 : : #endif
|
