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 initalization.
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-2022, 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 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, slist_node *node);
290 
291 #ifdef ILIST_DEBUG
292 extern void dlist_member_check(dlist_head *head, dlist_node *node);
293 extern void dlist_check(dlist_head *head);
294 extern void slist_check(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  * Is the list empty?
321  *
322  * An empty list has either its first 'next' pointer set to NULL, or to itself.
323  */
324 static inline bool
326 {
327  dlist_check(head);
328 
329  return head->head.next == NULL || head->head.next == &(head->head);
330 }
331 
332 /*
333  * Insert a node at the beginning of the list.
334  */
335 static inline void
337 {
338  if (head->head.next == NULL) /* convert NULL header to circular */
339  dlist_init(head);
340 
341  node->next = head->head.next;
342  node->prev = &head->head;
343  node->next->prev = node;
344  head->head.next = node;
345 
346  dlist_check(head);
347 }
348 
349 /*
350  * Insert a node at the end of the list.
351  */
352 static inline void
354 {
355  if (head->head.next == NULL) /* convert NULL header to circular */
356  dlist_init(head);
357 
358  node->next = &head->head;
359  node->prev = head->head.prev;
360  node->prev->next = node;
361  head->head.prev = node;
362 
363  dlist_check(head);
364 }
365 
366 /*
367  * Insert a node after another *in the same list*
368  */
369 static inline void
371 {
372  node->prev = after;
373  node->next = after->next;
374  after->next = node;
375  node->next->prev = node;
376 }
377 
378 /*
379  * Insert a node before another *in the same list*
380  */
381 static inline void
383 {
384  node->prev = before->prev;
385  node->next = before;
386  before->prev = node;
387  node->prev->next = node;
388 }
389 
390 /*
391  * Delete 'node' from its list (it must be in one).
392  */
393 static inline void
395 {
396  node->prev->next = node->next;
397  node->next->prev = node->prev;
398 }
399 
400 /*
401  * Same as dlist_delete, but performs checks in ILIST_DEBUG builds to ensure
402  * that 'node' belongs to 'head'.
403  */
404 static inline void
406 {
407  dlist_member_check(head, node);
408  dlist_delete(node);
409 }
410 
411 /*
412  * Remove and return the first node from a list (there must be one).
413  */
414 static inline dlist_node *
416 {
417  dlist_node *node;
418 
419  Assert(!dlist_is_empty(head));
420  node = head->head.next;
421  dlist_delete(node);
422  return node;
423 }
424 
425 /*
426  * Move element from its current position in the list to the head position in
427  * the same list.
428  *
429  * Undefined behaviour if 'node' is not already part of the list.
430  */
431 static inline void
433 {
434  /* fast path if it's already at the head */
435  if (head->head.next == node)
436  return;
437 
438  dlist_delete(node);
439  dlist_push_head(head, node);
440 
441  dlist_check(head);
442 }
443 
444 /*
445  * Move element from its current position in the list to the tail position in
446  * the same list.
447  *
448  * Undefined behaviour if 'node' is not already part of the list.
449  */
450 static inline void
452 {
453  /* fast path if it's already at the tail */
454  if (head->head.prev == node)
455  return;
456 
457  dlist_delete(node);
458  dlist_push_tail(head, node);
459 
460  dlist_check(head);
461 }
462 
463 /*
464  * Check whether 'node' has a following node.
465  * Caution: unreliable if 'node' is not in the list.
466  */
467 static inline bool
469 {
470  return node->next != &head->head;
471 }
472 
473 /*
474  * Check whether 'node' has a preceding node.
475  * Caution: unreliable if 'node' is not in the list.
476  */
477 static inline bool
479 {
480  return node->prev != &head->head;
481 }
482 
483 /*
484  * Return the next node in the list (there must be one).
485  */
486 static inline dlist_node *
488 {
489  Assert(dlist_has_next(head, node));
490  return node->next;
491 }
492 
493 /*
494  * Return previous node in the list (there must be one).
495  */
496 static inline dlist_node *
498 {
499  Assert(dlist_has_prev(head, node));
500  return node->prev;
501 }
502 
503 /* internal support function to get address of head element's struct */
504 static inline void *
506 {
507  Assert(!dlist_is_empty(head));
508  return (char *) head->head.next - off;
509 }
510 
511 /*
512  * Return the first node in the list (there must be one).
513  */
514 static inline dlist_node *
516 {
517  return (dlist_node *) dlist_head_element_off(head, 0);
518 }
519 
520 /* internal support function to get address of tail element's struct */
521 static inline void *
523 {
524  Assert(!dlist_is_empty(head));
525  return (char *) head->head.prev - off;
526 }
527 
528 /*
529  * Return the last node in the list (there must be one).
530  */
531 static inline dlist_node *
533 {
534  return (dlist_node *) dlist_tail_element_off(head, 0);
535 }
536 
537 /*
538  * Return the containing struct of 'type' where 'membername' is the dlist_node
539  * pointed at by 'ptr'.
540  *
541  * This is used to convert a dlist_node * back to its containing struct.
542  */
543 #define dlist_container(type, membername, ptr) \
544  (AssertVariableIsOfTypeMacro(ptr, dlist_node *), \
545  AssertVariableIsOfTypeMacro(((type *) NULL)->membername, dlist_node), \
546  ((type *) ((char *) (ptr) - offsetof(type, membername))))
547 
548 /*
549  * Return the address of the first element in the list.
550  *
551  * The list must not be empty.
552  */
553 #define dlist_head_element(type, membername, lhead) \
554  (AssertVariableIsOfTypeMacro(((type *) NULL)->membername, dlist_node), \
555  (type *) dlist_head_element_off(lhead, offsetof(type, membername)))
556 
557 /*
558  * Return the address of the last element in the list.
559  *
560  * The list must not be empty.
561  */
562 #define dlist_tail_element(type, membername, lhead) \
563  (AssertVariableIsOfTypeMacro(((type *) NULL)->membername, dlist_node), \
564  ((type *) dlist_tail_element_off(lhead, offsetof(type, membername))))
565 
566 /*
567  * Iterate through the list pointed at by 'lhead' storing the state in 'iter'.
568  *
569  * Access the current element with iter.cur.
570  *
571  * It is *not* allowed to manipulate the list during iteration.
572  */
573 #define dlist_foreach(iter, lhead) \
574  for (AssertVariableIsOfTypeMacro(iter, dlist_iter), \
575  AssertVariableIsOfTypeMacro(lhead, dlist_head *), \
576  (iter).end = &(lhead)->head, \
577  (iter).cur = (iter).end->next ? (iter).end->next : (iter).end; \
578  (iter).cur != (iter).end; \
579  (iter).cur = (iter).cur->next)
580 
581 /*
582  * Iterate through the list pointed at by 'lhead' storing the state in 'iter'.
583  *
584  * Access the current element with iter.cur.
585  *
586  * Iterations using this are only allowed to change the list at the current
587  * point of iteration. It is fine to delete the current node, but it is *not*
588  * fine to insert or delete adjacent nodes.
589  */
590 #define dlist_foreach_modify(iter, lhead) \
591  for (AssertVariableIsOfTypeMacro(iter, dlist_mutable_iter), \
592  AssertVariableIsOfTypeMacro(lhead, dlist_head *), \
593  (iter).end = &(lhead)->head, \
594  (iter).cur = (iter).end->next ? (iter).end->next : (iter).end, \
595  (iter).next = (iter).cur->next; \
596  (iter).cur != (iter).end; \
597  (iter).cur = (iter).next, (iter).next = (iter).cur->next)
598 
599 /*
600  * Iterate through the list in reverse order.
601  *
602  * It is *not* allowed to manipulate the list during iteration.
603  */
604 #define dlist_reverse_foreach(iter, lhead) \
605  for (AssertVariableIsOfTypeMacro(iter, dlist_iter), \
606  AssertVariableIsOfTypeMacro(lhead, dlist_head *), \
607  (iter).end = &(lhead)->head, \
608  (iter).cur = (iter).end->prev ? (iter).end->prev : (iter).end; \
609  (iter).cur != (iter).end; \
610  (iter).cur = (iter).cur->prev)
611 
612 /* doubly-linked count list implementation */
613 
614 /*
615  * dclist_init
616  * Initialize a doubly linked count list.
617  *
618  * Previous state will be thrown away without any cleanup.
619  */
620 static inline void
622 {
623  dlist_init(&head->dlist);
624  head->count = 0;
625 }
626 
627 /*
628  * dclist_is_empty
629  * Returns true if the list is empty, otherwise false.
630  */
631 static inline bool
633 {
634  Assert(dlist_is_empty(&head->dlist) == (head->count == 0));
635  return (head->count == 0);
636 }
637 
638 /*
639  * dclist_push_head
640  * Insert a node at the beginning of the list.
641  */
642 static inline void
644 {
645  if (head->dlist.head.next == NULL) /* convert NULL header to circular */
646  dclist_init(head);
647 
648  dlist_push_head(&head->dlist, node);
649  head->count++;
650 
651  Assert(head->count > 0); /* count overflow check */
652 }
653 
654 /*
655  * dclist_push_tail
656  * Insert a node at the end of the list.
657  */
658 static inline void
660 {
661  if (head->dlist.head.next == NULL) /* convert NULL header to circular */
662  dclist_init(head);
663 
664  dlist_push_tail(&head->dlist, node);
665  head->count++;
666 
667  Assert(head->count > 0); /* count overflow check */
668 }
669 
670 /*
671  * dclist_insert_after
672  * Insert a node after another *in the same list*
673  *
674  * Caution: 'after' must be a member of 'head'.
675  */
676 static inline void
678 {
679  dlist_member_check(&head->dlist, after);
680  Assert(head->count > 0); /* must be at least 1 already */
681 
682  dlist_insert_after(after, node);
683  head->count++;
684 
685  Assert(head->count > 0); /* count overflow check */
686 }
687 
688 /*
689  * dclist_insert_before
690  * Insert a node before another *in the same list*
691  *
692  * Caution: 'before' must be a member of 'head'.
693  */
694 static inline void
696 {
698  Assert(head->count > 0); /* must be at least 1 already */
699 
701  head->count++;
702 
703  Assert(head->count > 0); /* count overflow check */
704 }
705 
706 /*
707  * dclist_delete_from
708  * Deletes 'node' from 'head'.
709  *
710  * Caution: 'node' must be a member of 'head'.
711  */
712 static inline void
714 {
715  Assert(head->count > 0);
716 
717  dlist_delete_from(&head->dlist, node);
718  head->count--;
719 }
720 
721 /*
722  * dclist_pop_head_node
723  * Remove and return the first node from a list (there must be one).
724  */
725 static inline dlist_node *
727 {
728  dlist_node *node;
729 
730  Assert(head->count > 0);
731 
732  node = dlist_pop_head_node(&head->dlist);
733  head->count--;
734  return node;
735 }
736 
737 /*
738  * dclist_move_head
739  * Move 'node' from its current position in the list to the head position
740  * in 'head'.
741  *
742  * Caution: 'node' must be a member of 'head'.
743  */
744 static inline void
746 {
747  dlist_member_check(&head->dlist, node);
748  Assert(head->count > 0);
749 
750  dlist_move_head(&head->dlist, node);
751 }
752 
753 /*
754  * dclist_move_tail
755  * Move 'node' from its current position in the list to the tail position
756  * in 'head'.
757  *
758  * Caution: 'node' must be a member of 'head'.
759  */
760 static inline void
762 {
763  dlist_member_check(&head->dlist, node);
764  Assert(head->count > 0);
765 
766  dlist_move_tail(&head->dlist, node);
767 }
768 
769 /*
770  * dclist_has_next
771  * Check whether 'node' has a following node.
772  *
773  * Caution: 'node' must be a member of 'head'.
774  */
775 static inline bool
777 {
778  dlist_member_check(&head->dlist, node);
779  Assert(head->count > 0);
780 
781  return dlist_has_next(&head->dlist, node);
782 }
783 
784 /*
785  * dclist_has_prev
786  * Check whether 'node' has a preceding node.
787  *
788  * Caution: 'node' must be a member of 'head'.
789  */
790 static inline bool
792 {
793  dlist_member_check(&head->dlist, node);
794  Assert(head->count > 0);
795 
796  return dlist_has_prev(&head->dlist, node);
797 }
798 
799 /*
800  * dclist_next_node
801  * Return the next node in the list (there must be one).
802  */
803 static inline dlist_node *
805 {
806  Assert(head->count > 0);
807 
808  return dlist_next_node(&head->dlist, node);
809 }
810 
811 /*
812  * dclist_prev_node
813  * Return the prev node in the list (there must be one).
814  */
815 static inline dlist_node *
817 {
818  Assert(head->count > 0);
819 
820  return dlist_prev_node(&head->dlist, node);
821 }
822 
823 /* internal support function to get address of head element's struct */
824 static inline void *
826 {
827  Assert(!dclist_is_empty(head));
828 
829  return (char *) head->dlist.head.next - off;
830 }
831 
832 /*
833  * dclist_head_node
834  * Return the first node in the list (there must be one).
835  */
836 static inline dlist_node *
838 {
839  Assert(head->count > 0);
840 
841  return (dlist_node *) dlist_head_element_off(&head->dlist, 0);
842 }
843 
844 /* internal support function to get address of tail element's struct */
845 static inline void *
847 {
848  Assert(!dclist_is_empty(head));
849 
850  return (char *) head->dlist.head.prev - off;
851 }
852 
853 /*
854  * Return the last node in the list (there must be one).
855  */
856 static inline dlist_node *
858 {
859  Assert(head->count > 0);
860 
861  return (dlist_node *) dlist_tail_element_off(&head->dlist, 0);
862 }
863 
864 /*
865  * dclist_count
866  * Returns the stored number of entries in 'head'
867  */
868 static inline uint32
870 {
871  Assert(dlist_is_empty(&head->dlist) == (head->count == 0));
872 
873  return head->count;
874 }
875 
876 /*
877  * Return the containing struct of 'type' where 'membername' is the dlist_node
878  * pointed at by 'ptr'.
879  *
880  * This is used to convert a dlist_node * back to its containing struct.
881  *
882  * Note: This is effectively just the same as dlist_container, so reuse that.
883  */
884 #define dclist_container(type, membername, ptr) \
885  dlist_container(type, membername, ptr)
886 
887  /*
888  * Return the address of the first element in the list.
889  *
890  * The list must not be empty.
891  */
892 #define dclist_head_element(type, membername, lhead) \
893  (AssertVariableIsOfTypeMacro(((type *) NULL)->membername, dlist_node), \
894  (type *) dclist_head_element_off(lhead, offsetof(type, membername)))
895 
896  /*
897  * Return the address of the last element in the list.
898  *
899  * The list must not be empty.
900  */
901 #define dclist_tail_element(type, membername, lhead) \
902  (AssertVariableIsOfTypeMacro(((type *) NULL)->membername, dlist_node), \
903  ((type *) dclist_tail_element_off(lhead, offsetof(type, membername))))
904 
905 
906 /* Iterators for dclists */
907 #define dclist_foreach(iter, lhead) \
908  dlist_foreach(iter, &((lhead)->dlist))
909 
910 #define dclist_foreach_modify(iter, lhead) \
911  dlist_foreach_modify(iter, &((lhead)->dlist))
912 
913 #define dclist_reverse_foreach(iter, lhead) \
914  dlist_reverse_foreach(iter, &((lhead)->dlist))
915 
916 /* singly linked list implementation */
917 
918 /*
919  * Initialize a singly linked list.
920  * Previous state will be thrown away without any cleanup.
921  */
922 static inline void
924 {
925  head->head.next = NULL;
926 }
927 
928 /*
929  * Is the list empty?
930  */
931 static inline bool
933 {
934  slist_check(head);
935 
936  return head->head.next == NULL;
937 }
938 
939 /*
940  * Insert a node at the beginning of the list.
941  */
942 static inline void
944 {
945  node->next = head->head.next;
946  head->head.next = node;
947 
948  slist_check(head);
949 }
950 
951 /*
952  * Insert a node after another *in the same list*
953  */
954 static inline void
956 {
957  node->next = after->next;
958  after->next = node;
959 }
960 
961 /*
962  * Remove and return the first node from a list (there must be one).
963  */
964 static inline slist_node *
966 {
967  slist_node *node;
968 
969  Assert(!slist_is_empty(head));
970  node = head->head.next;
971  head->head.next = node->next;
972  slist_check(head);
973  return node;
974 }
975 
976 /*
977  * Check whether 'node' has a following node.
978  */
979 static inline bool
981 {
982  slist_check(head);
983 
984  return node->next != NULL;
985 }
986 
987 /*
988  * Return the next node in the list (there must be one).
989  */
990 static inline slist_node *
992 {
993  Assert(slist_has_next(head, node));
994  return node->next;
995 }
996 
997 /* internal support function to get address of head element's struct */
998 static inline void *
1000 {
1001  Assert(!slist_is_empty(head));
1002  return (char *) head->head.next - off;
1003 }
1004 
1005 /*
1006  * Return the first node in the list (there must be one).
1007  */
1008 static inline slist_node *
1010 {
1011  return (slist_node *) slist_head_element_off(head, 0);
1012 }
1013 
1014 /*
1015  * Delete the list element the iterator currently points to.
1016  *
1017  * Caution: this modifies iter->cur, so don't use that again in the current
1018  * loop iteration.
1019  */
1020 static inline void
1022 {
1023  /*
1024  * Update previous element's forward link. If the iteration is at the
1025  * first list element, iter->prev will point to the list header's "head"
1026  * field, so we don't need a special case for that.
1027  */
1028  iter->prev->next = iter->next;
1029 
1030  /*
1031  * Reset cur to prev, so that prev will continue to point to the prior
1032  * valid list element after slist_foreach_modify() advances to the next.
1033  */
1034  iter->cur = iter->prev;
1035 }
1036 
1037 /*
1038  * Return the containing struct of 'type' where 'membername' is the slist_node
1039  * pointed at by 'ptr'.
1040  *
1041  * This is used to convert a slist_node * back to its containing struct.
1042  */
1043 #define slist_container(type, membername, ptr) \
1044  (AssertVariableIsOfTypeMacro(ptr, slist_node *), \
1045  AssertVariableIsOfTypeMacro(((type *) NULL)->membername, slist_node), \
1046  ((type *) ((char *) (ptr) - offsetof(type, membername))))
1047 
1048 /*
1049  * Return the address of the first element in the list.
1050  *
1051  * The list must not be empty.
1052  */
1053 #define slist_head_element(type, membername, lhead) \
1054  (AssertVariableIsOfTypeMacro(((type *) NULL)->membername, slist_node), \
1055  (type *) slist_head_element_off(lhead, offsetof(type, membername)))
1056 
1057 /*
1058  * Iterate through the list pointed at by 'lhead' storing the state in 'iter'.
1059  *
1060  * Access the current element with iter.cur.
1061  *
1062  * It's allowed to modify the list while iterating, with the exception of
1063  * deleting the iterator's current node; deletion of that node requires
1064  * care if the iteration is to be continued afterward. (Doing so and also
1065  * deleting or inserting adjacent list elements might misbehave; also, if
1066  * the user frees the current node's storage, continuing the iteration is
1067  * not safe.)
1068  */
1069 #define slist_foreach(iter, lhead) \
1070  for (AssertVariableIsOfTypeMacro(iter, slist_iter), \
1071  AssertVariableIsOfTypeMacro(lhead, slist_head *), \
1072  (iter).cur = (lhead)->head.next; \
1073  (iter).cur != NULL; \
1074  (iter).cur = (iter).cur->next)
1075 
1076 /*
1077  * Iterate through the list pointed at by 'lhead' storing the state in 'iter'.
1078  *
1079  * Access the current element with iter.cur.
1080  *
1081  * The only list modification allowed while iterating is to remove the current
1082  * node via slist_delete_current() (*not* slist_delete()). Insertion or
1083  * deletion of nodes adjacent to the current node would misbehave.
1084  */
1085 #define slist_foreach_modify(iter, lhead) \
1086  for (AssertVariableIsOfTypeMacro(iter, slist_mutable_iter), \
1087  AssertVariableIsOfTypeMacro(lhead, slist_head *), \
1088  (iter).prev = &(lhead)->head, \
1089  (iter).cur = (iter).prev->next, \
1090  (iter).next = (iter).cur ? (iter).cur->next : NULL; \
1091  (iter).cur != NULL; \
1092  (iter).prev = (iter).cur, \
1093  (iter).cur = (iter).next, \
1094  (iter).next = (iter).next ? (iter).next->next : NULL)
1095 
1096 #endif /* ILIST_H */
unsigned int uint32
Definition: c.h:442
static dlist_node * dlist_prev_node(dlist_head *head, dlist_node *node)
Definition: ilist.h:497
struct slist_iter slist_iter
static void slist_delete_current(slist_mutable_iter *iter)
Definition: ilist.h:1021
static bool slist_is_empty(slist_head *head)
Definition: ilist.h:932
struct dlist_iter dlist_iter
static void dlist_insert_after(dlist_node *after, dlist_node *node)
Definition: ilist.h:370
static void * slist_head_element_off(slist_head *head, size_t off)
Definition: ilist.h:999
static void * dclist_tail_element_off(dclist_head *head, size_t off)
Definition: ilist.h:846
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:405
static void * dlist_tail_element_off(dlist_head *head, size_t off)
Definition: ilist.h:522
static void dclist_push_tail(dclist_head *head, dlist_node *node)
Definition: ilist.h:659
static void * dclist_head_element_off(dclist_head *head, size_t off)
Definition: ilist.h:825
static void dlist_insert_before(dlist_node *before, dlist_node *node)
Definition: ilist.h:382
static bool slist_has_next(slist_head *head, slist_node *node)
Definition: ilist.h:980
static dlist_node * dclist_tail_node(dclist_head *head)
Definition: ilist.h:857
#define dlist_check(head)
Definition: ilist.h:303
static bool dlist_is_empty(dlist_head *head)
Definition: ilist.h:325
static void dlist_delete(dlist_node *node)
Definition: ilist.h:394
static void slist_init(slist_head *head)
Definition: ilist.h:923
static bool dclist_has_next(dclist_head *head, dlist_node *node)
Definition: ilist.h:776
static dlist_node * dlist_next_node(dlist_head *head, dlist_node *node)
Definition: ilist.h:487
static void dclist_move_head(dclist_head *head, dlist_node *node)
Definition: ilist.h:745
struct dlist_head dlist_head
static void * dlist_head_element_off(dlist_head *head, size_t off)
Definition: ilist.h:505
static dlist_node * dlist_pop_head_node(dlist_head *head)
Definition: ilist.h:415
static bool dlist_has_next(dlist_head *head, dlist_node *node)
Definition: ilist.h:468
static void dlist_push_head(dlist_head *head, dlist_node *node)
Definition: ilist.h:336
static void slist_insert_after(slist_node *after, slist_node *node)
Definition: ilist.h:955
void slist_delete(slist_head *head, slist_node *node)
Definition: ilist.c:31
static void slist_push_head(slist_head *head, slist_node *node)
Definition: ilist.h:943
static dlist_node * dclist_next_node(dclist_head *head, dlist_node *node)
Definition: ilist.h:804
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:353
static uint32 dclist_count(dclist_head *head)
Definition: ilist.h:869
static void dclist_delete_from(dclist_head *head, dlist_node *node)
Definition: ilist.h:713
static slist_node * slist_next_node(slist_head *head, slist_node *node)
Definition: ilist.h:991
struct dclist_head dclist_head
struct dlist_mutable_iter dlist_mutable_iter
static bool dclist_is_empty(dclist_head *head)
Definition: ilist.h:632
static dlist_node * dclist_head_node(dclist_head *head)
Definition: ilist.h:837
static void dclist_push_head(dclist_head *head, dlist_node *node)
Definition: ilist.h:643
static bool dlist_has_prev(dlist_head *head, dlist_node *node)
Definition: ilist.h:478
static void dclist_move_tail(dclist_head *head, dlist_node *node)
Definition: ilist.h:761
static void dclist_insert_before(dclist_head *head, dlist_node *before, dlist_node *node)
Definition: ilist.h:695
static bool dclist_has_prev(dclist_head *head, dlist_node *node)
Definition: ilist.h:791
static void dclist_init(dclist_head *head)
Definition: ilist.h:621
static void dlist_move_head(dlist_head *head, dlist_node *node)
Definition: ilist.h:432
struct slist_mutable_iter slist_mutable_iter
static dlist_node * dlist_head_node(dlist_head *head)
Definition: ilist.h:515
static dlist_node * dclist_prev_node(dclist_head *head, dlist_node *node)
Definition: ilist.h:816
static void dlist_move_tail(dlist_head *head, dlist_node *node)
Definition: ilist.h:451
static slist_node * slist_head_node(slist_head *head)
Definition: ilist.h:1009
#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:677
static slist_node * slist_pop_head_node(slist_head *head)
Definition: ilist.h:965
static dlist_node * dclist_pop_head_node(dclist_head *head)
Definition: ilist.h:726
static dlist_node * dlist_tail_node(dlist_head *head)
Definition: ilist.h:532
Assert(fmt[strlen(fmt) - 1] !='\n')
static int before(chr x, chr y)
Definition: regc_locale.c:492
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