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-2021, 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 */
120 typedef struct dlist_node dlist_node;
121 struct 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 */
135 typedef 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 */
159 typedef 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 */
178 typedef 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 */
190 typedef struct slist_node slist_node;
191 struct 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 */
203 typedef 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 */
224 typedef 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 */
239 typedef 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 */
255 extern void slist_delete(slist_head *head, slist_node *node);
256
257 #ifdef ILIST_DEBUG
258 extern void dlist_check(dlist_head *head);
259 extern 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 */
277 static inline void
dlist_init(dlist_head * head)278 dlist_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 */
288 static inline bool
dlist_is_empty(dlist_head * head)289 dlist_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 */
299 static inline void
dlist_push_head(dlist_head * head,dlist_node * node)300 dlist_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 */
316 static inline void
dlist_push_tail(dlist_head * head,dlist_node * node)317 dlist_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 */
333 static inline void
dlist_insert_after(dlist_node * after,dlist_node * node)334 dlist_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 */
345 static inline void
dlist_insert_before(dlist_node * before,dlist_node * node)346 dlist_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 */
357 static inline void
dlist_delete(dlist_node * node)358 dlist_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 */
367 static inline dlist_node *
dlist_pop_head_node(dlist_head * head)368 dlist_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 */
384 static inline void
dlist_move_head(dlist_head * head,dlist_node * node)385 dlist_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 * Move element from its current position in the list to the tail position in
399 * the same list.
400 *
401 * Undefined behaviour if 'node' is not already part of the list.
402 */
403 static inline void
dlist_move_tail(dlist_head * head,dlist_node * node)404 dlist_move_tail(dlist_head *head, dlist_node *node)
405 {
406 /* fast path if it's already at the tail */
407 if (head->head.prev == node)
408 return;
409
410 dlist_delete(node);
411 dlist_push_tail(head, node);
412
413 dlist_check(head);
414 }
415
416 /*
417 * Check whether 'node' has a following node.
418 * Caution: unreliable if 'node' is not in the list.
419 */
420 static inline bool
dlist_has_next(dlist_head * head,dlist_node * node)421 dlist_has_next(dlist_head *head, dlist_node *node)
422 {
423 return node->next != &head->head;
424 }
425
426 /*
427 * Check whether 'node' has a preceding node.
428 * Caution: unreliable if 'node' is not in the list.
429 */
430 static inline bool
dlist_has_prev(dlist_head * head,dlist_node * node)431 dlist_has_prev(dlist_head *head, dlist_node *node)
432 {
433 return node->prev != &head->head;
434 }
435
436 /*
437 * Return the next node in the list (there must be one).
438 */
439 static inline dlist_node *
dlist_next_node(dlist_head * head,dlist_node * node)440 dlist_next_node(dlist_head *head, dlist_node *node)
441 {
442 Assert(dlist_has_next(head, node));
443 return node->next;
444 }
445
446 /*
447 * Return previous node in the list (there must be one).
448 */
449 static inline dlist_node *
dlist_prev_node(dlist_head * head,dlist_node * node)450 dlist_prev_node(dlist_head *head, dlist_node *node)
451 {
452 Assert(dlist_has_prev(head, node));
453 return node->prev;
454 }
455
456 /* internal support function to get address of head element's struct */
457 static inline void *
dlist_head_element_off(dlist_head * head,size_t off)458 dlist_head_element_off(dlist_head *head, size_t off)
459 {
460 Assert(!dlist_is_empty(head));
461 return (char *) head->head.next - off;
462 }
463
464 /*
465 * Return the first node in the list (there must be one).
466 */
467 static inline dlist_node *
dlist_head_node(dlist_head * head)468 dlist_head_node(dlist_head *head)
469 {
470 return (dlist_node *) dlist_head_element_off(head, 0);
471 }
472
473 /* internal support function to get address of tail element's struct */
474 static inline void *
dlist_tail_element_off(dlist_head * head,size_t off)475 dlist_tail_element_off(dlist_head *head, size_t off)
476 {
477 Assert(!dlist_is_empty(head));
478 return (char *) head->head.prev - off;
479 }
480
481 /*
482 * Return the last node in the list (there must be one).
483 */
484 static inline dlist_node *
dlist_tail_node(dlist_head * head)485 dlist_tail_node(dlist_head *head)
486 {
487 return (dlist_node *) dlist_tail_element_off(head, 0);
488 }
489
490 /*
491 * Return the containing struct of 'type' where 'membername' is the dlist_node
492 * pointed at by 'ptr'.
493 *
494 * This is used to convert a dlist_node * back to its containing struct.
495 */
496 #define dlist_container(type, membername, ptr) \
497 (AssertVariableIsOfTypeMacro(ptr, dlist_node *), \
498 AssertVariableIsOfTypeMacro(((type *) NULL)->membername, dlist_node), \
499 ((type *) ((char *) (ptr) - offsetof(type, membername))))
500
501 /*
502 * Return the address of the first element in the list.
503 *
504 * The list must not be empty.
505 */
506 #define dlist_head_element(type, membername, lhead) \
507 (AssertVariableIsOfTypeMacro(((type *) NULL)->membername, dlist_node), \
508 (type *) dlist_head_element_off(lhead, offsetof(type, membername)))
509
510 /*
511 * Return the address of the last element in the list.
512 *
513 * The list must not be empty.
514 */
515 #define dlist_tail_element(type, membername, lhead) \
516 (AssertVariableIsOfTypeMacro(((type *) NULL)->membername, dlist_node), \
517 ((type *) dlist_tail_element_off(lhead, offsetof(type, membername))))
518
519 /*
520 * Iterate through the list pointed at by 'lhead' storing the state in 'iter'.
521 *
522 * Access the current element with iter.cur.
523 *
524 * It is *not* allowed to manipulate the list during iteration.
525 */
526 #define dlist_foreach(iter, lhead) \
527 for (AssertVariableIsOfTypeMacro(iter, dlist_iter), \
528 AssertVariableIsOfTypeMacro(lhead, dlist_head *), \
529 (iter).end = &(lhead)->head, \
530 (iter).cur = (iter).end->next ? (iter).end->next : (iter).end; \
531 (iter).cur != (iter).end; \
532 (iter).cur = (iter).cur->next)
533
534 /*
535 * Iterate through the list pointed at by 'lhead' storing the state in 'iter'.
536 *
537 * Access the current element with iter.cur.
538 *
539 * Iterations using this are only allowed to change the list at the current
540 * point of iteration. It is fine to delete the current node, but it is *not*
541 * fine to insert or delete adjacent nodes.
542 */
543 #define dlist_foreach_modify(iter, lhead) \
544 for (AssertVariableIsOfTypeMacro(iter, dlist_mutable_iter), \
545 AssertVariableIsOfTypeMacro(lhead, dlist_head *), \
546 (iter).end = &(lhead)->head, \
547 (iter).cur = (iter).end->next ? (iter).end->next : (iter).end, \
548 (iter).next = (iter).cur->next; \
549 (iter).cur != (iter).end; \
550 (iter).cur = (iter).next, (iter).next = (iter).cur->next)
551
552 /*
553 * Iterate through the list in reverse order.
554 *
555 * It is *not* allowed to manipulate the list during iteration.
556 */
557 #define dlist_reverse_foreach(iter, lhead) \
558 for (AssertVariableIsOfTypeMacro(iter, dlist_iter), \
559 AssertVariableIsOfTypeMacro(lhead, dlist_head *), \
560 (iter).end = &(lhead)->head, \
561 (iter).cur = (iter).end->prev ? (iter).end->prev : (iter).end; \
562 (iter).cur != (iter).end; \
563 (iter).cur = (iter).cur->prev)
564
565
566 /* singly linked list implementation */
567
568 /*
569 * Initialize a singly linked list.
570 * Previous state will be thrown away without any cleanup.
571 */
572 static inline void
slist_init(slist_head * head)573 slist_init(slist_head *head)
574 {
575 head->head.next = NULL;
576 }
577
578 /*
579 * Is the list empty?
580 */
581 static inline bool
slist_is_empty(slist_head * head)582 slist_is_empty(slist_head *head)
583 {
584 slist_check(head);
585
586 return head->head.next == NULL;
587 }
588
589 /*
590 * Insert a node at the beginning of the list.
591 */
592 static inline void
slist_push_head(slist_head * head,slist_node * node)593 slist_push_head(slist_head *head, slist_node *node)
594 {
595 node->next = head->head.next;
596 head->head.next = node;
597
598 slist_check(head);
599 }
600
601 /*
602 * Insert a node after another *in the same list*
603 */
604 static inline void
slist_insert_after(slist_node * after,slist_node * node)605 slist_insert_after(slist_node *after, slist_node *node)
606 {
607 node->next = after->next;
608 after->next = node;
609 }
610
611 /*
612 * Remove and return the first node from a list (there must be one).
613 */
614 static inline slist_node *
slist_pop_head_node(slist_head * head)615 slist_pop_head_node(slist_head *head)
616 {
617 slist_node *node;
618
619 Assert(!slist_is_empty(head));
620 node = head->head.next;
621 head->head.next = node->next;
622 slist_check(head);
623 return node;
624 }
625
626 /*
627 * Check whether 'node' has a following node.
628 */
629 static inline bool
slist_has_next(slist_head * head,slist_node * node)630 slist_has_next(slist_head *head, slist_node *node)
631 {
632 slist_check(head);
633
634 return node->next != NULL;
635 }
636
637 /*
638 * Return the next node in the list (there must be one).
639 */
640 static inline slist_node *
slist_next_node(slist_head * head,slist_node * node)641 slist_next_node(slist_head *head, slist_node *node)
642 {
643 Assert(slist_has_next(head, node));
644 return node->next;
645 }
646
647 /* internal support function to get address of head element's struct */
648 static inline void *
slist_head_element_off(slist_head * head,size_t off)649 slist_head_element_off(slist_head *head, size_t off)
650 {
651 Assert(!slist_is_empty(head));
652 return (char *) head->head.next - off;
653 }
654
655 /*
656 * Return the first node in the list (there must be one).
657 */
658 static inline slist_node *
slist_head_node(slist_head * head)659 slist_head_node(slist_head *head)
660 {
661 return (slist_node *) slist_head_element_off(head, 0);
662 }
663
664 /*
665 * Delete the list element the iterator currently points to.
666 *
667 * Caution: this modifies iter->cur, so don't use that again in the current
668 * loop iteration.
669 */
670 static inline void
slist_delete_current(slist_mutable_iter * iter)671 slist_delete_current(slist_mutable_iter *iter)
672 {
673 /*
674 * Update previous element's forward link. If the iteration is at the
675 * first list element, iter->prev will point to the list header's "head"
676 * field, so we don't need a special case for that.
677 */
678 iter->prev->next = iter->next;
679
680 /*
681 * Reset cur to prev, so that prev will continue to point to the prior
682 * valid list element after slist_foreach_modify() advances to the next.
683 */
684 iter->cur = iter->prev;
685 }
686
687 /*
688 * Return the containing struct of 'type' where 'membername' is the slist_node
689 * pointed at by 'ptr'.
690 *
691 * This is used to convert a slist_node * back to its containing struct.
692 */
693 #define slist_container(type, membername, ptr) \
694 (AssertVariableIsOfTypeMacro(ptr, slist_node *), \
695 AssertVariableIsOfTypeMacro(((type *) NULL)->membername, slist_node), \
696 ((type *) ((char *) (ptr) - offsetof(type, membername))))
697
698 /*
699 * Return the address of the first element in the list.
700 *
701 * The list must not be empty.
702 */
703 #define slist_head_element(type, membername, lhead) \
704 (AssertVariableIsOfTypeMacro(((type *) NULL)->membername, slist_node), \
705 (type *) slist_head_element_off(lhead, offsetof(type, membername)))
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 * It's allowed to modify the list while iterating, with the exception of
713 * deleting the iterator's current node; deletion of that node requires
714 * care if the iteration is to be continued afterward. (Doing so and also
715 * deleting or inserting adjacent list elements might misbehave; also, if
716 * the user frees the current node's storage, continuing the iteration is
717 * not safe.)
718 */
719 #define slist_foreach(iter, lhead) \
720 for (AssertVariableIsOfTypeMacro(iter, slist_iter), \
721 AssertVariableIsOfTypeMacro(lhead, slist_head *), \
722 (iter).cur = (lhead)->head.next; \
723 (iter).cur != NULL; \
724 (iter).cur = (iter).cur->next)
725
726 /*
727 * Iterate through the list pointed at by 'lhead' storing the state in 'iter'.
728 *
729 * Access the current element with iter.cur.
730 *
731 * The only list modification allowed while iterating is to remove the current
732 * node via slist_delete_current() (*not* slist_delete()). Insertion or
733 * deletion of nodes adjacent to the current node would misbehave.
734 */
735 #define slist_foreach_modify(iter, lhead) \
736 for (AssertVariableIsOfTypeMacro(iter, slist_mutable_iter), \
737 AssertVariableIsOfTypeMacro(lhead, slist_head *), \
738 (iter).prev = &(lhead)->head, \
739 (iter).cur = (iter).prev->next, \
740 (iter).next = (iter).cur ? (iter).cur->next : NULL; \
741 (iter).cur != NULL; \
742 (iter).prev = (iter).cur, \
743 (iter).cur = (iter).next, \
744 (iter).next = (iter).next ? (iter).next->next : NULL)
745
746 #endif /* ILIST_H */
747