1/*-------------------------------------------------------------------------
2 *
3 * ilist.c
4 * support for integrated/inline doubly- and singly- linked lists
5 *
6 * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group
7 * Portions Copyright (c) 1994, Regents of the University of California
8 *
9 *
10 * IDENTIFICATION
11 * src/backend/lib/ilist.c
12 *
13 * NOTES
14 * This file only contains functions that are too big to be considered
15 * for inlining. See ilist.h for most of the goodies.
16 *
17 *-------------------------------------------------------------------------
18 */
19#include "postgres.h"
20
21#include "lib/ilist.h"
22
23/*
24 * Delete 'node' from list.
25 *
26 * It is not allowed to delete a 'node' which is not in the list 'head'
27 *
28 * Caution: this is O(n); consider using slist_delete_current() instead.
29 */
30void
31slist_delete(slist_head *head, slist_node *node)
32{
33 slist_node *last = &head->head;
34 slist_node *cur;
35 bool found PG_USED_FOR_ASSERTS_ONLY = false;
36
37 while ((cur = last->next) != NULL)
38 {
39 if (cur == node)
40 {
41 last->next = cur->next;
42#ifdef USE_ASSERT_CHECKING
43 found = true;
44#endif
45 break;
46 }
47 last = cur;
48 }
49 Assert(found);
50
51 slist_check(head);
52}
53
54#ifdef ILIST_DEBUG
55/*
56 * Verify integrity of a doubly linked list
57 */
58void
59dlist_check(dlist_head *head)
60{
61 dlist_node *cur;
62
63 if (head == NULL)
64 elog(ERROR, "doubly linked list head address is NULL");
65
66 if (head->head.next == NULL && head->head.prev == NULL)
67 return; /* OK, initialized as zeroes */
68
69 /* iterate in forward direction */
70 for (cur = head->head.next; cur != &head->head; cur = cur->next)
71 {
72 if (cur == NULL ||
73 cur->next == NULL ||
74 cur->prev == NULL ||
75 cur->prev->next != cur ||
76 cur->next->prev != cur)
77 elog(ERROR, "doubly linked list is corrupted");
78 }
79
80 /* iterate in backward direction */
81 for (cur = head->head.prev; cur != &head->head; cur = cur->prev)
82 {
83 if (cur == NULL ||
84 cur->next == NULL ||
85 cur->prev == NULL ||
86 cur->prev->next != cur ||
87 cur->next->prev != cur)
88 elog(ERROR, "doubly linked list is corrupted");
89 }
90}
91
92/*
93 * Verify integrity of a singly linked list
94 */
95void
96slist_check(slist_head *head)
97{
98 slist_node *cur;
99
100 if (head == NULL)
101 elog(ERROR, "singly linked list head address is NULL");
102
103 /*
104 * there isn't much we can test in a singly linked list except that it
105 * actually ends sometime, i.e. hasn't introduced a cycle or similar
106 */
107 for (cur = head->head.next; cur != NULL; cur = cur->next)
108 ;
109}
110
111#endif /* ILIST_DEBUG */
112