list.h

   1 /* SPDX-License-Identifier: GPL-2.0 */
   2
   3 /*
   4  * Copied from the Linux kernel source tree, version 2.6.13.
   5  *
   6  * Licensed under the GPL v2 as per the whole kernel source tree.
   7  *
   8  */
   9
  10 /** \file list.h doubly linked list implementation */
  11
  12 #include <stddef.h> /* offsetof */
  13
  14 /** get the struct this entry is embedded in */
  15 #define container_of(ptr, type, member) ({                      \
  16         const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
  17         (type *)( (char *)__mptr - offsetof(type,member) );})
  18
  19 /**
  20  * Non-NULL pointers that will result in page faults under normal
  21  * circumstances, used to verify that nobody uses non-initialized list entries.
  22  * Used for poisoning the \a next pointer of struct list_head.
  23  */
  24 #define LIST_POISON1  ((void *) 0x00100100)
  25 /** Non-null pointer, used for poisoning the \a prev pointer of struct
  26  * list_head
  27  */
  28 #define LIST_POISON2  ((void *) 0x00200200)
  29
  30 /** Simple doubly linked list implementation. */
  31 struct list_head {
  32         /** pointer to the next list entry */
  33         struct list_head *next;
  34         /** pointer to the previous list entry */
  35         struct list_head *prev;
  36 };
  37
  38 /** Define an initialized list head. */
  39 #define INITIALIZED_LIST_HEAD(name) struct list_head name = { &(name), &(name) }
  40
  41
  42 /** must be called before using any other list functions */
  43 #define INIT_LIST_HEAD(ptr) do { \
  44         (ptr)->next = (ptr); (ptr)->prev = (ptr); \
  45 } while (0)
  46
  47
  48 /*
  49  * Some of the internal functions ("__xxx") are useful when
  50  * manipulating whole lists rather than single entries, as
  51  * sometimes we already know the next/prev entries and we can
  52  * generate better code by using them directly rather than
  53  * using the generic single-entry routines.
  54  */
  55
  56
  57 /*
  58  * Insert a new entry between two known consecutive entries.
  59  *
  60  * This is only for internal list manipulation where we know
  61  * the prev/next entries already!
  62  */
  63 static inline void __list_add(struct list_head *new,
  64                               struct list_head *prev,
  65                               struct list_head *next)
  66 {
  67         next->prev = new;
  68         new->next = next;
  69         new->prev = prev;
  70         prev->next = new;
  71 }
  72
  73 /**
  74  * add a new entry
  75  *
  76  * \param new new entry to be added
  77  * \param head list head to add it after
  78  *
  79  * Insert a new entry after the specified head.
  80  * This is good for implementing stacks.
  81  */
  82 static inline void list_add(struct list_head *new, struct list_head *head)
  83 {
  84         __list_add(new, head, head->next);
  85 }
  86
  87 /**
  88  * add a new entry
  89  *
  90  * \param new new entry to be added
  91  * \param head list head to add it before
  92  *
  93  * Insert a new entry before the specified head.
  94  * This is useful for implementing queues.
  95  */
  96 static inline void list_add_tail(struct list_head *new, struct list_head *head)
  97 {
  98         __list_add(new, head->prev, head);
  99 }
 100
 101 /*
 102  * Delete a list entry by making the prev/next entries
 103  * point to each other.
 104  *
 105  * This is only for internal list manipulation where we know
 106  * the prev/next entries already!
 107  */
 108 static inline void __list_del(struct list_head * prev, struct list_head * next)
 109 {
 110         next->prev = prev;
 111         prev->next = next;
 112 }
 113
 114 /**
 115  * Delete entry from list.
 116  *
 117  * \param entry the element to delete from the list.
 118  *
 119  * Note: list_empty on entry does not return true after this, the entry is
 120  * in an undefined state.
 121  */
 122 static inline void list_del(struct list_head *entry)
 123 {
 124         __list_del(entry->prev, entry->next);
 125         entry->next = LIST_POISON1;
 126         entry->prev = LIST_POISON2;
 127 }
 128
 129 /**
 130  * delete from one list and add as another's head
 131  *
 132  * \param list: the entry to move
 133  * \param head: the head that will precede our entry
 134  */
 135 static inline void list_move(struct list_head *list, struct list_head *head)
 136 {
 137         __list_del(list->prev, list->next);
 138         _list_add(list, head);
 139 }
 140
 141 /**
 142  * test whether a list is empty
 143  *
 144  * \param head the list to test.
 145  */
 146 static inline int list_empty(const struct list_head *head)
 147 {
 148         return head->next == head;
 149 }
 150
 151 /**
 152  * get the struct for this entry
 153  *
 154  * \param ptr the &struct list_head pointer.
 155  * \param type the type of the struct this is embedded in.
 156  * \param member the name of the list_struct within the struct.
 157  */
 158 #define list_entry(ptr, type, member) \
 159         container_of(ptr, type, member)
 160
 161 /**
 162  * iterate over list of given type
 163  *
 164  * \param pos the type * to use as a loop counter.
 165  * \param head the head for your list.
 166  * \param member the name of the list_struct within the struct.
 167  */
 168 #define list_for_each_entry(pos, head, member)                          \
 169         for (pos = list_entry((head)->next, typeof(*pos), member);      \
 170              &pos->member != (head);    \
 171              pos = list_entry(pos->member.next, typeof(*pos), member))
 172
 173 /**
 174  * iterate over list of given type safe against removal of list entry
 175  *
 176  * \param pos the type * to use as a loop counter.
 177  * \param n another type * to use as temporary storage
 178  * \param head the head for your list.
 179  * \param member the name of the list_struct within the struct.
 180  */
 181 #define list_for_each_entry_safe(pos, n, head, member)                  \
 182         for (pos = list_entry((head)->next, typeof(*pos), member),      \
 183                 n = list_entry(pos->member.next, typeof(*pos), member); \
 184              &pos->member != (head);                                    \
 185              pos = n, n = list_entry(n->member.next, typeof(*n), member))
 186 /**
 187  * iterate backwards over list of given type safe against removal of list entry
 188  * \param pos the type * to use as a loop counter.
 189  * \param n another type * to use as temporary storage
 190  * \param head the head for your list.
 191  * \param member the name of the list_struct within the struct.
 192  */
 193 #define list_for_each_entry_safe_reverse(pos, n, head, member)          \
 194         for (pos = list_entry((head)->prev, typeof(*pos), member),      \
 195                 n = list_entry(pos->member.prev, typeof(*pos), member); \
 196              &pos->member != (head);                                    \
 197              pos = n, n = list_entry(n->member.prev, typeof(*n), member))
 198
 199 /**
 200  * Get the first element from a list
 201  * \param ptr the list head to take the element from.
 202  * \param type The type of the struct this is embedded in.
 203  * \param member The name of the list_struct within the struct.
 204  *
 205  * Note that list is expected to be not empty.
 206  */
 207 #define list_first_entry(ptr, type, member) \
 208         list_entry((ptr)->next, type, member)
 209
 210 /**
 211  * Test whether a list has just one entry.
 212  *
 213  * \param head The list to test.
 214  */
 215 static inline int list_is_singular(const struct list_head *head)
 216 {
 217         return !list_empty(head) && (head->next == head->prev);
 218 }
 219