aboutsummaryrefslogtreecommitdiff
path: root/src/backend/lib
diff options
context:
space:
mode:
Diffstat (limited to 'src/backend/lib')
-rw-r--r--src/backend/lib/Makefile2
-rw-r--r--src/backend/lib/dllist.c214
-rw-r--r--src/backend/lib/ilist.c109
3 files changed, 110 insertions, 215 deletions
diff --git a/src/backend/lib/Makefile b/src/backend/lib/Makefile
index 2e1061e24aa..98ce3d7e4ad 100644
--- a/src/backend/lib/Makefile
+++ b/src/backend/lib/Makefile
@@ -12,6 +12,6 @@ subdir = src/backend/lib
top_builddir = ../../..
include $(top_builddir)/src/Makefile.global
-OBJS = dllist.o stringinfo.o
+OBJS = ilist.o stringinfo.o
include $(top_srcdir)/src/backend/common.mk
diff --git a/src/backend/lib/dllist.c b/src/backend/lib/dllist.c
deleted file mode 100644
index 52af56a0795..00000000000
--- a/src/backend/lib/dllist.c
+++ /dev/null
@@ -1,214 +0,0 @@
-/*-------------------------------------------------------------------------
- *
- * dllist.c
- * this is a simple doubly linked list implementation
- * the elements of the lists are void*
- *
- * Portions Copyright (c) 1996-2012, PostgreSQL Global Development Group
- * Portions Copyright (c) 1994, Regents of the University of California
- *
- *
- * IDENTIFICATION
- * src/backend/lib/dllist.c
- *
- *-------------------------------------------------------------------------
- */
-#include "postgres.h"
-
-#include "lib/dllist.h"
-
-
-Dllist *
-DLNewList(void)
-{
- Dllist *l;
-
- l = (Dllist *) palloc(sizeof(Dllist));
-
- l->dll_head = NULL;
- l->dll_tail = NULL;
-
- return l;
-}
-
-void
-DLInitList(Dllist *list)
-{
- list->dll_head = NULL;
- list->dll_tail = NULL;
-}
-
-/*
- * free up a list and all the nodes in it --- but *not* whatever the nodes
- * might point to!
- */
-void
-DLFreeList(Dllist *list)
-{
- Dlelem *curr;
-
- while ((curr = DLRemHead(list)) != NULL)
- pfree(curr);
-
- pfree(list);
-}
-
-Dlelem *
-DLNewElem(void *val)
-{
- Dlelem *e;
-
- e = (Dlelem *) palloc(sizeof(Dlelem));
-
- e->dle_next = NULL;
- e->dle_prev = NULL;
- e->dle_val = val;
- e->dle_list = NULL;
- return e;
-}
-
-void
-DLInitElem(Dlelem *e, void *val)
-{
- e->dle_next = NULL;
- e->dle_prev = NULL;
- e->dle_val = val;
- e->dle_list = NULL;
-}
-
-void
-DLFreeElem(Dlelem *e)
-{
- pfree(e);
-}
-
-void
-DLRemove(Dlelem *e)
-{
- Dllist *l = e->dle_list;
-
- if (e->dle_prev)
- e->dle_prev->dle_next = e->dle_next;
- else
- {
- /* must be the head element */
- Assert(e == l->dll_head);
- l->dll_head = e->dle_next;
- }
- if (e->dle_next)
- e->dle_next->dle_prev = e->dle_prev;
- else
- {
- /* must be the tail element */
- Assert(e == l->dll_tail);
- l->dll_tail = e->dle_prev;
- }
-
- e->dle_next = NULL;
- e->dle_prev = NULL;
- e->dle_list = NULL;
-}
-
-void
-DLAddHead(Dllist *l, Dlelem *e)
-{
- e->dle_list = l;
-
- if (l->dll_head)
- l->dll_head->dle_prev = e;
- e->dle_next = l->dll_head;
- e->dle_prev = NULL;
- l->dll_head = e;
-
- if (l->dll_tail == NULL) /* if this is first element added */
- l->dll_tail = e;
-}
-
-void
-DLAddTail(Dllist *l, Dlelem *e)
-{
- e->dle_list = l;
-
- if (l->dll_tail)
- l->dll_tail->dle_next = e;
- e->dle_prev = l->dll_tail;
- e->dle_next = NULL;
- l->dll_tail = e;
-
- if (l->dll_head == NULL) /* if this is first element added */
- l->dll_head = e;
-}
-
-Dlelem *
-DLRemHead(Dllist *l)
-{
- /* remove and return the head */
- Dlelem *result = l->dll_head;
-
- if (result == NULL)
- return result;
-
- if (result->dle_next)
- result->dle_next->dle_prev = NULL;
-
- l->dll_head = result->dle_next;
-
- if (result == l->dll_tail) /* if the head is also the tail */
- l->dll_tail = NULL;
-
- result->dle_next = NULL;
- result->dle_list = NULL;
-
- return result;
-}
-
-Dlelem *
-DLRemTail(Dllist *l)
-{
- /* remove and return the tail */
- Dlelem *result = l->dll_tail;
-
- if (result == NULL)
- return result;
-
- if (result->dle_prev)
- result->dle_prev->dle_next = NULL;
-
- l->dll_tail = result->dle_prev;
-
- if (result == l->dll_head) /* if the tail is also the head */
- l->dll_head = NULL;
-
- result->dle_prev = NULL;
- result->dle_list = NULL;
-
- return result;
-}
-
-/* Same as DLRemove followed by DLAddHead, but faster */
-void
-DLMoveToFront(Dlelem *e)
-{
- Dllist *l = e->dle_list;
-
- if (l->dll_head == e)
- return; /* Fast path if already at front */
-
- Assert(e->dle_prev != NULL); /* since it's not the head */
- e->dle_prev->dle_next = e->dle_next;
-
- if (e->dle_next)
- e->dle_next->dle_prev = e->dle_prev;
- else
- {
- /* must be the tail element */
- Assert(e == l->dll_tail);
- l->dll_tail = e->dle_prev;
- }
-
- l->dll_head->dle_prev = e;
- e->dle_next = l->dll_head;
- e->dle_prev = NULL;
- l->dll_head = e;
- /* We need not check dll_tail, since there must have been > 1 entry */
-}
diff --git a/src/backend/lib/ilist.c b/src/backend/lib/ilist.c
new file mode 100644
index 00000000000..c5831acd67d
--- /dev/null
+++ b/src/backend/lib/ilist.c
@@ -0,0 +1,109 @@
+/*-------------------------------------------------------------------------
+ *
+ * ilist.c
+ * support for integrated/inline doubly- and singly- linked lists
+ *
+ * Portions Copyright (c) 1996-2012, 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"
+
+/*
+ * removes a node from a list
+ *
+ * Attention: 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;
+ }
+
+ slist_check(head);
+ Assert(found);
+}
+
+#ifdef ILIST_DEBUG
+/*
+ * Verify integrity of a doubly linked list
+ */
+void
+dlist_check(dlist_head *head)
+{
+ dlist_node *cur;
+
+ if (head == NULL || !(&head->head))
+ elog(ERROR, "doubly linked list head is not properly initialized");
+
+ /* 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 is NULL");
+
+ /*
+ * there isn't much we can test in a singly linked list other 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 */
generated by cgit v1.2.3 (git 2.25.1) at 2025-06-23 16:39:53 +0000