0001-initial-ilist-stuff-from-Andres.patch

From 5f72be6b33b43f9615700305e469e3e3698417dd Mon Sep 17 00:00:00 2001
From: Alvaro Herrera <alvherre@alvh.no-ip.org>
Date: Tue, 4 Sep 2012 19:07:38 -0300
Subject: [PATCH 1/3] initial ilist stuff from Andres

---
 src/backend/lib/Makefile     |    2 +-
 src/backend/lib/README.ilist |   43 ++++
 src/backend/lib/ilist.c      |  115 +++++++++++
 src/include/lib/ilist.h      |  454 ++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 613 insertions(+), 1 deletions(-)
 create mode 100644 src/backend/lib/README.ilist
 create mode 100644 src/backend/lib/ilist.c
 create mode 100644 src/include/lib/ilist.h

diff --git a/src/backend/lib/Makefile b/src/backend/lib/Makefile
index 2e1061e..c94297a 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 = dllist.o stringinfo.o ilist.o
 
 include $(top_srcdir)/src/backend/common.mk
diff --git a/src/backend/lib/README.ilist b/src/backend/lib/README.ilist
new file mode 100644
index 0000000..3a3d8a8
--- /dev/null
+++ b/src/backend/lib/README.ilist
@@ -0,0 +1,43 @@
+his is intended to be used in the following manner:
+
+#include "lib/ilist.h"
+
+typedef struct something_in_a_list
+{
+	int value;
+	int somethingelse;
+	Dlist_head values;
+} something_in_a_list;
+
+typedef struct value_in_a_list
+{
+	int data;
+	int somethingelse;
+	Dlist_node list_node;
+} value_in_a_list;
+
+something_in_a_list *somelist = get_blarg();
+
+Dlist_push_head(somelist, &get_value_in_a_list()->list_node);
+...
+Dlist_push_head(somelist, &get_value_in_a_list()->list_node);
+...
+...
+Dlist_node *node,
+		   *next;
+
+Dlist_foreach(node, somelist)
+{
+	value_in_a_list *val = ilist_container(value_in_a_list, list_node, node);
+	do_something_with_val(val);
+}
+
+Dlist_foreach_modify(node, next, somelist)
+{
+	/*
+	 * here we can inspect the node and maybe delete it.  Any other
+	 * manipulation is forbidden.
+	 */
+	if (node is to be deleted)
+		Dlist_delete(node);
+}
diff --git a/src/backend/lib/ilist.c b/src/backend/lib/ilist.c
new file mode 100644
index 0000000..d8bd4f3
--- /dev/null
+++ b/src/backend/lib/ilist.c
@@ -0,0 +1,115 @@
+/*-------------------------------------------------------------------------
+ *
+ * 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"
+
+/*
+ * If inlines are in use, include the header normally which will get us only
+ * the function definitions as inlines.  But if inlines aren't available,
+ * include the header with ILIST_USE_DEFINITION defined; this makes it pour in
+ * regular (not inline) function declarations and the corresponding (non
+ * inline) definitions.
+ */
+#ifndef USE_INLINE
+#define ILIST_USE_DEFINITION
+#endif
+#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 || !(&head->head))
+		elog(ERROR, "doubly linked list head is not properly initialized");
+
+	for (cur = head->head.next; cur != &head->head; cur = cur->next)
+	{
+		if (!(cur) ||
+			!(cur->next) ||
+			!(cur->prev) ||
+			!(cur->prev->next == cur) ||
+			!(cur->next->prev == cur))
+			elog(ERROR, "doubly linked list is corrupted");
+	}
+
+	for (cur = head->head.prev; cur != &head->head; cur = cur->prev)
+	{
+		if (!(cur) ||
+			!(cur->next) ||
+			!(cur->prev) ||
+			!(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 || !(&head->head))
+		elog(ERROR, "singly linked list head is not properly initialized");
+
+	/*
+	 * there isn't much we can test in a singly linked list except that its
+	 * really circular
+	 */
+	for (cur = head->head.next; cur != &head->head; cur = cur->next)
+		if (!cur)
+			elog(ERROR, "singly linked list is corrupted");
+}
+
+#endif   /* ILIST_DEBUG */
diff --git a/src/include/lib/ilist.h b/src/include/lib/ilist.h
new file mode 100644
index 0000000..2c29902
--- /dev/null
+++ b/src/include/lib/ilist.h
@@ -0,0 +1,454 @@
+/*-------------------------------------------------------------------------
+ *
+ * ilist.h
+ *		integrated/inline doubly- and singly-linked lists
+ *
+ * This implementation is as efficient as possible: the lists don't have
+ * any memory management overhead, because the list pointers are embedded
+ * within some larger structure.  Also, they are always circularly linked, even
+ * when empty; this enables many manipulations to be done without branches,
+ * which is beneficial performance-wise.
+ *
+ * See src/backend/lib/README.ilist for intended usage.
+ *
+ * Portions Copyright (c) 1996-2012, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * IDENTIFICATION
+ *		src/include/lib/ilist.h
+ *-------------------------------------------------------------------------
+ */
+#ifndef ILIST_H
+#define ILIST_H
+
+/*
+ * enable for extra debugging. This is rather expensive, so it's not enabled by
+ * default even with --enable-cassert.
+*/
+#undef ILIST_DEBUG
+
+/*
+ * struct to embed in other structs that need to be part of a doubly linked
+ * list.
+ */
+typedef struct dlist_node dlist_node;
+struct dlist_node
+{
+	dlist_node *prev;
+	dlist_node *next;
+};
+
+/*
+ * Head of a doubly linked list.
+ *
+ * Lists are internally *always* circularly linked, even when empty.
+ */
+typedef struct dlist_head
+{
+	dlist_node	head;
+} dlist_head;
+
+/*
+ * struct to embed in other structs that need to be part of a singly linked
+ * list.
+ */
+typedef struct slist_node slist_node;
+struct slist_node
+{
+	slist_node *next;
+};
+
+/*
+ * Head of a singly linked list.
+ *
+ * Lists are internally *always* circularly linked, even when empty.
+ */
+typedef struct slist_head
+{
+	slist_node	head;
+} slist_head;
+
+#ifdef USE_INLINE
+#define INLINE_IF_POSSIBLE static inline
+#define ILIST_USE_DEFINITION
+#else
+#define INLINE_IF_POSSIBLE
+
+/* Prototypes for functions we want to be inlined if possible */
+extern void dlist_init(dlist_head *head);
+extern void dlist_push_head(dlist_head *head, dlist_node *node);
+extern void dlist_push_tail(dlist_head *head, dlist_node *node);
+extern void dlist_insert_after(dlist_head *head,
+				   dlist_node *after, dlist_node *node);
+extern void dlist_insert_before(dlist_head *head,
+					dlist_node *before, dlist_node *node);
+extern void dlist_delete(dlist_head *head, dlist_node *node);
+extern dlist_node *dlist_pop_head(dlist_head *head);
+extern void dlist_move_head(dlist_head *head, dlist_node *node);
+extern bool dlist_has_next(dlist_head *head, dlist_node *node);
+extern bool dlist_has_prev(dlist_head *head, dlist_node *node);
+extern bool dlist_is_empty(dlist_head *head);
+extern void dlist_check(dlist_head *head);
+
+extern void slist_init(slist_head *head);
+extern void slist_push_head(slist_head *head, slist_node *node);
+extern slist_node *slist_pop_head(slist_head *head);
+extern void slist_insert_after(slist_head *head,
+				   slist_node *after, slist_node *node);
+extern bool slist_is_empty(slist_head *head);
+extern bool slist_has_next(slist_head *head,
+			   slist_node *node);
+#endif   /* USE_INLINE */
+
+/* These functions are too big to be inline, so they are in the C file always */
+extern void slist_delete(slist_head *head, slist_node *node);
+
+#ifdef ILIST_DEBUG
+extern void dlist_check(dlist_head *head);
+extern void slist_check(slist_head *head);
+#else
+/*
+ * These seemingly useless casts to void are here to keep the compiler quiet
+ * about the argument being unused in many functions in a non-debug compile,
+ * in which functions the only point of passing the list head pointer is to be
+ * able to run these checks.
+ */
+#define dlist_check(head)	(void) (head)
+#define slist_check(head)	(void) (head)
+#endif   /* ILIST_DEBUG */
+
+/*
+ * Return a pointer to the struct 'type' when the passed 'ptr' points to the
+ * element 'membername'.
+ */
+#define ilist_container(type, membername, ptr)								\
+	((type *)((char *)(ptr) - offsetof(type, membername)))
+
+/*
+ * The following function definitions are only used if inlining is supported by
+ * the compiler, or when included from a file that explicitly declares
+ * ILIST_USE_DEFINITION.
+ */
+#ifdef ILIST_USE_DEFINITION
+
+/*
+ * Initialize the head of a list. Previous state will be thrown away without
+ * any cleanup.
+ */
+INLINE_IF_POSSIBLE void
+dlist_init(dlist_head *head)
+{
+	head->head.next = head->head.prev = &head->head;
+
+	dlist_check(head);
+}
+
+/*
+ * inserts a node at the beginning of the list
+ */
+INLINE_IF_POSSIBLE void
+dlist_push_head(dlist_head *head, dlist_node *node)
+{
+	node->next = head->head.next;
+	node->prev = &head->head;
+	node->next->prev = node;
+	head->head.next = node;
+
+	dlist_check(head);
+}
+
+/*
+ * inserts a node at the end of the list
+ */
+INLINE_IF_POSSIBLE void
+dlist_push_tail(dlist_head *head, dlist_node *node)
+{
+	node->next = &head->head;
+	node->prev = head->head.prev;
+	node->prev->next = node;
+	head->head.prev = node;
+
+	dlist_check(head);
+}
+
+/*
+ * insert a node after another *in the same list*
+ */
+INLINE_IF_POSSIBLE void
+dlist_insert_after(dlist_head *head, dlist_node *after,
+				   dlist_node *node)
+{
+	dlist_check(head);
+
+	node->prev = after;
+	node->next = after->next;
+	after->next = node;
+	node->next->prev = node;
+
+	dlist_check(head);
+}
+
+/*
+ * insert a node after another *in the same list*
+ */
+INLINE_IF_POSSIBLE void
+dlist_insert_before(dlist_head *head, dlist_node *before,
+					dlist_node *node)
+{
+	dlist_check(head);
+
+	node->prev = before->prev;
+	node->next = before;
+	before->prev = node;
+	node->prev->next = node;
+
+	dlist_check(head);
+}
+
+/*
+ * deletes a node from a list
+ */
+INLINE_IF_POSSIBLE void
+dlist_delete(dlist_head *head, dlist_node *node)
+{
+	dlist_check(head);
+
+	node->prev->next = node->next;
+	node->next->prev = node->prev;
+
+	dlist_check(head);
+}
+
+/*
+ * deletes the first node from a list or returns NULL
+ */
+INLINE_IF_POSSIBLE dlist_node *
+dlist_pop_head(dlist_head *head)
+{
+	dlist_node *ret;
+
+	if (&head->head == head->head.next)
+		return NULL;
+
+	ret = head->head.next;
+	dlist_delete(head, head->head.next);
+	return ret;
+}
+
+/*
+ * moves an element (that has to be in the list) to the head of the list
+ */
+INLINE_IF_POSSIBLE void
+dlist_move_head(dlist_head *head, dlist_node *node)
+{
+	/* fast path if it's already at the head */
+	if (&head->head == node)
+		return;
+
+	dlist_delete(head, node);
+	dlist_push_head(head, node);
+
+	dlist_check(head);
+}
+
+/*
+ * Check whether the passed node is the last element in the list
+ */
+INLINE_IF_POSSIBLE bool
+dlist_has_next(dlist_head *head, dlist_node *node)
+{
+	return node->next != &head->head;
+}
+
+/*
+ * Check whether the passed node is the first element in the list
+ */
+INLINE_IF_POSSIBLE bool
+dlist_has_prev(dlist_head *head, dlist_node *node)
+{
+	return node->prev != &head->head;
+}
+
+/*
+ * Check whether the list is empty.
+ */
+INLINE_IF_POSSIBLE bool
+dlist_is_empty(dlist_head *head)
+{
+	return head->head.next == &head->head;
+}
+#endif   /* ILIST_USE_DEFINITION */
+
+/*
+ * Return the value of first element in the list if there is one, return NULL
+ * otherwise.
+ *
+ * ptr *will* be evaluated multiple times.
+ */
+#define dlist_get_head(type, membername, ptr)								\
+(																			\
+	(&((ptr)->head) == (ptr)->head.next) ?									\
+		NULL : ilist_container(type, membername, (ptr)->head.next)			\
+)
+
+/*
+ * Return the value of the first element. This will return corrupt data if
+ * there is no element in the list.
+ */
+#define dlist_get_head_unchecked(type, membername, ptr)						\
+	ilist_container(type, membername, (ptr)->head.next)
+
+/*
+ * Return the value of the last element in the list if there is one, return
+ * NULL otherwise.
+ *
+ * ptr *will* be evaluated multiple times.
+ */
+#define dlist_get_tail(type, membername, ptr)								\
+(																			\
+	(&((ptr)->head) == (ptr)->head.prev) ?									\
+		NULL : ilist_container(type, membername, (ptr)->head.prev)			\
+)
+
+/*
+ * Iterate through the list storing the current element in the variable
+ * 'name'. 'ptr' will be evaluated repeatedly.
+ *
+ * It is *not* allowed to manipulate the list during iteration.
+ */
+#define dlist_foreach(name, ptr)											\
+	for (name = (ptr)->head.next; name != &(ptr)->head; name = name->next)
+
+/*
+ * Iterate through the list storing the current element in the variable 'name'
+ * and also storing the next list element in the variable 'nxt'.
+ *
+ * It is allowed to delete the current element from the list. Every other
+ * manipulation can lead to corruption.
+ */
+#define dlist_foreach_modify(name, nxt, ptr)								\
+	for (name = (ptr)->head.next, nxt = name->next;							\
+		 name != &(ptr)->head;												\
+		 name = nxt, nxt = name->next)
+
+/*
+ * Iterate through the list in reverse order storing the current element in the
+ * variable 'name'. 'ptr' will be evaluated repeatedly.
+ *
+ * It is *not* allowed to manipulate the list during iteration.
+ */
+#define dlist_reverse_foreach(name, ptr)									\
+	for (name = (ptr)->head.prev; name != &(ptr)->head; name = name->prev)
+
+
+#ifdef ILIST_USE_DEFINITION
+
+/*
+ * Initialize a singly linked list.
+ */
+INLINE_IF_POSSIBLE void
+slist_init(slist_head *head)
+{
+	head->head.next = NULL;
+
+	slist_check(head);
+}
+
+/*
+ * Install a new element as head of the list, pushing the original head to the
+ * second position.
+ */
+INLINE_IF_POSSIBLE void
+slist_push_head(slist_head *head, slist_node *node)
+{
+	node->next = head->head.next;
+	head->head.next = node;
+
+	slist_check(head);
+}
+
+/*
+ * Returns the first element of the list, removing it.
+ * Fails if the list is empty
+ */
+INLINE_IF_POSSIBLE slist_node *
+slist_pop_head(slist_head *head)
+{
+	slist_node *node;
+
+	node = head->head.next;
+	head->head.next = head->head.next->next;
+
+	slist_check(head);
+
+	return node;
+}
+
+/*
+ * Insert a new element after the listed one.
+ */
+INLINE_IF_POSSIBLE void
+slist_insert_after(slist_head *head, slist_node *after,
+				   slist_node *node)
+{
+	node->next = after->next;
+	after->next = node;
+
+	slist_check(head);
+}
+
+/*
+ * Is the list empty?
+ */
+INLINE_IF_POSSIBLE bool
+slist_is_empty(slist_head *head)
+{
+	slist_check(head);
+
+	return head->head.next == NULL;
+}
+
+/*
+ * Is there at least one more element in the list?
+ */
+INLINE_IF_POSSIBLE bool
+slist_has_next(slist_head *head,
+			   slist_node *node)
+{
+	slist_check(head);
+
+	return node->next != NULL;
+}
+#endif   /* ILIST_USE_DEFINITION */
+
+#define slist_get_head(type, membername, ptr)								\
+(																			\
+	slist_is_empty(ptr) ? NULL :											\
+		ilist_container(type, membername, (ptr).next) 						\
+)
+
+#define slist_get_head_unchecked(type, membername, ptr)						\
+	ilist_container(type, membername, (ptr)->head.next)
+
+/*
+ * Iterate through the list storing the current element in the variable
+ * 'name'. 'ptr' will be evaluated repeatedly.
+ *
+ * It is *not* allowed to manipulate the list during iteration.
+ */
+#define slist_foreach(name, ptr)											\
+	for (name = (ptr)->head.next; name != NULL; name = name->next)
+
+/*
+ * Iterate through the list storing the current element in the variable 'name'
+ * and also storing the next list element in the variable 'nxt'.
+ *
+ * It is allowed to delete the current element from the list. Every other
+ * manipulation can lead to corruption.
+ */
+#define slist_foreach_modify(name, nxt, ptr)								\
+	for (name = (ptr)->head.next, nxt = name ? name->next : NULL;			\
+		name != NULL;														\
+		name = nxt, nxt = name ? name->next : NULL)
+
+#endif   /* ILIST_H */
-- 
1.7.2.5