PostgreSQL Source Code git master
ilist.c
Go to the documentation of this file.
1/*-------------------------------------------------------------------------
2 *
3 * ilist.c
4 * support for integrated/inline doubly- and singly- linked lists
5 *
6 * Portions Copyright (c) 1996-2025, 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
32{
33 slist_node *last = &head->head;
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 * dlist_member_check
57 * Validate that 'node' is a member of 'head'
58 */
59void
60dlist_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 */
76void
77dlist_check(const dlist_head *head)
78{
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 */
113void
114slist_check(const slist_head *head)
115{
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 */
#define PG_USED_FOR_ASSERTS_ONLY
Definition: c.h:204
#define Assert(condition)
Definition: c.h:815
struct cursor * cur
Definition: ecpg.c:29
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:225
void slist_delete(slist_head *head, const slist_node *node)
Definition: ilist.c:31
#define dlist_check(head)
Definition: ilist.h:303
#define slist_check(head)
Definition: ilist.h:304
#define dlist_member_check(head, node)
Definition: ilist.h:302
struct cursor * next
Definition: type.h:148
dlist_node head
Definition: ilist.h:160
dlist_node * next
Definition: ilist.h:140
dlist_node * prev
Definition: ilist.h:139
slist_node head
Definition: ilist.h:238
slist_node * next
Definition: ilist.h:226