1 files changed, 109 insertions, 0 deletions
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 */