LCOV - code coverage report
Current view: top level - src/include/lib - ilist.h (source / functions) Hit Total Coverage
Test: PostgreSQL 15devel Lines: 78 84 92.9 %
Date: 2021-12-05 02:08:31 Functions: 22 23 95.7 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * ilist.h
       4             :  *      integrated/inline doubly- and singly-linked lists
       5             :  *
       6             :  * These list types are useful when there are only a predetermined set of
       7             :  * lists that an object could be in.  List links are embedded directly into
       8             :  * the objects, and thus no extra memory management overhead is required.
       9             :  * (Of course, if only a small proportion of existing objects are in a list,
      10             :  * the link fields in the remainder would be wasted space.  But usually,
      11             :  * it saves space to not have separately-allocated list nodes.)
      12             :  *
      13             :  * None of the functions here allocate any memory; they just manipulate
      14             :  * externally managed memory.  The APIs for singly and doubly linked lists
      15             :  * are identical as far as capabilities of both allow.
      16             :  *
      17             :  * Each list has a list header, which exists even when the list is empty.
      18             :  * An empty singly-linked list has a NULL pointer in its header.
      19             :  * There are two kinds of empty doubly linked lists: those that have been
      20             :  * initialized to NULL, and those that have been initialized to circularity.
      21             :  * (If a dlist is modified and then all its elements are deleted, it will be
      22             :  * in the circular state.)  We prefer circular dlists because there are some
      23             :  * operations that can be done without branches (and thus faster) on lists
      24             :  * that use circular representation.  However, it is often convenient to
      25             :  * initialize list headers to zeroes rather than setting them up with an
      26             :  * explicit initialization function, so we also allow the other case.
      27             :  *
      28             :  * EXAMPLES
      29             :  *
      30             :  * Here's a simple example demonstrating how this can be used.  Let's assume
      31             :  * we want to store information about the tables contained in a database.
      32             :  *
      33             :  * #include "lib/ilist.h"
      34             :  *
      35             :  * // Define struct for the databases including a list header that will be
      36             :  * // used to access the nodes in the table list later on.
      37             :  * typedef struct my_database
      38             :  * {
      39             :  *      char       *datname;
      40             :  *      dlist_head  tables;
      41             :  *      // ...
      42             :  * } my_database;
      43             :  *
      44             :  * // Define struct for the tables.  Note the list_node element which stores
      45             :  * // prev/next list links.  The list_node element need not be first.
      46             :  * typedef struct my_table
      47             :  * {
      48             :  *      char       *tablename;
      49             :  *      dlist_node  list_node;
      50             :  *      perm_t      permissions;
      51             :  *      // ...
      52             :  * } my_table;
      53             :  *
      54             :  * // create a database
      55             :  * my_database *db = create_database();
      56             :  *
      57             :  * // and add a few tables to its table list
      58             :  * dlist_push_head(&db->tables, &create_table(db, "a")->list_node);
      59             :  * ...
      60             :  * dlist_push_head(&db->tables, &create_table(db, "b")->list_node);
      61             :  *
      62             :  *
      63             :  * To iterate over the table list, we allocate an iterator variable and use
      64             :  * a specialized looping construct.  Inside a dlist_foreach, the iterator's
      65             :  * 'cur' field can be used to access the current element.  iter.cur points to
      66             :  * a 'dlist_node', but most of the time what we want is the actual table
      67             :  * information; dlist_container() gives us that, like so:
      68             :  *
      69             :  * dlist_iter   iter;
      70             :  * dlist_foreach(iter, &db->tables)
      71             :  * {
      72             :  *      my_table   *tbl = dlist_container(my_table, list_node, iter.cur);
      73             :  *      printf("we have a table: %s in database %s\n",
      74             :  *             tbl->tablename, db->datname);
      75             :  * }
      76             :  *
      77             :  *
      78             :  * While a simple iteration is useful, we sometimes also want to manipulate
      79             :  * the list while iterating.  There is a different iterator element and looping
      80             :  * construct for that.  Suppose we want to delete tables that meet a certain
      81             :  * criterion:
      82             :  *
      83             :  * dlist_mutable_iter miter;
      84             :  * dlist_foreach_modify(miter, &db->tables)
      85             :  * {
      86             :  *      my_table   *tbl = dlist_container(my_table, list_node, miter.cur);
      87             :  *
      88             :  *      if (!tbl->to_be_deleted)
      89             :  *          continue;       // don't touch this one
      90             :  *
      91             :  *      // unlink the current table from the linked list
      92             :  *      dlist_delete(miter.cur);
      93             :  *      // as these lists never manage memory, we can still access the table
      94             :  *      // after it's been unlinked
      95             :  *      drop_table(db, tbl);
      96             :  * }
      97             :  *
      98             :  *
      99             :  * Portions Copyright (c) 1996-2021, PostgreSQL Global Development Group
     100             :  * Portions Copyright (c) 1994, Regents of the University of California
     101             :  *
     102             :  * IDENTIFICATION
     103             :  *      src/include/lib/ilist.h
     104             :  *-------------------------------------------------------------------------
     105             :  */
     106             : #ifndef ILIST_H
     107             : #define ILIST_H
     108             : 
     109             : /*
     110             :  * Enable for extra debugging. This is rather expensive, so it's not enabled by
     111             :  * default even when USE_ASSERT_CHECKING.
     112             :  */
     113             : /* #define ILIST_DEBUG */
     114             : 
     115             : /*
     116             :  * Node of a doubly linked list.
     117             :  *
     118             :  * Embed this in structs that need to be part of a doubly linked list.
     119             :  */
     120             : typedef struct dlist_node dlist_node;
     121             : struct dlist_node
     122             : {
     123             :     dlist_node *prev;
     124             :     dlist_node *next;
     125             : };
     126             : 
     127             : /*
     128             :  * Head of a doubly linked list.
     129             :  *
     130             :  * Non-empty lists are internally circularly linked.  Circular lists have the
     131             :  * advantage of not needing any branches in the most common list manipulations.
     132             :  * An empty list can also be represented as a pair of NULL pointers, making
     133             :  * initialization easier.
     134             :  */
     135             : typedef struct dlist_head
     136             : {
     137             :     /*
     138             :      * head.next either points to the first element of the list; to &head if
     139             :      * it's a circular empty list; or to NULL if empty and not circular.
     140             :      *
     141             :      * head.prev either points to the last element of the list; to &head if
     142             :      * it's a circular empty list; or to NULL if empty and not circular.
     143             :      */
     144             :     dlist_node  head;
     145             : } dlist_head;
     146             : 
     147             : 
     148             : /*
     149             :  * Doubly linked list iterator.
     150             :  *
     151             :  * Used as state in dlist_foreach() and dlist_reverse_foreach(). To get the
     152             :  * current element of the iteration use the 'cur' member.
     153             :  *
     154             :  * Iterations using this are *not* allowed to change the list while iterating!
     155             :  *
     156             :  * NB: We use an extra "end" field here to avoid multiple evaluations of
     157             :  * arguments in the dlist_foreach() macro.
     158             :  */
     159             : typedef struct dlist_iter
     160             : {
     161             :     dlist_node *cur;            /* current element */
     162             :     dlist_node *end;            /* last node we'll iterate to */
     163             : } dlist_iter;
     164             : 
     165             : /*
     166             :  * Doubly linked list iterator allowing some modifications while iterating.
     167             :  *
     168             :  * Used as state in dlist_foreach_modify(). To get the current element of the
     169             :  * iteration use the 'cur' member.
     170             :  *
     171             :  * Iterations using this are only allowed to change the list at the current
     172             :  * point of iteration. It is fine to delete the current node, but it is *not*
     173             :  * fine to insert or delete adjacent nodes.
     174             :  *
     175             :  * NB: We need a separate type for mutable iterations so that we can store
     176             :  * the 'next' node of the current node in case it gets deleted or modified.
     177             :  */
     178             : typedef struct dlist_mutable_iter
     179             : {
     180             :     dlist_node *cur;            /* current element */
     181             :     dlist_node *next;           /* next node we'll iterate to */
     182             :     dlist_node *end;            /* last node we'll iterate to */
     183             : } dlist_mutable_iter;
     184             : 
     185             : /*
     186             :  * Node of a singly linked list.
     187             :  *
     188             :  * Embed this in structs that need to be part of a singly linked list.
     189             :  */
     190             : typedef struct slist_node slist_node;
     191             : struct slist_node
     192             : {
     193             :     slist_node *next;
     194             : };
     195             : 
     196             : /*
     197             :  * Head of a singly linked list.
     198             :  *
     199             :  * Singly linked lists are not circularly linked, in contrast to doubly linked
     200             :  * lists; we just set head.next to NULL if empty.  This doesn't incur any
     201             :  * additional branches in the usual manipulations.
     202             :  */
     203             : typedef struct slist_head
     204             : {
     205             :     slist_node  head;
     206             : } slist_head;
     207             : 
     208             : /*
     209             :  * Singly linked list iterator.
     210             :  *
     211             :  * Used as state in slist_foreach(). To get the current element of the
     212             :  * iteration use the 'cur' member.
     213             :  *
     214             :  * It's allowed to modify the list while iterating, with the exception of
     215             :  * deleting the iterator's current node; deletion of that node requires
     216             :  * care if the iteration is to be continued afterward.  (Doing so and also
     217             :  * deleting or inserting adjacent list elements might misbehave; also, if
     218             :  * the user frees the current node's storage, continuing the iteration is
     219             :  * not safe.)
     220             :  *
     221             :  * NB: this wouldn't really need to be an extra struct, we could use an
     222             :  * slist_node * directly. We prefer a separate type for consistency.
     223             :  */
     224             : typedef struct slist_iter
     225             : {
     226             :     slist_node *cur;
     227             : } slist_iter;
     228             : 
     229             : /*
     230             :  * Singly linked list iterator allowing some modifications while iterating.
     231             :  *
     232             :  * Used as state in slist_foreach_modify(). To get the current element of the
     233             :  * iteration use the 'cur' member.
     234             :  *
     235             :  * The only list modification allowed while iterating is to remove the current
     236             :  * node via slist_delete_current() (*not* slist_delete()).  Insertion or
     237             :  * deletion of nodes adjacent to the current node would misbehave.
     238             :  */
     239             : typedef struct slist_mutable_iter
     240             : {
     241             :     slist_node *cur;            /* current element */
     242             :     slist_node *next;           /* next node we'll iterate to */
     243             :     slist_node *prev;           /* prev node, for deletions */
     244             : } slist_mutable_iter;
     245             : 
     246             : 
     247             : /* Static initializers */
     248             : #define DLIST_STATIC_INIT(name) {{&(name).head, &(name).head}}
     249             : #define SLIST_STATIC_INIT(name) {{NULL}}
     250             : 
     251             : 
     252             : /* Prototypes for functions too big to be inline */
     253             : 
     254             : /* Caution: this is O(n); consider using slist_delete_current() instead */
     255             : extern void slist_delete(slist_head *head, slist_node *node);
     256             : 
     257             : #ifdef ILIST_DEBUG
     258             : extern void dlist_check(dlist_head *head);
     259             : extern void slist_check(slist_head *head);
     260             : #else
     261             : /*
     262             :  * These seemingly useless casts to void are here to keep the compiler quiet
     263             :  * about the argument being unused in many functions in a non-debug compile,
     264             :  * in which functions the only point of passing the list head pointer is to be
     265             :  * able to run these checks.
     266             :  */
     267             : #define dlist_check(head)   ((void) (head))
     268             : #define slist_check(head)   ((void) (head))
     269             : #endif                          /* ILIST_DEBUG */
     270             : 
     271             : /* doubly linked list implementation */
     272             : 
     273             : /*
     274             :  * Initialize a doubly linked list.
     275             :  * Previous state will be thrown away without any cleanup.
     276             :  */
     277             : static inline void
     278     5027530 : dlist_init(dlist_head *head)
     279             : {
     280     5027530 :     head->head.next = head->head.prev = &head->head;
     281     5027530 : }
     282             : 
     283             : /*
     284             :  * Is the list empty?
     285             :  *
     286             :  * An empty list has either its first 'next' pointer set to NULL, or to itself.
     287             :  */
     288             : static inline bool
     289     4101952 : dlist_is_empty(dlist_head *head)
     290             : {
     291             :     dlist_check(head);
     292             : 
     293     4101952 :     return head->head.next == NULL || head->head.next == &(head->head);
     294             : }
     295             : 
     296             : /*
     297             :  * Insert a node at the beginning of the list.
     298             :  */
     299             : static inline void
     300    19842634 : dlist_push_head(dlist_head *head, dlist_node *node)
     301             : {
     302    19842634 :     if (head->head.next == NULL) /* convert NULL header to circular */
     303     3774416 :         dlist_init(head);
     304             : 
     305    19842634 :     node->next = head->head.next;
     306    19842634 :     node->prev = &head->head;
     307    19842634 :     node->next->prev = node;
     308    19842634 :     head->head.next = node;
     309             : 
     310             :     dlist_check(head);
     311    19842634 : }
     312             : 
     313             : /*
     314             :  * Insert a node at the end of the list.
     315             :  */
     316             : static inline void
     317     5839678 : dlist_push_tail(dlist_head *head, dlist_node *node)
     318             : {
     319     5839678 :     if (head->head.next == NULL) /* convert NULL header to circular */
     320         358 :         dlist_init(head);
     321             : 
     322     5839678 :     node->next = &head->head;
     323     5839678 :     node->prev = head->head.prev;
     324     5839678 :     node->prev->next = node;
     325     5839678 :     head->head.prev = node;
     326             : 
     327             :     dlist_check(head);
     328     5839678 : }
     329             : 
     330             : /*
     331             :  * Insert a node after another *in the same list*
     332             :  */
     333             : static inline void
     334        1440 : dlist_insert_after(dlist_node *after, dlist_node *node)
     335             : {
     336        1440 :     node->prev = after;
     337        1440 :     node->next = after->next;
     338        1440 :     after->next = node;
     339        1440 :     node->next->prev = node;
     340        1440 : }
     341             : 
     342             : /*
     343             :  * Insert a node before another *in the same list*
     344             :  */
     345             : static inline void
     346           0 : dlist_insert_before(dlist_node *before, dlist_node *node)
     347             : {
     348           0 :     node->prev = before->prev;
     349           0 :     node->next = before;
     350           0 :     before->prev = node;
     351           0 :     node->prev->next = node;
     352           0 : }
     353             : 
     354             : /*
     355             :  * Delete 'node' from its list (it must be in one).
     356             :  */
     357             : static inline void
     358    20276132 : dlist_delete(dlist_node *node)
     359             : {
     360    20276132 :     node->prev->next = node->next;
     361    20276132 :     node->next->prev = node->prev;
     362    20276132 : }
     363             : 
     364             : /*
     365             :  * Remove and return the first node from a list (there must be one).
     366             :  */
     367             : static inline dlist_node *
     368         162 : dlist_pop_head_node(dlist_head *head)
     369             : {
     370             :     dlist_node *node;
     371             : 
     372             :     Assert(!dlist_is_empty(head));
     373         162 :     node = head->head.next;
     374         162 :     dlist_delete(node);
     375         162 :     return node;
     376             : }
     377             : 
     378             : /*
     379             :  * Move element from its current position in the list to the head position in
     380             :  * the same list.
     381             :  *
     382             :  * Undefined behaviour if 'node' is not already part of the list.
     383             :  */
     384             : static inline void
     385   113024266 : dlist_move_head(dlist_head *head, dlist_node *node)
     386             : {
     387             :     /* fast path if it's already at the head */
     388   113024266 :     if (head->head.next == node)
     389   107541854 :         return;
     390             : 
     391     5482412 :     dlist_delete(node);
     392     5482412 :     dlist_push_head(head, node);
     393             : 
     394             :     dlist_check(head);
     395             : }
     396             : 
     397             : /*
     398             :  * Move element from its current position in the list to the tail position in
     399             :  * the same list.
     400             :  *
     401             :  * Undefined behaviour if 'node' is not already part of the list.
     402             :  */
     403             : static inline void
     404      230386 : dlist_move_tail(dlist_head *head, dlist_node *node)
     405             : {
     406             :     /* fast path if it's already at the tail */
     407      230386 :     if (head->head.prev == node)
     408      124838 :         return;
     409             : 
     410      105548 :     dlist_delete(node);
     411      105548 :     dlist_push_tail(head, node);
     412             : 
     413             :     dlist_check(head);
     414             : }
     415             : 
     416             : /*
     417             :  * Check whether 'node' has a following node.
     418             :  * Caution: unreliable if 'node' is not in the list.
     419             :  */
     420             : static inline bool
     421     2128554 : dlist_has_next(dlist_head *head, dlist_node *node)
     422             : {
     423     2128554 :     return node->next != &head->head;
     424             : }
     425             : 
     426             : /*
     427             :  * Check whether 'node' has a preceding node.
     428             :  * Caution: unreliable if 'node' is not in the list.
     429             :  */
     430             : static inline bool
     431         184 : dlist_has_prev(dlist_head *head, dlist_node *node)
     432             : {
     433         184 :     return node->prev != &head->head;
     434             : }
     435             : 
     436             : /*
     437             :  * Return the next node in the list (there must be one).
     438             :  */
     439             : static inline dlist_node *
     440     1999106 : dlist_next_node(dlist_head *head, dlist_node *node)
     441             : {
     442             :     Assert(dlist_has_next(head, node));
     443     1999106 :     return node->next;
     444             : }
     445             : 
     446             : /*
     447             :  * Return previous node in the list (there must be one).
     448             :  */
     449             : static inline dlist_node *
     450         274 : dlist_prev_node(dlist_head *head, dlist_node *node)
     451             : {
     452             :     Assert(dlist_has_prev(head, node));
     453         274 :     return node->prev;
     454             : }
     455             : 
     456             : /* internal support function to get address of head element's struct */
     457             : static inline void *
     458     3209878 : dlist_head_element_off(dlist_head *head, size_t off)
     459             : {
     460             :     Assert(!dlist_is_empty(head));
     461     3209878 :     return (char *) head->head.next - off;
     462             : }
     463             : 
     464             : /*
     465             :  * Return the first node in the list (there must be one).
     466             :  */
     467             : static inline dlist_node *
     468       42970 : dlist_head_node(dlist_head *head)
     469             : {
     470       42970 :     return (dlist_node *) dlist_head_element_off(head, 0);
     471             : }
     472             : 
     473             : /* internal support function to get address of tail element's struct */
     474             : static inline void *
     475       73564 : dlist_tail_element_off(dlist_head *head, size_t off)
     476             : {
     477             :     Assert(!dlist_is_empty(head));
     478       73564 :     return (char *) head->head.prev - off;
     479             : }
     480             : 
     481             : /*
     482             :  * Return the last node in the list (there must be one).
     483             :  */
     484             : static inline dlist_node *
     485       42840 : dlist_tail_node(dlist_head *head)
     486             : {
     487       42840 :     return (dlist_node *) dlist_tail_element_off(head, 0);
     488             : }
     489             : 
     490             : /*
     491             :  * Return the containing struct of 'type' where 'membername' is the dlist_node
     492             :  * pointed at by 'ptr'.
     493             :  *
     494             :  * This is used to convert a dlist_node * back to its containing struct.
     495             :  */
     496             : #define dlist_container(type, membername, ptr)                              \
     497             :     (AssertVariableIsOfTypeMacro(ptr, dlist_node *),                        \
     498             :      AssertVariableIsOfTypeMacro(((type *) NULL)->membername, dlist_node),   \
     499             :      ((type *) ((char *) (ptr) - offsetof(type, membername))))
     500             : 
     501             : /*
     502             :  * Return the address of the first element in the list.
     503             :  *
     504             :  * The list must not be empty.
     505             :  */
     506             : #define dlist_head_element(type, membername, lhead)                         \
     507             :     (AssertVariableIsOfTypeMacro(((type *) NULL)->membername, dlist_node),   \
     508             :      (type *) dlist_head_element_off(lhead, offsetof(type, membername)))
     509             : 
     510             : /*
     511             :  * Return the address of the last element in the list.
     512             :  *
     513             :  * The list must not be empty.
     514             :  */
     515             : #define dlist_tail_element(type, membername, lhead)                         \
     516             :     (AssertVariableIsOfTypeMacro(((type *) NULL)->membername, dlist_node),   \
     517             :      ((type *) dlist_tail_element_off(lhead, offsetof(type, membername))))
     518             : 
     519             : /*
     520             :  * Iterate through the list pointed at by 'lhead' storing the state in 'iter'.
     521             :  *
     522             :  * Access the current element with iter.cur.
     523             :  *
     524             :  * It is *not* allowed to manipulate the list during iteration.
     525             :  */
     526             : #define dlist_foreach(iter, lhead)                                          \
     527             :     for (AssertVariableIsOfTypeMacro(iter, dlist_iter),                     \
     528             :          AssertVariableIsOfTypeMacro(lhead, dlist_head *),                  \
     529             :          (iter).end = &(lhead)->head,                                        \
     530             :          (iter).cur = (iter).end->next ? (iter).end->next : (iter).end;       \
     531             :          (iter).cur != (iter).end;                                          \
     532             :          (iter).cur = (iter).cur->next)
     533             : 
     534             : /*
     535             :  * Iterate through the list pointed at by 'lhead' storing the state in 'iter'.
     536             :  *
     537             :  * Access the current element with iter.cur.
     538             :  *
     539             :  * Iterations using this are only allowed to change the list at the current
     540             :  * point of iteration. It is fine to delete the current node, but it is *not*
     541             :  * fine to insert or delete adjacent nodes.
     542             :  */
     543             : #define dlist_foreach_modify(iter, lhead)                                   \
     544             :     for (AssertVariableIsOfTypeMacro(iter, dlist_mutable_iter),             \
     545             :          AssertVariableIsOfTypeMacro(lhead, dlist_head *),                  \
     546             :          (iter).end = &(lhead)->head,                                        \
     547             :          (iter).cur = (iter).end->next ? (iter).end->next : (iter).end,       \
     548             :          (iter).next = (iter).cur->next;                                 \
     549             :          (iter).cur != (iter).end;                                          \
     550             :          (iter).cur = (iter).next, (iter).next = (iter).cur->next)
     551             : 
     552             : /*
     553             :  * Iterate through the list in reverse order.
     554             :  *
     555             :  * It is *not* allowed to manipulate the list during iteration.
     556             :  */
     557             : #define dlist_reverse_foreach(iter, lhead)                                  \
     558             :     for (AssertVariableIsOfTypeMacro(iter, dlist_iter),                     \
     559             :          AssertVariableIsOfTypeMacro(lhead, dlist_head *),                  \
     560             :          (iter).end = &(lhead)->head,                                        \
     561             :          (iter).cur = (iter).end->prev ? (iter).end->prev : (iter).end;       \
     562             :          (iter).cur != (iter).end;                                          \
     563             :          (iter).cur = (iter).cur->prev)
     564             : 
     565             : 
     566             : /* singly linked list implementation */
     567             : 
     568             : /*
     569             :  * Initialize a singly linked list.
     570             :  * Previous state will be thrown away without any cleanup.
     571             :  */
     572             : static inline void
     573       83280 : slist_init(slist_head *head)
     574             : {
     575       83280 :     head->head.next = NULL;
     576       83280 : }
     577             : 
     578             : /*
     579             :  * Is the list empty?
     580             :  */
     581             : static inline bool
     582       15084 : slist_is_empty(slist_head *head)
     583             : {
     584             :     slist_check(head);
     585             : 
     586       15084 :     return head->head.next == NULL;
     587             : }
     588             : 
     589             : /*
     590             :  * Insert a node at the beginning of the list.
     591             :  */
     592             : static inline void
     593     1363304 : slist_push_head(slist_head *head, slist_node *node)
     594             : {
     595     1363304 :     node->next = head->head.next;
     596     1363304 :     head->head.next = node;
     597             : 
     598             :     slist_check(head);
     599     1363304 : }
     600             : 
     601             : /*
     602             :  * Insert a node after another *in the same list*
     603             :  */
     604             : static inline void
     605             : slist_insert_after(slist_node *after, slist_node *node)
     606             : {
     607             :     node->next = after->next;
     608             :     after->next = node;
     609             : }
     610             : 
     611             : /*
     612             :  * Remove and return the first node from a list (there must be one).
     613             :  */
     614             : static inline slist_node *
     615        9510 : slist_pop_head_node(slist_head *head)
     616             : {
     617             :     slist_node *node;
     618             : 
     619             :     Assert(!slist_is_empty(head));
     620        9510 :     node = head->head.next;
     621        9510 :     head->head.next = node->next;
     622             :     slist_check(head);
     623        9510 :     return node;
     624             : }
     625             : 
     626             : /*
     627             :  * Check whether 'node' has a following node.
     628             :  */
     629             : static inline bool
     630             : slist_has_next(slist_head *head, slist_node *node)
     631             : {
     632             :     slist_check(head);
     633             : 
     634             :     return node->next != NULL;
     635             : }
     636             : 
     637             : /*
     638             :  * Return the next node in the list (there must be one).
     639             :  */
     640             : static inline slist_node *
     641             : slist_next_node(slist_head *head, slist_node *node)
     642             : {
     643             :     Assert(slist_has_next(head, node));
     644             :     return node->next;
     645             : }
     646             : 
     647             : /* internal support function to get address of head element's struct */
     648             : static inline void *
     649             : slist_head_element_off(slist_head *head, size_t off)
     650             : {
     651             :     Assert(!slist_is_empty(head));
     652             :     return (char *) head->head.next - off;
     653             : }
     654             : 
     655             : /*
     656             :  * Return the first node in the list (there must be one).
     657             :  */
     658             : static inline slist_node *
     659             : slist_head_node(slist_head *head)
     660             : {
     661             :     return (slist_node *) slist_head_element_off(head, 0);
     662             : }
     663             : 
     664             : /*
     665             :  * Delete the list element the iterator currently points to.
     666             :  *
     667             :  * Caution: this modifies iter->cur, so don't use that again in the current
     668             :  * loop iteration.
     669             :  */
     670             : static inline void
     671       57266 : slist_delete_current(slist_mutable_iter *iter)
     672             : {
     673             :     /*
     674             :      * Update previous element's forward link.  If the iteration is at the
     675             :      * first list element, iter->prev will point to the list header's "head"
     676             :      * field, so we don't need a special case for that.
     677             :      */
     678       57266 :     iter->prev->next = iter->next;
     679             : 
     680             :     /*
     681             :      * Reset cur to prev, so that prev will continue to point to the prior
     682             :      * valid list element after slist_foreach_modify() advances to the next.
     683             :      */
     684       57266 :     iter->cur = iter->prev;
     685       57266 : }
     686             : 
     687             : /*
     688             :  * Return the containing struct of 'type' where 'membername' is the slist_node
     689             :  * pointed at by 'ptr'.
     690             :  *
     691             :  * This is used to convert a slist_node * back to its containing struct.
     692             :  */
     693             : #define slist_container(type, membername, ptr)                              \
     694             :     (AssertVariableIsOfTypeMacro(ptr, slist_node *),                        \
     695             :      AssertVariableIsOfTypeMacro(((type *) NULL)->membername, slist_node),   \
     696             :      ((type *) ((char *) (ptr) - offsetof(type, membername))))
     697             : 
     698             : /*
     699             :  * Return the address of the first element in the list.
     700             :  *
     701             :  * The list must not be empty.
     702             :  */
     703             : #define slist_head_element(type, membername, lhead)                         \
     704             :     (AssertVariableIsOfTypeMacro(((type *) NULL)->membername, slist_node),   \
     705             :      (type *) slist_head_element_off(lhead, offsetof(type, membername)))
     706             : 
     707             : /*
     708             :  * Iterate through the list pointed at by 'lhead' storing the state in 'iter'.
     709             :  *
     710             :  * Access the current element with iter.cur.
     711             :  *
     712             :  * It's allowed to modify the list while iterating, with the exception of
     713             :  * deleting the iterator's current node; deletion of that node requires
     714             :  * care if the iteration is to be continued afterward.  (Doing so and also
     715             :  * deleting or inserting adjacent list elements might misbehave; also, if
     716             :  * the user frees the current node's storage, continuing the iteration is
     717             :  * not safe.)
     718             :  */
     719             : #define slist_foreach(iter, lhead)                                          \
     720             :     for (AssertVariableIsOfTypeMacro(iter, slist_iter),                     \
     721             :          AssertVariableIsOfTypeMacro(lhead, slist_head *),                  \
     722             :          (iter).cur = (lhead)->head.next;                                    \
     723             :          (iter).cur != NULL;                                                \
     724             :          (iter).cur = (iter).cur->next)
     725             : 
     726             : /*
     727             :  * Iterate through the list pointed at by 'lhead' storing the state in 'iter'.
     728             :  *
     729             :  * Access the current element with iter.cur.
     730             :  *
     731             :  * The only list modification allowed while iterating is to remove the current
     732             :  * node via slist_delete_current() (*not* slist_delete()).  Insertion or
     733             :  * deletion of nodes adjacent to the current node would misbehave.
     734             :  */
     735             : #define slist_foreach_modify(iter, lhead)                                   \
     736             :     for (AssertVariableIsOfTypeMacro(iter, slist_mutable_iter),             \
     737             :          AssertVariableIsOfTypeMacro(lhead, slist_head *),                  \
     738             :          (iter).prev = &(lhead)->head,                                       \
     739             :          (iter).cur = (iter).prev->next,                                 \
     740             :          (iter).next = (iter).cur ? (iter).cur->next : NULL;             \
     741             :          (iter).cur != NULL;                                                \
     742             :          (iter).prev = (iter).cur,                                          \
     743             :          (iter).cur = (iter).next,                                          \
     744             :          (iter).next = (iter).next ? (iter).next->next : NULL)
     745             : 
     746             : #endif                          /* ILIST_H */

Generated by: LCOV version 1.14