Merge branch 'XL_MASTER_MERGE_9_4' into XL_NEW_MASTER

Conflicts:
	src/test/regress/expected/aggregates.out
	src/test/regress/expected/create_index.out
	src/test/regress/expected/inherit.out
	src/test/regress/expected/join.out
	src/test/regress/expected/window.out
	src/test/regress/expected/with.out

5 files changed, 453 insertions, 254 deletions

diff --git a/src/backend/lib/Makefile b/src/backend/lib/Makefile
index 2e1061e24a..327a1bc16d 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 binaryheap.o stringinfo.o
 
 include $(top_srcdir)/src/backend/common.mk
diff --git a/src/backend/lib/binaryheap.c b/src/backend/lib/binaryheap.c
new file mode 100644
index 0000000000..24ba55b451
--- /dev/null
+++ b/src/backend/lib/binaryheap.c
@@ -0,0 +1,307 @@
+/*-------------------------------------------------------------------------
+ *
+ * binaryheap.c
+ *	  A simple binary heap implementaion
+ *
+ * Portions Copyright (c) 2012-2014, PostgreSQL Global Development Group
+ *
+ * IDENTIFICATION
+ *	  src/backend/lib/binaryheap.c
+ *
+ *-------------------------------------------------------------------------
+ */
+
+#include "postgres.h"
+
+#include <math.h>
+
+#include "lib/binaryheap.h"
+
+static void sift_down(binaryheap *heap, int node_off);
+static void sift_up(binaryheap *heap, int node_off);
+static inline void swap_nodes(binaryheap *heap, int a, int b);
+
+/*
+ * binaryheap_allocate
+ *
+ * Returns a pointer to a newly-allocated heap that has the capacity to
+ * store the given number of nodes, with the heap property defined by
+ * the given comparator function, which will be invoked with the additional
+ * argument specified by 'arg'.
+ */
+binaryheap *
+binaryheap_allocate(int capacity, binaryheap_comparator compare, void *arg)
+{
+	int			sz;
+	binaryheap *heap;
+
+	sz = offsetof(binaryheap, bh_nodes) +sizeof(Datum) * capacity;
+	heap = (binaryheap *) palloc(sz);
+	heap->bh_space = capacity;
+	heap->bh_compare = compare;
+	heap->bh_arg = arg;
+
+	heap->bh_size = 0;
+	heap->bh_has_heap_property = true;
+
+	return heap;
+}
+
+/*
+ * binaryheap_reset
+ *
+ * Resets the heap to an empty state, losing its data content but not the
+ * parameters passed at allocation.
+ */
+void
+binaryheap_reset(binaryheap *heap)
+{
+	heap->bh_size = 0;
+	heap->bh_has_heap_property = true;
+}
+
+/*
+ * binaryheap_free
+ *
+ * Releases memory used by the given binaryheap.
+ */
+void
+binaryheap_free(binaryheap *heap)
+{
+	pfree(heap);
+}
+
+/*
+ * These utility functions return the offset of the left child, right
+ * child, and parent of the node at the given index, respectively.
+ *
+ * The heap is represented as an array of nodes, with the root node
+ * stored at index 0. The left child of node i is at index 2*i+1, and
+ * the right child at 2*i+2. The parent of node i is at index (i-1)/2.
+ */
+
+static inline int
+left_offset(int i)
+{
+	return 2 * i + 1;
+}
+
+static inline int
+right_offset(int i)
+{
+	return 2 * i + 2;
+}
+
+static inline int
+parent_offset(int i)
+{
+	return (i - 1) / 2;
+}
+
+/*
+ * binaryheap_add_unordered
+ *
+ * Adds the given datum to the end of the heap's list of nodes in O(1) without
+ * preserving the heap property. This is a convenience to add elements quickly
+ * to a new heap. To obtain a valid heap, one must call binaryheap_build()
+ * afterwards.
+ */
+void
+binaryheap_add_unordered(binaryheap *heap, Datum d)
+{
+	if (heap->bh_size >= heap->bh_space)
+		elog(ERROR, "out of binary heap slots");
+	heap->bh_has_heap_property = false;
+	heap->bh_nodes[heap->bh_size] = d;
+	heap->bh_size++;
+}
+
+/*
+ * binaryheap_build
+ *
+ * Assembles a valid heap in O(n) from the nodes added by
+ * binaryheap_add_unordered(). Not needed otherwise.
+ */
+void
+binaryheap_build(binaryheap *heap)
+{
+	int			i;
+
+	for (i = parent_offset(heap->bh_size - 1); i >= 0; i--)
+		sift_down(heap, i);
+	heap->bh_has_heap_property = true;
+}
+
+/*
+ * binaryheap_add
+ *
+ * Adds the given datum to the heap in O(log n) time, while preserving
+ * the heap property.
+ */
+void
+binaryheap_add(binaryheap *heap, Datum d)
+{
+	if (heap->bh_size >= heap->bh_space)
+		elog(ERROR, "out of binary heap slots");
+	heap->bh_nodes[heap->bh_size] = d;
+	heap->bh_size++;
+	sift_up(heap, heap->bh_size - 1);
+}
+
+/*
+ * binaryheap_first
+ *
+ * Returns a pointer to the first (root, topmost) node in the heap
+ * without modifying the heap. The caller must ensure that this
+ * routine is not used on an empty heap. Always O(1).
+ */
+Datum
+binaryheap_first(binaryheap *heap)
+{
+	Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property);
+	return heap->bh_nodes[0];
+}
+
+/*
+ * binaryheap_remove_first
+ *
+ * Removes the first (root, topmost) node in the heap and returns a
+ * pointer to it after rebalancing the heap. The caller must ensure
+ * that this routine is not used on an empty heap. O(log n) worst
+ * case.
+ */
+Datum
+binaryheap_remove_first(binaryheap *heap)
+{
+	Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property);
+
+	if (heap->bh_size == 1)
+	{
+		heap->bh_size--;
+		return heap->bh_nodes[0];
+	}
+
+	/*
+	 * Swap the root and last nodes, decrease the size of the heap (i.e.
+	 * remove the former root node) and sift the new root node down to its
+	 * correct position.
+	 */
+	swap_nodes(heap, 0, heap->bh_size - 1);
+	heap->bh_size--;
+	sift_down(heap, 0);
+
+	return heap->bh_nodes[heap->bh_size];
+}
+
+/*
+ * binaryheap_replace_first
+ *
+ * Replace the topmost element of a non-empty heap, preserving the heap
+ * property.  O(1) in the best case, or O(log n) if it must fall back to
+ * sifting the new node down.
+ */
+void
+binaryheap_replace_first(binaryheap *heap, Datum d)
+{
+	Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property);
+
+	heap->bh_nodes[0] = d;
+
+	if (heap->bh_size > 1)
+		sift_down(heap, 0);
+}
+
+/*
+ * Swap the contents of two nodes.
+ */
+static inline void
+swap_nodes(binaryheap *heap, int a, int b)
+{
+	Datum		swap;
+
+	swap = heap->bh_nodes[a];
+	heap->bh_nodes[a] = heap->bh_nodes[b];
+	heap->bh_nodes[b] = swap;
+}
+
+/*
+ * Sift a node up to the highest position it can hold according to the
+ * comparator.
+ */
+static void
+sift_up(binaryheap *heap, int node_off)
+{
+	while (node_off != 0)
+	{
+		int			cmp;
+		int			parent_off;
+
+		/*
+		 * If this node is smaller than its parent, the heap condition is
+		 * satisfied, and we're done.
+		 */
+		parent_off = parent_offset(node_off);
+		cmp = heap->bh_compare(heap->bh_nodes[node_off],
+							   heap->bh_nodes[parent_off],
+							   heap->bh_arg);
+		if (cmp <= 0)
+			break;
+
+		/*
+		 * Otherwise, swap the node and its parent and go on to check the
+		 * node's new parent.
+		 */
+		swap_nodes(heap, node_off, parent_off);
+		node_off = parent_off;
+	}
+}
+
+/*
+ * Sift a node down from its current position to satisfy the heap
+ * property.
+ */
+static void
+sift_down(binaryheap *heap, int node_off)
+{
+	while (true)
+	{
+		int			left_off = left_offset(node_off);
+		int			right_off = right_offset(node_off);
+		int			swap_off = 0;
+
+		/* Is the left child larger than the parent? */
+		if (left_off < heap->bh_size &&
+			heap->bh_compare(heap->bh_nodes[node_off],
+							 heap->bh_nodes[left_off],
+							 heap->bh_arg) < 0)
+			swap_off = left_off;
+
+		/* Is the right child larger than the parent? */
+		if (right_off < heap->bh_size &&
+			heap->bh_compare(heap->bh_nodes[node_off],
+							 heap->bh_nodes[right_off],
+							 heap->bh_arg) < 0)
+		{
+			/* swap with the larger child */
+			if (!swap_off ||
+				heap->bh_compare(heap->bh_nodes[left_off],
+								 heap->bh_nodes[right_off],
+								 heap->bh_arg) < 0)
+				swap_off = right_off;
+		}
+
+		/*
+		 * If we didn't find anything to swap, the heap condition is
+		 * satisfied, and we're done.
+		 */
+		if (!swap_off)
+			break;
+
+		/*
+		 * Otherwise, swap the node with the child that violates the heap
+		 * property; then go on to check its children.
+		 */
+		swap_nodes(heap, swap_off, node_off);
+		node_off = swap_off;
+	}
+}
diff --git a/src/backend/lib/dllist.c b/src/backend/lib/dllist.c
deleted file mode 100644
index 52af56a079..0000000000
--- 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 0000000000..73a647381a
--- /dev/null
+++ b/src/backend/lib/ilist.c
@@ -0,0 +1,114 @@
+/*-------------------------------------------------------------------------
+ *
+ * ilist.c
+ *	  support for integrated/inline doubly- and singly- linked lists
+ *
+ * Portions Copyright (c) 1996-2014, 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"
+
+/*
+ * Delete 'node' from list.
+ *
+ * It is not allowed to delete a 'node' which is not in the list 'head'
+ *
+ * Caution: this is O(n); consider using slist_delete_current() instead.
+ */
+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;
+	}
+	Assert(found);
+
+	slist_check(head);
+}
+
+#ifdef ILIST_DEBUG
+/*
+ * Verify integrity of a doubly linked list
+ */
+void
+dlist_check(dlist_head *head)
+{
+	dlist_node *cur;
+
+	if (head == NULL)
+		elog(ERROR, "doubly linked list head address is NULL");
+
+	if (head->head.next == NULL && head->head.prev == NULL)
+		return;					/* OK, initialized as zeroes */
+
+	/* 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 list head address is NULL");
+
+	/*
+	 * there isn't much we can test in a singly linked list except 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 */
diff --git a/src/backend/lib/stringinfo.c b/src/backend/lib/stringinfo.c
index d9e93e1de7..7d0309079d 100644
--- a/src/backend/lib/stringinfo.c
+++ b/src/backend/lib/stringinfo.c
@@ -6,7 +6,7 @@
  * It can be used to buffer either ordinary C strings (null-terminated text)
  * or arbitrary binary data.  All storage is allocated with palloc().
  *
- * Portions Copyright (c) 1996-2012, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1996-2014, PostgreSQL Global Development Group
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  *	  src/backend/lib/stringinfo.c
@@ -80,18 +80,18 @@ appendStringInfo(StringInfo str, const char *fmt,...)
 	for (;;)
 	{
 		va_list		args;
-		bool		success;
+		int			needed;
 
 		/* Try to format the data. */
 		va_start(args, fmt);
-		success = appendStringInfoVA(str, fmt, args);
+		needed = appendStringInfoVA(str, fmt, args);
 		va_end(args);
 
-		if (success)
-			break;
+		if (needed == 0)
+			break;				/* success */
 
-		/* Double the buffer size and try again. */
-		enlargeStringInfo(str, str->maxlen);
+		/* Increase the buffer size and try again. */
+		enlargeStringInfo(str, needed);
 	}
 }
 
@@ -99,60 +99,52 @@ appendStringInfo(StringInfo str, const char *fmt,...)
  * appendStringInfoVA
  *
  * Attempt to format text data under the control of fmt (an sprintf-style
- * format string) and append it to whatever is already in str.	If successful
- * return true; if not (because there's not enough space), return false
- * without modifying str.  Typically the caller would enlarge str and retry
- * on false return --- see appendStringInfo for standard usage pattern.
+ * format string) and append it to whatever is already in str.  If successful
+ * return zero; if not (because there's not enough space), return an estimate
+ * of the space needed, without modifying str.  Typically the caller should
+ * pass the return value to enlargeStringInfo() before trying again; see
+ * appendStringInfo for standard usage pattern.
  *
  * XXX This API is ugly, but there seems no alternative given the C spec's
  * restrictions on what can portably be done with va_list arguments: you have
  * to redo va_start before you can rescan the argument list, and we can't do
  * that from here.
  */
-bool
+int
 appendStringInfoVA(StringInfo str, const char *fmt, va_list args)
 {
-	int			avail,
-				nprinted;
+	int			avail;
+	size_t		nprinted;
 
 	Assert(str != NULL);
 
 	/*
 	 * If there's hardly any space, don't bother trying, just fail to make the
-	 * caller enlarge the buffer first.
+	 * caller enlarge the buffer first.  We have to guess at how much to
+	 * enlarge, since we're skipping the formatting work.
 	 */
-	avail = str->maxlen - str->len - 1;
+	avail = str->maxlen - str->len;
 	if (avail < 16)
-		return false;
+		return 32;
 
-	/*
-	 * Assert check here is to catch buggy vsnprintf that overruns the
-	 * specified buffer length.  Solaris 7 in 64-bit mode is an example of a
-	 * platform with such a bug.
-	 */
-#ifdef USE_ASSERT_CHECKING
-	str->data[str->maxlen - 1] = '\0';
-#endif
-
-	nprinted = vsnprintf(str->data + str->len, avail, fmt, args);
+	nprinted = pvsnprintf(str->data + str->len, (size_t) avail, fmt, args);
 
-	Assert(str->data[str->maxlen - 1] == '\0');
-
-	/*
-	 * Note: some versions of vsnprintf return the number of chars actually
-	 * stored, but at least one returns -1 on failure. Be conservative about
-	 * believing whether the print worked.
-	 */
-	if (nprinted >= 0 && nprinted < avail - 1)
+	if (nprinted < (size_t) avail)
 	{
 		/* Success.  Note nprinted does not include trailing null. */
-		str->len += nprinted;
-		return true;
+		str->len += (int) nprinted;
+		return 0;
 	}
 
 	/* Restore the trailing null so that str is unmodified. */
 	str->data[str->len] = '\0';
-	return false;
+
+	/*
+	 * Return pvsnprintf's estimate of the space needed.  (Although this is
+	 * given as a size_t, we know it will fit in int because it's not more
+	 * than MaxAllocSize.)
+	 */
+	return (int) nprinted;
 }
 
 /*
@@ -255,7 +247,7 @@ enlargeStringInfo(StringInfo str, int needed)
 	int			newlen;
 
 	/*
-	 * Guard against out-of-range "needed" values.	Without this, we can get
+	 * Guard against out-of-range "needed" values.  Without this, we can get
 	 * an overflow or infinite loop in the following.
 	 */
 	if (needed < 0)				/* should not happen */