blob: 957a11812277b9991e6a0f6a82912e7c33532c6d (
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
|
/*-------------------------------------------------------------------------
*
* ilist.c
* support for integrated/inline doubly- and singly- linked lists
*
* Portions Copyright (c) 1996-2013, 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"
/* See ilist.h */
#define ILIST_INCLUDE_DEFINITIONS
#include "lib/ilist.h"
/*
* Delete 'node' from list.
*
* It is not allowed to delete a 'node' which is is not in the list 'head'
*
* Caution: this is O(n)
*/
void
slist_delete(slist_head *head, 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
/*
* Verify integrity of a doubly linked list
*/
void
dlist_check(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(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 */
|
