1/* 2 * @TAG(OTHER_GPL) 3 */ 4#pragma once 5 6#include <stddef.h> 7 8#define LIST_POISON1 ((void *) 0x0) 9#define LIST_POISON2 ((void *) 0x0) 10 11#pragma once 12static inline void prefetch(const void *x) {;} 13 14/* 15 * Simple doubly linked list implementation. 16 * 17 * Some of the internal functions ("__xxx") are useful when 18 * manipulating whole lists rather than single entries, as 19 * sometimes we already know the next/prev entries and we can 20 * generate better code by using them directly rather than 21 * using the generic single-entry routines. 22 */ 23 24struct list_head { 25 struct list_head *next, *prev; 26}; 27 28#define LIST_HEAD_INIT(name) { &(name), &(name) } 29 30#define LIST_HEAD(name) \ 31 struct list_head name = LIST_HEAD_INIT(name) 32 33static inline void INIT_LIST_HEAD(struct list_head *list) 34{ 35 list->next = list; 36 list->prev = list; 37} 38 39/* 40 * Insert a new entry between two known consecutive entries. 41 * 42 * This is only for internal list manipulation where we know 43 * the prev/next entries already! 44 */ 45static inline void __list_add(struct list_head *new, 46 struct list_head *prev, 47 struct list_head *next) 48{ 49 next->prev = new; 50 new->next = next; 51 new->prev = prev; 52 prev->next = new; 53} 54 55/** 56 * list_add - add a new entry 57 * @new: new entry to be added 58 * @head: list head to add it after 59 * 60 * Insert a new entry after the specified head. 61 * This is good for implementing stacks. 62 */ 63static inline void list_add(struct list_head *new, struct list_head *head) 64{ 65 __list_add(new, head, head->next); 66} 67 68/** 69 * list_add_tail - add a new entry 70 * @new: new entry to be added 71 * @head: list head to add it before 72 * 73 * Insert a new entry before the specified head. 74 * This is useful for implementing queues. 75 */ 76static inline void list_add_tail(struct list_head *new, struct list_head *head) 77{ 78 __list_add(new, head->prev, head); 79} 80 81/* 82 * Delete a list entry by making the prev/next entries 83 * point to each other. 84 * 85 * This is only for internal list manipulation where we know 86 * the prev/next entries already! 87 */ 88static inline void __list_del(struct list_head *prev, struct list_head *next) 89{ 90 next->prev = prev; 91 prev->next = next; 92} 93 94/** 95 * list_del - deletes entry from list. 96 * @entry: the element to delete from the list. 97 * Note: list_empty() on entry does not return true after this, the entry is 98 * in an undefined state. 99 */ 100static inline void list_del(struct list_head *entry) 101{ 102 __list_del(entry->prev, entry->next); 103 entry->next = LIST_POISON1; 104 entry->prev = LIST_POISON2; 105} 106 107/** 108 * list_replace - replace old entry by new one 109 * @old : the element to be replaced 110 * @new : the new element to insert 111 * 112 * If @old was empty, it will be overwritten. 113 */ 114static inline void list_replace(struct list_head *old, 115 struct list_head *new) 116{ 117 new->next = old->next; 118 new->next->prev = new; 119 new->prev = old->prev; 120 new->prev->next = new; 121} 122 123static inline void list_replace_init(struct list_head *old, 124 struct list_head *new) 125{ 126 list_replace(old, new); 127 INIT_LIST_HEAD(old); 128} 129 130/** 131 * list_del_init - deletes entry from list and reinitialize it. 132 * @entry: the element to delete from the list. 133 */ 134static inline void list_del_init(struct list_head *entry) 135{ 136 __list_del(entry->prev, entry->next); 137 INIT_LIST_HEAD(entry); 138} 139 140/** 141 * list_move - delete from one list and add as another's head 142 * @list: the entry to move 143 * @head: the head that will precede our entry 144 */ 145static inline void list_move(struct list_head *list, struct list_head *head) 146{ 147 __list_del(list->prev, list->next); 148 list_add(list, head); 149} 150 151/** 152 * list_move_tail - delete from one list and add as another's tail 153 * @list: the entry to move 154 * @head: the head that will follow our entry 155 */ 156static inline void list_move_tail(struct list_head *list, 157 struct list_head *head) 158{ 159 __list_del(list->prev, list->next); 160 list_add_tail(list, head); 161} 162 163/** 164 * list_is_last - tests whether @list is the last entry in list @head 165 * @list: the entry to test 166 * @head: the head of the list 167 */ 168static inline int list_is_last(const struct list_head *list, 169 const struct list_head *head) 170{ 171 return list->next == head; 172} 173 174/** 175 * list_empty - tests whether a list is empty 176 * @head: the list to test. 177 */ 178static inline int list_empty(const struct list_head *head) 179{ 180 return head->next == head; 181} 182 183/** 184 * list_empty_careful - tests whether a list is empty and not being modified 185 * @head: the list to test 186 * 187 * Description: 188 * tests whether a list is empty _and_ checks that no other CPU might be 189 * in the process of modifying either member (next or prev) 190 * 191 * NOTE: using list_empty_careful() without synchronization 192 * can only be safe if the only activity that can happen 193 * to the list entry is list_del_init(). Eg. it cannot be used 194 * if another CPU could re-list_add() it. 195 */ 196static inline int list_empty_careful(const struct list_head *head) 197{ 198 struct list_head *next = head->next; 199 return (next == head) && (next == head->prev); 200} 201 202/** 203 * list_is_singular - tests whether a list has just one entry. 204 * @head: the list to test. 205 */ 206static inline int list_is_singular(const struct list_head *head) 207{ 208 return !list_empty(head) && (head->next == head->prev); 209} 210 211static inline void __list_cut_position(struct list_head *list, 212 struct list_head *head, struct list_head *entry) 213{ 214 struct list_head *new_first = entry->next; 215 list->next = head->next; 216 list->next->prev = list; 217 list->prev = entry; 218 entry->next = list; 219 head->next = new_first; 220 new_first->prev = head; 221} 222 223/** 224 * list_cut_position - cut a list into two 225 * @list: a new list to add all removed entries 226 * @head: a list with entries 227 * @entry: an entry within head, could be the head itself 228 * and if so we won't cut the list 229 * 230 * This helper moves the initial part of @head, up to and 231 * including @entry, from @head to @list. You should 232 * pass on @entry an element you know is on @head. @list 233 * should be an empty list or a list you do not care about 234 * losing its data. 235 * 236 */ 237static inline void list_cut_position(struct list_head *list, 238 struct list_head *head, struct list_head *entry) 239{ 240 if (list_empty(head)) { 241 return; 242 } 243 if (list_is_singular(head) && 244 (head->next != entry && head != entry)) { 245 return; 246 } 247 if (entry == head) { 248 INIT_LIST_HEAD(list); 249 } else { 250 __list_cut_position(list, head, entry); 251 } 252} 253 254static inline void __list_splice(const struct list_head *list, 255 struct list_head *prev, 256 struct list_head *next) 257{ 258 struct list_head *first = list->next; 259 struct list_head *last = list->prev; 260 261 first->prev = prev; 262 prev->next = first; 263 264 last->next = next; 265 next->prev = last; 266} 267 268/** 269 * list_splice - join two lists, this is designed for stacks 270 * @list: the new list to add. 271 * @head: the place to add it in the first list. 272 */ 273static inline void list_splice(const struct list_head *list, 274 struct list_head *head) 275{ 276 if (!list_empty(list)) { 277 __list_splice(list, head, head->next); 278 } 279} 280 281/** 282 * list_splice_tail - join two lists, each list being a queue 283 * @list: the new list to add. 284 * @head: the place to add it in the first list. 285 */ 286static inline void list_splice_tail(struct list_head *list, 287 struct list_head *head) 288{ 289 if (!list_empty(list)) { 290 __list_splice(list, head->prev, head); 291 } 292} 293 294/** 295 * list_splice_init - join two lists and reinitialise the emptied list. 296 * @list: the new list to add. 297 * @head: the place to add it in the first list. 298 * 299 * The list at @list is reinitialised 300 */ 301static inline void list_splice_init(struct list_head *list, 302 struct list_head *head) 303{ 304 if (!list_empty(list)) { 305 __list_splice(list, head, head->next); 306 INIT_LIST_HEAD(list); 307 } 308} 309 310/** 311 * list_splice_tail_init - join two lists and reinitialise the emptied list 312 * @list: the new list to add. 313 * @head: the place to add it in the first list. 314 * 315 * Each of the lists is a queue. 316 * The list at @list is reinitialised 317 */ 318static inline void list_splice_tail_init(struct list_head *list, 319 struct list_head *head) 320{ 321 if (!list_empty(list)) { 322 __list_splice(list, head->prev, head); 323 INIT_LIST_HEAD(list); 324 } 325} 326 327/** 328 * list_entry - get the struct for this entry 329 * @ptr: the &struct list_head pointer. 330 * @type: the type of the struct this is embedded in. 331 * @member: the name of the list_struct within the struct. 332 */ 333#define list_entry(ptr, type, member) \ 334 container_of(ptr, type, member) 335 336/** 337 * list_first_entry - get the first element from a list 338 * @ptr: the list head to take the element from. 339 * @type: the type of the struct this is embedded in. 340 * @member: the name of the list_struct within the struct. 341 * 342 * Note, that list is expected to be not empty. 343 */ 344#define list_first_entry(ptr, type, member) \ 345 list_entry((ptr)->next, type, member) 346 347/** 348 * list_for_each - iterate over a list 349 * @pos: the &struct list_head to use as a loop cursor. 350 * @head: the head for your list. 351 */ 352#define list_for_each(pos, head) \ 353 for (pos = (head)->next; prefetch(pos->next), pos != (head); \ 354 pos = pos->next) 355 356/** 357 * __list_for_each - iterate over a list 358 * @pos: the &struct list_head to use as a loop cursor. 359 * @head: the head for your list. 360 * 361 * This variant differs from list_for_each() in that it's the 362 * simplest possible list iteration code, no prefetching is done. 363 * Use this for code that knows the list to be very short (empty 364 * or 1 entry) most of the time. 365 */ 366#define __list_for_each(pos, head) \ 367 for (pos = (head)->next; pos != (head); pos = pos->next) 368 369/** 370 * list_for_each_prev - iterate over a list backwards 371 * @pos: the &struct list_head to use as a loop cursor. 372 * @head: the head for your list. 373 */ 374#define list_for_each_prev(pos, head) \ 375 for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \ 376 pos = pos->prev) 377 378/** 379 * list_for_each_safe - iterate over a list safe against removal of list entry 380 * @pos: the &struct list_head to use as a loop cursor. 381 * @n: another &struct list_head to use as temporary storage 382 * @head: the head for your list. 383 */ 384#define list_for_each_safe(pos, n, head) \ 385 for (pos = (head)->next, n = pos->next; pos != (head); \ 386 pos = n, n = pos->next) 387 388/** 389 * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry 390 * @pos: the &struct list_head to use as a loop cursor. 391 * @n: another &struct list_head to use as temporary storage 392 * @head: the head for your list. 393 */ 394#define list_for_each_prev_safe(pos, n, head) \ 395 for (pos = (head)->prev, n = pos->prev; \ 396 prefetch(pos->prev), pos != (head); \ 397 pos = n, n = pos->prev) 398 399/** 400 * list_for_each_entry - iterate over list of given type 401 * @pos: the type * to use as a loop cursor. 402 * @head: the head for your list. 403 * @member: the name of the list_struct within the struct. 404 */ 405#define list_for_each_entry(pos, head, member) \ 406 for (pos = list_entry((head)->next, typeof(*pos), member); \ 407 prefetch(pos->member.next), &pos->member != (head); \ 408 pos = list_entry(pos->member.next, typeof(*pos), member)) 409 410/** 411 * list_for_each_entry_reverse - iterate backwards over list of given type. 412 * @pos: the type * to use as a loop cursor. 413 * @head: the head for your list. 414 * @member: the name of the list_struct within the struct. 415 */ 416#define list_for_each_entry_reverse(pos, head, member) \ 417 for (pos = list_entry((head)->prev, typeof(*pos), member); \ 418 prefetch(pos->member.prev), &pos->member != (head); \ 419 pos = list_entry(pos->member.prev, typeof(*pos), member)) 420 421/** 422 * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue() 423 * @pos: the type * to use as a start point 424 * @head: the head of the list 425 * @member: the name of the list_struct within the struct. 426 * 427 * Prepares a pos entry for use as a start point in list_for_each_entry_continue(). 428 */ 429#define list_prepare_entry(pos, head, member) \ 430 ((pos) ? : list_entry(head, typeof(*pos), member)) 431 432/** 433 * list_for_each_entry_continue - continue iteration over list of given type 434 * @pos: the type * to use as a loop cursor. 435 * @head: the head for your list. 436 * @member: the name of the list_struct within the struct. 437 * 438 * Continue to iterate over list of given type, continuing after 439 * the current position. 440 */ 441#define list_for_each_entry_continue(pos, head, member) \ 442 for (pos = list_entry(pos->member.next, typeof(*pos), member); \ 443 prefetch(pos->member.next), &pos->member != (head); \ 444 pos = list_entry(pos->member.next, typeof(*pos), member)) 445 446/** 447 * list_for_each_entry_continue_reverse - iterate backwards from the given point 448 * @pos: the type * to use as a loop cursor. 449 * @head: the head for your list. 450 * @member: the name of the list_struct within the struct. 451 * 452 * Start to iterate over list of given type backwards, continuing after 453 * the current position. 454 */ 455#define list_for_each_entry_continue_reverse(pos, head, member) \ 456 for (pos = list_entry(pos->member.prev, typeof(*pos), member); \ 457 prefetch(pos->member.prev), &pos->member != (head); \ 458 pos = list_entry(pos->member.prev, typeof(*pos), member)) 459 460/** 461 * list_for_each_entry_from - iterate over list of given type from the current point 462 * @pos: the type * to use as a loop cursor. 463 * @head: the head for your list. 464 * @member: the name of the list_struct within the struct. 465 * 466 * Iterate over list of given type, continuing from current position. 467 */ 468#define list_for_each_entry_from(pos, head, member) \ 469 for (; prefetch(pos->member.next), &pos->member != (head); \ 470 pos = list_entry(pos->member.next, typeof(*pos), member)) 471 472/** 473 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry 474 * @pos: the type * to use as a loop cursor. 475 * @n: another type * to use as temporary storage 476 * @head: the head for your list. 477 * @member: the name of the list_struct within the struct. 478 */ 479#define list_for_each_entry_safe(pos, n, head, member) \ 480 for (pos = list_entry((head)->next, typeof(*pos), member), \ 481 n = list_entry(pos->member.next, typeof(*pos), member); \ 482 &pos->member != (head); \ 483 pos = n, n = list_entry(n->member.next, typeof(*n), member)) 484 485/** 486 * list_for_each_entry_safe_continue 487 * @pos: the type * to use as a loop cursor. 488 * @n: another type * to use as temporary storage 489 * @head: the head for your list. 490 * @member: the name of the list_struct within the struct. 491 * 492 * Iterate over list of given type, continuing after current point, 493 * safe against removal of list entry. 494 */ 495#define list_for_each_entry_safe_continue(pos, n, head, member) \ 496 for (pos = list_entry(pos->member.next, typeof(*pos), member), \ 497 n = list_entry(pos->member.next, typeof(*pos), member); \ 498 &pos->member != (head); \ 499 pos = n, n = list_entry(n->member.next, typeof(*n), member)) 500 501/** 502 * list_for_each_entry_safe_from 503 * @pos: the type * to use as a loop cursor. 504 * @n: another type * to use as temporary storage 505 * @head: the head for your list. 506 * @member: the name of the list_struct within the struct. 507 * 508 * Iterate over list of given type from current point, safe against 509 * removal of list entry. 510 */ 511#define list_for_each_entry_safe_from(pos, n, head, member) \ 512 for (n = list_entry(pos->member.next, typeof(*pos), member); \ 513 &pos->member != (head); \ 514 pos = n, n = list_entry(n->member.next, typeof(*n), member)) 515 516/** 517 * list_for_each_entry_safe_reverse 518 * @pos: the type * to use as a loop cursor. 519 * @n: another type * to use as temporary storage 520 * @head: the head for your list. 521 * @member: the name of the list_struct within the struct. 522 * 523 * Iterate backwards over list of given type, safe against removal 524 * of list entry. 525 */ 526#define list_for_each_entry_safe_reverse(pos, n, head, member) \ 527 for (pos = list_entry((head)->prev, typeof(*pos), member), \ 528 n = list_entry(pos->member.prev, typeof(*pos), member); \ 529 &pos->member != (head); \ 530 pos = n, n = list_entry(n->member.prev, typeof(*n), member)) 531 532/* 533 * Double linked lists with a single pointer list head. 534 * Mostly useful for hash tables where the two pointer list head is 535 * too wasteful. 536 * You lose the ability to access the tail in O(1). 537 */ 538 539struct hlist_head { 540 struct hlist_node *first; 541}; 542 543struct hlist_node { 544 struct hlist_node *next, * *pprev; 545}; 546 547#define HLIST_HEAD_INIT { .first = NULL } 548#define HLIST_HEAD(name) struct hlist_head name = { .first = NULL } 549#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL) 550static inline void INIT_HLIST_NODE(struct hlist_node *h) 551{ 552 h->next = NULL; 553 h->pprev = NULL; 554} 555 556static inline int hlist_unhashed(const struct hlist_node *h) 557{ 558 return !h->pprev; 559} 560 561static inline int hlist_empty(const struct hlist_head *h) 562{ 563 return !h->first; 564} 565 566static inline void __hlist_del(struct hlist_node *n) 567{ 568 struct hlist_node *next = n->next; 569 struct hlist_node **pprev = n->pprev; 570 *pprev = next; 571 if (next) { 572 next->pprev = pprev; 573 } 574} 575 576static inline void hlist_del(struct hlist_node *n) 577{ 578 __hlist_del(n); 579 n->next = LIST_POISON1; 580 n->pprev = LIST_POISON2; 581} 582 583static inline void hlist_del_init(struct hlist_node *n) 584{ 585 if (!hlist_unhashed(n)) { 586 __hlist_del(n); 587 INIT_HLIST_NODE(n); 588 } 589} 590 591static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h) 592{ 593 struct hlist_node *first = h->first; 594 n->next = first; 595 if (first) { 596 first->pprev = &n->next; 597 } 598 h->first = n; 599 n->pprev = &h->first; 600} 601 602/* next must be != NULL */ 603static inline void hlist_add_before(struct hlist_node *n, 604 struct hlist_node *next) 605{ 606 n->pprev = next->pprev; 607 n->next = next; 608 next->pprev = &n->next; 609 *(n->pprev) = n; 610} 611 612static inline void hlist_add_after(struct hlist_node *n, 613 struct hlist_node *next) 614{ 615 next->next = n->next; 616 n->next = next; 617 next->pprev = &n->next; 618 619 if (next->next) { 620 next->next->pprev = &next->next; 621 } 622} 623 624#define hlist_entry(ptr, type, member) container_of(ptr,type,member) 625 626#define hlist_for_each(pos, head) \ 627 for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \ 628 pos = pos->next) 629 630#define hlist_for_each_safe(pos, n, head) \ 631 for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \ 632 pos = n) 633 634/** 635 * hlist_for_each_entry - iterate over list of given type 636 * @tpos: the type * to use as a loop cursor. 637 * @pos: the &struct hlist_node to use as a loop cursor. 638 * @head: the head for your list. 639 * @member: the name of the hlist_node within the struct. 640 */ 641#define hlist_for_each_entry(tpos, pos, head, member) \ 642 for (pos = (head)->first; \ 643 pos && ({ prefetch(pos->next); 1;}) && \ 644 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \ 645 pos = pos->next) 646 647/** 648 * hlist_for_each_entry_continue - iterate over a hlist continuing after current point 649 * @tpos: the type * to use as a loop cursor. 650 * @pos: the &struct hlist_node to use as a loop cursor. 651 * @member: the name of the hlist_node within the struct. 652 */ 653#define hlist_for_each_entry_continue(tpos, pos, member) \ 654 for (pos = (pos)->next; \ 655 pos && ({ prefetch(pos->next); 1;}) && \ 656 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \ 657 pos = pos->next) 658 659/** 660 * hlist_for_each_entry_from - iterate over a hlist continuing from current point 661 * @tpos: the type * to use as a loop cursor. 662 * @pos: the &struct hlist_node to use as a loop cursor. 663 * @member: the name of the hlist_node within the struct. 664 */ 665#define hlist_for_each_entry_from(tpos, pos, member) \ 666 for (; pos && ({ prefetch(pos->next); 1;}) && \ 667 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \ 668 pos = pos->next) 669 670/** 671 * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry 672 * @tpos: the type * to use as a loop cursor. 673 * @pos: the &struct hlist_node to use as a loop cursor. 674 * @n: another &struct hlist_node to use as temporary storage 675 * @head: the head for your list. 676 * @member: the name of the hlist_node within the struct. 677 */ 678#define hlist_for_each_entry_safe(tpos, pos, n, head, member) \ 679 for (pos = (head)->first; \ 680 pos && ({ n = pos->next; 1; }) && \ 681 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \ 682 pos = n) 683