/src/postgres/src/backend/lib/ilist.c
Line | Count | Source |
1 | | /*------------------------------------------------------------------------- |
2 | | * |
3 | | * ilist.c |
4 | | * support for integrated/inline doubly- and singly- linked lists |
5 | | * |
6 | | * Portions Copyright (c) 1996-2026, 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 |
31 | | slist_delete(slist_head *head, const slist_node *node) |
32 | 0 | { |
33 | 0 | slist_node *last = &head->head; |
34 | 0 | slist_node *cur; |
35 | 0 | bool found PG_USED_FOR_ASSERTS_ONLY = false; |
36 | |
|
37 | 0 | while ((cur = last->next) != NULL) |
38 | 0 | { |
39 | 0 | if (cur == node) |
40 | 0 | { |
41 | 0 | last->next = cur->next; |
42 | | #ifdef USE_ASSERT_CHECKING |
43 | | found = true; |
44 | | #endif |
45 | 0 | break; |
46 | 0 | } |
47 | 0 | last = cur; |
48 | 0 | } |
49 | 0 | Assert(found); |
50 | |
|
51 | 0 | slist_check(head); |
52 | 0 | } |
53 | | |
54 | | #ifdef ILIST_DEBUG |
55 | | /* |
56 | | * dlist_member_check |
57 | | * Validate that 'node' is a member of 'head' |
58 | | */ |
59 | | void |
60 | | dlist_member_check(const dlist_head *head, const dlist_node *node) |
61 | | { |
62 | | const dlist_node *cur; |
63 | | |
64 | | /* iteration open-coded to due to the use of const */ |
65 | | for (cur = head->head.next; cur != &head->head; cur = cur->next) |
66 | | { |
67 | | if (cur == node) |
68 | | return; |
69 | | } |
70 | | elog(ERROR, "double linked list member check failure"); |
71 | | } |
72 | | |
73 | | /* |
74 | | * Verify integrity of a doubly linked list |
75 | | */ |
76 | | void |
77 | | dlist_check(const dlist_head *head) |
78 | | { |
79 | | dlist_node *cur; |
80 | | |
81 | | if (head == NULL) |
82 | | elog(ERROR, "doubly linked list head address is NULL"); |
83 | | |
84 | | if (head->head.next == NULL && head->head.prev == NULL) |
85 | | return; /* OK, initialized as zeroes */ |
86 | | |
87 | | /* iterate in forward direction */ |
88 | | for (cur = head->head.next; cur != &head->head; cur = cur->next) |
89 | | { |
90 | | if (cur == NULL || |
91 | | cur->next == NULL || |
92 | | cur->prev == NULL || |
93 | | cur->prev->next != cur || |
94 | | cur->next->prev != cur) |
95 | | elog(ERROR, "doubly linked list is corrupted"); |
96 | | } |
97 | | |
98 | | /* iterate in backward direction */ |
99 | | for (cur = head->head.prev; cur != &head->head; cur = cur->prev) |
100 | | { |
101 | | if (cur == NULL || |
102 | | cur->next == NULL || |
103 | | cur->prev == NULL || |
104 | | cur->prev->next != cur || |
105 | | cur->next->prev != cur) |
106 | | elog(ERROR, "doubly linked list is corrupted"); |
107 | | } |
108 | | } |
109 | | |
110 | | /* |
111 | | * Verify integrity of a singly linked list |
112 | | */ |
113 | | void |
114 | | slist_check(const slist_head *head) |
115 | | { |
116 | | slist_node *cur; |
117 | | |
118 | | if (head == NULL) |
119 | | elog(ERROR, "singly linked list head address is NULL"); |
120 | | |
121 | | /* |
122 | | * there isn't much we can test in a singly linked list except that it |
123 | | * actually ends sometime, i.e. hasn't introduced a cycle or similar |
124 | | */ |
125 | | for (cur = head->head.next; cur != NULL; cur = cur->next) |
126 | | ; |
127 | | } |
128 | | |
129 | | #endif /* ILIST_DEBUG */ |