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