PostgreSQL Source Code  git master
ilist.h
Go to the documentation of this file.
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;
138 {
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  */
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 */
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 */
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 */
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;
225 {
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 {
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 {
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 */
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
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  */
324 static inline void
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  */
335 static inline bool
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  */
346 static inline void
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  */
363 static inline void
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  */
380 static inline void
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  */
392 static inline void
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  */
404 static inline void
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 in
413  * a list.
414  */
415 static inline void
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 ensure
426  * that 'node' belongs to 'head'.
427  */
428 static inline void
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 not
437  * being in a list.
438  */
439 static inline void
441 {
442  dlist_member_check(head, node);
444 }
445 
446 /*
447  * Remove and return the first node from a list (there must be one).
448  */
449 static inline dlist_node *
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 in
462  * the same list.
463  *
464  * Undefined behaviour if 'node' is not already part of the list.
465  */
466 static inline void
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 in
481  * the same list.
482  *
483  * Undefined behaviour if 'node' is not already part of the list.
484  */
485 static inline void
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  */
502 static inline bool
503 dlist_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  */
512 static inline bool
513 dlist_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 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
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  */
536 static inline dlist_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  */
546 static inline dlist_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 */
554 static inline void *
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  */
564 static inline dlist_node *
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 */
571 static inline void *
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  */
581 static inline dlist_node *
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_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
672 {
673  dlist_init(&head->dlist);
674  head->count = 0;
675 }
676 
677 /*
678  * dclist_is_empty
679  * Returns true if the list is empty, otherwise false.
680  */
681 static inline bool
683 {
684  Assert(dlist_is_empty(&head->dlist) == (head->count == 0));
685  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
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_tail
706  * Insert a node at the end of the list.
707  */
708 static inline void
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_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
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
746 {
748  Assert(head->count > 0); /* must be at least 1 already */
749 
751  head->count++;
752 
753  Assert(head->count > 0); /* count overflow check */
754 }
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
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 not
773  * being in a list.
774  */
775 static inline void
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_node
786  * Remove and return the first node from a list (there must be one).
787  */
788 static inline dlist_node *
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_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
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_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
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 *
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 *
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 *
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 *
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 *
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 *
921 {
922  Assert(head->count > 0);
923 
924  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
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_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
987 {
988  head->head.next = NULL;
989 }
990 
991 /*
992  * Is the list empty?
993  */
994 static inline bool
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  */
1005 static inline void
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  */
1017 static inline void
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 *
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  */
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 *
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 *
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 *
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
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  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  iter->cur = iter->prev;
1098 }
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 */
unsigned int uint32
Definition: c.h:493
static dlist_node * dlist_prev_node(dlist_head *head, dlist_node *node)
Definition: ilist.h:547
struct slist_iter slist_iter
static void slist_delete_current(slist_mutable_iter *iter)
Definition: ilist.h:1084
struct dlist_iter dlist_iter
static void dlist_delete_from_thoroughly(dlist_head *head, dlist_node *node)
Definition: ilist.h:440
static void dlist_insert_after(dlist_node *after, dlist_node *node)
Definition: ilist.h:381
static void * slist_head_element_off(slist_head *head, size_t off)
Definition: ilist.h:1062
static void * dclist_tail_element_off(dclist_head *head, size_t off)
Definition: ilist.h:909
static void dlist_init(dlist_head *head)
Definition: ilist.h:314
static void dlist_delete_from(dlist_head *head, dlist_node *node)
Definition: ilist.h:429
static bool dlist_has_next(const dlist_head *head, const dlist_node *node)
Definition: ilist.h:503
static void * dlist_tail_element_off(dlist_head *head, size_t off)
Definition: ilist.h:572
static bool dlist_has_prev(const dlist_head *head, const dlist_node *node)
Definition: ilist.h:513
void slist_delete(slist_head *head, const slist_node *node)
Definition: ilist.c:31
static void dclist_push_tail(dclist_head *head, dlist_node *node)
Definition: ilist.h:709
static void * dclist_head_element_off(dclist_head *head, size_t off)
Definition: ilist.h:888
static void dlist_insert_before(dlist_node *before, dlist_node *node)
Definition: ilist.h:393
static dlist_node * dclist_tail_node(dclist_head *head)
Definition: ilist.h:920
#define dlist_check(head)
Definition: ilist.h:303
static void dlist_delete_thoroughly(dlist_node *node)
Definition: ilist.h:416
static bool dclist_has_next(const dclist_head *head, const dlist_node *node)
Definition: ilist.h:839
static void dlist_delete(dlist_node *node)
Definition: ilist.h:405
static uint32 dclist_count(const dclist_head *head)
Definition: ilist.h:932
static bool dclist_is_empty(const dclist_head *head)
Definition: ilist.h:682
static void slist_init(slist_head *head)
Definition: ilist.h:986
static bool dlist_node_is_detached(const dlist_node *node)
Definition: ilist.h:525
static dlist_node * dlist_next_node(dlist_head *head, dlist_node *node)
Definition: ilist.h:537
static void dclist_move_head(dclist_head *head, dlist_node *node)
Definition: ilist.h:808
struct dlist_head dlist_head
static void * dlist_head_element_off(dlist_head *head, size_t off)
Definition: ilist.h:555
static dlist_node * dlist_pop_head_node(dlist_head *head)
Definition: ilist.h:450
static bool slist_is_empty(const slist_head *head)
Definition: ilist.h:995
static void dlist_push_head(dlist_head *head, dlist_node *node)
Definition: ilist.h:347
static bool dlist_is_empty(const dlist_head *head)
Definition: ilist.h:336
static void slist_insert_after(slist_node *after, slist_node *node)
Definition: ilist.h:1018
static void slist_push_head(slist_head *head, slist_node *node)
Definition: ilist.h:1006
static dlist_node * dclist_next_node(dclist_head *head, dlist_node *node)
Definition: ilist.h:867
struct slist_head slist_head
#define slist_check(head)
Definition: ilist.h:304
static void dlist_push_tail(dlist_head *head, dlist_node *node)
Definition: ilist.h:364
static void dclist_delete_from(dclist_head *head, dlist_node *node)
Definition: ilist.h:763
static slist_node * slist_next_node(slist_head *head, slist_node *node)
Definition: ilist.h:1054
struct dclist_head dclist_head
static void dclist_delete_from_thoroughly(dclist_head *head, dlist_node *node)
Definition: ilist.h:776
struct dlist_mutable_iter dlist_mutable_iter
static dlist_node * dclist_head_node(dclist_head *head)
Definition: ilist.h:900
static void dclist_push_head(dclist_head *head, dlist_node *node)
Definition: ilist.h:693
static void dclist_move_tail(dclist_head *head, dlist_node *node)
Definition: ilist.h:824
static void dclist_insert_before(dclist_head *head, dlist_node *before, dlist_node *node)
Definition: ilist.h:745
static void dclist_init(dclist_head *head)
Definition: ilist.h:671
static void dlist_move_head(dlist_head *head, dlist_node *node)
Definition: ilist.h:467
static bool slist_has_next(const slist_head *head, const slist_node *node)
Definition: ilist.h:1043
static bool dclist_has_prev(const dclist_head *head, const dlist_node *node)
Definition: ilist.h:854
static void dlist_node_init(dlist_node *node)
Definition: ilist.h:325
struct slist_mutable_iter slist_mutable_iter
static dlist_node * dlist_head_node(dlist_head *head)
Definition: ilist.h:565
static dlist_node * dclist_prev_node(dclist_head *head, dlist_node *node)
Definition: ilist.h:879
static void dlist_move_tail(dlist_head *head, dlist_node *node)
Definition: ilist.h:486
static slist_node * slist_head_node(slist_head *head)
Definition: ilist.h:1072
#define dlist_member_check(head, node)
Definition: ilist.h:302
static void dclist_insert_after(dclist_head *head, dlist_node *after, dlist_node *node)
Definition: ilist.h:727
static slist_node * slist_pop_head_node(slist_head *head)
Definition: ilist.h:1028
static dlist_node * dclist_pop_head_node(dclist_head *head)
Definition: ilist.h:789
static dlist_node * dlist_tail_node(dlist_head *head)
Definition: ilist.h:582
Assert(fmt[strlen(fmt) - 1] !='\n')
static int before(chr x, chr y)
Definition: regc_locale.c:488
uint32 count
Definition: ilist.h:215
dlist_head dlist
Definition: ilist.h:214
dlist_node head
Definition: ilist.h:160
dlist_node * cur
Definition: ilist.h:179
dlist_node * end
Definition: ilist.h:180
dlist_node * next
Definition: ilist.h:201
dlist_node * cur
Definition: ilist.h:200
dlist_node * end
Definition: ilist.h:202
dlist_node * next
Definition: ilist.h:140
dlist_node * prev
Definition: ilist.h:139
slist_node head
Definition: ilist.h:238
slist_node * cur
Definition: ilist.h:259
slist_node * next
Definition: ilist.h:275
slist_node * prev
Definition: ilist.h:276
slist_node * cur
Definition: ilist.h:274
slist_node * next
Definition: ilist.h:226