LCOV - code coverage report
Current view: top level - ccan/list - list.h (source / functions) Hit Total Coverage
Test: skiboot.info Lines: 96 96 100.0 %
Date: 2024-01-02 21:04:04 Functions: 20 20 100.0 %
Branches: 0 0 -

           Branch data     Line data    Source code
       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 <ccan/str/str.h>
       8                 :            : #include <ccan/container_of/container_of.h>
       9                 :            : #include <ccan/check_type/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                 :       1714 : static inline void list_head_init(struct list_head *h)
     144                 :            : {
     145                 :       1714 :         h->n.next = h->n.prev = &h->n;
     146                 :       1714 : }
     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                 :         80 : static inline void list_node_init(struct list_node *n)
     156                 :            : {
     157                 :         80 :         n->next = n->prev = n;
     158                 :         80 : }
     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                 :      14729 : 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                 :      14729 :         n->next = p->next;
     184                 :      14729 :         n->prev = p;
     185                 :      14729 :         p->next->prev = n;
     186                 :      14729 :         p->next = n;
     187                 :      14729 :         (void)list_debug(h, abortstr);
     188                 :      14729 : }
     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                 :      14673 : static inline void list_add_(struct list_head *h,
     205                 :            :                              struct list_node *n,
     206                 :            :                              const char *abortstr)
     207                 :            : {
     208                 :      14673 :         list_add_after_(h, &h->n, n, abortstr);
     209                 :      14673 : }
     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                 :       4057 : 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                 :       4057 :         n->next = p;
     233                 :       4057 :         n->prev = p->prev;
     234                 :       4057 :         p->prev->next = n;
     235                 :       4057 :         p->prev = n;
     236                 :       4057 :         (void)list_debug(h, abortstr);
     237                 :       4057 : }
     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                 :       3235 : static inline void list_add_tail_(struct list_head *h,
     251                 :            :                                   struct list_node *n,
     252                 :            :                                   const char *abortstr)
     253                 :            : {
     254                 :       3235 :         list_add_before_(h, &h->n, n, abortstr);
     255                 :       3235 : }
     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                 :     158065 : static inline bool list_empty_(const struct list_head *h, const char* abortstr)
     268                 :            : {
     269                 :     158065 :         (void)list_debug(h, abortstr);
     270                 :     158055 :         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                 :     130932 : static inline bool list_empty_nocheck(const struct list_head *h)
     305                 :            : {
     306                 :     130932 :         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                 :      18533 : static inline void list_del_(struct list_node *n, const char* abortstr)
     325                 :            : {
     326                 :      18533 :         (void)list_debug_node(n, abortstr);
     327                 :      18533 :         n->next->prev = n->prev;
     328                 :      18533 :         n->prev->next = n->next;
     329                 :            : #ifdef CCAN_LIST_DEBUG
     330                 :            :         /* Catch use-after-del. */
     331                 :      18533 :         n->next = n->prev = NULL;
     332                 :            : #endif
     333                 :      18533 : }
     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                 :         60 : static inline void list_del_init_(struct list_node *n, const char *abortstr)
     351                 :            : {
     352                 :         60 :         list_del_(n, abortstr);
     353                 :         60 :         list_node_init(n);
     354                 :         60 : }
     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                 :      15142 : 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                 :      16870 :                 for (i = h->n.next; i != n; i = i->next)
     377                 :       1728 :                         assert(i != &h->n);
     378                 :            :         }
     379                 :            : #endif /* CCAN_LIST_DEBUG */
     380                 :            : 
     381                 :            :         /* Quick test that catches a surprising number of bugs. */
     382                 :      15142 :         assert(!list_empty(h));
     383                 :      15142 :         list_del(n);
     384                 :      15142 : }
     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                 :         20 : static inline void list_swap_(struct list_node *o,
     406                 :            :                               struct list_node *n,
     407                 :            :                               const char* abortstr)
     408                 :            : {
     409                 :         20 :         (void)list_debug_node(o, abortstr);
     410                 :         20 :         *n = *o;
     411                 :         20 :         n->next->prev = n;
     412                 :         20 :         n->prev->next = n;
     413                 :            : #ifdef CCAN_LIST_DEBUG
     414                 :            :         /* Catch use-after-del. */
     415                 :         20 :         o->next = o->prev = NULL;
     416                 :            : #endif
     417                 :         20 : }
     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                 :     132944 : static inline const void *list_top_(const struct list_head *h, size_t off)
     452                 :            : {
     453                 :     132944 :         if (list_empty(h))
     454                 :      66218 :                 return NULL;
     455                 :      66726 :         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                 :       3522 : static inline const void *list_pop_(const struct list_head *h, size_t off)
     476                 :            : {
     477                 :            :         struct list_node *n;
     478                 :            : 
     479                 :       3522 :         if (list_empty(h))
     480                 :        727 :                 return NULL;
     481                 :       2795 :         n = h->n.next;
     482                 :       2795 :         list_del(n);
     483                 :       2795 :         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                 :        241 : static inline const void *list_tail_(const struct list_head *h, size_t off)
     504                 :            : {
     505                 :        241 :         if (list_empty(h))
     506                 :        156 :                 return NULL;
     507                 :         85 :         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                 :         50 : static inline void list_append_list_(struct list_head *to,
     641                 :            :                                      struct list_head *from,
     642                 :            :                                      const char *abortstr)
     643                 :            : {
     644                 :         50 :         struct list_node *from_tail = list_debug(from, abortstr)->n.prev;
     645                 :         50 :         struct list_node *to_tail = list_debug(to, abortstr)->n.prev;
     646                 :            : 
     647                 :            :         /* Sew in head and entire list. */
     648                 :         50 :         to->n.prev = from_tail;
     649                 :         50 :         from_tail->next = &to->n;
     650                 :         50 :         to_tail->next = &from->n;
     651                 :         50 :         from->n.prev = to_tail;
     652                 :            : 
     653                 :            :         /* Now remove head. */
     654                 :         50 :         list_del(&from->n);
     655                 :         50 :         list_head_init(from);
     656                 :         50 : }
     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                 :         50 : static inline void list_prepend_list_(struct list_head *to,
     673                 :            :                                       struct list_head *from,
     674                 :            :                                       const char *abortstr)
     675                 :            : {
     676                 :         50 :         struct list_node *from_tail = list_debug(from, abortstr)->n.prev;
     677                 :         50 :         struct list_node *to_head = list_debug(to, abortstr)->n.next;
     678                 :            : 
     679                 :            :         /* Sew in head and entire list. */
     680                 :         50 :         to->n.next = &from->n;
     681                 :         50 :         from->n.prev = &to->n;
     682                 :         50 :         to_head->prev = from_tail;
     683                 :         50 :         from_tail->next = to_head;
     684                 :            : 
     685                 :            :         /* Now remove head. */
     686                 :         50 :         list_del(&from->n);
     687                 :         50 :         list_head_init(from);
     688                 :         50 : }
     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                 :     313478 : static inline void *list_node_to_off_(struct list_node *node, size_t off)
     810                 :            : {
     811                 :     313478 :         return (void *)((char *)node - off);
     812                 :            : }
     813                 :     483072 : static inline struct list_node *list_node_from_off_(void *ptr, size_t off)
     814                 :            : {
     815                 :     483072 :         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                 :        203 : static inline void *list_entry_or_null(const struct list_head *h,
     835                 :            :                                        const struct list_node *n,
     836                 :            :                                        size_t off)
     837                 :            : {
     838                 :        203 :         if (n == &h->n)
     839                 :         81 :                 return NULL;
     840                 :        122 :         return (char *)n - off;
     841                 :            : }
     842                 :            : #endif /* CCAN_LIST_H */

Generated by: LCOV version 1.14