nostrdb

an unfairly fast embedded nostr database backed by lmdb
git clone git://jb55.com/nostrdb
Log | Files | Refs | Submodules | README | LICENSE

list.h (25752B)


      1 /* Licensed under BSD-MIT - see LICENSE file for details */
      2 #ifndef CCAN_LIST_H
      3 #define CCAN_LIST_H
      4 //#define CCAN_LIST_DEBUG 1
      5 #include <stdbool.h>
      6 #include <assert.h>
      7 #include "str.h"
      8 #include "container_of.h"
      9 #include "check_type.h"
     10 
     11 /**
     12  * struct list_node - an entry in a doubly-linked list
     13  * @next: next entry (self if empty)
     14  * @prev: previous entry (self if empty)
     15  *
     16  * This is used as an entry in a linked list.
     17  * Example:
     18  *    struct child {
     19  *        const char *name;
     20  *        // Linked list of all us children.
     21  *        struct list_node list;
     22  *    };
     23  */
     24 struct list_node
     25 {
     26     struct list_node *next, *prev;
     27 };
     28 
     29 /**
     30  * struct list_head - the head of a doubly-linked list
     31  * @h: the list_head (containing next and prev pointers)
     32  *
     33  * This is used as the head of a linked list.
     34  * Example:
     35  *    struct parent {
     36  *        const char *name;
     37  *        struct list_head children;
     38  *        unsigned int num_children;
     39  *    };
     40  */
     41 struct list_head
     42 {
     43     struct list_node n;
     44 };
     45 
     46 /**
     47  * list_check - check head of a list for consistency
     48  * @h: the list_head
     49  * @abortstr: the location to print on aborting, or NULL.
     50  *
     51  * Because list_nodes have redundant information, consistency checking between
     52  * the back and forward links can be done.  This is useful as a debugging check.
     53  * If @abortstr is non-NULL, that will be printed in a diagnostic if the list
     54  * is inconsistent, and the function will abort.
     55  *
     56  * Returns the list head if the list is consistent, NULL if not (it
     57  * can never return NULL if @abortstr is set).
     58  *
     59  * See also: list_check_node()
     60  *
     61  * Example:
     62  *    static void dump_parent(struct parent *p)
     63  *    {
     64  *        struct child *c;
     65  *
     66  *        printf("%s (%u children):\n", p->name, p->num_children);
     67  *        list_check(&p->children, "bad child list");
     68  *        list_for_each(&p->children, c, list)
     69  *            printf(" -> %s\n", c->name);
     70  *    }
     71  */
     72 struct list_head *list_check(const struct list_head *h, const char *abortstr);
     73 
     74 /**
     75  * list_check_node - check node of a list for consistency
     76  * @n: the list_node
     77  * @abortstr: the location to print on aborting, or NULL.
     78  *
     79  * Check consistency of the list node is in (it must be in one).
     80  *
     81  * See also: list_check()
     82  *
     83  * Example:
     84  *    static void dump_child(const struct child *c)
     85  *    {
     86  *        list_check_node(&c->list, "bad child list");
     87  *        printf("%s\n", c->name);
     88  *    }
     89  */
     90 struct list_node *list_check_node(const struct list_node *n,
     91                   const char *abortstr);
     92 
     93 #define LIST_LOC __FILE__  ":" stringify(__LINE__)
     94 #ifdef CCAN_LIST_DEBUG
     95 #define list_debug(h, loc) list_check((h), loc)
     96 #define list_debug_node(n, loc) list_check_node((n), loc)
     97 #else
     98 #define list_debug(h, loc) ((void)loc, h)
     99 #define list_debug_node(n, loc) ((void)loc, n)
    100 #endif
    101 
    102 /**
    103  * LIST_HEAD_INIT - initializer for an empty list_head
    104  * @name: the name of the list.
    105  *
    106  * Explicit initializer for an empty list.
    107  *
    108  * See also:
    109  *    LIST_HEAD, list_head_init()
    110  *
    111  * Example:
    112  *    static struct list_head my_list = LIST_HEAD_INIT(my_list);
    113  */
    114 #define LIST_HEAD_INIT(name) { { &(name).n, &(name).n } }
    115 
    116 /**
    117  * LIST_HEAD - define and initialize an empty list_head
    118  * @name: the name of the list.
    119  *
    120  * The LIST_HEAD macro defines a list_head and initializes it to an empty
    121  * list.  It can be prepended by "static" to define a static list_head.
    122  *
    123  * See also:
    124  *    LIST_HEAD_INIT, list_head_init()
    125  *
    126  * Example:
    127  *    static LIST_HEAD(my_global_list);
    128  */
    129 #define LIST_HEAD(name) \
    130     struct list_head name = LIST_HEAD_INIT(name)
    131 
    132 /**
    133  * list_head_init - initialize a list_head
    134  * @h: the list_head to set to the empty list
    135  *
    136  * Example:
    137  *    ...
    138  *    struct parent *parent = malloc(sizeof(*parent));
    139  *
    140  *    list_head_init(&parent->children);
    141  *    parent->num_children = 0;
    142  */
    143 static inline void list_head_init(struct list_head *h)
    144 {
    145     h->n.next = h->n.prev = &h->n;
    146 }
    147 
    148 /**
    149  * list_node_init - initialize a list_node
    150  * @n: the list_node to link to itself.
    151  *
    152  * You don't need to use this normally!  But it lets you list_del(@n)
    153  * safely.
    154  */
    155 static inline void list_node_init(struct list_node *n)
    156 {
    157     n->next = n->prev = n;
    158 }
    159 
    160 /**
    161  * list_add_after - add an entry after an existing node in a linked list
    162  * @h: the list_head to add the node to (for debugging)
    163  * @p: the existing list_node to add the node after
    164  * @n: the new list_node to add to the list.
    165  *
    166  * The existing list_node must already be a member of the list.
    167  * The new list_node does not need to be initialized; it will be overwritten.
    168  *
    169  * Example:
    170  *    struct child c1, c2, c3;
    171  *    LIST_HEAD(h);
    172  *
    173  *    list_add_tail(&h, &c1.list);
    174  *    list_add_tail(&h, &c3.list);
    175  *    list_add_after(&h, &c1.list, &c2.list);
    176  */
    177 #define list_add_after(h, p, n) list_add_after_(h, p, n, LIST_LOC)
    178 static inline void list_add_after_(struct list_head *h,
    179                    struct list_node *p,
    180                    struct list_node *n,
    181                    const char *abortstr)
    182 {
    183     n->next = p->next;
    184     n->prev = p;
    185     p->next->prev = n;
    186     p->next = n;
    187     (void)list_debug(h, abortstr);
    188 }
    189 
    190 /**
    191  * list_add - add an entry at the start of a linked list.
    192  * @h: the list_head to add the node to
    193  * @n: the list_node to add to the list.
    194  *
    195  * The list_node does not need to be initialized; it will be overwritten.
    196  * Example:
    197  *    struct child *child = malloc(sizeof(*child));
    198  *
    199  *    child->name = "marvin";
    200  *    list_add(&parent->children, &child->list);
    201  *    parent->num_children++;
    202  */
    203 #define list_add(h, n) list_add_(h, n, LIST_LOC)
    204 static inline void list_add_(struct list_head *h,
    205                  struct list_node *n,
    206                  const char *abortstr)
    207 {
    208     list_add_after_(h, &h->n, n, abortstr);
    209 }
    210 
    211 /**
    212  * list_add_before - add an entry before an existing node in a linked list
    213  * @h: the list_head to add the node to (for debugging)
    214  * @p: the existing list_node to add the node before
    215  * @n: the new list_node to add to the list.
    216  *
    217  * The existing list_node must already be a member of the list.
    218  * The new list_node does not need to be initialized; it will be overwritten.
    219  *
    220  * Example:
    221  *    list_head_init(&h);
    222  *    list_add_tail(&h, &c1.list);
    223  *    list_add_tail(&h, &c3.list);
    224  *    list_add_before(&h, &c3.list, &c2.list);
    225  */
    226 #define list_add_before(h, p, n) list_add_before_(h, p, n, LIST_LOC)
    227 static inline void list_add_before_(struct list_head *h,
    228                     struct list_node *p,
    229                     struct list_node *n,
    230                     const char *abortstr)
    231 {
    232     n->next = p;
    233     n->prev = p->prev;
    234     p->prev->next = n;
    235     p->prev = n;
    236     (void)list_debug(h, abortstr);
    237 }
    238 
    239 /**
    240  * list_add_tail - add an entry at the end of a linked list.
    241  * @h: the list_head to add the node to
    242  * @n: the list_node to add to the list.
    243  *
    244  * The list_node does not need to be initialized; it will be overwritten.
    245  * Example:
    246  *    list_add_tail(&parent->children, &child->list);
    247  *    parent->num_children++;
    248  */
    249 #define list_add_tail(h, n) list_add_tail_(h, n, LIST_LOC)
    250 static inline void list_add_tail_(struct list_head *h,
    251                   struct list_node *n,
    252                   const char *abortstr)
    253 {
    254     list_add_before_(h, &h->n, n, abortstr);
    255 }
    256 
    257 /**
    258  * list_empty - is a list empty?
    259  * @h: the list_head
    260  *
    261  * If the list is empty, returns true.
    262  *
    263  * Example:
    264  *    assert(list_empty(&parent->children) == (parent->num_children == 0));
    265  */
    266 #define list_empty(h) list_empty_(h, LIST_LOC)
    267 static inline bool list_empty_(const struct list_head *h, const char* abortstr)
    268 {
    269     (void)list_debug(h, abortstr);
    270     return h->n.next == &h->n;
    271 }
    272 
    273 /**
    274  * list_empty_nodebug - is a list empty (and don't perform debug checks)?
    275  * @h: the list_head
    276  *
    277  * If the list is empty, returns true.
    278  * This differs from list_empty() in that if CCAN_LIST_DEBUG is set it
    279  * will NOT perform debug checks. Only use this function if you REALLY
    280  * know what you're doing.
    281  *
    282  * Example:
    283  *    assert(list_empty_nodebug(&parent->children) == (parent->num_children == 0));
    284  */
    285 #ifndef CCAN_LIST_DEBUG
    286 #define list_empty_nodebug(h) list_empty(h)
    287 #else
    288 static inline bool list_empty_nodebug(const struct list_head *h)
    289 {
    290     return h->n.next == &h->n;
    291 }
    292 #endif
    293 
    294 /**
    295  * list_empty_nocheck - is a list empty?
    296  * @h: the list_head
    297  *
    298  * If the list is empty, returns true. This doesn't perform any
    299  * debug check for list consistency, so it can be called without
    300  * locks, racing with the list being modified. This is ok for
    301  * checks where an incorrect result is not an issue (optimized
    302  * bail out path for example).
    303  */
    304 static inline bool list_empty_nocheck(const struct list_head *h)
    305 {
    306     return h->n.next == &h->n;
    307 }
    308 
    309 /**
    310  * list_del - delete an entry from an (unknown) linked list.
    311  * @n: the list_node to delete from the list.
    312  *
    313  * Note that this leaves @n in an undefined state; it can be added to
    314  * another list, but not deleted again.
    315  *
    316  * See also:
    317  *    list_del_from(), list_del_init()
    318  *
    319  * Example:
    320  *    list_del(&child->list);
    321  *    parent->num_children--;
    322  */
    323 #define list_del(n) list_del_(n, LIST_LOC)
    324 static inline void list_del_(struct list_node *n, const char* abortstr)
    325 {
    326     (void)list_debug_node(n, abortstr);
    327     n->next->prev = n->prev;
    328     n->prev->next = n->next;
    329 #ifdef CCAN_LIST_DEBUG
    330     /* Catch use-after-del. */
    331     n->next = n->prev = NULL;
    332 #endif
    333 }
    334 
    335 /**
    336  * list_del_init - delete a node, and reset it so it can be deleted again.
    337  * @n: the list_node to be deleted.
    338  *
    339  * list_del(@n) or list_del_init() again after this will be safe,
    340  * which can be useful in some cases.
    341  *
    342  * See also:
    343  *    list_del_from(), list_del()
    344  *
    345  * Example:
    346  *    list_del_init(&child->list);
    347  *    parent->num_children--;
    348  */
    349 #define list_del_init(n) list_del_init_(n, LIST_LOC)
    350 static inline void list_del_init_(struct list_node *n, const char *abortstr)
    351 {
    352     list_del_(n, abortstr);
    353     list_node_init(n);
    354 }
    355 
    356 /**
    357  * list_del_from - delete an entry from a known linked list.
    358  * @h: the list_head the node is in.
    359  * @n: the list_node to delete from the list.
    360  *
    361  * This explicitly indicates which list a node is expected to be in,
    362  * which is better documentation and can catch more bugs.
    363  *
    364  * See also: list_del()
    365  *
    366  * Example:
    367  *    list_del_from(&parent->children, &child->list);
    368  *    parent->num_children--;
    369  */
    370 static inline void list_del_from(struct list_head *h, struct list_node *n)
    371 {
    372 #ifdef CCAN_LIST_DEBUG
    373     {
    374         /* Thorough check: make sure it was in list! */
    375         struct list_node *i;
    376         for (i = h->n.next; i != n; i = i->next)
    377             assert(i != &h->n);
    378     }
    379 #endif /* CCAN_LIST_DEBUG */
    380 
    381     /* Quick test that catches a surprising number of bugs. */
    382     assert(!list_empty(h));
    383     list_del(n);
    384 }
    385 
    386 /**
    387  * list_swap - swap out an entry from an (unknown) linked list for a new one.
    388  * @o: the list_node to replace from the list.
    389  * @n: the list_node to insert in place of the old one.
    390  *
    391  * Note that this leaves @o in an undefined state; it can be added to
    392  * another list, but not deleted/swapped again.
    393  *
    394  * See also:
    395  *    list_del()
    396  *
    397  * Example:
    398  *    struct child x1, x2;
    399  *    LIST_HEAD(xh);
    400  *
    401  *    list_add(&xh, &x1.list);
    402  *    list_swap(&x1.list, &x2.list);
    403  */
    404 #define list_swap(o, n) list_swap_(o, n, LIST_LOC)
    405 static inline void list_swap_(struct list_node *o,
    406                   struct list_node *n,
    407                   const char* abortstr)
    408 {
    409     (void)list_debug_node(o, abortstr);
    410     *n = *o;
    411     n->next->prev = n;
    412     n->prev->next = n;
    413 #ifdef CCAN_LIST_DEBUG
    414     /* Catch use-after-del. */
    415     o->next = o->prev = NULL;
    416 #endif
    417 }
    418 
    419 /**
    420  * list_entry - convert a list_node back into the structure containing it.
    421  * @n: the list_node
    422  * @type: the type of the entry
    423  * @member: the list_node member of the type
    424  *
    425  * Example:
    426  *    // First list entry is children.next; convert back to child.
    427  *    child = list_entry(parent->children.n.next, struct child, list);
    428  *
    429  * See Also:
    430  *    list_top(), list_for_each()
    431  */
    432 #define list_entry(n, type, member) container_of(n, type, member)
    433 
    434 /**
    435  * list_top - get the first entry in a list
    436  * @h: the list_head
    437  * @type: the type of the entry
    438  * @member: the list_node member of the type
    439  *
    440  * If the list is empty, returns NULL.
    441  *
    442  * Example:
    443  *    struct child *first;
    444  *    first = list_top(&parent->children, struct child, list);
    445  *    if (!first)
    446  *        printf("Empty list!\n");
    447  */
    448 #define list_top(h, type, member)                    \
    449     ((type *)list_top_((h), list_off_(type, member)))
    450 
    451 static inline const void *list_top_(const struct list_head *h, size_t off)
    452 {
    453     if (list_empty(h))
    454         return NULL;
    455     return (const char *)h->n.next - off;
    456 }
    457 
    458 /**
    459  * list_pop - remove the first entry in a list
    460  * @h: the list_head
    461  * @type: the type of the entry
    462  * @member: the list_node member of the type
    463  *
    464  * If the list is empty, returns NULL.
    465  *
    466  * Example:
    467  *    struct child *one;
    468  *    one = list_pop(&parent->children, struct child, list);
    469  *    if (!one)
    470  *        printf("Empty list!\n");
    471  */
    472 #define list_pop(h, type, member)                    \
    473     ((type *)list_pop_((h), list_off_(type, member)))
    474 
    475 static inline const void *list_pop_(const struct list_head *h, size_t off)
    476 {
    477     struct list_node *n;
    478 
    479     if (list_empty(h))
    480         return NULL;
    481     n = h->n.next;
    482     list_del(n);
    483     return (const char *)n - off;
    484 }
    485 
    486 /**
    487  * list_tail - get the last entry in a list
    488  * @h: the list_head
    489  * @type: the type of the entry
    490  * @member: the list_node member of the type
    491  *
    492  * If the list is empty, returns NULL.
    493  *
    494  * Example:
    495  *    struct child *last;
    496  *    last = list_tail(&parent->children, struct child, list);
    497  *    if (!last)
    498  *        printf("Empty list!\n");
    499  */
    500 #define list_tail(h, type, member) \
    501     ((type *)list_tail_((h), list_off_(type, member)))
    502 
    503 static inline const void *list_tail_(const struct list_head *h, size_t off)
    504 {
    505     if (list_empty(h))
    506         return NULL;
    507     return (const char *)h->n.prev - off;
    508 }
    509 
    510 /**
    511  * list_for_each - iterate through a list.
    512  * @h: the list_head (warning: evaluated multiple times!)
    513  * @i: the structure containing the list_node
    514  * @member: the list_node member of the structure
    515  *
    516  * This is a convenient wrapper to iterate @i over the entire list.  It's
    517  * a for loop, so you can break and continue as normal.
    518  *
    519  * Example:
    520  *    list_for_each(&parent->children, child, list)
    521  *        printf("Name: %s\n", child->name);
    522  */
    523 #define list_for_each(h, i, member)                    \
    524     list_for_each_off(h, i, list_off_var_(i, member))
    525 
    526 /**
    527  * list_for_each_rev - iterate through a list backwards.
    528  * @h: the list_head
    529  * @i: the structure containing the list_node
    530  * @member: the list_node member of the structure
    531  *
    532  * This is a convenient wrapper to iterate @i over the entire list.  It's
    533  * a for loop, so you can break and continue as normal.
    534  *
    535  * Example:
    536  *    list_for_each_rev(&parent->children, child, list)
    537  *        printf("Name: %s\n", child->name);
    538  */
    539 #define list_for_each_rev(h, i, member)                    \
    540     list_for_each_rev_off(h, i, list_off_var_(i, member))
    541 
    542 /**
    543  * list_for_each_rev_safe - iterate through a list backwards,
    544  * maybe during deletion
    545  * @h: the list_head
    546  * @i: the structure containing the list_node
    547  * @nxt: the structure containing the list_node
    548  * @member: the list_node member of the structure
    549  *
    550  * This is a convenient wrapper to iterate @i over the entire list backwards.
    551  * It's a for loop, so you can break and continue as normal.  The extra
    552  * variable * @nxt is used to hold the next element, so you can delete @i
    553  * from the list.
    554  *
    555  * Example:
    556  *    struct child *next;
    557  *    list_for_each_rev_safe(&parent->children, child, next, list) {
    558  *        printf("Name: %s\n", child->name);
    559  *    }
    560  */
    561 #define list_for_each_rev_safe(h, i, nxt, member)            \
    562     list_for_each_rev_safe_off(h, i, nxt, list_off_var_(i, member))
    563 
    564 /**
    565  * list_for_each_safe - iterate through a list, maybe during deletion
    566  * @h: the list_head
    567  * @i: the structure containing the list_node
    568  * @nxt: the structure containing the list_node
    569  * @member: the list_node member of the structure
    570  *
    571  * This is a convenient wrapper to iterate @i over the entire list.  It's
    572  * a for loop, so you can break and continue as normal.  The extra variable
    573  * @nxt is used to hold the next element, so you can delete @i from the list.
    574  *
    575  * Example:
    576  *    list_for_each_safe(&parent->children, child, next, list) {
    577  *        list_del(&child->list);
    578  *        parent->num_children--;
    579  *    }
    580  */
    581 #define list_for_each_safe(h, i, nxt, member)                \
    582     list_for_each_safe_off(h, i, nxt, list_off_var_(i, member))
    583 
    584 /**
    585  * list_next - get the next entry in a list
    586  * @h: the list_head
    587  * @i: a pointer to an entry in the list.
    588  * @member: the list_node member of the structure
    589  *
    590  * If @i was the last entry in the list, returns NULL.
    591  *
    592  * Example:
    593  *    struct child *second;
    594  *    second = list_next(&parent->children, first, list);
    595  *    if (!second)
    596  *        printf("No second child!\n");
    597  */
    598 #define list_next(h, i, member)                        \
    599     ((list_typeof(i))list_entry_or_null(list_debug(h,        \
    600                         __FILE__ ":" stringify(__LINE__)), \
    601                         (i)->member.next,        \
    602                         list_off_var_((i), member)))
    603 
    604 /**
    605  * list_prev - get the previous entry in a list
    606  * @h: the list_head
    607  * @i: a pointer to an entry in the list.
    608  * @member: the list_node member of the structure
    609  *
    610  * If @i was the first entry in the list, returns NULL.
    611  *
    612  * Example:
    613  *    first = list_prev(&parent->children, second, list);
    614  *    if (!first)
    615  *        printf("Can't go back to first child?!\n");
    616  */
    617 #define list_prev(h, i, member)                        \
    618     ((list_typeof(i))list_entry_or_null(list_debug(h,        \
    619                         __FILE__ ":" stringify(__LINE__)), \
    620                         (i)->member.prev,        \
    621                         list_off_var_((i), member)))
    622 
    623 /**
    624  * list_append_list - empty one list onto the end of another.
    625  * @to: the list to append into
    626  * @from: the list to empty.
    627  *
    628  * This takes the entire contents of @from and moves it to the end of
    629  * @to.  After this @from will be empty.
    630  *
    631  * Example:
    632  *    struct list_head adopter;
    633  *
    634  *    list_append_list(&adopter, &parent->children);
    635  *    assert(list_empty(&parent->children));
    636  *    parent->num_children = 0;
    637  */
    638 #define list_append_list(t, f) list_append_list_(t, f,            \
    639                    __FILE__ ":" stringify(__LINE__))
    640 static inline void list_append_list_(struct list_head *to,
    641                      struct list_head *from,
    642                      const char *abortstr)
    643 {
    644     struct list_node *from_tail = list_debug(from, abortstr)->n.prev;
    645     struct list_node *to_tail = list_debug(to, abortstr)->n.prev;
    646 
    647     /* Sew in head and entire list. */
    648     to->n.prev = from_tail;
    649     from_tail->next = &to->n;
    650     to_tail->next = &from->n;
    651     from->n.prev = to_tail;
    652 
    653     /* Now remove head. */
    654     list_del(&from->n);
    655     list_head_init(from);
    656 }
    657 
    658 /**
    659  * list_prepend_list - empty one list into the start of another.
    660  * @to: the list to prepend into
    661  * @from: the list to empty.
    662  *
    663  * This takes the entire contents of @from and moves it to the start
    664  * of @to.  After this @from will be empty.
    665  *
    666  * Example:
    667  *    list_prepend_list(&adopter, &parent->children);
    668  *    assert(list_empty(&parent->children));
    669  *    parent->num_children = 0;
    670  */
    671 #define list_prepend_list(t, f) list_prepend_list_(t, f, LIST_LOC)
    672 static inline void list_prepend_list_(struct list_head *to,
    673                       struct list_head *from,
    674                       const char *abortstr)
    675 {
    676     struct list_node *from_tail = list_debug(from, abortstr)->n.prev;
    677     struct list_node *to_head = list_debug(to, abortstr)->n.next;
    678 
    679     /* Sew in head and entire list. */
    680     to->n.next = &from->n;
    681     from->n.prev = &to->n;
    682     to_head->prev = from_tail;
    683     from_tail->next = to_head;
    684 
    685     /* Now remove head. */
    686     list_del(&from->n);
    687     list_head_init(from);
    688 }
    689 
    690 /* internal macros, do not use directly */
    691 #define list_for_each_off_dir_(h, i, off, dir)                \
    692     for (i = list_node_to_off_(list_debug(h, LIST_LOC)->n.dir,    \
    693                    (off));                \
    694     list_node_from_off_((void *)i, (off)) != &(h)->n;        \
    695     i = list_node_to_off_(list_node_from_off_((void *)i, (off))->dir, \
    696                   (off)))
    697 
    698 #define list_for_each_safe_off_dir_(h, i, nxt, off, dir)        \
    699     for (i = list_node_to_off_(list_debug(h, LIST_LOC)->n.dir,    \
    700                    (off)),                \
    701     nxt = list_node_to_off_(list_node_from_off_(i, (off))->dir,    \
    702                 (off));                    \
    703     list_node_from_off_(i, (off)) != &(h)->n;            \
    704     i = nxt,                            \
    705     nxt = list_node_to_off_(list_node_from_off_(i, (off))->dir,    \
    706                 (off)))
    707 
    708 /**
    709  * list_for_each_off - iterate through a list of memory regions.
    710  * @h: the list_head
    711  * @i: the pointer to a memory region which contains list node data.
    712  * @off: offset(relative to @i) at which list node data resides.
    713  *
    714  * This is a low-level wrapper to iterate @i over the entire list, used to
    715  * implement all oher, more high-level, for-each constructs. It's a for loop,
    716  * so you can break and continue as normal.
    717  *
    718  * WARNING! Being the low-level macro that it is, this wrapper doesn't know
    719  * nor care about the type of @i. The only assumption made is that @i points
    720  * to a chunk of memory that at some @offset, relative to @i, contains a
    721  * properly filled `struct list_node' which in turn contains pointers to
    722  * memory chunks and it's turtles all the way down. With all that in mind
    723  * remember that given the wrong pointer/offset couple this macro will
    724  * happily churn all you memory until SEGFAULT stops it, in other words
    725  * caveat emptor.
    726  *
    727  * It is worth mentioning that one of legitimate use-cases for that wrapper
    728  * is operation on opaque types with known offset for `struct list_node'
    729  * member(preferably 0), because it allows you not to disclose the type of
    730  * @i.
    731  *
    732  * Example:
    733  *    list_for_each_off(&parent->children, child,
    734  *                offsetof(struct child, list))
    735  *        printf("Name: %s\n", child->name);
    736  */
    737 #define list_for_each_off(h, i, off)                                    \
    738     list_for_each_off_dir_((h),(i),(off),next)
    739 
    740 /**
    741  * list_for_each_rev_off - iterate through a list of memory regions backwards
    742  * @h: the list_head
    743  * @i: the pointer to a memory region which contains list node data.
    744  * @off: offset(relative to @i) at which list node data resides.
    745  *
    746  * See list_for_each_off for details
    747  */
    748 #define list_for_each_rev_off(h, i, off)                                    \
    749     list_for_each_off_dir_((h),(i),(off),prev)
    750 
    751 /**
    752  * list_for_each_safe_off - iterate through a list of memory regions, maybe
    753  * during deletion
    754  * @h: the list_head
    755  * @i: the pointer to a memory region which contains list node data.
    756  * @nxt: the structure containing the list_node
    757  * @off: offset(relative to @i) at which list node data resides.
    758  *
    759  * For details see `list_for_each_off' and `list_for_each_safe'
    760  * descriptions.
    761  *
    762  * Example:
    763  *    list_for_each_safe_off(&parent->children, child,
    764  *        next, offsetof(struct child, list))
    765  *        printf("Name: %s\n", child->name);
    766  */
    767 #define list_for_each_safe_off(h, i, nxt, off)                          \
    768     list_for_each_safe_off_dir_((h),(i),(nxt),(off),next)
    769 
    770 /**
    771  * list_for_each_rev_safe_off - iterate backwards through a list of
    772  * memory regions, maybe during deletion
    773  * @h: the list_head
    774  * @i: the pointer to a memory region which contains list node data.
    775  * @nxt: the structure containing the list_node
    776  * @off: offset(relative to @i) at which list node data resides.
    777  *
    778  * For details see `list_for_each_rev_off' and `list_for_each_rev_safe'
    779  * descriptions.
    780  *
    781  * Example:
    782  *    list_for_each_rev_safe_off(&parent->children, child,
    783  *        next, offsetof(struct child, list))
    784  *        printf("Name: %s\n", child->name);
    785  */
    786 #define list_for_each_rev_safe_off(h, i, nxt, off)                      \
    787     list_for_each_safe_off_dir_((h),(i),(nxt),(off),prev)
    788 
    789 /* Other -off variants. */
    790 #define list_entry_off(n, type, off)        \
    791     ((type *)list_node_from_off_((n), (off)))
    792 
    793 #define list_head_off(h, type, off)        \
    794     ((type *)list_head_off((h), (off)))
    795 
    796 #define list_tail_off(h, type, off)        \
    797     ((type *)list_tail_((h), (off)))
    798 
    799 #define list_add_off(h, n, off)                 \
    800     list_add((h), list_node_from_off_((n), (off)))
    801 
    802 #define list_del_off(n, off)                    \
    803     list_del(list_node_from_off_((n), (off)))
    804 
    805 #define list_del_from_off(h, n, off)            \
    806     list_del_from(h, list_node_from_off_((n), (off)))
    807 
    808 /* Offset helper functions so we only single-evaluate. */
    809 static inline void *list_node_to_off_(struct list_node *node, size_t off)
    810 {
    811     return (void *)((char *)node - off);
    812 }
    813 static inline struct list_node *list_node_from_off_(void *ptr, size_t off)
    814 {
    815     return (struct list_node *)((char *)ptr + off);
    816 }
    817 
    818 /* Get the offset of the member, but make sure it's a list_node. */
    819 #define list_off_(type, member)                    \
    820     (container_off(type, member) +                \
    821      check_type(((type *)0)->member, struct list_node))
    822 
    823 #define list_off_var_(var, member)            \
    824     (container_off_var(var, member) +        \
    825      check_type(var->member, struct list_node))
    826 
    827 #if HAVE_TYPEOF
    828 #define list_typeof(var) typeof(var)
    829 #else
    830 #define list_typeof(var) void *
    831 #endif
    832 
    833 /* Returns member, or NULL if at end of list. */
    834 static inline void *list_entry_or_null(const struct list_head *h,
    835                        const struct list_node *n,
    836                        size_t off)
    837 {
    838     if (n == &h->n)
    839         return NULL;
    840     return (char *)n - off;
    841 }
    842 #endif /* CCAN_LIST_H */