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