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