1/* SPDX-License-Identifier: GPL-2.0 */ 2#ifndef LIST_H 3#define LIST_H 4 5#include <stddef.h> 6 7#include "list_types.h" 8 9/* Are two types/vars the same type (ignoring qualifiers)? */ 10#define __same_type(a, b) __builtin_types_compatible_p(typeof(a), typeof(b)) 11 12/** 13 * container_of - cast a member of a structure out to the containing structure 14 * @ptr: the pointer to the member. 15 * @type: the type of the container struct this is embedded in. 16 * @member: the name of the member within the struct. 17 * 18 */ 19#define container_of(ptr, type, member) ({ \ 20 void *__mptr = (void *)(ptr); \ 21 _Static_assert(__same_type(*(ptr), ((type *)0)->member) || \ 22 __same_type(*(ptr), void), \ 23 "pointer type mismatch in container_of()"); \ 24 ((type *)(__mptr - offsetof(type, member))); }) 25 26#define LIST_POISON1 ((void *) 0x100) 27#define LIST_POISON2 ((void *) 0x122) 28 29/* 30 * Circular doubly linked list implementation. 31 * 32 * Some of the internal functions ("__xxx") are useful when 33 * manipulating whole lists rather than single entries, as 34 * sometimes we already know the next/prev entries and we can 35 * generate better code by using them directly rather than 36 * using the generic single-entry routines. 37 */ 38 39#define LIST_HEAD_INIT(name) { &(name), &(name) } 40 41#define LIST_HEAD(name) \ 42 struct list_head name = LIST_HEAD_INIT(name) 43 44/** 45 * INIT_LIST_HEAD - Initialize a list_head structure 46 * @list: list_head structure to be initialized. 47 * 48 * Initializes the list_head to point to itself. If it is a list header, 49 * the result is an empty list. 50 */ 51static inline void INIT_LIST_HEAD(struct list_head *list) 52{ 53 list->next = list; 54 list->prev = list; 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 */ 63static 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 * list_add - add a new entry 75 * @new: new entry to be added 76 * @head: list head to add it after 77 * 78 * Insert a new entry after the specified head. 79 * This is good for implementing stacks. 80 */ 81static inline void list_add(struct list_head *new, struct list_head *head) 82{ 83 __list_add(new, head, head->next); 84} 85 86/** 87 * list_add_tail - add a new entry 88 * @new: new entry to be added 89 * @head: list head to add it before 90 * 91 * Insert a new entry before the specified head. 92 * This is useful for implementing queues. 93 */ 94static inline void list_add_tail(struct list_head *new, struct list_head *head) 95{ 96 __list_add(new, head->prev, head); 97} 98 99/* 100 * Delete a list entry by making the prev/next entries 101 * point to each other. 102 * 103 * This is only for internal list manipulation where we know 104 * the prev/next entries already! 105 */ 106static inline void __list_del(struct list_head *prev, struct list_head *next) 107{ 108 next->prev = prev; 109 prev->next = next; 110} 111 112static inline void __list_del_entry(struct list_head *entry) 113{ 114 __list_del(entry->prev, entry->next); 115} 116 117/** 118 * list_del - deletes entry from list. 119 * @entry: the element to delete from the list. 120 * Note: list_empty() on entry does not return true after this, the entry is 121 * in an undefined state. 122 */ 123static 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_is_head - tests whether @list is the list @head 132 * @list: the entry to test 133 * @head: the head of the list 134 */ 135static inline int list_is_head(const struct list_head *list, const struct list_head *head) 136{ 137 return list == head; 138} 139 140/** 141 * list_empty - tests whether a list is empty 142 * @head: the list to test. 143 */ 144static inline int list_empty(const struct list_head *head) 145{ 146 return head->next == head; 147} 148 149/** 150 * list_entry - get the struct for this entry 151 * @ptr: the &struct list_head pointer. 152 * @type: the type of the struct this is embedded in. 153 * @member: the name of the list_head within the struct. 154 */ 155#define list_entry(ptr, type, member) \ 156 container_of(ptr, type, member) 157 158/** 159 * list_first_entry - get the first element from a list 160 * @ptr: the list head to take the element from. 161 * @type: the type of the struct this is embedded in. 162 * @member: the name of the list_head within the struct. 163 * 164 * Note, that list is expected to be not empty. 165 */ 166#define list_first_entry(ptr, type, member) \ 167 list_entry((ptr)->next, type, member) 168 169/** 170 * list_next_entry - get the next element in list 171 * @pos: the type * to cursor 172 * @member: the name of the list_head within the struct. 173 */ 174#define list_next_entry(pos, member) \ 175 list_entry((pos)->member.next, typeof(*(pos)), member) 176 177/** 178 * list_entry_is_head - test if the entry points to the head of the list 179 * @pos: the type * to cursor 180 * @head: the head for your list. 181 * @member: the name of the list_head within the struct. 182 */ 183#define list_entry_is_head(pos, head, member) \ 184 (&pos->member == (head)) 185 186/** 187 * list_for_each_entry - iterate over list of given type 188 * @pos: the type * to use as a loop cursor. 189 * @head: the head for your list. 190 * @member: the name of the list_head within the struct. 191 */ 192#define list_for_each_entry(pos, head, member) \ 193 for (pos = list_first_entry(head, typeof(*pos), member); \ 194 !list_entry_is_head(pos, head, member); \ 195 pos = list_next_entry(pos, member)) 196 197/** 198 * list_for_each_entry_safe - iterate over list of given type. Safe against removal of list entry 199 * @pos: the type * to use as a loop cursor. 200 * @n: another type * to use as temporary storage 201 * @head: the head for your list. 202 * @member: the name of the list_head within the struct. 203 */ 204#define list_for_each_entry_safe(pos, n, head, member) \ 205 for (pos = list_first_entry(head, typeof(*pos), member), \ 206 n = list_next_entry(pos, member); \ 207 !list_entry_is_head(pos, head, member); \ 208 pos = n, n = list_next_entry(n, member)) 209 210/* 211 * Double linked lists with a single pointer list head. 212 * Mostly useful for hash tables where the two pointer list head is 213 * too wasteful. 214 * You lose the ability to access the tail in O(1). 215 */ 216 217#define HLIST_HEAD_INIT { .first = NULL } 218 219/** 220 * hlist_add_head - add a new entry at the beginning of the hlist 221 * @n: new entry to be added 222 * @h: hlist head to add it after 223 * 224 * Insert a new entry after the specified head. 225 * This is good for implementing stacks. 226 */ 227static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h) 228{ 229 struct hlist_node *first = h->first; 230 231 n->next = first; 232 if (first) 233 first->pprev = &n->next; 234 h->first = n; 235 n->pprev = &h->first; 236} 237 238#define hlist_entry(ptr, type, member) container_of(ptr, type, member) 239 240#define hlist_entry_safe(ptr, type, member) \ 241 ({ typeof(ptr) ____ptr = (ptr); \ 242 ____ptr ? hlist_entry(____ptr, type, member) : NULL; \ 243 }) 244 245/** 246 * hlist_for_each_entry - iterate over list of given type 247 * @pos: the type * to use as a loop cursor. 248 * @head: the head for your list. 249 * @member: the name of the hlist_node within the struct. 250 */ 251#define hlist_for_each_entry(pos, head, member) \ 252 for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\ 253 pos; \ 254 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member)) 255 256#endif /* LIST_H */ 257