1 /*-------------------------------------------------------------------------
2 *
3 * ilist.c
4 * support for integrated/inline doubly- and singly- linked lists
5 *
6 * Portions Copyright (c) 1996-2016, 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 */
30 void
slist_delete(slist_head * head,slist_node * node)31 slist_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 */
58 void
dlist_check(dlist_head * head)59 dlist_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 */
95 void
slist_check(slist_head * head)96 slist_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