1 /* $OpenBSD: list.h,v 1.7 2023/01/18 23:47:25 jsg Exp $ */ 2 /* drm_linux_list.h -- linux list functions for the BSDs. 3 * Created: Mon Apr 7 14:30:16 1999 by anholt@FreeBSD.org 4 */ 5 /*- 6 * Copyright 2003 Eric Anholt 7 * All Rights Reserved. 8 * 9 * Permission is hereby granted, free of charge, to any person obtaining a 10 * copy of this software and associated documentation files (the "Software"), 11 * to deal in the Software without restriction, including without limitation 12 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 13 * and/or sell copies of the Software, and to permit persons to whom the 14 * Software is furnished to do so, subject to the following conditions: 15 * 16 * The above copyright notice and this permission notice (including the next 17 * paragraph) shall be included in all copies or substantial portions of the 18 * Software. 19 * 20 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 21 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 22 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 23 * VA LINUX SYSTEMS AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, DAMAGES OR 24 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, 25 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 26 * OTHER DEALINGS IN THE SOFTWARE. 27 * 28 * Authors: 29 * Eric Anholt <anholt@FreeBSD.org> 30 * 31 */ 32 33 #ifndef _DRM_LINUX_LIST_H_ 34 #define _DRM_LINUX_LIST_H_ 35 36 #include <sys/param.h> 37 #include <linux/container_of.h> 38 #include <linux/types.h> 39 #include <linux/poison.h> 40 41 #define list_entry(ptr, type, member) container_of(ptr, type, member) 42 43 static inline void 44 INIT_LIST_HEAD(struct list_head *head) { 45 (head)->next = head; 46 (head)->prev = head; 47 } 48 49 #define LIST_HEAD_INIT(name) { &(name), &(name) } 50 51 #define DRM_LIST_HEAD(name) \ 52 struct list_head name = LIST_HEAD_INIT(name) 53 54 static inline int 55 list_empty(const struct list_head *head) { 56 return (head)->next == head; 57 } 58 59 static inline int 60 list_is_singular(const struct list_head *head) { 61 return !list_empty(head) && ((head)->next == (head)->prev); 62 } 63 64 static inline int 65 list_is_first(const struct list_head *list, 66 const struct list_head *head) 67 { 68 return list->prev == head; 69 } 70 71 static inline int 72 list_is_last(const struct list_head *list, 73 const struct list_head *head) 74 { 75 return list->next == head; 76 } 77 78 static inline void 79 __list_add(struct list_head *new, struct list_head *prev, 80 struct list_head *next) 81 { 82 next->prev = new; 83 new->next = next; 84 new->prev = prev; 85 prev->next = new; 86 } 87 88 static inline void 89 list_add(struct list_head *new, struct list_head *head) { 90 (head)->next->prev = new; 91 (new)->next = (head)->next; 92 (new)->prev = head; 93 (head)->next = new; 94 } 95 96 static inline void 97 list_add_tail(struct list_head *entry, struct list_head *head) { 98 (entry)->prev = (head)->prev; 99 (entry)->next = head; 100 (head)->prev->next = entry; 101 (head)->prev = entry; 102 } 103 104 static inline void 105 list_del(struct list_head *entry) { 106 (entry)->next->prev = (entry)->prev; 107 (entry)->prev->next = (entry)->next; 108 } 109 110 #define __list_del_entry(x) list_del(x) 111 112 static inline void list_replace(struct list_head *old, 113 struct list_head *new) 114 { 115 new->next = old->next; 116 new->next->prev = new; 117 new->prev = old->prev; 118 new->prev->next = new; 119 } 120 121 static inline void list_replace_init(struct list_head *old, 122 struct list_head *new) 123 { 124 list_replace(old, new); 125 INIT_LIST_HEAD(old); 126 } 127 128 static inline void list_move(struct list_head *list, struct list_head *head) 129 { 130 list_del(list); 131 list_add(list, head); 132 } 133 134 static inline void list_move_tail(struct list_head *list, 135 struct list_head *head) 136 { 137 list_del(list); 138 list_add_tail(list, head); 139 } 140 141 static inline void 142 list_rotate_to_front(struct list_head *list, struct list_head *head) 143 { 144 list_del(head); 145 list_add_tail(head, list); 146 } 147 148 static inline void 149 list_bulk_move_tail(struct list_head *head, struct list_head *first, 150 struct list_head *last) 151 { 152 first->prev->next = last->next; 153 last->next->prev = first->prev; 154 head->prev->next = first; 155 first->prev = head->prev; 156 last->next = head; 157 head->prev = last; 158 } 159 160 static inline void 161 list_del_init(struct list_head *entry) { 162 (entry)->next->prev = (entry)->prev; 163 (entry)->prev->next = (entry)->next; 164 INIT_LIST_HEAD(entry); 165 } 166 167 #define list_next_entry(pos, member) \ 168 list_entry(((pos)->member.next), typeof(*(pos)), member) 169 170 #define list_prev_entry(pos, member) \ 171 list_entry(((pos)->member.prev), typeof(*(pos)), member) 172 173 #define list_safe_reset_next(pos, n, member) \ 174 n = list_next_entry(pos, member) 175 176 #define list_for_each(entry, head) \ 177 for (entry = (head)->next; entry != head; entry = (entry)->next) 178 179 #define list_for_each_prev(entry, head) \ 180 for (entry = (head)->prev; entry != (head); \ 181 entry = entry->prev) 182 183 #define list_for_each_safe(entry, temp, head) \ 184 for (entry = (head)->next, temp = (entry)->next; \ 185 entry != head; \ 186 entry = temp, temp = entry->next) 187 188 #define list_for_each_entry_safe_reverse(pos, n, head, member) \ 189 for (pos = list_entry((head)->prev, __typeof(*pos), member), \ 190 n = list_entry((pos)->member.prev, __typeof(*pos), member); \ 191 &(pos)->member != (head); \ 192 pos = n, n = list_entry(n->member.prev, __typeof(*n), member)) 193 194 #define list_for_each_entry_safe_from(pos, n, head, member) \ 195 for (n = list_entry(pos->member.next, __typeof(*pos), member); \ 196 &pos->member != (head); \ 197 pos = n, n = list_entry(n->member.next, __typeof(*n), member)) 198 199 #define list_for_each_entry(pos, head, member) \ 200 for (pos = list_entry((head)->next, __typeof(*pos), member); \ 201 &pos->member != (head); \ 202 pos = list_entry(pos->member.next, __typeof(*pos), member)) 203 204 #define list_for_each_entry_from(pos, head, member) \ 205 for (; \ 206 &pos->member != (head); \ 207 pos = list_entry(pos->member.next, __typeof(*pos), member)) 208 209 #define list_for_each_entry_reverse(pos, head, member) \ 210 for (pos = list_entry((head)->prev, __typeof(*pos), member); \ 211 &pos->member != (head); \ 212 pos = list_entry(pos->member.prev, __typeof(*pos), member)) 213 214 #define list_for_each_entry_from_reverse(pos, head, member) \ 215 for (; \ 216 &pos->member != (head); \ 217 pos = list_entry(pos->member.prev, __typeof(*pos), member)) 218 219 #define list_for_each_entry_continue(pos, head, member) \ 220 for (pos = list_entry((pos)->member.next, __typeof(*pos), member); \ 221 &pos->member != (head); \ 222 pos = list_entry(pos->member.next, __typeof(*pos), member)) 223 224 #define list_for_each_entry_continue_reverse(pos, head, member) \ 225 for (pos = list_entry(pos->member.prev, __typeof(*pos), member); \ 226 &pos->member != (head); \ 227 pos = list_entry(pos->member.prev, __typeof(*pos), member)) 228 229 /** 230 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry 231 * @pos: the type * to use as a loop cursor. 232 * @n: another type * to use as temporary storage 233 * @head: the head for your list. 234 * @member: the name of the list_struct within the struct. 235 */ 236 #define list_for_each_entry_safe(pos, n, head, member) \ 237 for (pos = list_entry((head)->next, __typeof(*pos), member), \ 238 n = list_entry(pos->member.next, __typeof(*pos), member); \ 239 &pos->member != (head); \ 240 pos = n, n = list_entry(n->member.next, __typeof(*n), member)) 241 242 #define list_first_entry(ptr, type, member) \ 243 list_entry((ptr)->next, type, member) 244 245 #define list_first_entry_or_null(ptr, type, member) \ 246 (list_empty(ptr) ? NULL : list_first_entry(ptr, type, member)) 247 248 #define list_last_entry(ptr, type, member) \ 249 list_entry((ptr)->prev, type, member) 250 251 static inline void 252 __list_splice(const struct list_head *list, struct list_head *prev, 253 struct list_head *next) 254 { 255 struct list_head *first = list->next; 256 struct list_head *last = list->prev; 257 258 first->prev = prev; 259 prev->next = first; 260 261 last->next = next; 262 next->prev = last; 263 } 264 265 static inline void 266 list_splice(const struct list_head *list, struct list_head *head) 267 { 268 if (list_empty(list)) 269 return; 270 271 __list_splice(list, head, head->next); 272 } 273 274 static inline void 275 list_splice_init(struct list_head *list, struct list_head *head) 276 { 277 if (list_empty(list)) 278 return; 279 280 __list_splice(list, head, head->next); 281 INIT_LIST_HEAD(list); 282 } 283 284 static inline void 285 list_splice_tail(const struct list_head *list, struct list_head *head) 286 { 287 if (list_empty(list)) 288 return; 289 290 __list_splice(list, head->prev, head); 291 } 292 293 static inline void 294 list_splice_tail_init(struct list_head *list, struct list_head *head) 295 { 296 if (list_empty(list)) 297 return; 298 299 __list_splice(list, head->prev, head); 300 INIT_LIST_HEAD(list); 301 } 302 303 void list_sort(void *, struct list_head *, 304 int (*)(void *, const struct list_head *, const struct list_head *)); 305 306 #define hlist_entry(ptr, type, member) \ 307 ((ptr) ? container_of(ptr, type, member) : NULL) 308 309 static inline void 310 INIT_HLIST_HEAD(struct hlist_head *head) { 311 head->first = NULL; 312 } 313 314 static inline int 315 hlist_empty(const struct hlist_head *head) { 316 return head->first == NULL; 317 } 318 319 static inline void 320 hlist_add_head(struct hlist_node *new, struct hlist_head *head) 321 { 322 if ((new->next = head->first) != NULL) 323 head->first->prev = &new->next; 324 head->first = new; 325 new->prev = &head->first; 326 } 327 328 static inline void 329 hlist_del_init(struct hlist_node *node) 330 { 331 if (node->next != NULL) 332 node->next->prev = node->prev; 333 *(node->prev) = node->next; 334 node->next = NULL; 335 node->prev = NULL; 336 } 337 338 #define hlist_for_each(pos, head) \ 339 for (pos = (head)->first; pos != NULL; pos = pos->next) 340 341 #define hlist_for_each_entry(pos, head, member) \ 342 for (pos = hlist_entry((head)->first, __typeof(*pos), member); \ 343 pos != NULL; \ 344 pos = hlist_entry((pos)->member.next, __typeof(*pos), member)) 345 346 #define hlist_for_each_entry_safe(pos, n, head, member) \ 347 for (pos = hlist_entry((head)->first, __typeof(*pos), member); \ 348 pos != NULL && (n = pos->member.next, 1); \ 349 pos = hlist_entry(n, __typeof(*pos), member)) 350 351 #endif /* _DRM_LINUX_LIST_H_ */ 352