PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
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-2017, 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
32 {
33  slist_node *last = &head->head;
34  slist_node *cur;
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  * Verify integrity of a doubly linked list
57  */
58 void
60 {
61  dlist_node *cur;
62 
63  if (head == NULL)
64  elog(ERROR, "doubly linked list head address is NULL");
65 
66  if (head->head.next == NULL && head->head.prev == NULL)
67  return; /* OK, initialized as zeroes */
68 
69  /* iterate in forward direction */
70  for (cur = head->head.next; cur != &head->head; cur = cur->next)
71  {
72  if (cur == NULL ||
73  cur->next == NULL ||
74  cur->prev == NULL ||
75  cur->prev->next != cur ||
76  cur->next->prev != cur)
77  elog(ERROR, "doubly linked list is corrupted");
78  }
79 
80  /* iterate in backward direction */
81  for (cur = head->head.prev; cur != &head->head; cur = cur->prev)
82  {
83  if (cur == NULL ||
84  cur->next == NULL ||
85  cur->prev == NULL ||
86  cur->prev->next != cur ||
87  cur->next->prev != cur)
88  elog(ERROR, "doubly linked list is corrupted");
89  }
90 }
91 
92 /*
93  * Verify integrity of a singly linked list
94  */
95 void
97 {
98  slist_node *cur;
99 
100  if (head == NULL)
101  elog(ERROR, "singly linked list head address is NULL");
102 
103  /*
104  * there isn't much we can test in a singly linked list except that it
105  * actually ends sometime, i.e. hasn't introduced a cycle or similar
106  */
107  for (cur = head->head.next; cur != NULL; cur = cur->next)
108  ;
109 }
110 
111 #endif /* ILIST_DEBUG */
slist_node head
Definition: ilist.h:205
struct cursor * cur
Definition: ecpg.c:28
dlist_node * next
Definition: ilist.h:124
#define ERROR
Definition: elog.h:43
#define slist_check(head)
Definition: ilist.h:268
slist_node * next
Definition: ilist.h:193
#define NULL
Definition: c.h:229
#define Assert(condition)
Definition: c.h:675
dlist_node * prev
Definition: ilist.h:123
#define dlist_check(head)
Definition: ilist.h:267
#define elog
Definition: elog.h:219
#define PG_USED_FOR_ASSERTS_ONLY
Definition: c.h:990
dlist_node head
Definition: ilist.h:144
void slist_delete(slist_head *head, slist_node *node)
Definition: ilist.c:31