scripts/mod/list.h

0001 /* SPDX-License-Identifier: GPL-2.0 */
0002 #ifndef LIST_H
0003 #define LIST_H
0004
0005 #include <stdbool.h>
0006 #include <stddef.h>
0007
0008 /* Are two types/vars the same type (ignoring qualifiers)? */
0009 #define __same_type(a, b) __builtin_types_compatible_p(typeof(a), typeof(b))
0010
0011 /**
0012  * container_of - cast a member of a structure out to the containing structure
0013  * @ptr:    the pointer to the member.
0014  * @type:   the type of the container struct this is embedded in.
0015  * @member: the name of the member within the struct.
0016  *
0017  */
0018 #define container_of(ptr, type, member) ({              \
0019     void *__mptr = (void *)(ptr);                   \
0020     _Static_assert(__same_type(*(ptr), ((type *)0)->member) ||  \
0021               __same_type(*(ptr), void),            \
0022               "pointer type mismatch in container_of()");   \
0023     ((type *)(__mptr - offsetof(type, member))); })
0024
0025 #define LIST_POISON1  ((void *) 0x100)
0026 #define LIST_POISON2  ((void *) 0x122)
0027
0028 /*
0029  * Circular doubly linked list implementation.
0030  *
0031  * Some of the internal functions ("__xxx") are useful when
0032  * manipulating whole lists rather than single entries, as
0033  * sometimes we already know the next/prev entries and we can
0034  * generate better code by using them directly rather than
0035  * using the generic single-entry routines.
0036  */
0037
0038 struct list_head {
0039     struct list_head *next, *prev;
0040 };
0041
0042 #define LIST_HEAD_INIT(name) { &(name), &(name) }
0043
0044 #define LIST_HEAD(name) \
0045     struct list_head name = LIST_HEAD_INIT(name)
0046
0047 /**
0048  * INIT_LIST_HEAD - Initialize a list_head structure
0049  * @list: list_head structure to be initialized.
0050  *
0051  * Initializes the list_head to point to itself.  If it is a list header,
0052  * the result is an empty list.
0053  */
0054 static inline void INIT_LIST_HEAD(struct list_head *list)
0055 {
0056     list->next = list;
0057     list->prev = list;
0058 }
0059
0060 /*
0061  * Insert a new entry between two known consecutive entries.
0062  *
0063  * This is only for internal list manipulation where we know
0064  * the prev/next entries already!
0065  */
0066 static inline void __list_add(struct list_head *new,
0067                   struct list_head *prev,
0068                   struct list_head *next)
0069 {
0070     next->prev = new;
0071     new->next = next;
0072     new->prev = prev;
0073     prev->next = new;
0074 }
0075
0076 /**
0077  * list_add - add a new entry
0078  * @new: new entry to be added
0079  * @head: list head to add it after
0080  *
0081  * Insert a new entry after the specified head.
0082  * This is good for implementing stacks.
0083  */
0084 static inline void list_add(struct list_head *new, struct list_head *head)
0085 {
0086     __list_add(new, head, head->next);
0087 }
0088
0089 /**
0090  * list_add_tail - add a new entry
0091  * @new: new entry to be added
0092  * @head: list head to add it before
0093  *
0094  * Insert a new entry before the specified head.
0095  * This is useful for implementing queues.
0096  */
0097 static inline void list_add_tail(struct list_head *new, struct list_head *head)
0098 {
0099     __list_add(new, head->prev, head);
0100 }
0101
0102 /*
0103  * Delete a list entry by making the prev/next entries
0104  * point to each other.
0105  *
0106  * This is only for internal list manipulation where we know
0107  * the prev/next entries already!
0108  */
0109 static inline void __list_del(struct list_head *prev, struct list_head *next)
0110 {
0111     next->prev = prev;
0112     prev->next = next;
0113 }
0114
0115 static inline void __list_del_entry(struct list_head *entry)
0116 {
0117     __list_del(entry->prev, entry->next);
0118 }
0119
0120 /**
0121  * list_del - deletes entry from list.
0122  * @entry: the element to delete from the list.
0123  * Note: list_empty() on entry does not return true after this, the entry is
0124  * in an undefined state.
0125  */
0126 static inline void list_del(struct list_head *entry)
0127 {
0128     __list_del_entry(entry);
0129     entry->next = LIST_POISON1;
0130     entry->prev = LIST_POISON2;
0131 }
0132
0133 /**
0134  * list_is_head - tests whether @list is the list @head
0135  * @list: the entry to test
0136  * @head: the head of the list
0137  */
0138 static inline int list_is_head(const struct list_head *list, const struct list_head *head)
0139 {
0140     return list == head;
0141 }
0142
0143 /**
0144  * list_empty - tests whether a list is empty
0145  * @head: the list to test.
0146  */
0147 static inline int list_empty(const struct list_head *head)
0148 {
0149     return head->next == head;
0150 }
0151
0152 /**
0153  * list_entry - get the struct for this entry
0154  * @ptr:    the &struct list_head pointer.
0155  * @type:   the type of the struct this is embedded in.
0156  * @member: the name of the list_head within the struct.
0157  */
0158 #define list_entry(ptr, type, member) \
0159     container_of(ptr, type, member)
0160
0161 /**
0162  * list_first_entry - get the first element from a list
0163  * @ptr:    the list head to take the element from.
0164  * @type:   the type of the struct this is embedded in.
0165  * @member: the name of the list_head within the struct.
0166  *
0167  * Note, that list is expected to be not empty.
0168  */
0169 #define list_first_entry(ptr, type, member) \
0170     list_entry((ptr)->next, type, member)
0171
0172 /**
0173  * list_next_entry - get the next element in list
0174  * @pos:    the type * to cursor
0175  * @member: the name of the list_head within the struct.
0176  */
0177 #define list_next_entry(pos, member) \
0178     list_entry((pos)->member.next, typeof(*(pos)), member)
0179
0180 /**
0181  * list_entry_is_head - test if the entry points to the head of the list
0182  * @pos:    the type * to cursor
0183  * @head:   the head for your list.
0184  * @member: the name of the list_head within the struct.
0185  */
0186 #define list_entry_is_head(pos, head, member)               \
0187     (&pos->member == (head))
0188
0189 /**
0190  * list_for_each_entry - iterate over list of given type
0191  * @pos:    the type * to use as a loop cursor.
0192  * @head:   the head for your list.
0193  * @member: the name of the list_head within the struct.
0194  */
0195 #define list_for_each_entry(pos, head, member)              \
0196     for (pos = list_first_entry(head, typeof(*pos), member);    \
0197          !list_entry_is_head(pos, head, member);            \
0198          pos = list_next_entry(pos, member))
0199
0200 /**
0201  * list_for_each_entry_safe - iterate over list of given type. Safe against removal of list entry
0202  * @pos:    the type * to use as a loop cursor.
0203  * @n:      another type * to use as temporary storage
0204  * @head:   the head for your list.
0205  * @member: the name of the list_head within the struct.
0206  */
0207 #define list_for_each_entry_safe(pos, n, head, member)          \
0208     for (pos = list_first_entry(head, typeof(*pos), member),    \
0209         n = list_next_entry(pos, member);           \
0210          !list_entry_is_head(pos, head, member);            \
0211          pos = n, n = list_next_entry(n, member))
0212
0213 #endif /* LIST_H */