1 /*! \file linuxlist.h 2 * 3 * Simple doubly linked list implementation. 4 * 5 * Some of the internal functions ("__xxx") are useful when 6 * manipulating whole llists rather than single entries, as 7 * sometimes we already know the next/prev entries and we can 8 * generate better code by using them directly rather than 9 * using the generic single-entry routines. 10 */ 11 12 #pragma once 13 14 /*! \defgroup linuxlist Simple doubly linked list implementation 15 * @{ 16 * \file linuxlist.h */ 17 18 #include <stddef.h> 19 #include <stdbool.h> 20 21 #ifndef inline 22 #define inline __inline__ 23 #endif 24 25 static inline void prefetch(const void *x) {;} 26 27 /*! Cast a member of a structure out to the containing structure. 28 * \param[in] ptr the pointer to the member. 29 * \param[in] type the type of the container struct this is embedded in. 30 * \param[in] member the name of the member within the struct. 31 */ 32 #define container_of(ptr, type, member) ({ \ 33 const typeof( ((type *)0)->member ) *__mptr = (ptr); \ 34 (type *)( (char *)__mptr - offsetof(type, member) );}) 35 36 37 /*! 38 * These are non-NULL pointers that will result in page faults 39 * under normal circumstances, used to verify that nobody uses 40 * non-initialized llist entries. 41 */ 42 #define LLIST_POISON1 ((void *) 0x00100100) 43 #define LLIST_POISON2 ((void *) 0x00200200) 44 45 /*! (double) linked list header structure */ 46 struct llist_head { 47 /*! Pointer to next and previous item */ 48 struct llist_head *next, *prev; 49 }; 50 51 /*! Define a new llist_head pointing to a given llist_head. 52 * \param[in] name another llist_head to be pointed. 53 */ 54 #define LLIST_HEAD_INIT(name) { &(name), &(name) } 55 56 /*! Define a statically-initialized variable of type llist_head. 57 * \param[in] name variable (symbol) name. 58 */ 59 #define LLIST_HEAD(name) \ 60 struct llist_head name = LLIST_HEAD_INIT(name) 61 62 /*! Initialize a llist_head to point back to itself. 63 * \param[in] ptr llist_head to be initialized. 64 */ 65 #define INIT_LLIST_HEAD(ptr) do { \ 66 (ptr)->next = (ptr); (ptr)->prev = (ptr); \ 67 } while (0) 68 69 /* 70 * Insert a new entry between two known consecutive entries. 71 * 72 * This is only for internal llist manipulation where we know 73 * the prev/next entries already! 74 */ 75 static inline void __llist_add(struct llist_head *_new, 76 struct llist_head *prev, 77 struct llist_head *next) 78 { 79 next->prev = _new; 80 _new->next = next; 81 _new->prev = prev; 82 prev->next = _new; 83 } 84 85 /*! Add a new entry into a linked list (at head). 86 * \param _new the entry to be added. 87 * \param head llist_head to prepend the element to. 88 * 89 * Insert a new entry after the specified head. 90 * This is good for implementing stacks. 91 */ 92 static inline void llist_add(struct llist_head *_new, struct llist_head *head) 93 { 94 __llist_add(_new, head, head->next); 95 } 96 97 /*! Add a new entry into a linked list (at tail). 98 * \param _new the entry to be added. 99 * \param head llist_head to append the element to. 100 * 101 * Insert a new entry before the specified head. 102 * This is useful for implementing queues. 103 */ 104 static inline void llist_add_tail(struct llist_head *_new, struct llist_head *head) 105 { 106 __llist_add(_new, head->prev, head); 107 } 108 109 /* 110 * Delete a llist entry by making the prev/next entries 111 * point to each other. 112 * 113 * This is only for internal llist manipulation where we know 114 * the prev/next entries already! 115 */ 116 static inline void __llist_del(struct llist_head * prev, struct llist_head * next) 117 { 118 next->prev = prev; 119 prev->next = next; 120 } 121 122 /*! Delete a single entry from a linked list. 123 * \param entry the element to delete. 124 * 125 * Note: llist_empty on entry does not return true after this, the entry is 126 * in an undefined state. 127 */ 128 static inline void llist_del(struct llist_head *entry) 129 { 130 __llist_del(entry->prev, entry->next); 131 entry->next = (struct llist_head *)LLIST_POISON1; 132 entry->prev = (struct llist_head *)LLIST_POISON2; 133 } 134 135 /*! Delete a single entry from a linked list and reinitialize it. 136 * \param entry the element to delete and reinitialize. 137 */ 138 static inline void llist_del_init(struct llist_head *entry) 139 { 140 __llist_del(entry->prev, entry->next); 141 INIT_LLIST_HEAD(entry); 142 } 143 144 /*! Delete from one llist and add as another's head. 145 * \param llist the entry to move. 146 * \param head the head that will precede our entry. 147 */ 148 static inline void llist_move(struct llist_head *llist, struct llist_head *head) 149 { 150 __llist_del(llist->prev, llist->next); 151 llist_add(llist, head); 152 } 153 154 /*! Delete from one llist and add as another's tail. 155 * \param llist the entry to move. 156 * \param head the head that will follow our entry. 157 */ 158 static inline void llist_move_tail(struct llist_head *llist, 159 struct llist_head *head) 160 { 161 __llist_del(llist->prev, llist->next); 162 llist_add_tail(llist, head); 163 } 164 165 /*! Test whether a linked list is empty. 166 * \param[in] head the llist to test. 167 * \returns 1 if the list is empty, 0 otherwise. 168 */ 169 static inline int llist_empty(const struct llist_head *head) 170 { 171 return head->next == head; 172 } 173 174 static inline void __llist_splice(struct llist_head *llist, 175 struct llist_head *head) 176 { 177 struct llist_head *first = llist->next; 178 struct llist_head *last = llist->prev; 179 struct llist_head *at = head->next; 180 181 first->prev = head; 182 head->next = first; 183 184 last->next = at; 185 at->prev = last; 186 } 187 188 /*! Join two linked lists. 189 * \param llist the new linked list to add. 190 * \param head the place to add llist within the other list. 191 */ 192 static inline void llist_splice(struct llist_head *llist, struct llist_head *head) 193 { 194 if (!llist_empty(llist)) 195 __llist_splice(llist, head); 196 } 197 198 /*! Join two llists and reinitialise the emptied llist. 199 * \param llist the new linked list to add. 200 * \param head the place to add it within the first llist. 201 * 202 * The llist is reinitialised. 203 */ 204 static inline void llist_splice_init(struct llist_head *llist, 205 struct llist_head *head) 206 { 207 if (!llist_empty(llist)) { 208 __llist_splice(llist, head); 209 INIT_LLIST_HEAD(llist); 210 } 211 } 212 213 /*! Get the struct containing this list entry. 214 * \param ptr the llist_head pointer. 215 * \param type the type of the struct this is embedded in. 216 * \param member the name of the llist_head within the struct. 217 */ 218 #define llist_entry(ptr, type, member) \ 219 container_of(ptr, type, member) 220 221 /*! Get the first element from a linked list. 222 * \param ptr the list head to take the element from. 223 * \param type the type of the struct this is embedded in. 224 * \param member the name of the list_head within the struct. 225 * 226 * Note, that list is expected to be not empty. 227 */ 228 #define llist_first_entry(ptr, type, member) \ 229 llist_entry((ptr)->next, type, member) 230 231 /*! Get the last element from a list. 232 * \param ptr the list head to take the element from. 233 * \param type the type of the struct this is embedded in. 234 * \param member the name of the llist_head within the struct. 235 * 236 * Note, that list is expected to be not empty. 237 */ 238 #define llist_last_entry(ptr, type, member) \ 239 llist_entry((ptr)->prev, type, member) 240 241 /*! Return the last element of the list. 242 * \param head the llist head of the list. 243 * \returns last element of the list, head if the list is empty. 244 */ 245 #define llist_last(head) (head)->prev 246 247 /*! Get the first element from a list, or NULL. 248 * \param ptr the list head to take the element from. 249 * \param type the type of the struct this is embedded in. 250 * \param member the name of the list_head within the struct. 251 * 252 * Note that if the list is empty, it returns NULL. 253 */ 254 #define llist_first_entry_or_null(ptr, type, member) \ 255 (!llist_empty(ptr) ? llist_first_entry(ptr, type, member) : NULL) 256 257 /*! Iterate over a linked list. 258 * \param pos the llist_head to use as a loop counter. 259 * \param head the head of the list over which to iterate. 260 */ 261 #define llist_for_each(pos, head) \ 262 for (pos = (head)->next, prefetch(pos->next); pos != (head); \ 263 pos = pos->next, prefetch(pos->next)) 264 265 /*! Iterate over a linked list (no prefetch). 266 * \param pos the llist_head to use as a loop counter. 267 * \param head the head of the list over which to iterate. 268 * 269 * This variant differs from llist_for_each() in that it's the 270 * simplest possible llist iteration code, no prefetching is done. 271 * Use this for code that knows the llist to be very short (empty 272 * or 1 entry) most of the time. 273 */ 274 #define __llist_for_each(pos, head) \ 275 for (pos = (head)->next; pos != (head); pos = pos->next) 276 277 /*! Iterate over a linked list backwards. 278 * \param pos the llist_head to use as a loop counter. 279 * \param head the head of the list over which to iterate. 280 */ 281 #define llist_for_each_prev(pos, head) \ 282 for (pos = (head)->prev, prefetch(pos->prev); pos != (head); \ 283 pos = pos->prev, prefetch(pos->prev)) 284 285 /*! Iterate over a linked list, safe against removal of llist entry. 286 * \param pos the llist_head to use as a loop counter. 287 * \param n another llist_head to use as temporary storage. 288 * \param head the head of the list over which to iterate. 289 */ 290 #define llist_for_each_safe(pos, n, head) \ 291 for (pos = (head)->next, n = pos->next; pos != (head); \ 292 pos = n, n = pos->next) 293 294 /*! Iterate over a linked list of a given type. 295 * \param pos the 'type *' to use as a loop counter. 296 * \param head the head of the list over which to iterate. 297 * \param member the name of the llist_head within the struct pos. 298 */ 299 #define llist_for_each_entry(pos, head, member) \ 300 for (pos = llist_entry((head)->next, typeof(*pos), member), \ 301 prefetch(pos->member.next); \ 302 &pos->member != (head); \ 303 pos = llist_entry(pos->member.next, typeof(*pos), member), \ 304 prefetch(pos->member.next)) 305 306 /*! Iterate backwards over a linked list of a given type. 307 * \param pos the 'type *' to use as a loop counter. 308 * \param head the head of the list over which to iterate. 309 * \param member the name of the llist_head within the struct pos. 310 */ 311 #define llist_for_each_entry_reverse(pos, head, member) \ 312 for (pos = llist_entry((head)->prev, typeof(*pos), member), \ 313 prefetch(pos->member.prev); \ 314 &pos->member != (head); \ 315 pos = llist_entry(pos->member.prev, typeof(*pos), member), \ 316 prefetch(pos->member.prev)) 317 318 /*! Iterate over a linked list of a given type, 319 * continuing after an existing point. 320 * \param pos the 'type *' to use as a loop counter. 321 * \param head the head of the list over which to iterate. 322 * \param member the name of the llist_head within the struct pos. 323 */ 324 #define llist_for_each_entry_continue(pos, head, member) \ 325 for (pos = llist_entry(pos->member.next, typeof(*pos), member), \ 326 prefetch(pos->member.next); \ 327 &pos->member != (head); \ 328 pos = llist_entry(pos->member.next, typeof(*pos), member), \ 329 prefetch(pos->member.next)) 330 331 /*! Iterate over llist of given type, safe against removal of llist entry. 332 * \param pos the 'type *' to use as a loop counter. 333 * \param n another 'type *' to use as temporary storage. 334 * \param head the head of the list over which to iterate. 335 * \param member the name of the llist_head within the struct pos. 336 */ 337 #define llist_for_each_entry_safe(pos, n, head, member) \ 338 for (pos = llist_entry((head)->next, typeof(*pos), member), \ 339 n = llist_entry(pos->member.next, typeof(*pos), member); \ 340 &pos->member != (head); \ 341 pos = n, n = llist_entry(n->member.next, typeof(*n), member)) 342 343 /*! Iterate over an rcu-protected llist. 344 * \param pos the llist_head to use as a loop counter. 345 * \param head the head of the list over which to iterate. 346 */ 347 #define llist_for_each_rcu(pos, head) \ 348 for (pos = (head)->next, prefetch(pos->next); pos != (head); \ 349 pos = pos->next, ({ smp_read_barrier_depends(); 0;}), prefetch(pos->next)) 350 351 #define __llist_for_each_rcu(pos, head) \ 352 for (pos = (head)->next; pos != (head); \ 353 pos = pos->next, ({ smp_read_barrier_depends(); 0;})) 354 355 /*! Iterate over an rcu-protected llist, safe against removal of llist entry. 356 * \param pos the llist_head to use as a loop counter. 357 * \param n another llist_head to use as temporary storage. 358 * \param head the head of the list over which to iterate. 359 */ 360 #define llist_for_each_safe_rcu(pos, n, head) \ 361 for (pos = (head)->next, n = pos->next; pos != (head); \ 362 pos = n, ({ smp_read_barrier_depends(); 0;}), n = pos->next) 363 364 /*! Iterate over an rcu-protected llist of a given type. 365 * \param pos the 'type *' to use as a loop counter. 366 * \param head the head of the list over which to iterate. 367 * \param member the name of the llist_struct within the struct. 368 */ 369 #define llist_for_each_entry_rcu(pos, head, member) \ 370 for (pos = llist_entry((head)->next, typeof(*pos), member), \ 371 prefetch(pos->member.next); \ 372 &pos->member != (head); \ 373 pos = llist_entry(pos->member.next, typeof(*pos), member), \ 374 ({ smp_read_barrier_depends(); 0;}), \ 375 prefetch(pos->member.next)) 376 377 378 /*! Iterate over an rcu-protected llist, continuing after existing point. 379 * \param pos the llist_head to use as a loop counter. 380 * \param head the head of the list over which to iterate. 381 */ 382 #define llist_for_each_continue_rcu(pos, head) \ 383 for ((pos) = (pos)->next, prefetch((pos)->next); (pos) != (head); \ 384 (pos) = (pos)->next, ({ smp_read_barrier_depends(); 0;}), prefetch((pos)->next)) 385 386 /*! Count number of llist items by iterating. 387 * \param head the llist head to count items of. 388 * \returns Number of items. 389 * 390 * This function is not efficient, mostly useful for small lists and non time 391 * critical cases like unit tests. 392 */ 393 static inline unsigned int llist_count(const struct llist_head *head) 394 { 395 struct llist_head *entry; 396 unsigned int i = 0; 397 llist_for_each(entry, head) 398 i++; 399 return i; 400 } 401 402 403 404 /*! Double linked lists with a single pointer list head. 405 * Mostly useful for hash tables where the two pointer list head is 406 * too wasteful. 407 * You lose the ability to access the tail in O(1). 408 */ 409 410 struct hlist_head { 411 struct hlist_node *first; 412 }; 413 414 struct hlist_node { 415 struct hlist_node *next, **pprev; 416 }; 417 418 #define HLIST_HEAD_INIT { .first = NULL } 419 #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL } 420 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL) 421 static inline void INIT_HLIST_NODE(struct hlist_node *h) 422 { 423 h->next = NULL; 424 h->pprev = NULL; 425 } 426 427 #define READ_ONCE(x) x 428 #define WRITE_ONCE(a, b) a = b 429 430 /*! Has node been removed from list and reinitialized?. 431 * \param[in] h: Node to be checked 432 * \return 1 if node is unhashed; 0 if not 433 * 434 * Not that not all removal functions will leave a node in unhashed 435 * state. For example, hlist_nulls_del_init_rcu() does leave the 436 * node in unhashed state, but hlist_nulls_del() does not. 437 */ 438 static inline int hlist_unhashed(const struct hlist_node *h) 439 { 440 return !h->pprev; 441 } 442 443 /*! Version of hlist_unhashed for lockless use. 444 * \param[in] n Node to be checked 445 * \return 1 if node is unhashed; 0 if not 446 * 447 * This variant of hlist_unhashed() must be used in lockless contexts 448 * to avoid potential load-tearing. The READ_ONCE() is paired with the 449 * various WRITE_ONCE() in hlist helpers that are defined below. 450 */ 451 static inline int hlist_unhashed_lockless(const struct hlist_node *h) 452 { 453 return !READ_ONCE(h->pprev); 454 } 455 456 /*!Is the specified hlist_head structure an empty hlist?. 457 * \param[in] h Structure to check. 458 * \return 1 if hlist is empty; 0 if not 459 */ 460 static inline int hlist_empty(const struct hlist_head *h) 461 { 462 return !READ_ONCE(h->first); 463 } 464 465 static inline void __hlist_del(struct hlist_node *n) 466 { 467 struct hlist_node *next = n->next; 468 struct hlist_node **pprev = n->pprev; 469 470 WRITE_ONCE(*pprev, next); 471 if (next) 472 WRITE_ONCE(next->pprev, pprev); 473 } 474 475 /*! Delete the specified hlist_node from its list. 476 * \param[in] n: Node to delete. 477 * 478 * Note that this function leaves the node in hashed state. Use 479 * hlist_del_init() or similar instead to unhash @n. 480 */ 481 static inline void hlist_del(struct hlist_node *n) 482 { 483 __hlist_del(n); 484 n->next = (struct hlist_node *)LLIST_POISON1; 485 n->pprev = (struct hlist_node **)LLIST_POISON2; 486 } 487 488 /*! Delete the specified hlist_node from its list and initialize. 489 * \param[in] n Node to delete. 490 * 491 * Note that this function leaves the node in unhashed state. 492 */ 493 static inline void hlist_del_init(struct hlist_node *n) 494 { 495 if (!hlist_unhashed(n)) { 496 __hlist_del(n); 497 INIT_HLIST_NODE(n); 498 } 499 } 500 501 /*! add a new entry at the beginning of the hlist. 502 * \param[in] n new entry to be added 503 * \param[in] h hlist head to add it after 504 * 505 * Insert a new entry after the specified head. 506 * This is good for implementing stacks. 507 */ 508 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h) 509 { 510 struct hlist_node *first = h->first; 511 WRITE_ONCE(n->next, first); 512 if (first) 513 WRITE_ONCE(first->pprev, &n->next); 514 WRITE_ONCE(h->first, n); 515 WRITE_ONCE(n->pprev, &h->first); 516 } 517 518 /*! add a new entry before the one specified. 519 * @n: new entry to be added 520 * @next: hlist node to add it before, which must be non-NULL 521 */ 522 static inline void hlist_add_before(struct hlist_node *n, 523 struct hlist_node *next) 524 { 525 WRITE_ONCE(n->pprev, next->pprev); 526 WRITE_ONCE(n->next, next); 527 WRITE_ONCE(next->pprev, &n->next); 528 WRITE_ONCE(*(n->pprev), n); 529 } 530 531 /*! add a new entry after the one specified 532 * \param[in] n new entry to be added 533 * \param[in] prev hlist node to add it after, which must be non-NULL 534 */ 535 static inline void hlist_add_behind(struct hlist_node *n, 536 struct hlist_node *prev) 537 { 538 WRITE_ONCE(n->next, prev->next); 539 WRITE_ONCE(prev->next, n); 540 WRITE_ONCE(n->pprev, &prev->next); 541 542 if (n->next) 543 WRITE_ONCE(n->next->pprev, &n->next); 544 } 545 546 /*! create a fake hlist consisting of a single headless node. 547 * \param[in] n Node to make a fake list out of 548 * 549 * This makes @n appear to be its own predecessor on a headless hlist. 550 * The point of this is to allow things like hlist_del() to work correctly 551 * in cases where there is no list. 552 */ 553 static inline void hlist_add_fake(struct hlist_node *n) 554 { 555 n->pprev = &n->next; 556 } 557 558 /*! Is this node a fake hlist?. 559 * \param[in] h Node to check for being a self-referential fake hlist. 560 */ 561 static inline bool hlist_fake(struct hlist_node *h) 562 { 563 return h->pprev == &h->next; 564 } 565 566 /*!is node the only element of the specified hlist?. 567 * \param[in] n Node to check for singularity. 568 * \param[in] h Header for potentially singular list. 569 * 570 * Check whether the node is the only node of the head without 571 * accessing head, thus avoiding unnecessary cache misses. 572 */ 573 static inline bool 574 hlist_is_singular_node(struct hlist_node *n, struct hlist_head *h) 575 { 576 return !n->next && n->pprev == &h->first; 577 } 578 579 /*! Move an hlist. 580 * \param[in] old hlist_head for old list. 581 * \param[in] new hlist_head for new list. 582 * 583 * Move a list from one list head to another. Fixup the pprev 584 * reference of the first entry if it exists. 585 */ 586 static inline void hlist_move_list(struct hlist_head *old, 587 struct hlist_head *_new) 588 { 589 _new->first = old->first; 590 if (_new->first) 591 _new->first->pprev = &_new->first; 592 old->first = NULL; 593 } 594 595 #define hlist_entry(ptr, type, member) container_of(ptr,type,member) 596 597 #define hlist_for_each(pos, head) \ 598 for (pos = (head)->first; pos ; pos = pos->next) 599 600 #define hlist_for_each_safe(pos, n, head) \ 601 for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \ 602 pos = n) 603 604 #define hlist_entry_safe(ptr, type, member) \ 605 ({ typeof(ptr) ____ptr = (ptr); \ 606 ____ptr ? hlist_entry(____ptr, type, member) : NULL; \ 607 }) 608 609 /*! iterate over list of given type. 610 * \param[out] pos the type * to use as a loop cursor. 611 * \param[in] head the head for your list. 612 * \param[in] member the name of the hlist_node within the struct. 613 */ 614 #define hlist_for_each_entry(pos, head, member) \ 615 for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\ 616 pos; \ 617 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member)) 618 619 /*! iterate over a hlist continuing after current point. 620 * \param[out] pos the type * to use as a loop cursor. 621 * \param[in] member the name of the hlist_node within the struct. 622 */ 623 #define hlist_for_each_entry_continue(pos, member) \ 624 for (pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member);\ 625 pos; \ 626 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member)) 627 628 /*! iterate over a hlist continuing from current point. 629 * \param[out] pos the type * to use as a loop cursor. 630 * \param[in] member the name of the hlist_node within the struct. 631 */ 632 #define hlist_for_each_entry_from(pos, member) \ 633 for (; pos; \ 634 pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member)) 635 636 /*! hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry. 637 * \param[out] pos the type * to use as a loop cursor. 638 * \param[out] n a &struct hlist_node to use as temporary storage 639 * \param[in] head the head for your list. 640 * \param[in] member the name of the hlist_node within the struct 641 */ 642 #define hlist_for_each_entry_safe(pos, n, head, member) \ 643 for (pos = hlist_entry_safe((head)->first, typeof(*pos), member);\ 644 pos && ({ n = pos->member.next; 1; }); \ 645 pos = hlist_entry_safe(n, typeof(*pos), member)) 646 647 648 /*! 649 * @} 650 */ 651
This page was automatically generated by LXR 0.3.1. • OpenWrt