codekingpro/portable-devtools

1/*-------------------------------------------------------------------------2 *3 * ilist.h4 *		integrated/inline doubly- and singly-linked lists5 *6 * These list types are useful when there are only a predetermined set of7 * lists that an object could be in.  List links are embedded directly into8 * 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 a14 * doubly-linked list of dlist_nodes, whereas dclist_head defines the head of15 * a doubly-linked list of dlist_nodes with an additional 'count' field to16 * keep track of how many items are contained within the given list.  For17 * simplicity, dlist_head and dclist_head share the same node and iterator18 * types.  The functions to manipulate a dlist_head always have a name19 * starting with "dlist", whereas functions to manipulate a dclist_head have a20 * name starting with "dclist".  dclist_head comes with an additional function21 * (dclist_count) to return the number of entries in the list.  dclists are22 * able to store a maximum of PG_UINT32_MAX elements.  It is up to the caller23 * 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 manipulate26 * externally managed memory.  With the exception doubly-linked count lists27 * providing the ability to obtain the number of items in the list, the APIs28 * for singly and both doubly linked lists are identical as far as29 * 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 an35 * empty list.  The head's 'next' pointer can either be NULL or the head's36 * '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 be38 * in the circular state.).  We prefer circular dlists because there are some39 * operations that can be done without branches (and thus faster) on lists40 * that use circular representation.  However, it is often convenient to41 * initialize list headers to zeroes rather than setting them up with an42 * explicit initialization function, so we also allow the NULL initialization.43 *44 * EXAMPLES45 *46 * Here's a simple example demonstrating how this can be used.  Let's assume47 * 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 be52 * // used to access the nodes in the table list later on.53 * typedef struct my_database54 * {55 *		char	   *datname;56 *		dlist_head	tables;57 *		// ...58 * } my_database;59 *60 * // Define struct for the tables.  Note the list_node element which stores61 * // prev/next list links.  The list_node element need not be first.62 * typedef struct my_table63 * {64 *		char	   *tablename;65 *		dlist_node	list_node;66 *		perm_t		permissions;67 *		// ...68 * } my_table;69 *70 * // create a database71 * my_database *db = create_database();72 *73 * // and add a few tables to its table list74 * 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 use80 * a specialized looping construct.  Inside a dlist_foreach, the iterator's81 * 'cur' field can be used to access the current element.  iter.cur points to82 * a 'dlist_node', but most of the time what we want is the actual table83 * 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 manipulate95 * the list while iterating.  There is a different iterator element and looping96 * construct for that.  Suppose we want to delete tables that meet a certain97 * 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 one106 *107 *		// unlink the current table from the linked list108 *		dlist_delete(miter.cur);109 *		// as these lists never manage memory, we can still access the table110 *		// after it's been unlinked111 *		drop_table(db, tbl);112 * }113 *114 *115 * Portions Copyright (c) 1996-2023, PostgreSQL Global Development Group116 * Portions Copyright (c) 1994, Regents of the University of California117 *118 * IDENTIFICATION119 *		src/include/lib/ilist.h120 *-------------------------------------------------------------------------121 */122#ifndef ILIST_H123#define ILIST_H124 125/*126 * Enable for extra debugging. This is rather expensive, so it's not enabled by127 * 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 */136typedef struct dlist_node dlist_node;137struct dlist_node138{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 the147 * 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, making149 * initialization easier.150 */151typedef struct dlist_head152{153	/*154	 * head.next either points to the first element of the list; to &head if155	 * 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 if158	 * 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 the168 * 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 of175 * arguments in the dlist_foreach() and dclist_foreach() macros.176 */177typedef struct dlist_iter178{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 current192 * 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 store196 * the 'next' node of the current node in case it gets deleted or modified.197 */198typedef struct dlist_mutable_iter199{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 items207 *208 * This internally makes use of a dlist to implement the actual list.  When209 * items are added or removed from the list the count is updated to reflect210 * the current number of items in the list.211 */212typedef struct dclist_head213{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 */223typedef struct slist_node slist_node;224struct slist_node225{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 linked233 * lists; we just set head.next to NULL if empty.  This doesn't incur any234 * additional branches in the usual manipulations.235 */236typedef struct slist_head237{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 the245 * iteration use the 'cur' member.246 *247 * It's allowed to modify the list while iterating, with the exception of248 * deleting the iterator's current node; deletion of that node requires249 * care if the iteration is to be continued afterward.  (Doing so and also250 * deleting or inserting adjacent list elements might misbehave; also, if251 * the user frees the current node's storage, continuing the iteration is252 * not safe.)253 *254 * NB: this wouldn't really need to be an extra struct, we could use an255 * slist_node * directly. We prefer a separate type for consistency.256 */257typedef struct slist_iter258{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 the266 * iteration use the 'cur' member.267 *268 * The only list modification allowed while iterating is to remove the current269 * node via slist_delete_current() (*not* slist_delete()).  Insertion or270 * deletion of nodes adjacent to the current node would misbehave.271 */272typedef struct slist_mutable_iter273{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 */289extern void slist_delete(slist_head *head, const slist_node *node);290 291#ifdef ILIST_DEBUG292extern void dlist_member_check(const dlist_head *head, const dlist_node *node);293extern void dlist_check(const dlist_head *head);294extern void slist_check(const slist_head *head);295#else296/*297 * These seemingly useless casts to void are here to keep the compiler quiet298 * 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 be300 * 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 */313static inline void314dlist_init(dlist_head *head)315{316	head->head.next = head->head.prev = &head->head;317}318 319/*320 * Initialize a doubly linked list element.321 *322 * This is only needed when dlist_node_is_detached() may be needed.323 */324static inline void325dlist_node_init(dlist_node *node)326{327	node->next = node->prev = NULL;328}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 */335static inline bool336dlist_is_empty(const dlist_head *head)337{338	dlist_check(head);339 340	return head->head.next == NULL || head->head.next == &(head->head);341}342 343/*344 * Insert a node at the beginning of the list.345 */346static inline void347dlist_push_head(dlist_head *head, dlist_node *node)348{349	if (head->head.next == NULL)	/* convert NULL header to circular */350		dlist_init(head);351 352	node->next = head->head.next;353	node->prev = &head->head;354	node->next->prev = node;355	head->head.next = node;356 357	dlist_check(head);358}359 360/*361 * Insert a node at the end of the list.362 */363static inline void364dlist_push_tail(dlist_head *head, dlist_node *node)365{366	if (head->head.next == NULL)	/* convert NULL header to circular */367		dlist_init(head);368 369	node->next = &head->head;370	node->prev = head->head.prev;371	node->prev->next = node;372	head->head.prev = node;373 374	dlist_check(head);375}376 377/*378 * Insert a node after another *in the same list*379 */380static inline void381dlist_insert_after(dlist_node *after, dlist_node *node)382{383	node->prev = after;384	node->next = after->next;385	after->next = node;386	node->next->prev = node;387}388 389/*390 * Insert a node before another *in the same list*391 */392static inline void393dlist_insert_before(dlist_node *before, dlist_node *node)394{395	node->prev = before->prev;396	node->next = before;397	before->prev = node;398	node->prev->next = node;399}400 401/*402 * Delete 'node' from its list (it must be in one).403 */404static inline void405dlist_delete(dlist_node *node)406{407	node->prev->next = node->next;408	node->next->prev = node->prev;409}410 411/*412 * Like dlist_delete(), but also sets next/prev to NULL to signal not being in413 * a list.414 */415static inline void416dlist_delete_thoroughly(dlist_node *node)417{418	node->prev->next = node->next;419	node->next->prev = node->prev;420	node->next = NULL;421	node->prev = NULL;422}423 424/*425 * Same as dlist_delete, but performs checks in ILIST_DEBUG builds to ensure426 * that 'node' belongs to 'head'.427 */428static inline void429dlist_delete_from(dlist_head *head, dlist_node *node)430{431	dlist_member_check(head, node);432	dlist_delete(node);433}434 435/*436 * Like dlist_delete_from, but also sets next/prev to NULL to signal not437 * being in a list.438 */439static inline void440dlist_delete_from_thoroughly(dlist_head *head, dlist_node *node)441{442	dlist_member_check(head, node);443	dlist_delete_thoroughly(node);444}445 446/*447 * Remove and return the first node from a list (there must be one).448 */449static inline dlist_node *450dlist_pop_head_node(dlist_head *head)451{452	dlist_node *node;453 454	Assert(!dlist_is_empty(head));455	node = head->head.next;456	dlist_delete(node);457	return node;458}459 460/*461 * Move element from its current position in the list to the head position in462 * the same list.463 *464 * Undefined behaviour if 'node' is not already part of the list.465 */466static inline void467dlist_move_head(dlist_head *head, dlist_node *node)468{469	/* fast path if it's already at the head */470	if (head->head.next == node)471		return;472 473	dlist_delete(node);474	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 in481 * the same list.482 *483 * Undefined behaviour if 'node' is not already part of the list.484 */485static inline void486dlist_move_tail(dlist_head *head, dlist_node *node)487{488	/* fast path if it's already at the tail */489	if (head->head.prev == node)490		return;491 492	dlist_delete(node);493	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 */502static inline bool503dlist_has_next(const dlist_head *head, const dlist_node *node)504{505	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 */512static inline bool513dlist_has_prev(const dlist_head *head, const dlist_node *node)514{515	return node->prev != &head->head;516}517 518/*519 * Check if node is detached. A node is only detached if it either has been520 * initialized with dlist_init_node(), or deleted with521 * dlist_delete_thoroughly() / dlist_delete_from_thoroughly() /522 * dclist_delete_from_thoroughly().523 */524static inline bool525dlist_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	return node->next == NULL;531}532 533/*534 * Return the next node in the list (there must be one).535 */536static inline dlist_node *537dlist_next_node(dlist_head *head, dlist_node *node)538{539	Assert(dlist_has_next(head, node));540	return node->next;541}542 543/*544 * Return previous node in the list (there must be one).545 */546static inline dlist_node *547dlist_prev_node(dlist_head *head, dlist_node *node)548{549	Assert(dlist_has_prev(head, node));550	return node->prev;551}552 553/* internal support function to get address of head element's struct */554static inline void *555dlist_head_element_off(dlist_head *head, size_t off)556{557	Assert(!dlist_is_empty(head));558	return (char *) head->head.next - off;559}560 561/*562 * Return the first node in the list (there must be one).563 */564static inline dlist_node *565dlist_head_node(dlist_head *head)566{567	return (dlist_node *) dlist_head_element_off(head, 0);568}569 570/* internal support function to get address of tail element's struct */571static inline void *572dlist_tail_element_off(dlist_head *head, size_t off)573{574	Assert(!dlist_is_empty(head));575	return (char *) head->head.prev - off;576}577 578/*579 * Return the last node in the list (there must be one).580 */581static inline dlist_node *582dlist_tail_node(dlist_head *head)583{584	return (dlist_node *) dlist_tail_element_off(head, 0);585}586 587/*588 * Return the containing struct of 'type' where 'membername' is the dlist_node589 * 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 current637 * 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_init666 *		Initialize a doubly linked count list.667 *668 * Previous state will be thrown away without any cleanup.669 */670static inline void671dclist_init(dclist_head *head)672{673	dlist_init(&head->dlist);674	head->count = 0;675}676 677/*678 * dclist_is_empty679 *		Returns true if the list is empty, otherwise false.680 */681static inline bool682dclist_is_empty(const dclist_head *head)683{684	Assert(dlist_is_empty(&head->dlist) == (head->count == 0));685	return (head->count == 0);686}687 688/*689 * dclist_push_head690 *		Insert a node at the beginning of the list.691 */692static inline void693dclist_push_head(dclist_head *head, dlist_node *node)694{695	if (head->dlist.head.next == NULL)	/* convert NULL header to circular */696		dclist_init(head);697 698	dlist_push_head(&head->dlist, node);699	head->count++;700 701	Assert(head->count > 0);	/* count overflow check */702}703 704/*705 * dclist_push_tail706 *		Insert a node at the end of the list.707 */708static inline void709dclist_push_tail(dclist_head *head, dlist_node *node)710{711	if (head->dlist.head.next == NULL)	/* convert NULL header to circular */712		dclist_init(head);713 714	dlist_push_tail(&head->dlist, node);715	head->count++;716 717	Assert(head->count > 0);	/* count overflow check */718}719 720/*721 * dclist_insert_after722 *		Insert a node after another *in the same list*723 *724 * Caution: 'after' must be a member of 'head'.725 */726static inline void727dclist_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_before740 *		Insert a node before another *in the same list*741 *742 * Caution: 'before' must be a member of 'head'.743 */744static inline void745dclist_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	dlist_insert_before(before, node);751	head->count++;752 753	Assert(head->count > 0);	/* count overflow check */754}755 756/*757 * dclist_delete_from758 *		Deletes 'node' from 'head'.759 *760 * Caution: 'node' must be a member of 'head'.761 */762static inline void763dclist_delete_from(dclist_head *head, dlist_node *node)764{765	Assert(head->count > 0);766 767	dlist_delete_from(&head->dlist, node);768	head->count--;769}770 771/*772 * Like dclist_delete_from(), but also sets next/prev to NULL to signal not773 * being in a list.774 */775static inline void776dclist_delete_from_thoroughly(dclist_head *head, dlist_node *node)777{778	Assert(head->count > 0);779 780	dlist_delete_from_thoroughly(&head->dlist, node);781	head->count--;782}783 784/*785 * dclist_pop_head_node786 *		Remove and return the first node from a list (there must be one).787 */788static inline dlist_node *789dclist_pop_head_node(dclist_head *head)790{791	dlist_node *node;792 793	Assert(head->count > 0);794 795	node = dlist_pop_head_node(&head->dlist);796	head->count--;797	return node;798}799 800/*801 * dclist_move_head802 *		Move 'node' from its current position in the list to the head position803 *		in 'head'.804 *805 * Caution: 'node' must be a member of 'head'.806 */807static inline void808dclist_move_head(dclist_head *head, dlist_node *node)809{810	dlist_member_check(&head->dlist, node);811	Assert(head->count > 0);812 813	dlist_move_head(&head->dlist, node);814}815 816/*817 * dclist_move_tail818 *		Move 'node' from its current position in the list to the tail position819 *		in 'head'.820 *821 * Caution: 'node' must be a member of 'head'.822 */823static inline void824dclist_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_next834 *		Check whether 'node' has a following node.835 *836 * Caution: 'node' must be a member of 'head'.837 */838static inline bool839dclist_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_prev849 *		Check whether 'node' has a preceding node.850 *851 * Caution: 'node' must be a member of 'head'.852 */853static inline bool854dclist_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_node864 *		Return the next node in the list (there must be one).865 */866static inline dlist_node *867dclist_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_node876 *		Return the prev node in the list (there must be one).877 */878static inline dlist_node *879dclist_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 */887static inline void *888dclist_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_node897 *		Return the first node in the list (there must be one).898 */899static inline dlist_node *900dclist_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 */908static inline void *909dclist_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 */919static inline dlist_node *920dclist_tail_node(dclist_head *head)921{922	Assert(head->count > 0);923 924	return (dlist_node *) dlist_tail_element_off(&head->dlist, 0);925}926 927/*928 * dclist_count929 *		Returns the stored number of entries in 'head'930 */931static inline uint32932dclist_count(const dclist_head *head)933{934	Assert(dlist_is_empty(&head->dlist) == (head->count == 0));935 936	return head->count;937}938 939/*940 * Return the containing struct of 'type' where 'membername' is the dlist_node941 * 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 */985static inline void986slist_init(slist_head *head)987{988	head->head.next = NULL;989}990 991/*992 * Is the list empty?993 */994static inline bool995slist_is_empty(const slist_head *head)996{997	slist_check(head);998 999	return head->head.next == NULL;1000}1001 1002/*1003 * Insert a node at the beginning of the list.1004 */1005static inline void1006slist_push_head(slist_head *head, slist_node *node)1007{1008	node->next = head->head.next;1009	head->head.next = node;1010 1011	slist_check(head);1012}1013 1014/*1015 * Insert a node after another *in the same list*1016 */1017static inline void1018slist_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 */1027static inline slist_node *1028slist_pop_head_node(slist_head *head)1029{1030	slist_node *node;1031 1032	Assert(!slist_is_empty(head));1033	node = head->head.next;1034	head->head.next = node->next;1035	slist_check(head);1036	return node;1037}1038 1039/*1040 * Check whether 'node' has a following node.1041 */1042static inline bool1043slist_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 */1053static inline slist_node *1054slist_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 */1061static inline void *1062slist_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 */1071static inline slist_node *1072slist_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 current1081 * loop iteration.1082 */1083static inline void1084slist_delete_current(slist_mutable_iter *iter)1085{1086	/*1087	 * Update previous element's forward link.  If the iteration is at the1088	 * 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	iter->prev->next = iter->next;1092 1093	/*1094	 * Reset cur to prev, so that prev will continue to point to the prior1095	 * valid list element after slist_foreach_modify() advances to the next.1096	 */1097	iter->cur = iter->prev;1098}1099 1100/*1101 * Return the containing struct of 'type' where 'membername' is the slist_node1102 * 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 of1126 * deleting the iterator's current node; deletion of that node requires1127 * care if the iteration is to be continued afterward.  (Doing so and also1128 * deleting or inserting adjacent list elements might misbehave; also, if1129 * the user frees the current node's storage, continuing the iteration is1130 * 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 current1145 * node via slist_delete_current() (*not* slist_delete()).  Insertion or1146 * 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 */1160