list.h

   1 /*
   2  * Taken from Linux kernel.
   3  * Some parts:
   4  * Copyright Neil Brown ©2015-2023 <neil@brown.name>
   5  * May be distributed under terms of GPLv2 - see file:COPYING
   6  *
   7  */
   8 #ifndef __LIST_H__
   9 #define __LIST_H__
  10
  11 #include "safe.h"
  12
  13 #define ASSERT(x) do { if (!(x)) abort();} while (0)
  14
  15 /*Taken from various places in linux kernel */
  16
  17 #ifndef offsetof
  18 #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
  19 #endif
  20 /**
  21  * container_of - cast a member of a structure out to the containing structure
  22  * @ptr:        the pointer to the member.
  23  * @type:       the type of the container struct this is embedded in.
  24  * @member:     the name of the member within the struct.
  25  *
  26  */
  27 #define container_of(ptr, type, member) ({                      \
  28         const typeof( ((type *)0)->member ) *__mptr safe = (ptr);       \
  29         (type * safe)( (char *)__mptr - offsetof(type,member) );})
  30 #define container_of_array(ptr, type, member, index) ({                 \
  31         const typeof( ((type *)0)->member[index] ) *__mptr safe = (ptr);        \
  32         (type * safe)( (char *)__mptr - offsetof(type,member[index]) );})
  33
  34 /*
  35  * These are non-NULL pointers that will result in page faults
  36  * under normal circumstances, used to verify that nobody uses
  37  * non-initialized list entries.
  38  */
  39 #define LIST_POISON1  ((void *) 0x00100100)
  40 #define LIST_POISON2  ((void *) 0x00200200)
  41
  42 /*
  43  * Simple doubly linked list implementation.
  44  *
  45  * Some of the internal functions ("__xxx") are useful when
  46  * manipulating whole lists rather than single entries, as
  47  * sometimes we already know the next/prev entries and we can
  48  * generate better code by using them directly rather than
  49  * using the generic single-entry routines.
  50  */
  51
  52 struct list_head {
  53         struct list_head *next safe, *prev safe;
  54 };
  55
  56 #define LIST_HEAD_INIT(name) { &(name), &(name) }
  57
  58 #define LIST_HEAD(name) \
  59         struct list_head name = LIST_HEAD_INIT(name)
  60
  61 #define INIT_LIST_HEAD(ptr) do { \
  62         (ptr)->next = (ptr); (ptr)->prev = (ptr); \
  63 } while (0)
  64
  65 /*
  66  * Insert a new entry between two known consecutive entries.
  67  *
  68  * This is only for internal list manipulation where we know
  69  * the prev/next entries already!
  70  */
  71 static inline void __list_add(struct list_head *new safe,
  72                               struct list_head *prev safe,
  73                               struct list_head *next safe)
  74 {
  75         next->prev = new;
  76         new->next = next;
  77         new->prev = prev;
  78         prev->next = new;
  79 }
  80
  81 /**
  82  * list_add - add a new entry
  83  * @new: new entry to be added
  84  * @head: list head to add it after
  85  *
  86  * Insert a new entry after the specified head.
  87  * This is good for implementing stacks.
  88  */
  89 static inline void list_add(struct list_head *new safe, struct list_head *head safe)
  90 {
  91         __list_add(new, head, head->next);
  92 }
  93
  94 /**
  95  * list_add_tail - add a new entry
  96  * @new: new entry to be added
  97  * @head: list head to add it before
  98  *
  99  * Insert a new entry before the specified head.
 100  * This is useful for implementing queues.
 101  */
 102 static inline void list_add_tail(struct list_head *new safe, struct list_head *head safe)
 103 {
 104         __list_add(new, head->prev, head);
 105 }
 106
 107 /*
 108  * Delete a list entry by making the prev/next entries
 109  * point to each other.
 110  *
 111  * This is only for internal list manipulation where we know
 112  * the prev/next entries already!
 113  */
 114 static inline void __list_del(struct list_head *prev safe, struct list_head *next safe)
 115 {
 116         next->prev = prev;
 117         prev->next = next;
 118 }
 119
 120 /**
 121  * list_del - deletes entry from list.
 122  * @entry: the element to delete from the list.
 123  * Note: list_empty on entry does not return true after this, the entry is
 124  * in an undefined state.
 125  */
 126 static inline void list_del(struct list_head *entry safe)
 127 {
 128         __list_del(entry->prev, entry->next);
 129         entry->next = LIST_POISON1;
 130         entry->prev = LIST_POISON2;
 131 }
 132
 133 /**
 134  * list_del_init - deletes entry from list and reinitialize it.
 135  * @entry: the element to delete from the list.
 136  */
 137 static inline void list_del_init(struct list_head *entry safe)
 138 {
 139         __list_del(entry->prev, entry->next);
 140         INIT_LIST_HEAD(entry);
 141 }
 142
 143 /**
 144  * list_move - delete from one list and add as another's head
 145  * @list: the entry to move
 146  * @head: the head that will precede our entry
 147  */
 148 static inline void list_move(struct list_head *list safe, struct list_head *head safe)
 149 {
 150         __list_del(list->prev, list->next);
 151         list_add(list, head);
 152 }
 153
 154 /**
 155  * list_move_tail - delete from one list and add as another's tail
 156  * @list: the entry to move
 157  * @head: the head that will follow our entry
 158  */
 159 static inline void list_move_tail(struct list_head *list safe,
 160                                   struct list_head *head safe)
 161 {
 162         __list_del(list->prev, list->next);
 163         list_add_tail(list, head);
 164 }
 165
 166 /**
 167  * list_empty - tests whether a list is empty
 168  * @head: the list to test.
 169  */
 170 static inline int list_empty(struct list_head *head safe)
 171 {
 172         return head->next == head;
 173 }
 174
 175 /**
 176  * list_entry - get the struct for this entry
 177  * @ptr:        the &struct list_head pointer.
 178  * @type:       the type of the struct this is embedded in.
 179  * @member:     the name of the list_struct within the struct.
 180  */
 181 #define list_entry(ptr, type, member) \
 182         container_of(ptr, type, member)
 183
 184 /**
 185  * list_first_entry - get the first element from a list
 186  * @ptr:        the list head to take the element from.
 187  * @type:       the type of the struct this is embedded in.
 188  * @member:     the name of the list_head within the struct.
 189  *
 190  * Note, that list is expected to be not empty.
 191  */
 192 #define list_first_entry(ptr, type, member) \
 193         list_entry((ptr)->next, type, member)
 194
 195 /**
 196  * list_last_entry - get the last element from a list
 197  * @ptr:        the list head to take the element from.
 198  * @type:       the type of the struct this is embedded in.
 199  * @member:     the name of the list_head within the struct.
 200  *
 201  * Note, that list is expected to be not empty.
 202  */
 203 #define list_last_entry(ptr, type, member) \
 204         list_entry((ptr)->prev, type, member)
 205
 206 /**
 207  * list_first_entry_or_null - get the first element from a list
 208  * @ptr:        the list head to take the element from.
 209  * @type:       the type of the struct this is embedded in.
 210  * @member:     the name of the list_head within the struct.
 211  *
 212  * Note that if the list is empty, it returns NULL.
 213  */
 214 #define list_first_entry_or_null(ptr, type, member) \
 215         (!list_empty(ptr) ? list_first_entry(ptr, type, member) : NULL)
 216
 217 /**
 218  * list_next_entry - get the next element in list
 219  * @pos:        the type * to cursor
 220  * @member:     the name of the list_head within the struct.
 221  */
 222 #define list_next_entry(pos, member) \
 223         list_entry((pos)->member.next, typeof(*(pos)), member)
 224
 225 /**
 226  * list_prev_entry - get the prev element in list
 227  * @pos:        the type * to cursor
 228  * @member:     the name of the list_head within the struct.
 229  */
 230 #define list_prev_entry(pos, member) \
 231         list_entry((pos)->member.prev, typeof(*(pos)), member)
 232
 233 /**
 234  * list_for_each        -       iterate over a list
 235  * @pos:        the &struct list_head to use as a loop cursor.
 236  * @head:       the head for your list.
 237  */
 238 #define list_for_each(pos, head) \
 239         for (pos = (head)->next; pos != (head); pos = pos->next)
 240
 241 /**
 242  * list_for_each_entry  -       iterate over list of given type
 243  * @pos:        the type * to use as a loop cursor.
 244  * @head:       the head for your list.
 245  * @member:     the name of the list_head within the struct.
 246  */
 247 #define list_for_each_entry(pos, head, member)                          \
 248         for (pos = list_first_entry(head, typeof(*pos), member);        \
 249              &pos->member != (head);                                    \
 250              pos = list_next_entry(pos, member))
 251
 252 /**
 253  * list_for_each_entry_reverse - iterate backwards over list of given type.
 254  * @pos:        the type * to use as a loop cursor.
 255  * @head:       the head for your list.
 256  * @member:     the name of the list_head within the struct.
 257  */
 258 #define list_for_each_entry_reverse(pos, head, member)                  \
 259         for (pos = list_last_entry(head, typeof(*pos), member);         \
 260              &pos->member != (head);                                    \
 261              pos = list_prev_entry(pos, member))
 262
 263 /**
 264  * list_for_each_entry_safe     -       iterate over list of given type
 265  * @pos:        the type * to use as a loop cursor.
 266  * @n:          &struct list_node temp pointer.
 267  * @head:       the head for your list.
 268  * @member:     the name of the list_head within the struct.
 269  */
 270 #define list_for_each_entry_safe(pos, n, head, member)                  \
 271         for (pos = list_first_entry(head, typeof(*pos), member);        \
 272              &pos->member != (head) && ({n = pos->member.next; 1;});    \
 273              pos = list_entry(n, typeof(*pos), member))
 274
 275 /**
 276  * list_for_each_entry_continue - continue iteration over list of given type
 277  * @pos:        the type * to use as a loop cursor.
 278  * @head:       the head for your list.
 279  * @member:     the name of the list_head within the struct.
 280  *
 281  * Continue to iterate over list of given type, continuing after
 282  * the current position.
 283  */
 284 #define list_for_each_entry_continue(pos, head, member)                 \
 285         for (pos = list_next_entry(pos, member);                        \
 286              &pos->member != (head);                                    \
 287              pos = list_next_entry(pos, member))
 288
 289 /**
 290  * list_for_each_entry_from - iterate over list of given type from the current point
 291  * @pos:        the type * to use as a loop cursor.
 292  * @head:       the head for your list.
 293  * @member:     the name of the list_head within the struct.
 294  *
 295  * Iterate over list of given type, continuing from current position.
 296  */
 297 #define list_for_each_entry_from(pos, head, member)                     \
 298         for (; pos && &pos->member != (head);                           \
 299              pos = list_next_entry(pos, member))
 300
 301 /* 'first' has lsb set so the start of the list can be recognised
 302  * with passing the head around.
 303  */
 304 struct hlist_head {
 305         struct hlist_node *vfirst;
 306 };
 307 #define HLIST_PTR(_h) ((struct hlist_node *)(((unsigned long)_h) & ~1UL))
 308 #define HLIST_HEAD_PTR(_h) ((void*)(((unsigned long)_h) | 1UL))
 309 #define HLIST_IS_HEAD(_h) (((unsigned long)(*(_h))) & 1UL)
 310
 311 struct hlist_node {
 312         struct hlist_node *next;
 313         struct hlist_node **pprev safe;
 314 };
 315
 316 #define HLIST_HEAD_INIT { .vfirst = HLIST_HEAD_PTR(NULL) }
 317 #define HLIST_HEAD(name) struct hlist_head name = {  .vfirst = HLIST_HEAD_PTR(NULL) }
 318 #define INIT_HLIST_HEAD(ptr) ((ptr)->vfirst = HLIST_HEAD_PTR(NULL))
 319 static inline void INIT_HLIST_NODE(struct hlist_node *h safe)
 320 {
 321         h->next = NULL;
 322         h->pprev = &h->next;
 323 }
 324
 325 static inline int hlist_unhashed(const struct hlist_node *h safe)
 326 {
 327         return h->pprev == &h->next;
 328 }
 329
 330 static inline int hlist_empty(const struct hlist_head *h safe)
 331 {
 332 #ifndef __CHECKER__
 333         return !HLIST_PTR(h->vfirst);
 334 #else
 335         return (h->vfirst == NULL || h->vfirst == (struct hlist_node*)1);
 336 #endif
 337 }
 338
 339 static inline void __hlist_del(struct hlist_node *n safe)
 340 {
 341         struct hlist_node *next = n->next;
 342         struct hlist_node **pprev = n->pprev;
 343         if (HLIST_IS_HEAD(pprev))
 344                 *pprev= HLIST_HEAD_PTR(next);
 345         else
 346                 *pprev = next;
 347         if (next)
 348                 next->pprev = pprev;
 349 }
 350
 351 static inline void hlist_del(struct hlist_node *n safe)
 352 {
 353         __hlist_del(n);
 354         n->next = LIST_POISON1;
 355         n->pprev = LIST_POISON2;
 356 }
 357
 358 static inline void hlist_del_init(struct hlist_node *n safe)
 359 {
 360         if (!hlist_unhashed(n)) {
 361                 __hlist_del(n);
 362                 INIT_HLIST_NODE(n);
 363         }
 364 }
 365
 366 static inline void hlist_add_head(struct hlist_node *n safe, struct hlist_head *h safe)
 367 {
 368         struct hlist_node *first = HLIST_PTR(h->vfirst);
 369         n->next = first;
 370         if (first)
 371                 first->pprev = &n->next;
 372         h->vfirst = HLIST_HEAD_PTR(n);
 373         n->pprev = &h->vfirst;
 374 }
 375
 376 /* next must be != NULL */
 377 static inline void hlist_add_before(struct hlist_node *n safe,
 378                                     struct hlist_node *next safe)
 379 {
 380         n->pprev = next->pprev;
 381         n->next = next;
 382         next->pprev = &n->next;
 383         if (HLIST_IS_HEAD((n->pprev)))
 384                 *(n->pprev) = HLIST_HEAD_PTR(n);
 385         else
 386                 *(n->pprev) = n;
 387 }
 388
 389 static inline void hlist_add_after(struct hlist_node *n safe,
 390                                    struct hlist_node *next safe)
 391 {
 392         next->next = n->next;
 393         n->next = next;
 394         next->pprev = &n->next;
 395
 396         if(next->next)
 397                 next->next->pprev  = &next->next;
 398 }
 399
 400 /*
 401  * Move a list from one list head to another. Fixup the pprev
 402  * reference of the first entry if it exists.
 403  */
 404 static inline void hlist_move_list(struct hlist_head *old safe,
 405                                    struct hlist_head *new safe)
 406 {
 407         new->vfirst = old->vfirst;
 408         if (!hlist_empty(new))
 409                 HLIST_PTR(new->vfirst)->pprev = &new->vfirst;
 410         INIT_HLIST_HEAD(old);
 411 }
 412
 413 #define hlist_entry(ptr, type, member) container_of(HLIST_PTR(ptr),type,member)
 414
 415 #define hlist_next_entry(ptr, member) \
 416         hlist_entry((ptr)->member.next, typeof(*(ptr)), member)
 417 #define hlist_first_entry(head, type, member)                   \
 418         hlist_entry((head)->vfirst, type, member)
 419 #define hlist_prev(ptr) container_of((ptr)->pprev, struct hlist_node, next)
 420 #define hlist_prev_entry(ptr, member) \
 421         ({struct hlist_node *__hln = hlist_prev(&(ptr)->member); \
 422                 hlist_entry(__hln, typeof(*(ptr)), member); })
 423
 424 #define hlist_for_each(pos, head) \
 425         for (pos = HLIST_PTR((head)->first); pos ; pos = pos->next)
 426
 427 #define hlist_for_each_safe(pos, n, head) \
 428         for (pos = HLIST_PTR((head)->first); pos && ({ n = pos->next; 1; }); \
 429              pos = n)
 430
 431 /**
 432  * hlist_for_each_entry - iterate over list of given type
 433  * @pos:        the type * to use as a loop cursor.
 434  * @head:       the head for your list.
 435  * @member:     the name of the hlist_node within the struct.
 436  */
 437 #define hlist_for_each_entry(pos, head, member)                 \
 438         for (pos = hlist_empty(head) ? NULL : hlist_first_entry(head, typeof(*pos), member); \
 439              pos ;                                                      \
 440              pos = pos->member.next ? hlist_next_entry(pos, member) : NULL)
 441 /**
 442  * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
 443  * @pos:        the type * to use as a loop cursor.
 444  * @member:     the name of the hlist_node within the struct.
 445  */
 446 #define hlist_for_each_entry_continue(pos, member)               \
 447         for (pos = (pos)->member.next ? hlist_next_entry(pos, member) : NULL;   \
 448              pos ;                                                      \
 449              pos = pos->member.next ? hlist_next_entry(pos, member) : NULL)
 450
 451 /**
 452  * hlist_for_each_entry_continue_reverse - iterate backwards over a hlist continuing after current point
 453  * @pos:        the type * to use as a loop cursor.
 454  * @member:     the name of the hlist_node within the struct.
 455  */
 456 #define hlist_for_each_entry_continue_reverse(pos, member)               \
 457         for (pos = HLIST_IS_HEAD(pos->member.pprev) ? NULL : hlist_prev_entry(pos, member); \
 458              pos ;                                              \
 459              pos = HLIST_IS_HEAD(pos->member.pprev) ? NULL : hlist_prev_entry(pos, member ))
 460
 461 /**
 462  * hlist_for_each_entry_from - iterate over a hlist continuing from current point
 463  * @tpos:       the type * to use as a loop cursor.
 464  * @pos:        the &struct hlist_node to use as a loop cursor.
 465  * @member:     the name of the hlist_node within the struct.
 466  */
 467 #if 0
 468 #define hlist_for_each_entry_from(tpos, pos, member)                    \
 469         for (; pos &&                                                   \
 470                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 471              pos = pos->next)
 472 #endif
 473 /**
 474  * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 475  * @tpos:       the type * to use as a loop cursor.
 476  * @pos:        the &struct hlist_node to use as a loop cursor.
 477  * @n:          another &struct hlist_node to use as temporary storage
 478  * @head:       the head for your list.
 479  * @member:     the name of the hlist_node within the struct.
 480  */
 481 #if 0
 482 #define hlist_for_each_entry_safe(tpos, pos, n, head, member)           \
 483         for (pos = HLIST_PTR((head)->first);                            \
 484              pos && ({ n = pos->next; 1; }) &&                          \
 485                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
 486              pos = n)
 487 #endif
 488
 489 /*
 490  * tlists are lists with types.
 491  * The lsbs of each of the two pointers provide 2 bits of type
 492  * information.  This is useful when different fields in different
 493  * structures can all be on the same list
 494  */
 495 struct tlist_head {
 496         struct tlist_head *next safe, *prev safe;
 497 };
 498
 499 #define TLIST_PTR(p) ((struct tlist_head * safe)(((unsigned long)(p)) & ~1UL))
 500 #define __TLIST_TYPE(p,n) ((((unsigned long)(p)) & 1)<<1 | (((unsigned long)(n)) & 1))
 501 #define TLIST_TYPE(e) __TLIST_TYPE((e)->prev, (e)->next)
 502 #define TLIST_PREV(p,t) ((struct tlist_head * safe)((((t)>>1)&1)|(unsigned long)(p)))
 503 #define TLIST_NEXT(n,t) ((struct tlist_head * safe)(((t)&1)|(unsigned long)(n)))
 504
 505 #define TLIST_HEAD_INIT(name, type) { TLIST_NEXT(&(name),(type)),       \
 506                                       TLIST_PREV(&(name),(type)) }
 507 #define INIT_TLIST_HEAD(ptr, type) do {         \
 508         (ptr)->next = TLIST_NEXT((ptr),(type)); \
 509         (ptr)->prev = TLIST_PREV((ptr),(type)); \
 510 } while (0)
 511
 512 /**
 513  * tlist_empty - tests whether a tlist is empty
 514  * @head: the list to test.
 515  */
 516 static inline int tlist_empty(struct tlist_head *head safe)
 517 {
 518         return TLIST_PTR(head->next) == head;
 519 }
 520 /*
 521  * Insert a new entry between two known consecutive entries.
 522  *
 523  * This is only for internal list manipulation where we know
 524  * the prev/next entries already!
 525  */
 526 static inline void __tlist_add(struct tlist_head *new safe, int type,
 527                                struct tlist_head *prev safe,
 528                                struct tlist_head *next safe)
 529 {
 530         next->prev = TLIST_PREV(new, __TLIST_TYPE(next->prev, NULL));
 531         new->next = TLIST_NEXT(next, type);
 532         new->prev = TLIST_PREV(prev, type);
 533         prev->next = TLIST_NEXT(new, __TLIST_TYPE(NULL, prev->next));
 534 }
 535
 536 /**
 537  * list_entry - get the struct for this entry
 538  * @ptr:        the &struct list_head pointer.
 539  * @type:       the type of the struct this is embedded in.
 540  * @member:     the name of the list_head within the struct.
 541  */
 542 #define tlist_entry(ptr, type, member) \
 543         container_of(TLIST_PTR(ptr), type, member)
 544
 545 /**
 546  * tlist_add - add a new entry
 547  * @new: new entry to be added
 548  * @type: type of location
 549  * @head: list head to add it after
 550  *
 551  * Insert a new entry after the specified head.
 552  * This is good for implementing stacks.
 553  */
 554 static inline void tlist_add(struct tlist_head *new safe, int type, struct tlist_head *head safe)
 555 {
 556         __tlist_add(new, type, head, TLIST_PTR(head->next));
 557 }
 558
 559 /**
 560  * tlist_add_tail - add a new entry
 561  * @new: new entry to be added
 562  * @type: type of location
 563  * @head: list head to add it before
 564  *
 565  * Insert a new entry before the specified head.
 566  * This is useful for implementing queues.
 567  */
 568 static inline void tlist_add_tail(struct tlist_head *new safe, int type,
 569                                   struct tlist_head *head safe)
 570 {
 571         __tlist_add(new, type, TLIST_PTR(head->prev), head);
 572 }
 573
 574 /*
 575  * Delete a list entry by making the prev/next entries
 576  * point to each other.
 577  *
 578  * This is only for internal list manipulation where we know
 579  * the prev/next entries already!
 580  */
 581 static inline void __tlist_del(struct tlist_head *prev safe, struct tlist_head *next safe)
 582 {
 583         int nt = TLIST_TYPE(next);
 584         int pt = TLIST_TYPE(prev);
 585         next->prev = TLIST_PREV(TLIST_PTR(prev), nt);
 586         prev->next = TLIST_NEXT(TLIST_PTR(next), pt);
 587 }
 588
 589 /**
 590  * tlist_del - deletes entry from list.
 591  * @entry: the element to delete from the list.
 592  * Note: list_empty on entry does not return true after this, the entry is
 593  * in an undefined state.
 594  */
 595 static inline void tlist_del(struct tlist_head *entry safe)
 596 {
 597         __tlist_del(TLIST_PTR(entry->prev), TLIST_PTR(entry->next));
 598         entry->next = LIST_POISON1;
 599         entry->prev = LIST_POISON2;
 600 }
 601
 602 /**
 603  * tlist_del_init - deletes entry from list and reinitialize it.
 604  * @entry: the element to delete from the list.
 605  */
 606 static inline void tlist_del_init(struct tlist_head *entry safe)
 607 {
 608         int type = TLIST_TYPE(entry);
 609         __tlist_del(TLIST_PTR(entry->prev), TLIST_PTR(entry->next));
 610         INIT_TLIST_HEAD(entry, type);
 611 }
 612
 613 /**
 614  * tlist_next_entry - get the next element in list
 615  * @pos:        the type * to cursor
 616  * @member:     the name of the tlist_head within the struct.
 617  */
 618 #define tlist_next_entry(pos, member) \
 619         tlist_entry((pos)->member.next, typeof(*(pos)), member)
 620
 621 /**
 622  * tlist_prev_entry - get the prev element in list
 623  * @pos:        the type * to cursor
 624  * @member:     the name of the list_head within the struct.
 625  */
 626 #define tlist_prev_entry(pos, member) \
 627         tlist_entry((pos)->member.prev, typeof(*(pos)), member)
 628
 629 /**
 630  * tlist_for_each       -       iterate over a tlist
 631  * @pos:        the &struct tlist_head to use as a loop cursor.
 632  * @head:       the head for your tlist.
 633  */
 634 #define tlist_for_each(pos, head) \
 635         for (pos = TLIST_PTR((head)->next); pos != (head); pos = TLIST_PTR(pos->next))
 636
 637 /**
 638  * tlist_for_each_continue - continue iteration over tlist
 639  * @pos:        the struct tlist_head * to use as a loop cursor.
 640  * @head_typef: the the type of the head for your list.
 641  *
 642  * Continue to iterate over tlist, continuing after
 643  * the current position.
 644  */
 645 #define tlist_for_each_continue(pos, head_type)                 \
 646         for (pos = TLIST_PTR(pos->next);                        \
 647              TLIST_TYPE(pos) != (head_type);                    \
 648              pos = TLIST_PTR(pos->next))
 649
 650 /**
 651  * list_for_each_continue_reverse - iterate backwards from the given point
 652  * @pos:        the struct tlist_head * to use as a loop cursor.
 653  * @head:       the type of the head for your list.
 654  *
 655  * Start to iterate over list of given type backwards, continuing after
 656  * the current position.
 657  */
 658 #define tlist_for_each_continue_reverse(pos, head_type)         \
 659         for (pos = TLIST_PTR(pos->prev);                        \
 660              TLIST_TYPE(pos) != (head_type);                    \
 661              pos = TLIST_PTR(pos->prev))
 662
 663 /**
 664  * tlist_for_each_entry -  iterate over list of given type
 665  * @pos:        the type * to use as a loop cursor.
 666  * @head:       the head for your list.
 667  * @member:     the name of the tlist_head within the struct.
 668  *
 669  * Iterate over list of given type.
 670  */
 671 #define tlist_for_each_entry(pos, head, member)         \
 672         for (pos = list_entry((head)->next, typeof(*(pos)), member);    \
 673              &pos->member != (head);                                    \
 674              pos = tlist_next_entry(pos, member))
 675
 676 /**
 677  * tlist_for_each_entry_continue - continue iteration over list of given type
 678  * @pos:        the type * to use as a loop cursor.
 679  * @head_type:  type of pointer in the head for your list.
 680  * @member:     the name of the tlist_head within the struct.
 681  *
 682  * Continue to iterate over list of given type, continuing after
 683  * the current position.
 684  */
 685 #define tlist_for_each_entry_continue(pos, head_type, member)           \
 686         for (pos = tlist_next_entry(pos, member);                       \
 687              TLIST_TYPE(&pos->member) != (head_type);                   \
 688              pos = tlist_next_entry(pos, member))
 689
 690 /**
 691  * list_for_each_entry_continue_reverse - iterate backwards from the given point
 692  * @pos:        the type * to use as a loop cursor.
 693  * @head_type:  type of pointer in the head for your list.
 694  * @member:     the name of the list_head within the struct.
 695  *
 696  * Start to iterate over list of given type backwards, continuing after
 697  * the current position.
 698  */
 699 #define tlist_for_each_entry_continue_reverse(pos, head_type, member)           \
 700         for (pos = tlist_prev_entry(pos, member);                       \
 701              TLIST_TYPE(&pos->member) != (head_type);                   \
 702              pos = tlist_prev_entry(pos, member))
 703
 704 /* Natural merge sort of the linked list */
 705 static inline void sort_list(struct list_head *lst safe,
 706                              char * (*key)(struct list_head *le, const void *data),
 707                              const void *data)
 708 {
 709         struct list_head *de[2];
 710         struct list_head *l;
 711
 712         if (list_empty(lst))
 713                 return;
 714         /* Convert to NULL terminated singly-linked list for sorting */
 715         lst->prev->next = safe_cast NULL;
 716
 717         de[0] = lst->next;
 718         de[1] = NULL;
 719
 720         do {
 721                 struct list_head ** safe dep[2];
 722                 struct list_head *d[2];
 723                 int curr = 0;
 724                 char *prev = "";
 725                 int next = 0;
 726
 727                 dep[0] = &de[0];
 728                 dep[1] = &de[1];
 729                 d[0] = de[0];
 730                 d[1] = de[1];
 731
 732                 /* d[0] and d[1] are two lists to be merged and split.
 733                  * The results will be put in de[0] and de[1].
 734                  * dep[0] and dep[1] are end pointers to de[0] and de[1] so far.
 735                  *
 736                  * Take least of d[0] and d[1].
 737                  * If it is larger than prev, add to
 738                  * dep[curr], else swap curr then add
 739                  */
 740                 while (d[0] || d[1]) {
 741                         char *kn = key(d[next], data);
 742                         char *kp = key(d[1-next], data);
 743                         if (kn == NULL ||
 744                             (kp != NULL &&
 745                              !((strcmp(prev, kp) <= 0)
 746                                ^(strcmp(kp, kn) <= 0)
 747                                ^(strcmp(kn, prev) <= 0)))
 748                         ) {
 749                                 char *t = kn;
 750                                 kn = kp;
 751                                 kp = t;
 752                                 next = 1 - next;
 753                         }
 754
 755                         if (!d[next] || !kn)
 756                                 break;
 757                         if (strcmp(kn, prev) < 0)
 758                                 curr = 1 - curr;
 759                         prev = kn;
 760                         *dep[curr] = d[next];
 761                         dep[curr] = &d[next]->next;
 762                         d[next] = d[next]->next;
 763                 }
 764                 *dep[0] = NULL;
 765                 *dep[1] = NULL;
 766         } while (de[0] && de[1]);
 767
 768         /* Now re-assemble the doublely-linked list */
 769         if (de[0])
 770                 lst->next = de[0];
 771         else
 772                 lst->next = safe_cast de[1];
 773         l = lst;
 774
 775         while ((void*)l->next) {
 776                 l->next->prev = l;
 777                 l = l->next;
 778         }
 779         l->next = lst;
 780         lst->prev = l;
 781 }
 782 #endif /* __LIST_H__ */