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