Embedded list interface

Provide a common implementation of embedded singly-linked and
doubly-linked lists.  "Embedded" in the sense that the nodes'
next/previous pointers exist within some larger struct; this design
choice reduces memory allocation overhead.

Most of the implementation uses inlineable functions (where supported),
for performance.

Some existing uses of both types of lists have been converted to the new
code, for demonstration purposes.  Other uses can (and probably will) be
converted in the future.  Since dllist.c is unused after this conversion,
it has been removed.

Author: Andres Freund
Some tweaks by me
Reviewed by Tom Lane, Peter Geoghegan

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 */