1 /* 2 * Copyright (c) 2010 Isilon Systems, Inc. 3 * Copyright (c) 2010 iX Systems, Inc. 4 * Copyright (c) 2010 Panasas, Inc. 5 * Copyright (c) 2013-2016 Mellanox Technologies, Ltd. 6 * Copyright (c) 2015-2020 François Tigeot <ftigeot@wolfpond.org> 7 * All rights reserved. 8 * 9 * Redistribution and use in source and binary forms, with or without 10 * modification, are permitted provided that the following conditions 11 * are met: 12 * 1. Redistributions of source code must retain the above copyright 13 * notice unmodified, this list of conditions, and the following 14 * disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 20 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 21 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 22 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 23 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 24 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 28 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 */ 30 #ifndef _LINUX_LIST_H_ 31 #define _LINUX_LIST_H_ 32 33 #include <linux/types.h> 34 #include <linux/stddef.h> 35 #include <linux/poison.h> 36 #include <linux/kernel.h> 37 38 #include <sys/queue.h> 39 40 #define prefetch(x) 41 42 struct list_head { 43 struct list_head *next; 44 struct list_head *prev; 45 }; 46 47 #define LIST_HEAD_INIT(name) { .prev = &(name), .next = &(name) } 48 49 static inline void 50 INIT_LIST_HEAD(struct list_head *list) 51 { 52 53 list->next = list->prev = list; 54 } 55 56 static inline struct list_head * 57 list_first(const struct list_head *head) 58 { 59 return head->next; 60 } 61 62 static inline struct list_head * 63 list_last(const struct list_head *head) 64 { 65 return head->prev; 66 } 67 68 static inline int 69 list_empty(const struct list_head *head) 70 { 71 return (head->next == head); 72 } 73 74 static inline int 75 list_empty_careful(const struct list_head *head) 76 { 77 return (head == head->next) && (head == head->prev); 78 } 79 80 static inline void 81 __list_del(struct list_head *prev, struct list_head *next) 82 { 83 next->prev = prev; 84 WRITE_ONCE(prev->next, next); 85 } 86 87 static inline void 88 __list_del_entry(struct list_head *entry) 89 { 90 __list_del(entry->prev, entry->next); 91 } 92 93 static inline void 94 list_del(struct list_head *entry) 95 { 96 97 entry->next->prev = entry->prev; 98 entry->prev->next = entry->next; 99 } 100 101 static inline void list_replace(struct list_head *old, 102 struct list_head *new) 103 { 104 new->next = old->next; 105 new->next->prev = new; 106 new->prev = old->prev; 107 new->prev->next = new; 108 } 109 110 static inline void list_replace_init(struct list_head *old, 111 struct list_head *new) 112 { 113 list_replace(old, new); 114 INIT_LIST_HEAD(old); 115 } 116 117 static inline void 118 _list_add(struct list_head *new, struct list_head *prev, 119 struct list_head *next) 120 { 121 122 next->prev = new; 123 new->next = next; 124 new->prev = prev; 125 prev->next = new; 126 } 127 128 static inline void 129 list_del_init(struct list_head *entry) 130 { 131 132 list_del(entry); 133 INIT_LIST_HEAD(entry); 134 } 135 136 #define list_entry(ptr, type, field) container_of(ptr, type, field) 137 138 #define list_first_entry(ptr, type, member) \ 139 list_entry((ptr)->next, type, member) 140 141 #define list_first_entry_or_null(ptr, type, member) \ 142 (list_empty(ptr) ? NULL: list_first_entry(ptr, type, member)) 143 144 #define list_last_entry(ptr, type, field) \ 145 list_entry(list_last((ptr)), type, field) 146 147 #define list_next_entry(ptr, member) \ 148 list_entry(((ptr)->member.next), typeof(*(ptr)), member) 149 150 #define list_safe_reset_next(ptr, n, member) \ 151 (n) = list_next_entry(ptr, member) 152 153 #define list_prev_entry(ptr, member) \ 154 list_entry(((ptr)->member.prev), typeof(*(ptr)), member) 155 156 #define list_for_each(p, head) \ 157 for (p = (head)->next; p != (head); p = p->next) 158 159 #define list_for_each_safe(p, n, head) \ 160 for (p = (head)->next, n = p->next; p != (head); p = n, n = p->next) 161 162 #define list_for_each_entry(p, h, field) \ 163 for (p = list_entry((h)->next, typeof(*p), field); &p->field != (h); \ 164 p = list_entry(p->field.next, typeof(*p), field)) 165 166 #define list_for_each_entry_safe(p, n, h, field) \ 167 for (p = list_entry((h)->next, typeof(*p), field), \ 168 n = list_entry(p->field.next, typeof(*p), field); &p->field != (h);\ 169 p = n, n = list_entry(n->field.next, typeof(*n), field)) 170 171 #define list_for_each_entry_from(p, h, field) \ 172 for ( ; &(p)->field != (h); \ 173 p = list_entry((p)->field.next, typeof(*p), field)) 174 175 #define list_for_each_entry_continue(p, h, field) \ 176 for (p = list_next_entry((p), field); &p->field != (h); \ 177 p = list_next_entry((p), field)) 178 179 #define list_for_each_entry_continue_reverse(pos, head, member) \ 180 for (pos = list_entry(pos->member.prev, __typeof(*pos), member); \ 181 &pos->member != (head); \ 182 pos = list_entry(pos->member.prev, __typeof(*pos), member)) 183 184 #define list_for_each_entry_safe_from(pos, n, head, member) \ 185 for (n = list_entry(pos->member.next, typeof(*pos), member); \ 186 &pos->member != (head); \ 187 pos = n, n = list_entry(n->member.next, typeof(*n), member)) 188 189 #define list_for_each_entry_reverse(p, h, field) \ 190 for (p = list_entry((h)->prev, typeof(*p), field); &p->field != (h); \ 191 p = list_entry(p->field.prev, typeof(*p), field)) 192 193 #define list_for_each_entry_safe_reverse(p, n, h, field) \ 194 for (p = list_entry((h)->prev, typeof(*p), field), \ 195 n = list_entry((p)->field.prev, typeof(*p), field); &(p)->field != (h); \ 196 p = n, n = list_entry(n->field.prev, typeof(*n), field)) 197 198 #define list_for_each_prev(p, h) for (p = (h)->prev; p != (h); p = p->prev) 199 200 static inline void 201 list_add(struct list_head *new, struct list_head *head) 202 { 203 204 _list_add(new, head, head->next); 205 } 206 207 static inline void 208 list_add_tail(struct list_head *new, struct list_head *head) 209 { 210 211 _list_add(new, head->prev, head); 212 } 213 214 static inline void 215 list_move(struct list_head *list, struct list_head *head) 216 { 217 218 list_del(list); 219 list_add(list, head); 220 } 221 222 static inline void 223 list_move_tail(struct list_head *entry, struct list_head *head) 224 { 225 226 list_del(entry); 227 list_add_tail(entry, head); 228 } 229 230 static inline void 231 _list_splice(const struct list_head *list, struct list_head *prev, 232 struct list_head *next) 233 { 234 struct list_head *first; 235 struct list_head *last; 236 237 if (list_empty(list)) 238 return; 239 first = list->next; 240 last = list->prev; 241 first->prev = prev; 242 prev->next = first; 243 last->next = next; 244 next->prev = last; 245 } 246 247 static inline void 248 list_splice(const struct list_head *list, struct list_head *head) 249 { 250 251 _list_splice(list, head, head->next); 252 } 253 254 static inline void 255 list_splice_tail(struct list_head *list, struct list_head *head) 256 { 257 258 _list_splice(list, head->prev, head); 259 } 260 261 static inline void 262 list_splice_init(struct list_head *list, struct list_head *head) 263 { 264 265 _list_splice(list, head, head->next); 266 INIT_LIST_HEAD(list); 267 } 268 269 static inline void 270 list_splice_tail_init(struct list_head *list, struct list_head *head) 271 { 272 273 _list_splice(list, head->prev, head); 274 INIT_LIST_HEAD(list); 275 } 276 277 #define LINUX_LIST_HEAD(name) struct list_head name = { &(name), &(name) } 278 279 280 struct hlist_head { 281 struct hlist_node *first; 282 }; 283 284 struct hlist_node { 285 struct hlist_node *next, **pprev; 286 }; 287 288 #define HLIST_HEAD_INIT { } 289 #define HLIST_HEAD(name) struct hlist_head name = HLIST_HEAD_INIT 290 #define INIT_HLIST_HEAD(head) (head)->first = NULL 291 #define INIT_HLIST_NODE(node) \ 292 do { \ 293 (node)->next = NULL; \ 294 (node)->pprev = NULL; \ 295 } while (0) 296 297 static inline int 298 hlist_unhashed(const struct hlist_node *h) 299 { 300 301 return !h->pprev; 302 } 303 304 static inline int 305 hlist_empty(const struct hlist_head *h) 306 { 307 308 return !h->first; 309 } 310 311 static inline void 312 hlist_del(struct hlist_node *n) 313 { 314 315 if (n->next) 316 n->next->pprev = n->pprev; 317 *n->pprev = n->next; 318 } 319 320 static inline void 321 hlist_del_init(struct hlist_node *n) 322 { 323 324 if (hlist_unhashed(n)) 325 return; 326 hlist_del(n); 327 INIT_HLIST_NODE(n); 328 } 329 330 static inline void 331 hlist_add_head(struct hlist_node *n, struct hlist_head *h) 332 { 333 334 n->next = h->first; 335 if (h->first) 336 h->first->pprev = &n->next; 337 h->first = n; 338 n->pprev = &h->first; 339 } 340 341 static inline void 342 hlist_add_before(struct hlist_node *n, struct hlist_node *next) 343 { 344 345 n->pprev = next->pprev; 346 n->next = next; 347 next->pprev = &n->next; 348 *(n->pprev) = n; 349 } 350 351 static inline void 352 hlist_add_after(struct hlist_node *n, struct hlist_node *next) 353 { 354 355 next->next = n->next; 356 n->next = next; 357 next->pprev = &n->next; 358 if (next->next) 359 next->next->pprev = &next->next; 360 } 361 362 static inline void 363 hlist_move_list(struct hlist_head *old, struct hlist_head *new) 364 { 365 366 new->first = old->first; 367 if (new->first) 368 new->first->pprev = &new->first; 369 old->first = NULL; 370 } 371 372 /** 373 * list_is_singular - tests whether a list has just one entry. 374 * @head: the list to test. 375 */ 376 static inline int list_is_singular(const struct list_head *head) 377 { 378 return !list_empty(head) && (head->next == head->prev); 379 } 380 381 static inline void __list_cut_position(struct list_head *list, 382 struct list_head *head, struct list_head *entry) 383 { 384 struct list_head *new_first = entry->next; 385 list->next = head->next; 386 list->next->prev = list; 387 list->prev = entry; 388 entry->next = list; 389 head->next = new_first; 390 new_first->prev = head; 391 } 392 393 /** 394 * list_cut_position - cut a list into two 395 * @list: a new list to add all removed entries 396 * @head: a list with entries 397 * @entry: an entry within head, could be the head itself 398 * and if so we won't cut the list 399 * 400 * This helper moves the initial part of @head, up to and 401 * including @entry, from @head to @list. You should 402 * pass on @entry an element you know is on @head. @list 403 * should be an empty list or a list you do not care about 404 * losing its data. 405 * 406 */ 407 static inline void list_cut_position(struct list_head *list, 408 struct list_head *head, struct list_head *entry) 409 { 410 if (list_empty(head)) 411 return; 412 if (list_is_singular(head) && 413 (head->next != entry && head != entry)) 414 return; 415 if (entry == head) 416 INIT_LIST_HEAD(list); 417 else 418 __list_cut_position(list, head, entry); 419 } 420 421 /** 422 * list_is_last - tests whether @list is the last entry in list @head 423 * @list: the entry to test 424 * @head: the head of the list 425 */ 426 static inline int list_is_last(const struct list_head *list, 427 const struct list_head *head) 428 { 429 return list->next == head; 430 } 431 432 #define hlist_entry(ptr, type, field) container_of(ptr, type, field) 433 434 #define hlist_for_each(p, head) \ 435 for (p = (head)->first; p; p = p->next) 436 437 #define hlist_for_each_safe(p, n, head) \ 438 for (p = (head)->first; p && ({ n = p->next; 1; }); p = n) 439 440 #define hlist_entry_safe(ptr, type, member) \ 441 (ptr) ? hlist_entry(ptr, type, member) : NULL 442 443 #define hlist_for_each_entry(pos, head, member) \ 444 for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\ 445 pos; \ 446 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member)) 447 448 #define hlist_for_each_entry_continue(tp, p, field) \ 449 for (p = (p)->next; \ 450 p ? (tp = hlist_entry(p, typeof(*tp), field)): NULL; p = p->next) 451 452 #define hlist_for_each_entry_from(tp, p, field) \ 453 for (; p ? (tp = hlist_entry(p, typeof(*tp), field)): NULL; p = p->next) 454 455 #define hlist_for_each_entry_safe(pos, n, head, member) \ 456 for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member); \ 457 (pos) && ({ n = (pos)->member.next; 1; }); \ 458 pos = hlist_entry_safe(n, typeof(*(pos)), member)) 459 460 void drm_list_sort(void *priv, struct list_head *head, int (*cmp)(void *priv, 461 struct list_head *a, struct list_head *b)); 462 463 #define hlist_add_head_rcu(n, h) hlist_add_head(n, h) 464 465 #define hlist_del_init_rcu(n) hlist_del_init(n) 466 467 #endif /* _LINUX_LIST_H_ */ 468