Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * ilist.c
4 : : * support for integrated/inline doubly- and singly- linked lists
5 : : *
6 : : * Portions Copyright (c) 1996-2024, 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
458 peter@eisentraut.org 31 :CBC 5290 : slist_delete(slist_head *head, const slist_node *node)
32 : : {
4198 alvherre@alvh.no-ip. 33 : 5290 : slist_node *last = &head->head;
34 : : slist_node *cur;
2489 tgl@sss.pgh.pa.us 35 : 5290 : bool found PG_USED_FOR_ASSERTS_ONLY = false;
36 : :
4198 alvherre@alvh.no-ip. 37 [ + - ]: 19840 : while ((cur = last->next) != NULL)
38 : : {
39 [ + + ]: 19840 : if (cur == node)
40 : : {
41 : 5290 : last->next = cur->next;
42 : : #ifdef USE_ASSERT_CHECKING
43 : 5290 : found = true;
44 : : #endif
45 : 5290 : break;
46 : : }
47 : 14550 : last = cur;
48 : : }
4196 tgl@sss.pgh.pa.us 49 [ - + ]: 5290 : Assert(found);
50 : :
51 : : slist_check(head);
4198 alvherre@alvh.no-ip. 52 : 5290 : }
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 */
|
