LCOV - code coverage report
Current view: top level - src/include/lib - ilist.h (source / functions) Hit Total Coverage
Test: PostgreSQL 17beta1 Lines: 129 142 90.8 %
Date: 2024-06-14 19:10:57 Functions: 36 39 92.3 %
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             :  * The doubly-linked list comes in 2 forms.  dlist_head defines a head of a
      14             :  * doubly-linked list of dlist_nodes, whereas dclist_head defines the head of
      15             :  * a doubly-linked list of dlist_nodes with an additional 'count' field to
      16             :  * keep track of how many items are contained within the given list.  For
      17             :  * simplicity, dlist_head and dclist_head share the same node and iterator
      18             :  * types.  The functions to manipulate a dlist_head always have a name
      19             :  * starting with "dlist", whereas functions to manipulate a dclist_head have a
      20             :  * name starting with "dclist".  dclist_head comes with an additional function
      21             :  * (dclist_count) to return the number of entries in the list.  dclists are
      22             :  * able to store a maximum of PG_UINT32_MAX elements.  It is up to the caller
      23             :  * to ensure no more than this many items are added to a dclist.
      24             :  *
      25             :  * None of the functions here allocate any memory; they just manipulate
      26             :  * externally managed memory.  With the exception doubly-linked count lists
      27             :  * providing the ability to obtain the number of items in the list, the APIs
      28             :  * for singly and both doubly linked lists are identical as far as
      29             :  * capabilities of both allow.
      30             :  *
      31             :  * Each list has a list header, which exists even when the list is empty.
      32             :  * An empty singly-linked list has a NULL pointer in its header.
      33             :  *
      34             :  * For both doubly-linked list types, there are two valid ways to represent an
      35             :  * empty list.  The head's 'next' pointer can either be NULL or the head's
      36             :  * 'next' and 'prev' links can both point back to the list head (circular).
      37             :  * (If a dlist is modified and then all its elements are deleted, it will be
      38             :  * in the circular state.).  We prefer circular dlists because there are some
      39             :  * operations that can be done without branches (and thus faster) on lists
      40             :  * that use circular representation.  However, it is often convenient to
      41             :  * initialize list headers to zeroes rather than setting them up with an
      42             :  * explicit initialization function, so we also allow the NULL initialization.
      43             :  *
      44             :  * EXAMPLES
      45             :  *
      46             :  * Here's a simple example demonstrating how this can be used.  Let's assume
      47             :  * we want to store information about the tables contained in a database.
      48             :  *
      49             :  * #include "lib/ilist.h"
      50             :  *
      51             :  * // Define struct for the databases including a list header that will be
      52             :  * // used to access the nodes in the table list later on.
      53             :  * typedef struct my_database
      54             :  * {
      55             :  *      char       *datname;
      56             :  *      dlist_head  tables;
      57             :  *      // ...
      58             :  * } my_database;
      59             :  *
      60             :  * // Define struct for the tables.  Note the list_node element which stores
      61             :  * // prev/next list links.  The list_node element need not be first.
      62             :  * typedef struct my_table
      63             :  * {
      64             :  *      char       *tablename;
      65             :  *      dlist_node  list_node;
      66             :  *      perm_t      permissions;
      67             :  *      // ...
      68             :  * } my_table;
      69             :  *
      70             :  * // create a database
      71             :  * my_database *db = create_database();
      72             :  *
      73             :  * // and add a few tables to its table list
      74             :  * dlist_push_head(&db->tables, &create_table(db, "a")->list_node);
      75             :  * ...
      76             :  * dlist_push_head(&db->tables, &create_table(db, "b")->list_node);
      77             :  *
      78             :  *
      79             :  * To iterate over the table list, we allocate an iterator variable and use
      80             :  * a specialized looping construct.  Inside a dlist_foreach, the iterator's
      81             :  * 'cur' field can be used to access the current element.  iter.cur points to
      82             :  * a 'dlist_node', but most of the time what we want is the actual table
      83             :  * information; dlist_container() gives us that, like so:
      84             :  *
      85             :  * dlist_iter   iter;
      86             :  * dlist_foreach(iter, &db->tables)
      87             :  * {
      88             :  *      my_table   *tbl = dlist_container(my_table, list_node, iter.cur);
      89             :  *      printf("we have a table: %s in database %s\n",
      90             :  *             tbl->tablename, db->datname);
      91             :  * }
      92             :  *
      93             :  *
      94             :  * While a simple iteration is useful, we sometimes also want to manipulate
      95             :  * the list while iterating.  There is a different iterator element and looping
      96             :  * construct for that.  Suppose we want to delete tables that meet a certain
      97             :  * criterion:
      98             :  *
      99             :  * dlist_mutable_iter miter;
     100             :  * dlist_foreach_modify(miter, &db->tables)
     101             :  * {
     102             :  *      my_table   *tbl = dlist_container(my_table, list_node, miter.cur);
     103             :  *
     104             :  *      if (!tbl->to_be_deleted)
     105             :  *          continue;       // don't touch this one
     106             :  *
     107             :  *      // unlink the current table from the linked list
     108             :  *      dlist_delete(miter.cur);
     109             :  *      // as these lists never manage memory, we can still access the table
     110             :  *      // after it's been unlinked
     111             :  *      drop_table(db, tbl);
     112             :  * }
     113             :  *
     114             :  *
     115             :  * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
     116             :  * Portions Copyright (c) 1994, Regents of the University of California
     117             :  *
     118             :  * IDENTIFICATION
     119             :  *      src/include/lib/ilist.h
     120             :  *-------------------------------------------------------------------------
     121             :  */
     122             : #ifndef ILIST_H
     123             : #define ILIST_H
     124             : 
     125             : /*
     126             :  * Enable for extra debugging. This is rather expensive, so it's not enabled by
     127             :  * default even when USE_ASSERT_CHECKING.
     128             :  */
     129             : /* #define ILIST_DEBUG */
     130             : 
     131             : /*
     132             :  * Node of a doubly linked list.
     133             :  *
     134             :  * Embed this in structs that need to be part of a doubly linked list.
     135             :  */
     136             : typedef struct dlist_node dlist_node;
     137             : struct dlist_node
     138             : {
     139             :     dlist_node *prev;
     140             :     dlist_node *next;
     141             : };
     142             : 
     143             : /*
     144             :  * Head of a doubly linked list.
     145             :  *
     146             :  * Non-empty lists are internally circularly linked.  Circular lists have the
     147             :  * advantage of not needing any branches in the most common list manipulations.
     148             :  * An empty list can also be represented as a pair of NULL pointers, making
     149             :  * initialization easier.
     150             :  */
     151             : typedef struct dlist_head
     152             : {
     153             :     /*
     154             :      * head.next either points to the first element of the list; to &head if
     155             :      * it's a circular empty list; or to NULL if empty and not circular.
     156             :      *
     157             :      * head.prev either points to the last element of the list; to &head if
     158             :      * it's a circular empty list; or to NULL if empty and not circular.
     159             :      */
     160             :     dlist_node  head;
     161             : } dlist_head;
     162             : 
     163             : 
     164             : /*
     165             :  * Doubly linked list iterator type for dlist_head and dclist_head types.
     166             :  *
     167             :  * Used as state in dlist_foreach() and dlist_reverse_foreach() (and the
     168             :  * dclist variant thereof).
     169             :  *
     170             :  * To get the current element of the iteration use the 'cur' member.
     171             :  *
     172             :  * Iterations using this are *not* allowed to change the list while iterating!
     173             :  *
     174             :  * NB: We use an extra "end" field here to avoid multiple evaluations of
     175             :  * arguments in the dlist_foreach() and dclist_foreach() macros.
     176             :  */
     177             : typedef struct dlist_iter
     178             : {
     179             :     dlist_node *cur;            /* current element */
     180             :     dlist_node *end;            /* last node we'll iterate to */
     181             : } dlist_iter;
     182             : 
     183             : /*
     184             :  * Doubly linked list iterator for both dlist_head and dclist_head types.
     185             :  * This iterator type allows some modifications while iterating.
     186             :  *
     187             :  * Used as state in dlist_foreach_modify() and dclist_foreach_modify().
     188             :  *
     189             :  * To get the current element of the iteration use the 'cur' member.
     190             :  *
     191             :  * Iterations using this are only allowed to change the list at the current
     192             :  * point of iteration. It is fine to delete the current node, but it is *not*
     193             :  * fine to insert or delete adjacent nodes.
     194             :  *
     195             :  * NB: We need a separate type for mutable iterations so that we can store
     196             :  * the 'next' node of the current node in case it gets deleted or modified.
     197             :  */
     198             : typedef struct dlist_mutable_iter
     199             : {
     200             :     dlist_node *cur;            /* current element */
     201             :     dlist_node *next;           /* next node we'll iterate to */
     202             :     dlist_node *end;            /* last node we'll iterate to */
     203             : } dlist_mutable_iter;
     204             : 
     205             : /*
     206             :  * Head of a doubly linked list with a count of the number of items
     207             :  *
     208             :  * This internally makes use of a dlist to implement the actual list.  When
     209             :  * items are added or removed from the list the count is updated to reflect
     210             :  * the current number of items in the list.
     211             :  */
     212             : typedef struct dclist_head
     213             : {
     214             :     dlist_head  dlist;          /* the actual list header */
     215             :     uint32      count;          /* the number of items in the list */
     216             : } dclist_head;
     217             : 
     218             : /*
     219             :  * Node of a singly linked list.
     220             :  *
     221             :  * Embed this in structs that need to be part of a singly linked list.
     222             :  */
     223             : typedef struct slist_node slist_node;
     224             : struct slist_node
     225             : {
     226             :     slist_node *next;
     227             : };
     228             : 
     229             : /*
     230             :  * Head of a singly linked list.
     231             :  *
     232             :  * Singly linked lists are not circularly linked, in contrast to doubly linked
     233             :  * lists; we just set head.next to NULL if empty.  This doesn't incur any
     234             :  * additional branches in the usual manipulations.
     235             :  */
     236             : typedef struct slist_head
     237             : {
     238             :     slist_node  head;
     239             : } slist_head;
     240             : 
     241             : /*
     242             :  * Singly linked list iterator.
     243             :  *
     244             :  * Used as state in slist_foreach(). To get the current element of the
     245             :  * iteration use the 'cur' member.
     246             :  *
     247             :  * It's allowed to modify the list while iterating, with the exception of
     248             :  * deleting the iterator's current node; deletion of that node requires
     249             :  * care if the iteration is to be continued afterward.  (Doing so and also
     250             :  * deleting or inserting adjacent list elements might misbehave; also, if
     251             :  * the user frees the current node's storage, continuing the iteration is
     252             :  * not safe.)
     253             :  *
     254             :  * NB: this wouldn't really need to be an extra struct, we could use an
     255             :  * slist_node * directly. We prefer a separate type for consistency.
     256             :  */
     257             : typedef struct slist_iter
     258             : {
     259             :     slist_node *cur;
     260             : } slist_iter;
     261             : 
     262             : /*
     263             :  * Singly linked list iterator allowing some modifications while iterating.
     264             :  *
     265             :  * Used as state in slist_foreach_modify(). To get the current element of the
     266             :  * iteration use the 'cur' member.
     267             :  *
     268             :  * The only list modification allowed while iterating is to remove the current
     269             :  * node via slist_delete_current() (*not* slist_delete()).  Insertion or
     270             :  * deletion of nodes adjacent to the current node would misbehave.
     271             :  */
     272             : typedef struct slist_mutable_iter
     273             : {
     274             :     slist_node *cur;            /* current element */
     275             :     slist_node *next;           /* next node we'll iterate to */
     276             :     slist_node *prev;           /* prev node, for deletions */
     277             : } slist_mutable_iter;
     278             : 
     279             : 
     280             : /* Static initializers */
     281             : #define DLIST_STATIC_INIT(name) {{&(name).head, &(name).head}}
     282             : #define DCLIST_STATIC_INIT(name) {{{&(name).dlist.head, &(name).dlist.head}}, 0}
     283             : #define SLIST_STATIC_INIT(name) {{NULL}}
     284             : 
     285             : 
     286             : /* Prototypes for functions too big to be inline */
     287             : 
     288             : /* Caution: this is O(n); consider using slist_delete_current() instead */
     289             : extern void slist_delete(slist_head *head, const slist_node *node);
     290             : 
     291             : #ifdef ILIST_DEBUG
     292             : extern void dlist_member_check(const dlist_head *head, const dlist_node *node);
     293             : extern void dlist_check(const dlist_head *head);
     294             : extern void slist_check(const slist_head *head);
     295             : #else
     296             : /*
     297             :  * These seemingly useless casts to void are here to keep the compiler quiet
     298             :  * about the argument being unused in many functions in a non-debug compile,
     299             :  * in which functions the only point of passing the list head pointer is to be
     300             :  * able to run these checks.
     301             :  */
     302             : #define dlist_member_check(head, node) ((void) (head))
     303             : #define dlist_check(head)   ((void) (head))
     304             : #define slist_check(head)   ((void) (head))
     305             : #endif                          /* ILIST_DEBUG */
     306             : 
     307             : /* doubly linked list implementation */
     308             : 
     309             : /*
     310             :  * Initialize a doubly linked list.
     311             :  * Previous state will be thrown away without any cleanup.
     312             :  */
     313             : static inline void
     314    14346844 : dlist_init(dlist_head *head)
     315             : {
     316    14346844 :     head->head.next = head->head.prev = &head->head;
     317    14346844 : }
     318             : 
     319             : /*
     320             :  * Initialize a doubly linked list element.
     321             :  *
     322             :  * This is only needed when dlist_node_is_detached() may be needed.
     323             :  */
     324             : static inline void
     325      461204 : dlist_node_init(dlist_node *node)
     326             : {
     327      461204 :     node->next = node->prev = NULL;
     328      461204 : }
     329             : 
     330             : /*
     331             :  * Is the list empty?
     332             :  *
     333             :  * An empty list has either its first 'next' pointer set to NULL, or to itself.
     334             :  */
     335             : static inline bool
     336    31477894 : dlist_is_empty(const dlist_head *head)
     337             : {
     338             :     dlist_check(head);
     339             : 
     340    31477894 :     return head->head.next == NULL || head->head.next == &(head->head);
     341             : }
     342             : 
     343             : /*
     344             :  * Insert a node at the beginning of the list.
     345             :  */
     346             : static inline void
     347     9067474 : dlist_push_head(dlist_head *head, dlist_node *node)
     348             : {
     349     9067474 :     if (head->head.next == NULL) /* convert NULL header to circular */
     350     3641876 :         dlist_init(head);
     351             : 
     352     9067474 :     node->next = head->head.next;
     353     9067474 :     node->prev = &head->head;
     354     9067474 :     node->next->prev = node;
     355     9067474 :     head->head.next = node;
     356             : 
     357             :     dlist_check(head);
     358     9067474 : }
     359             : 
     360             : /*
     361             :  * Insert a node at the end of the list.
     362             :  */
     363             : static inline void
     364    24754608 : dlist_push_tail(dlist_head *head, dlist_node *node)
     365             : {
     366    24754608 :     if (head->head.next == NULL) /* convert NULL header to circular */
     367        1830 :         dlist_init(head);
     368             : 
     369    24754608 :     node->next = &head->head;
     370    24754608 :     node->prev = head->head.prev;
     371    24754608 :     node->prev->next = node;
     372    24754608 :     head->head.prev = node;
     373             : 
     374             :     dlist_check(head);
     375    24754608 : }
     376             : 
     377             : /*
     378             :  * Insert a node after another *in the same list*
     379             :  */
     380             : static inline void
     381        1900 : dlist_insert_after(dlist_node *after, dlist_node *node)
     382             : {
     383        1900 :     node->prev = after;
     384        1900 :     node->next = after->next;
     385        1900 :     after->next = node;
     386        1900 :     node->next->prev = node;
     387        1900 : }
     388             : 
     389             : /*
     390             :  * Insert a node before another *in the same list*
     391             :  */
     392             : static inline void
     393           0 : dlist_insert_before(dlist_node *before, dlist_node *node)
     394             : {
     395           0 :     node->prev = before->prev;
     396           0 :     node->next = before;
     397           0 :     before->prev = node;
     398           0 :     node->prev->next = node;
     399           0 : }
     400             : 
     401             : /*
     402             :  * Delete 'node' from its list (it must be in one).
     403             :  */
     404             : static inline void
     405    18998498 : dlist_delete(dlist_node *node)
     406             : {
     407    18998498 :     node->prev->next = node->next;
     408    18998498 :     node->next->prev = node->prev;
     409    18998498 : }
     410             : 
     411             : /*
     412             :  * Like dlist_delete(), but also sets next/prev to NULL to signal not being in
     413             :  * a list.
     414             :  */
     415             : static inline void
     416        4660 : dlist_delete_thoroughly(dlist_node *node)
     417             : {
     418        4660 :     node->prev->next = node->next;
     419        4660 :     node->next->prev = node->prev;
     420        4660 :     node->next = NULL;
     421        4660 :     node->prev = NULL;
     422        4660 : }
     423             : 
     424             : /*
     425             :  * Same as dlist_delete, but performs checks in ILIST_DEBUG builds to ensure
     426             :  * that 'node' belongs to 'head'.
     427             :  */
     428             : static inline void
     429      441098 : dlist_delete_from(dlist_head *head, dlist_node *node)
     430             : {
     431             :     dlist_member_check(head, node);
     432      441098 :     dlist_delete(node);
     433      441098 : }
     434             : 
     435             : /*
     436             :  * Like dlist_delete_from, but also sets next/prev to NULL to signal not
     437             :  * being in a list.
     438             :  */
     439             : static inline void
     440        2186 : dlist_delete_from_thoroughly(dlist_head *head, dlist_node *node)
     441             : {
     442             :     dlist_member_check(head, node);
     443        2186 :     dlist_delete_thoroughly(node);
     444        2186 : }
     445             : 
     446             : /*
     447             :  * Remove and return the first node from a list (there must be one).
     448             :  */
     449             : static inline dlist_node *
     450       79996 : dlist_pop_head_node(dlist_head *head)
     451             : {
     452             :     dlist_node *node;
     453             : 
     454             :     Assert(!dlist_is_empty(head));
     455       79996 :     node = head->head.next;
     456       79996 :     dlist_delete(node);
     457       79996 :     return node;
     458             : }
     459             : 
     460             : /*
     461             :  * Move element from its current position in the list to the head position in
     462             :  * the same list.
     463             :  *
     464             :  * Undefined behaviour if 'node' is not already part of the list.
     465             :  */
     466             : static inline void
     467    70030426 : dlist_move_head(dlist_head *head, dlist_node *node)
     468             : {
     469             :     /* fast path if it's already at the head */
     470    70030426 :     if (head->head.next == node)
     471    68064344 :         return;
     472             : 
     473     1966082 :     dlist_delete(node);
     474     1966082 :     dlist_push_head(head, node);
     475             : 
     476             :     dlist_check(head);
     477             : }
     478             : 
     479             : /*
     480             :  * Move element from its current position in the list to the tail position in
     481             :  * the same list.
     482             :  *
     483             :  * Undefined behaviour if 'node' is not already part of the list.
     484             :  */
     485             : static inline void
     486      400140 : dlist_move_tail(dlist_head *head, dlist_node *node)
     487             : {
     488             :     /* fast path if it's already at the tail */
     489      400140 :     if (head->head.prev == node)
     490      224008 :         return;
     491             : 
     492      176132 :     dlist_delete(node);
     493      176132 :     dlist_push_tail(head, node);
     494             : 
     495             :     dlist_check(head);
     496             : }
     497             : 
     498             : /*
     499             :  * Check whether 'node' has a following node.
     500             :  * Caution: unreliable if 'node' is not in the list.
     501             :  */
     502             : static inline bool
     503     3769578 : dlist_has_next(const dlist_head *head, const dlist_node *node)
     504             : {
     505     3769578 :     return node->next != &head->head;
     506             : }
     507             : 
     508             : /*
     509             :  * Check whether 'node' has a preceding node.
     510             :  * Caution: unreliable if 'node' is not in the list.
     511             :  */
     512             : static inline bool
     513         260 : dlist_has_prev(const dlist_head *head, const dlist_node *node)
     514             : {
     515         260 :     return node->prev != &head->head;
     516             : }
     517             : 
     518             : /*
     519             :  * Check if node is detached. A node is only detached if it either has been
     520             :  * initialized with dlist_init_node(), or deleted with
     521             :  * dlist_delete_thoroughly() / dlist_delete_from_thoroughly() /
     522             :  * dclist_delete_from_thoroughly().
     523             :  */
     524             : static inline bool
     525       27872 : dlist_node_is_detached(const dlist_node *node)
     526             : {
     527             :     Assert((node->next == NULL && node->prev == NULL) ||
     528             :            (node->next != NULL && node->prev != NULL));
     529             : 
     530       27872 :     return node->next == NULL;
     531             : }
     532             : 
     533             : /*
     534             :  * Return the next node in the list (there must be one).
     535             :  */
     536             : static inline dlist_node *
     537     3569232 : dlist_next_node(dlist_head *head, dlist_node *node)
     538             : {
     539             :     Assert(dlist_has_next(head, node));
     540     3569232 :     return node->next;
     541             : }
     542             : 
     543             : /*
     544             :  * Return previous node in the list (there must be one).
     545             :  */
     546             : static inline dlist_node *
     547         352 : dlist_prev_node(dlist_head *head, dlist_node *node)
     548             : {
     549             :     Assert(dlist_has_prev(head, node));
     550         352 :     return node->prev;
     551             : }
     552             : 
     553             : /* internal support function to get address of head element's struct */
     554             : static inline void *
     555    26379926 : dlist_head_element_off(dlist_head *head, size_t off)
     556             : {
     557             :     Assert(!dlist_is_empty(head));
     558    26379926 :     return (char *) head->head.next - off;
     559             : }
     560             : 
     561             : /*
     562             :  * Return the first node in the list (there must be one).
     563             :  */
     564             : static inline dlist_node *
     565    22544138 : dlist_head_node(dlist_head *head)
     566             : {
     567    22544138 :     return (dlist_node *) dlist_head_element_off(head, 0);
     568             : }
     569             : 
     570             : /* internal support function to get address of tail element's struct */
     571             : static inline void *
     572     1349188 : dlist_tail_element_off(dlist_head *head, size_t off)
     573             : {
     574             :     Assert(!dlist_is_empty(head));
     575     1349188 :     return (char *) head->head.prev - off;
     576             : }
     577             : 
     578             : /*
     579             :  * Return the last node in the list (there must be one).
     580             :  */
     581             : static inline dlist_node *
     582       49556 : dlist_tail_node(dlist_head *head)
     583             : {
     584       49556 :     return (dlist_node *) dlist_tail_element_off(head, 0);
     585             : }
     586             : 
     587             : /*
     588             :  * Return the containing struct of 'type' where 'membername' is the dlist_node
     589             :  * pointed at by 'ptr'.
     590             :  *
     591             :  * This is used to convert a dlist_node * back to its containing struct.
     592             :  */
     593             : #define dlist_container(type, membername, ptr)                              \
     594             :     (AssertVariableIsOfTypeMacro(ptr, dlist_node *),                        \
     595             :      AssertVariableIsOfTypeMacro(((type *) NULL)->membername, dlist_node),   \
     596             :      ((type *) ((char *) (ptr) - offsetof(type, membername))))
     597             : 
     598             : /*
     599             :  * Return the address of the first element in the list.
     600             :  *
     601             :  * The list must not be empty.
     602             :  */
     603             : #define dlist_head_element(type, membername, lhead)                         \
     604             :     (AssertVariableIsOfTypeMacro(((type *) NULL)->membername, dlist_node),   \
     605             :      (type *) dlist_head_element_off(lhead, offsetof(type, membername)))
     606             : 
     607             : /*
     608             :  * Return the address of the last element in the list.
     609             :  *
     610             :  * The list must not be empty.
     611             :  */
     612             : #define dlist_tail_element(type, membername, lhead)                         \
     613             :     (AssertVariableIsOfTypeMacro(((type *) NULL)->membername, dlist_node),   \
     614             :      ((type *) dlist_tail_element_off(lhead, offsetof(type, membername))))
     615             : 
     616             : /*
     617             :  * Iterate through the list pointed at by 'lhead' storing the state in 'iter'.
     618             :  *
     619             :  * Access the current element with iter.cur.
     620             :  *
     621             :  * It is *not* allowed to manipulate the list during iteration.
     622             :  */
     623             : #define dlist_foreach(iter, lhead)                                          \
     624             :     for (AssertVariableIsOfTypeMacro(iter, dlist_iter),                     \
     625             :          AssertVariableIsOfTypeMacro(lhead, dlist_head *),                  \
     626             :          (iter).end = &(lhead)->head,                                        \
     627             :          (iter).cur = (iter).end->next ? (iter).end->next : (iter).end;       \
     628             :          (iter).cur != (iter).end;                                          \
     629             :          (iter).cur = (iter).cur->next)
     630             : 
     631             : /*
     632             :  * Iterate through the list pointed at by 'lhead' storing the state in 'iter'.
     633             :  *
     634             :  * Access the current element with iter.cur.
     635             :  *
     636             :  * Iterations using this are only allowed to change the list at the current
     637             :  * point of iteration. It is fine to delete the current node, but it is *not*
     638             :  * fine to insert or delete adjacent nodes.
     639             :  */
     640             : #define dlist_foreach_modify(iter, lhead)                                   \
     641             :     for (AssertVariableIsOfTypeMacro(iter, dlist_mutable_iter),             \
     642             :          AssertVariableIsOfTypeMacro(lhead, dlist_head *),                  \
     643             :          (iter).end = &(lhead)->head,                                        \
     644             :          (iter).cur = (iter).end->next ? (iter).end->next : (iter).end,       \
     645             :          (iter).next = (iter).cur->next;                                 \
     646             :          (iter).cur != (iter).end;                                          \
     647             :          (iter).cur = (iter).next, (iter).next = (iter).cur->next)
     648             : 
     649             : /*
     650             :  * Iterate through the list in reverse order.
     651             :  *
     652             :  * It is *not* allowed to manipulate the list during iteration.
     653             :  */
     654             : #define dlist_reverse_foreach(iter, lhead)                                  \
     655             :     for (AssertVariableIsOfTypeMacro(iter, dlist_iter),                     \
     656             :          AssertVariableIsOfTypeMacro(lhead, dlist_head *),                  \
     657             :          (iter).end = &(lhead)->head,                                        \
     658             :          (iter).cur = (iter).end->prev ? (iter).end->prev : (iter).end;       \
     659             :          (iter).cur != (iter).end;                                          \
     660             :          (iter).cur = (iter).cur->prev)
     661             : 
     662             : /* doubly-linked count list implementation */
     663             : 
     664             : /*
     665             :  * dclist_init
     666             :  *      Initialize a doubly linked count list.
     667             :  *
     668             :  * Previous state will be thrown away without any cleanup.
     669             :  */
     670             : static inline void
     671     4068700 : dclist_init(dclist_head *head)
     672             : {
     673     4068700 :     dlist_init(&head->dlist);
     674     4068700 :     head->count = 0;
     675     4068700 : }
     676             : 
     677             : /*
     678             :  * dclist_is_empty
     679             :  *      Returns true if the list is empty, otherwise false.
     680             :  */
     681             : static inline bool
     682        2682 : dclist_is_empty(const dclist_head *head)
     683             : {
     684             :     Assert(dlist_is_empty(&head->dlist) == (head->count == 0));
     685        2682 :     return (head->count == 0);
     686             : }
     687             : 
     688             : /*
     689             :  * dclist_push_head
     690             :  *      Insert a node at the beginning of the list.
     691             :  */
     692             : static inline void
     693       53214 : dclist_push_head(dclist_head *head, dlist_node *node)
     694             : {
     695       53214 :     if (head->dlist.head.next == NULL)   /* convert NULL header to circular */
     696           0 :         dclist_init(head);
     697             : 
     698       53214 :     dlist_push_head(&head->dlist, node);
     699       53214 :     head->count++;
     700             : 
     701             :     Assert(head->count > 0);  /* count overflow check */
     702       53214 : }
     703             : 
     704             : /*
     705             :  * dclist_push_tail
     706             :  *      Insert a node at the end of the list.
     707             :  */
     708             : static inline void
     709      211310 : dclist_push_tail(dclist_head *head, dlist_node *node)
     710             : {
     711      211310 :     if (head->dlist.head.next == NULL)   /* convert NULL header to circular */
     712         420 :         dclist_init(head);
     713             : 
     714      211310 :     dlist_push_tail(&head->dlist, node);
     715      211310 :     head->count++;
     716             : 
     717             :     Assert(head->count > 0);  /* count overflow check */
     718      211310 : }
     719             : 
     720             : /*
     721             :  * dclist_insert_after
     722             :  *      Insert a node after another *in the same list*
     723             :  *
     724             :  * Caution: 'after' must be a member of 'head'.
     725             :  */
     726             : static inline void
     727             : dclist_insert_after(dclist_head *head, dlist_node *after, dlist_node *node)
     728             : {
     729             :     dlist_member_check(&head->dlist, after);
     730             :     Assert(head->count > 0);  /* must be at least 1 already */
     731             : 
     732             :     dlist_insert_after(after, node);
     733             :     head->count++;
     734             : 
     735             :     Assert(head->count > 0);  /* count overflow check */
     736             : }
     737             : 
     738             : /*
     739             :  * dclist_insert_before
     740             :  *      Insert a node before another *in the same list*
     741             :  *
     742             :  * Caution: 'before' must be a member of 'head'.
     743             :  */
     744             : static inline void
     745           0 : dclist_insert_before(dclist_head *head, dlist_node *before, dlist_node *node)
     746             : {
     747             :     dlist_member_check(&head->dlist, before);
     748             :     Assert(head->count > 0);  /* must be at least 1 already */
     749             : 
     750           0 :     dlist_insert_before(before, node);
     751           0 :     head->count++;
     752             : 
     753             :     Assert(head->count > 0);  /* count overflow check */
     754           0 : }
     755             : 
     756             : /*
     757             :  * dclist_delete_from
     758             :  *      Deletes 'node' from 'head'.
     759             :  *
     760             :  * Caution: 'node' must be a member of 'head'.
     761             :  */
     762             : static inline void
     763      210044 : dclist_delete_from(dclist_head *head, dlist_node *node)
     764             : {
     765             :     Assert(head->count > 0);
     766             : 
     767      210044 :     dlist_delete_from(&head->dlist, node);
     768      210044 :     head->count--;
     769      210044 : }
     770             : 
     771             : /*
     772             :  * Like dclist_delete_from(), but also sets next/prev to NULL to signal not
     773             :  * being in a list.
     774             :  */
     775             : static inline void
     776        2186 : dclist_delete_from_thoroughly(dclist_head *head, dlist_node *node)
     777             : {
     778             :     Assert(head->count > 0);
     779             : 
     780        2186 :     dlist_delete_from_thoroughly(&head->dlist, node);
     781        2186 :     head->count--;
     782        2186 : }
     783             : 
     784             : /*
     785             :  * dclist_pop_head_node
     786             :  *      Remove and return the first node from a list (there must be one).
     787             :  */
     788             : static inline dlist_node *
     789       49070 : dclist_pop_head_node(dclist_head *head)
     790             : {
     791             :     dlist_node *node;
     792             : 
     793             :     Assert(head->count > 0);
     794             : 
     795       49070 :     node = dlist_pop_head_node(&head->dlist);
     796       49070 :     head->count--;
     797       49070 :     return node;
     798             : }
     799             : 
     800             : /*
     801             :  * dclist_move_head
     802             :  *      Move 'node' from its current position in the list to the head position
     803             :  *      in 'head'.
     804             :  *
     805             :  * Caution: 'node' must be a member of 'head'.
     806             :  */
     807             : static inline void
     808        5992 : dclist_move_head(dclist_head *head, dlist_node *node)
     809             : {
     810             :     dlist_member_check(&head->dlist, node);
     811             :     Assert(head->count > 0);
     812             : 
     813        5992 :     dlist_move_head(&head->dlist, node);
     814        5992 : }
     815             : 
     816             : /*
     817             :  * dclist_move_tail
     818             :  *      Move 'node' from its current position in the list to the tail position
     819             :  *      in 'head'.
     820             :  *
     821             :  * Caution: 'node' must be a member of 'head'.
     822             :  */
     823             : static inline void
     824             : dclist_move_tail(dclist_head *head, dlist_node *node)
     825             : {
     826             :     dlist_member_check(&head->dlist, node);
     827             :     Assert(head->count > 0);
     828             : 
     829             :     dlist_move_tail(&head->dlist, node);
     830             : }
     831             : 
     832             : /*
     833             :  * dclist_has_next
     834             :  *      Check whether 'node' has a following node.
     835             :  *
     836             :  * Caution: 'node' must be a member of 'head'.
     837             :  */
     838             : static inline bool
     839             : dclist_has_next(const dclist_head *head, const dlist_node *node)
     840             : {
     841             :     dlist_member_check(&head->dlist, node);
     842             :     Assert(head->count > 0);
     843             : 
     844             :     return dlist_has_next(&head->dlist, node);
     845             : }
     846             : 
     847             : /*
     848             :  * dclist_has_prev
     849             :  *      Check whether 'node' has a preceding node.
     850             :  *
     851             :  * Caution: 'node' must be a member of 'head'.
     852             :  */
     853             : static inline bool
     854             : dclist_has_prev(const dclist_head *head, const dlist_node *node)
     855             : {
     856             :     dlist_member_check(&head->dlist, node);
     857             :     Assert(head->count > 0);
     858             : 
     859             :     return dlist_has_prev(&head->dlist, node);
     860             : }
     861             : 
     862             : /*
     863             :  * dclist_next_node
     864             :  *      Return the next node in the list (there must be one).
     865             :  */
     866             : static inline dlist_node *
     867             : dclist_next_node(dclist_head *head, dlist_node *node)
     868             : {
     869             :     Assert(head->count > 0);
     870             : 
     871             :     return dlist_next_node(&head->dlist, node);
     872             : }
     873             : 
     874             : /*
     875             :  * dclist_prev_node
     876             :  *      Return the prev node in the list (there must be one).
     877             :  */
     878             : static inline dlist_node *
     879             : dclist_prev_node(dclist_head *head, dlist_node *node)
     880             : {
     881             :     Assert(head->count > 0);
     882             : 
     883             :     return dlist_prev_node(&head->dlist, node);
     884             : }
     885             : 
     886             : /* internal support function to get address of head element's struct */
     887             : static inline void *
     888             : dclist_head_element_off(dclist_head *head, size_t off)
     889             : {
     890             :     Assert(!dclist_is_empty(head));
     891             : 
     892             :     return (char *) head->dlist.head.next - off;
     893             : }
     894             : 
     895             : /*
     896             :  * dclist_head_node
     897             :  *      Return the first node in the list (there must be one).
     898             :  */
     899             : static inline dlist_node *
     900             : dclist_head_node(dclist_head *head)
     901             : {
     902             :     Assert(head->count > 0);
     903             : 
     904             :     return (dlist_node *) dlist_head_element_off(&head->dlist, 0);
     905             : }
     906             : 
     907             : /* internal support function to get address of tail element's struct */
     908             : static inline void *
     909             : dclist_tail_element_off(dclist_head *head, size_t off)
     910             : {
     911             :     Assert(!dclist_is_empty(head));
     912             : 
     913             :     return (char *) head->dlist.head.prev - off;
     914             : }
     915             : 
     916             : /*
     917             :  * Return the last node in the list (there must be one).
     918             :  */
     919             : static inline dlist_node *
     920           0 : dclist_tail_node(dclist_head *head)
     921             : {
     922             :     Assert(head->count > 0);
     923             : 
     924           0 :     return (dlist_node *) dlist_tail_element_off(&head->dlist, 0);
     925             : }
     926             : 
     927             : /*
     928             :  * dclist_count
     929             :  *      Returns the stored number of entries in 'head'
     930             :  */
     931             : static inline uint32
     932      622752 : dclist_count(const dclist_head *head)
     933             : {
     934             :     Assert(dlist_is_empty(&head->dlist) == (head->count == 0));
     935             : 
     936      622752 :     return head->count;
     937             : }
     938             : 
     939             : /*
     940             :  * Return the containing struct of 'type' where 'membername' is the dlist_node
     941             :  * pointed at by 'ptr'.
     942             :  *
     943             :  * This is used to convert a dlist_node * back to its containing struct.
     944             :  *
     945             :  * Note: This is effectively just the same as dlist_container, so reuse that.
     946             :  */
     947             : #define dclist_container(type, membername, ptr) \
     948             :         dlist_container(type, membername, ptr)
     949             : 
     950             :  /*
     951             :   * Return the address of the first element in the list.
     952             :   *
     953             :   * The list must not be empty.
     954             :   */
     955             : #define dclist_head_element(type, membername, lhead)                            \
     956             :     (AssertVariableIsOfTypeMacro(((type *) NULL)->membername, dlist_node),   \
     957             :      (type *) dclist_head_element_off(lhead, offsetof(type, membername)))
     958             : 
     959             :  /*
     960             :   * Return the address of the last element in the list.
     961             :   *
     962             :   * The list must not be empty.
     963             :   */
     964             : #define dclist_tail_element(type, membername, lhead)                            \
     965             :     (AssertVariableIsOfTypeMacro(((type *) NULL)->membername, dlist_node),   \
     966             :      ((type *) dclist_tail_element_off(lhead, offsetof(type, membername))))
     967             : 
     968             : 
     969             : /* Iterators for dclists */
     970             : #define dclist_foreach(iter, lhead) \
     971             :     dlist_foreach(iter, &((lhead)->dlist))
     972             : 
     973             : #define dclist_foreach_modify(iter, lhead) \
     974             :     dlist_foreach_modify(iter, &((lhead)->dlist))
     975             : 
     976             : #define dclist_reverse_foreach(iter, lhead) \
     977             :     dlist_reverse_foreach(iter, &((lhead)->dlist))
     978             : 
     979             : /* singly linked list implementation */
     980             : 
     981             : /*
     982             :  * Initialize a singly linked list.
     983             :  * Previous state will be thrown away without any cleanup.
     984             :  */
     985             : static inline void
     986      163464 : slist_init(slist_head *head)
     987             : {
     988      163464 :     head->head.next = NULL;
     989      163464 : }
     990             : 
     991             : /*
     992             :  * Is the list empty?
     993             :  */
     994             : static inline bool
     995       52772 : slist_is_empty(const slist_head *head)
     996             : {
     997             :     slist_check(head);
     998             : 
     999       52772 :     return head->head.next == NULL;
    1000             : }
    1001             : 
    1002             : /*
    1003             :  * Insert a node at the beginning of the list.
    1004             :  */
    1005             : static inline void
    1006     2607358 : slist_push_head(slist_head *head, slist_node *node)
    1007             : {
    1008     2607358 :     node->next = head->head.next;
    1009     2607358 :     head->head.next = node;
    1010             : 
    1011             :     slist_check(head);
    1012     2607358 : }
    1013             : 
    1014             : /*
    1015             :  * Insert a node after another *in the same list*
    1016             :  */
    1017             : static inline void
    1018             : slist_insert_after(slist_node *after, slist_node *node)
    1019             : {
    1020             :     node->next = after->next;
    1021             :     after->next = node;
    1022             : }
    1023             : 
    1024             : /*
    1025             :  * Remove and return the first node from a list (there must be one).
    1026             :  */
    1027             : static inline slist_node *
    1028       15254 : slist_pop_head_node(slist_head *head)
    1029             : {
    1030             :     slist_node *node;
    1031             : 
    1032             :     Assert(!slist_is_empty(head));
    1033       15254 :     node = head->head.next;
    1034       15254 :     head->head.next = node->next;
    1035             :     slist_check(head);
    1036       15254 :     return node;
    1037             : }
    1038             : 
    1039             : /*
    1040             :  * Check whether 'node' has a following node.
    1041             :  */
    1042             : static inline bool
    1043             : slist_has_next(const slist_head *head, const slist_node *node)
    1044             : {
    1045             :     slist_check(head);
    1046             : 
    1047             :     return node->next != NULL;
    1048             : }
    1049             : 
    1050             : /*
    1051             :  * Return the next node in the list (there must be one).
    1052             :  */
    1053             : static inline slist_node *
    1054             : slist_next_node(slist_head *head, slist_node *node)
    1055             : {
    1056             :     Assert(slist_has_next(head, node));
    1057             :     return node->next;
    1058             : }
    1059             : 
    1060             : /* internal support function to get address of head element's struct */
    1061             : static inline void *
    1062             : slist_head_element_off(slist_head *head, size_t off)
    1063             : {
    1064             :     Assert(!slist_is_empty(head));
    1065             :     return (char *) head->head.next - off;
    1066             : }
    1067             : 
    1068             : /*
    1069             :  * Return the first node in the list (there must be one).
    1070             :  */
    1071             : static inline slist_node *
    1072             : slist_head_node(slist_head *head)
    1073             : {
    1074             :     return (slist_node *) slist_head_element_off(head, 0);
    1075             : }
    1076             : 
    1077             : /*
    1078             :  * Delete the list element the iterator currently points to.
    1079             :  *
    1080             :  * Caution: this modifies iter->cur, so don't use that again in the current
    1081             :  * loop iteration.
    1082             :  */
    1083             : static inline void
    1084      440514 : slist_delete_current(slist_mutable_iter *iter)
    1085             : {
    1086             :     /*
    1087             :      * Update previous element's forward link.  If the iteration is at the
    1088             :      * first list element, iter->prev will point to the list header's "head"
    1089             :      * field, so we don't need a special case for that.
    1090             :      */
    1091      440514 :     iter->prev->next = iter->next;
    1092             : 
    1093             :     /*
    1094             :      * Reset cur to prev, so that prev will continue to point to the prior
    1095             :      * valid list element after slist_foreach_modify() advances to the next.
    1096             :      */
    1097      440514 :     iter->cur = iter->prev;
    1098      440514 : }
    1099             : 
    1100             : /*
    1101             :  * Return the containing struct of 'type' where 'membername' is the slist_node
    1102             :  * pointed at by 'ptr'.
    1103             :  *
    1104             :  * This is used to convert a slist_node * back to its containing struct.
    1105             :  */
    1106             : #define slist_container(type, membername, ptr)                              \
    1107             :     (AssertVariableIsOfTypeMacro(ptr, slist_node *),                        \
    1108             :      AssertVariableIsOfTypeMacro(((type *) NULL)->membername, slist_node),   \
    1109             :      ((type *) ((char *) (ptr) - offsetof(type, membername))))
    1110             : 
    1111             : /*
    1112             :  * Return the address of the first element in the list.
    1113             :  *
    1114             :  * The list must not be empty.
    1115             :  */
    1116             : #define slist_head_element(type, membername, lhead)                         \
    1117             :     (AssertVariableIsOfTypeMacro(((type *) NULL)->membername, slist_node),   \
    1118             :      (type *) slist_head_element_off(lhead, offsetof(type, membername)))
    1119             : 
    1120             : /*
    1121             :  * Iterate through the list pointed at by 'lhead' storing the state in 'iter'.
    1122             :  *
    1123             :  * Access the current element with iter.cur.
    1124             :  *
    1125             :  * It's allowed to modify the list while iterating, with the exception of
    1126             :  * deleting the iterator's current node; deletion of that node requires
    1127             :  * care if the iteration is to be continued afterward.  (Doing so and also
    1128             :  * deleting or inserting adjacent list elements might misbehave; also, if
    1129             :  * the user frees the current node's storage, continuing the iteration is
    1130             :  * not safe.)
    1131             :  */
    1132             : #define slist_foreach(iter, lhead)                                          \
    1133             :     for (AssertVariableIsOfTypeMacro(iter, slist_iter),                     \
    1134             :          AssertVariableIsOfTypeMacro(lhead, slist_head *),                  \
    1135             :          (iter).cur = (lhead)->head.next;                                    \
    1136             :          (iter).cur != NULL;                                                \
    1137             :          (iter).cur = (iter).cur->next)
    1138             : 
    1139             : /*
    1140             :  * Iterate through the list pointed at by 'lhead' storing the state in 'iter'.
    1141             :  *
    1142             :  * Access the current element with iter.cur.
    1143             :  *
    1144             :  * The only list modification allowed while iterating is to remove the current
    1145             :  * node via slist_delete_current() (*not* slist_delete()).  Insertion or
    1146             :  * deletion of nodes adjacent to the current node would misbehave.
    1147             :  */
    1148             : #define slist_foreach_modify(iter, lhead)                                   \
    1149             :     for (AssertVariableIsOfTypeMacro(iter, slist_mutable_iter),             \
    1150             :          AssertVariableIsOfTypeMacro(lhead, slist_head *),                  \
    1151             :          (iter).prev = &(lhead)->head,                                       \
    1152             :          (iter).cur = (iter).prev->next,                                 \
    1153             :          (iter).next = (iter).cur ? (iter).cur->next : NULL;             \
    1154             :          (iter).cur != NULL;                                                \
    1155             :          (iter).prev = (iter).cur,                                          \
    1156             :          (iter).cur = (iter).next,                                          \
    1157             :          (iter).next = (iter).next ? (iter).next->next : NULL)
    1158             : 
    1159             : #endif                          /* ILIST_H */

Generated by: LCOV version 1.14