RaspberrPi project source code
view | history | commit | commitdiff
guowenxue
2024-03-14 7fa125e56f1de17c2f6aeb9a410ff02ac4e78e85
commit | author | age
d6b4a7 1 /*********************************************************************************
G 2  *      Copyright:  (C) 2020 LingYun IoT System Studio
3  *                  All rights reserved.
4  *
5  *       Filename:  list.h
6  *    Description:  This file is copied from Linux kernel, which provide link list API.
7  *
8  *        Version:  1.0.0(08/09/2020)
9  *         Author:  Guo Wenxue <guowenxue@gmail.com>
10  *      ChangeLog:  1, Release initial version on "08/09/2020 02:24:34 AM"
11  *
12  ********************************************************************************/
13
14 #ifndef _LINUX_LIST_H
15 #define _LINUX_LIST_H
16
17 #include <linux/stddef.h>
18
19
20 /**
21  * container_of - cast a member of a structure out to the containing structure
22  * @ptr:    the pointer to the member.
23  * @type:   the type of the container struct this is embedded in.
24  * @member: the name of the member within the struct.
25  *
26  */
27 #undef offsetof
28 #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
29 #define container_of(ptr, type, member) ({          \
30     const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
31     (type *)( (char *)__mptr - offsetof(type,member) );})
32
33
34 /*
35  * Architectures might want to move the poison pointer offset
36  * into some well-recognized area such as 0xdead000000000000,
37  * that is also not mappable by user-space exploits:
38  */
39 #ifdef CONFIG_ILLEGAL_POINTER_VALUE
40 # define POISON_POINTER_DELTA _AC(CONFIG_ILLEGAL_POINTER_VALUE, UL)
41 #else
42 # define POISON_POINTER_DELTA 0
43 #endif
44
45 /*
46  * These are non-NULL pointers that will result in page faults
47  * under normal circumstances, used to verify that nobody uses
48  * non-initialized list entries.
49  */
50 #define LIST_POISON1  ((void *) 0x00100100 + POISON_POINTER_DELTA)
51 #define LIST_POISON2  ((void *) 0x00200200 + POISON_POINTER_DELTA)
52
53 #ifndef ARCH_HAS_PREFETCH
54 #define ARCH_HAS_PREFETCH
55 static inline void prefetch(const void *x) {;}
56 #endif
57
58 /*
59  * Simple doubly linked list implementation.
60  *
61  * Some of the internal functions ("__xxx") are useful when
62  * manipulating whole lists rather than single entries, as
63  * sometimes we already know the next/prev entries and we can
64  * generate better code by using them directly rather than
65  * using the generic single-entry routines.
66  */
67
68 struct list_head {
69     struct list_head *next, *prev;
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 static inline void INIT_LIST_HEAD(struct list_head *list)
78 {
79     list->next = list;
80     list->prev = list;
81 }
82
83 /*
84  * Insert a new entry between two known consecutive entries.
85  *
86  * This is only for internal list manipulation where we know
87  * the prev/next entries already!
88  */
89 static inline void __list_add(struct list_head *new,
90                   struct list_head *prev,
91                   struct list_head *next)
92 {
93     next->prev = new;
94     new->next = next;
95     new->prev = prev;
96     prev->next = new;
97 }
98
99 /**
100  * list_add - add a new entry
101  * @new: new entry to be added
102  * @head: list head to add it after
103  *
104  * Insert a new entry after the specified head.
105  * This is good for implementing stacks.
106  */
107 static inline void list_add(struct list_head *new, struct list_head *head)
108 {
109     __list_add(new, head, head->next);
110 }
111
112 /**
113  * list_add_tail - add a new entry
114  * @new: new entry to be added
115  * @head: list head to add it before
116  *
117  * Insert a new entry before the specified head.
118  * This is useful for implementing queues.
119  */
120 static inline void list_add_tail(struct list_head *new, struct list_head *head)
121 {
122     __list_add(new, head->prev, head);
123 }
124
125 /*
126  * Delete a list entry by making the prev/next entries
127  * point to each other.
128  *
129  * This is only for internal list manipulation where we know
130  * the prev/next entries already!
131  */
132 static inline void __list_del(struct list_head *prev, struct list_head *next)
133 {
134     next->prev = prev;
135     prev->next = 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 static inline void list_del(struct list_head *entry)
145 {
146     __list_del(entry->prev, entry->next);
147     entry->next = LIST_POISON1;
148     entry->prev = LIST_POISON2;
149 }
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 static inline void list_replace(struct list_head *old,
159                 struct list_head *new)
160 {
161     new->next = old->next;
162     new->next->prev = new;
163     new->prev = old->prev;
164     new->prev->next = new;
165 }
166
167 static inline void list_replace_init(struct list_head *old,
168                     struct list_head *new)
169 {
170     list_replace(old, new);
171     INIT_LIST_HEAD(old);
172 }
173
174 /**
175  * list_del_init - deletes entry from list and reinitialize it.
176  * @entry: the element to delete from the list.
177  */
178 static inline void list_del_init(struct list_head *entry)
179 {
180     __list_del(entry->prev, entry->next);
181     INIT_LIST_HEAD(entry);
182 }
183
184 /**
185  * list_move - delete from one list and add as another's head
186  * @list: the entry to move
187  * @head: the head that will precede our entry
188  */
189 static inline void list_move(struct list_head *list, struct list_head *head)
190 {
191     __list_del(list->prev, list->next);
192     list_add(list, head);
193 }
194
195 /**
196  * list_move_tail - delete from one list and add as another's tail
197  * @list: the entry to move
198  * @head: the head that will follow our entry
199  */
200 static inline void list_move_tail(struct list_head *list,
201                   struct list_head *head)
202 {
203     __list_del(list->prev, list->next);
204     list_add_tail(list, head);
205 }
206
207 /**
208  * list_is_last - tests whether @list is the last entry in list @head
209  * @list: the entry to test
210  * @head: the head of the list
211  */
212 static inline int list_is_last(const struct list_head *list,
213                 const struct list_head *head)
214 {
215     return list->next == head;
216 }
217
218 /**
219  * list_empty - tests whether a list is empty
220  * @head: the list to test.
221  */
222 static inline int list_empty(const struct list_head *head)
223 {
224     return head->next == head;
225 }
226
227 /**
228  * list_empty_careful - tests whether a list is empty and not being modified
229  * @head: the list to test
230  *
231  * Description:
232  * tests whether a list is empty _and_ checks that no other CPU might be
233  * in the process of modifying either member (next or prev)
234  *
235  * NOTE: using list_empty_careful() without synchronization
236  * can only be safe if the only activity that can happen
237  * to the list entry is list_del_init(). Eg. it cannot be used
238  * if another CPU could re-list_add() it.
239  */
240 static inline int list_empty_careful(const struct list_head *head)
241 {
242     struct list_head *next = head->next;
243     return (next == head) && (next == head->prev);
244 }
245
246 /**
247  * list_is_singular - tests whether a list has just one entry.
248  * @head: the list to test.
249  */
250 static inline int list_is_singular(const struct list_head *head)
251 {
252     return !list_empty(head) && (head->next == head->prev);
253 }
254
255 static inline void __list_cut_position(struct list_head *list,
256         struct list_head *head, struct list_head *entry)
257 {
258     struct list_head *new_first = entry->next;
259     list->next = head->next;
260     list->next->prev = list;
261     list->prev = entry;
262     entry->next = list;
263     head->next = new_first;
264     new_first->prev = head;
265 }
266
267 /**
268  * list_cut_position - cut a list into two
269  * @list: a new list to add all removed entries
270  * @head: a list with entries
271  * @entry: an entry within head, could be the head itself
272  *    and if so we won't cut the list
273  *
274  * This helper moves the initial part of @head, up to and
275  * including @entry, from @head to @list. You should
276  * pass on @entry an element you know is on @head. @list
277  * should be an empty list or a list you do not care about
278  * losing its data.
279  *
280  */
281 static inline void list_cut_position(struct list_head *list,
282         struct list_head *head, struct list_head *entry)
283 {
284     if (list_empty(head))
285         return;
286     if (list_is_singular(head) &&
287         (head->next != entry && head != entry))
288         return;
289     if (entry == head)
290         INIT_LIST_HEAD(list);
291     else
292         __list_cut_position(list, head, entry);
293 }
294
295 static inline void __list_splice(const struct list_head *list,
296                  struct list_head *prev,
297                  struct list_head *next)
298 {
299     struct list_head *first = list->next;
300     struct list_head *last = list->prev;
301
302     first->prev = prev;
303     prev->next = first;
304
305     last->next = next;
306     next->prev = last;
307 }
308
309 /**
310  * list_splice - join two lists, this is designed for stacks
311  * @list: the new list to add.
312  * @head: the place to add it in the first list.
313  */
314 static inline void list_splice(const struct list_head *list,
315                 struct list_head *head)
316 {
317     if (!list_empty(list))
318         __list_splice(list, head, head->next);
319 }
320
321 /**
322  * list_splice_tail - join two lists, each list being a queue
323  * @list: the new list to add.
324  * @head: the place to add it in the first list.
325  */
326 static inline void list_splice_tail(struct list_head *list,
327                 struct list_head *head)
328 {
329     if (!list_empty(list))
330         __list_splice(list, head->prev, head);
331 }
332
333 /**
334  * list_splice_init - join two lists and reinitialise the emptied list.
335  * @list: the new list to add.
336  * @head: the place to add it in the first list.
337  *
338  * The list at @list is reinitialised
339  */
340 static inline void list_splice_init(struct list_head *list,
341                     struct list_head *head)
342 {
343     if (!list_empty(list)) {
344         __list_splice(list, head, head->next);
345         INIT_LIST_HEAD(list);
346     }
347 }
348
349 /**
350  * list_splice_tail_init - join two lists and reinitialise the emptied list
351  * @list: the new list to add.
352  * @head: the place to add it in the first list.
353  *
354  * Each of the lists is a queue.
355  * The list at @list is reinitialised
356  */
357 static inline void list_splice_tail_init(struct list_head *list,
358                      struct list_head *head)
359 {
360     if (!list_empty(list)) {
361         __list_splice(list, head->prev, head);
362         INIT_LIST_HEAD(list);
363     }
364 }
365
366 /**
367  * list_entry - get the struct for this entry
368  * @ptr:    the &struct list_head pointer.
369  * @type:    the type of the struct this is embedded in.
370  * @member:    the name of the list_struct within the struct.
371  */
372 #define list_entry(ptr, type, member) \
373     container_of(ptr, type, member)
374
375 /**
376  * list_first_entry - get the first element from a list
377  * @ptr:    the list head to take the element from.
378  * @type:    the type of the struct this is embedded in.
379  * @member:    the name of the list_struct within the struct.
380  *
381  * Note, that list is expected to be not empty.
382  */
383 #define list_first_entry(ptr, type, member) \
384     list_entry((ptr)->next, type, member)
385
386 /**
387  * list_for_each    -    iterate over a list
388  * @pos:    the &struct list_head to use as a loop cursor.
389  * @head:    the head for your list.
390  */
391 #define list_for_each(pos, head) \
392     for (pos = (head)->next; prefetch(pos->next), pos != (head); \
393         pos = pos->next)
394
395 /**
396  * __list_for_each    -    iterate over a list
397  * @pos:    the &struct list_head to use as a loop cursor.
398  * @head:    the head for your list.
399  *
400  * This variant differs from list_for_each() in that it's the
401  * simplest possible list iteration code, no prefetching is done.
402  * Use this for code that knows the list to be very short (empty
403  * or 1 entry) most of the time.
404  */
405 #define __list_for_each(pos, head) \
406     for (pos = (head)->next; pos != (head); pos = pos->next)
407
408 /**
409  * list_for_each_prev    -    iterate over a list backwards
410  * @pos:    the &struct list_head to use as a loop cursor.
411  * @head:    the head for your list.
412  */
413 #define list_for_each_prev(pos, head) \
414     for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
415         pos = pos->prev)
416
417 /**
418  * list_for_each_safe - iterate over a list safe against removal of list entry
419  * @pos:    the &struct list_head to use as a loop cursor.
420  * @n:        another &struct list_head to use as temporary storage
421  * @head:    the head for your list.
422  */
423 #define list_for_each_safe(pos, n, head) \
424     for (pos = (head)->next, n = pos->next; pos != (head); \
425         pos = n, n = pos->next)
426
427 /**
428  * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
429  * @pos:    the &struct list_head to use as a loop cursor.
430  * @n:        another &struct list_head to use as temporary storage
431  * @head:    the head for your list.
432  */
433 #define list_for_each_prev_safe(pos, n, head) \
434     for (pos = (head)->prev, n = pos->prev; \
435          prefetch(pos->prev), pos != (head); \
436          pos = n, n = pos->prev)
437
438 /**
439  * list_for_each_entry    -    iterate over list of given type
440  * @pos:    the type * to use as a loop cursor.
441  * @head:    the head for your list.
442  * @member:    the name of the list_struct within the struct.
443  */
444 #define list_for_each_entry(pos, head, member)                \
445     for (pos = list_entry((head)->next, typeof(*pos), member);    \
446          prefetch(pos->member.next), &pos->member != (head);    \
447          pos = list_entry(pos->member.next, typeof(*pos), member))
448
449 /**
450  * list_for_each_entry_reverse - iterate backwards over list of given type.
451  * @pos:    the type * to use as a loop cursor.
452  * @head:    the head for your list.
453  * @member:    the name of the list_struct within the struct.
454  */
455 #define list_for_each_entry_reverse(pos, head, member)            \
456     for (pos = list_entry((head)->prev, typeof(*pos), member);    \
457          prefetch(pos->member.prev), &pos->member != (head);    \
458          pos = list_entry(pos->member.prev, typeof(*pos), member))
459
460 /**
461  * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
462  * @pos:    the type * to use as a start point
463  * @head:    the head of the list
464  * @member:    the name of the list_struct within the struct.
465  *
466  * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
467  */
468 #define list_prepare_entry(pos, head, member) \
469     ((pos) ? : list_entry(head, typeof(*pos), member))
470
471 /**
472  * list_for_each_entry_continue - continue iteration over list of given type
473  * @pos:    the type * to use as a loop cursor.
474  * @head:    the head for your list.
475  * @member:    the name of the list_struct within the struct.
476  *
477  * Continue to iterate over list of given type, continuing after
478  * the current position.
479  */
480 #define list_for_each_entry_continue(pos, head, member)         \
481     for (pos = list_entry(pos->member.next, typeof(*pos), member);    \
482          prefetch(pos->member.next), &pos->member != (head);    \
483          pos = list_entry(pos->member.next, typeof(*pos), member))
484
485 /**
486  * list_for_each_entry_continue_reverse - iterate backwards from the given point
487  * @pos:    the type * to use as a loop cursor.
488  * @head:    the head for your list.
489  * @member:    the name of the list_struct within the struct.
490  *
491  * Start to iterate over list of given type backwards, continuing after
492  * the current position.
493  */
494 #define list_for_each_entry_continue_reverse(pos, head, member)        \
495     for (pos = list_entry(pos->member.prev, typeof(*pos), member);    \
496          prefetch(pos->member.prev), &pos->member != (head);    \
497          pos = list_entry(pos->member.prev, typeof(*pos), member))
498
499 /**
500  * list_for_each_entry_from - iterate over list of given type from the current point
501  * @pos:    the type * to use as a loop cursor.
502  * @head:    the head for your list.
503  * @member:    the name of the list_struct within the struct.
504  *
505  * Iterate over list of given type, continuing from current position.
506  */
507 #define list_for_each_entry_from(pos, head, member)            \
508     for (; prefetch(pos->member.next), &pos->member != (head);    \
509          pos = list_entry(pos->member.next, typeof(*pos), member))
510
511 /**
512  * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
513  * @pos:    the type * to use as a loop cursor.
514  * @n:        another type * to use as temporary storage
515  * @head:    the head for your list.
516  * @member:    the name of the list_struct within the struct.
517  */
518 #define list_for_each_entry_safe(pos, n, head, member)            \
519     for (pos = list_entry((head)->next, typeof(*pos), member),    \
520         n = list_entry(pos->member.next, typeof(*pos), member);    \
521          &pos->member != (head);                    \
522          pos = n, n = list_entry(n->member.next, typeof(*n), member))
523
524 /**
525  * list_for_each_entry_safe_continue
526  * @pos:    the type * to use as a loop cursor.
527  * @n:        another type * to use as temporary storage
528  * @head:    the head for your list.
529  * @member:    the name of the list_struct within the struct.
530  *
531  * Iterate over list of given type, continuing after current point,
532  * safe against removal of list entry.
533  */
534 #define list_for_each_entry_safe_continue(pos, n, head, member)         \
535     for (pos = list_entry(pos->member.next, typeof(*pos), member),        \
536         n = list_entry(pos->member.next, typeof(*pos), member);        \
537          &pos->member != (head);                        \
538          pos = n, n = list_entry(n->member.next, typeof(*n), member))
539
540 /**
541  * list_for_each_entry_safe_from
542  * @pos:    the type * to use as a loop cursor.
543  * @n:        another type * to use as temporary storage
544  * @head:    the head for your list.
545  * @member:    the name of the list_struct within the struct.
546  *
547  * Iterate over list of given type from current point, safe against
548  * removal of list entry.
549  */
550 #define list_for_each_entry_safe_from(pos, n, head, member)            \
551     for (n = list_entry(pos->member.next, typeof(*pos), member);        \
552          &pos->member != (head);                        \
553          pos = n, n = list_entry(n->member.next, typeof(*n), member))
554
555 /**
556  * list_for_each_entry_safe_reverse
557  * @pos:    the type * to use as a loop cursor.
558  * @n:        another type * to use as temporary storage
559  * @head:    the head for your list.
560  * @member:    the name of the list_struct within the struct.
561  *
562  * Iterate backwards over list of given type, safe against removal
563  * of list entry.
564  */
565 #define list_for_each_entry_safe_reverse(pos, n, head, member)        \
566     for (pos = list_entry((head)->prev, typeof(*pos), member),    \
567         n = list_entry(pos->member.prev, typeof(*pos), member);    \
568          &pos->member != (head);                    \
569          pos = n, n = list_entry(n->member.prev, typeof(*n), member))
570
571 /*
572  * Double linked lists with a single pointer list head.
573  * Mostly useful for hash tables where the two pointer list head is
574  * too wasteful.
575  * You lose the ability to access the tail in O(1).
576  */
577
578 struct hlist_head {
579     struct hlist_node *first;
580 };
581
582 struct hlist_node {
583     struct hlist_node *next, **pprev;
584 };
585
586 #define HLIST_HEAD_INIT { .first = NULL }
587 #define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
588 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
589 static inline void INIT_HLIST_NODE(struct hlist_node *h)
590 {
591     h->next = NULL;
592     h->pprev = NULL;
593 }
594
595 static inline int hlist_unhashed(const struct hlist_node *h)
596 {
597     return !h->pprev;
598 }
599
600 static inline int hlist_empty(const struct hlist_head *h)
601 {
602     return !h->first;
603 }
604
605 static inline void __hlist_del(struct hlist_node *n)
606 {
607     struct hlist_node *next = n->next;
608     struct hlist_node **pprev = n->pprev;
609     *pprev = next;
610     if (next)
611         next->pprev = pprev;
612 }
613
614 static inline void hlist_del(struct hlist_node *n)
615 {
616     __hlist_del(n);
617     n->next = LIST_POISON1;
618     n->pprev = LIST_POISON2;
619 }
620
621 static inline void hlist_del_init(struct hlist_node *n)
622 {
623     if (!hlist_unhashed(n)) {
624         __hlist_del(n);
625         INIT_HLIST_NODE(n);
626     }
627 }
628
629 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
630 {
631     struct hlist_node *first = h->first;
632     n->next = first;
633     if (first)
634         first->pprev = &n->next;
635     h->first = n;
636     n->pprev = &h->first;
637 }
638
639 /* next must be != NULL */
640 static inline void hlist_add_before(struct hlist_node *n,
641                     struct hlist_node *next)
642 {
643     n->pprev = next->pprev;
644     n->next = next;
645     next->pprev = &n->next;
646     *(n->pprev) = n;
647 }
648
649 static inline void hlist_add_after(struct hlist_node *n,
650                     struct hlist_node *next)
651 {
652     next->next = n->next;
653     n->next = next;
654     next->pprev = &n->next;
655
656     if(next->next)
657         next->next->pprev  = &next->next;
658 }
659
660 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
661
662 #define hlist_for_each(pos, head) \
663     for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
664          pos = pos->next)
665
666 #define hlist_for_each_safe(pos, n, head) \
667     for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
668          pos = n)
669
670 /**
671  * hlist_for_each_entry    - iterate over list of given type
672  * @tpos:    the type * to use as a loop cursor.
673  * @pos:    the &struct hlist_node to use as a loop cursor.
674  * @head:    the head for your list.
675  * @member:    the name of the hlist_node within the struct.
676  */
677 #define hlist_for_each_entry(tpos, pos, head, member)             \
678     for (pos = (head)->first;                     \
679          pos && ({ prefetch(pos->next); 1;}) &&             \
680         ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
681          pos = pos->next)
682
683 /**
684  * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
685  * @tpos:    the type * to use as a loop cursor.
686  * @pos:    the &struct hlist_node to use as a loop cursor.
687  * @member:    the name of the hlist_node within the struct.
688  */
689 #define hlist_for_each_entry_continue(tpos, pos, member)         \
690     for (pos = (pos)->next;                         \
691          pos && ({ prefetch(pos->next); 1;}) &&             \
692         ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
693          pos = pos->next)
694
695 /**
696  * hlist_for_each_entry_from - iterate over a hlist continuing from current point
697  * @tpos:    the type * to use as a loop cursor.
698  * @pos:    the &struct hlist_node to use as a loop cursor.
699  * @member:    the name of the hlist_node within the struct.
700  */
701 #define hlist_for_each_entry_from(tpos, pos, member)             \
702     for (; pos && ({ prefetch(pos->next); 1;}) &&             \
703         ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
704          pos = pos->next)
705
706 /**
707  * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
708  * @tpos:    the type * to use as a loop cursor.
709  * @pos:    the &struct hlist_node to use as a loop cursor.
710  * @n:        another &struct hlist_node to use as temporary storage
711  * @head:    the head for your list.
712  * @member:    the name of the hlist_node within the struct.
713  */
714 #define hlist_for_each_entry_safe(tpos, pos, n, head, member)         \
715     for (pos = (head)->first;                     \
716          pos && ({ n = pos->next; 1; }) &&                 \
717         ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
718          pos = n)
719
720
721 #endif
722
723