list_hacks.patch

diff --git a/src/backend/nodes/list.c b/src/backend/nodes/list.c
index 63cc815315..b8ee10017e 100644
--- a/src/backend/nodes/list.c
+++ b/src/backend/nodes/list.c
@@ -67,9 +67,14 @@ check_list_invariants(const List *list)
  * Since empty non-NIL lists are invalid, new_list() sets the initial length
  * to min_size, effectively marking that number of cells as valid; the caller
  * is responsible for filling in their data.
+ *
+ * forprepend marks we expect this list to be mostly built with lcons and
+ * friends.  In this case we'll mark the first property so that the first
+ * item to be added to the list is added at the end, leaving space in front
+ * for new items.
  */
 static List *
-new_list(NodeTag type, int min_size)
+new_list(NodeTag type, int min_size, bool forprepend)
 {
 	List	   *newlist;
 	int			max_size;
@@ -101,6 +106,7 @@ new_list(NodeTag type, int min_size)
 	newlist = (List *) palloc(sizeof(*newlist));
 	newlist->type = type;
 	newlist->length = min_size;
+	newlist->first = forprepend ? max_size - 1 : 0;
 	newlist->max_length = max_size;
 	newlist->elements = (ListCell *) palloc(max_size * sizeof(ListCell));
 
@@ -152,7 +158,7 @@ enlarge_list(List *list, int min_size)
 		ListCell   *newelements;
 
 		newelements = (ListCell *) palloc(new_max_len * sizeof(ListCell));
-		memcpy(newelements, list->elements,
+		memcpy(&newelements[list->first], &list->elements[list->first],
 			   list->length * sizeof(ListCell));
 		pfree(list->elements);
 		list->elements = newelements;
@@ -169,7 +175,7 @@ enlarge_list(List *list, int min_size)
 List *
 list_make1(void *datum1)
 {
-	List	   *list = new_list(T_List, 1);
+	List	   *list = new_list(T_List, 1, false);
 
 	lfirst(&list->elements[0]) = datum1;
 	check_list_invariants(list);
@@ -179,7 +185,7 @@ list_make1(void *datum1)
 List *
 list_make2(void *datum1, void *datum2)
 {
-	List	   *list = new_list(T_List, 2);
+	List	   *list = new_list(T_List, 2, false);
 
 	lfirst(&list->elements[0]) = datum1;
 	lfirst(&list->elements[1]) = datum2;
@@ -190,7 +196,7 @@ list_make2(void *datum1, void *datum2)
 List *
 list_make3(void *datum1, void *datum2, void *datum3)
 {
-	List	   *list = new_list(T_List, 3);
+	List	   *list = new_list(T_List, 3, false);
 
 	lfirst(&list->elements[0]) = datum1;
 	lfirst(&list->elements[1]) = datum2;
@@ -202,7 +208,7 @@ list_make3(void *datum1, void *datum2, void *datum3)
 List *
 list_make4(void *datum1, void *datum2, void *datum3, void *datum4)
 {
-	List	   *list = new_list(T_List, 4);
+	List	   *list = new_list(T_List, 4, false);
 
 	lfirst(&list->elements[0]) = datum1;
 	lfirst(&list->elements[1]) = datum2;
@@ -215,7 +221,7 @@ list_make4(void *datum1, void *datum2, void *datum3, void *datum4)
 List *
 list_make1_int(int datum1)
 {
-	List	   *list = new_list(T_IntList, 1);
+	List	   *list = new_list(T_IntList, 1, false);
 
 	lfirst_int(&list->elements[0]) = datum1;
 	check_list_invariants(list);
@@ -225,7 +231,7 @@ list_make1_int(int datum1)
 List *
 list_make2_int(int datum1, int datum2)
 {
-	List	   *list = new_list(T_IntList, 2);
+	List	   *list = new_list(T_IntList, 2, false);
 
 	lfirst_int(&list->elements[0]) = datum1;
 	lfirst_int(&list->elements[1]) = datum2;
@@ -236,7 +242,7 @@ list_make2_int(int datum1, int datum2)
 List *
 list_make3_int(int datum1, int datum2, int datum3)
 {
-	List	   *list = new_list(T_IntList, 3);
+	List	   *list = new_list(T_IntList, 3, false);
 
 	lfirst_int(&list->elements[0]) = datum1;
 	lfirst_int(&list->elements[1]) = datum2;
@@ -248,7 +254,7 @@ list_make3_int(int datum1, int datum2, int datum3)
 List *
 list_make4_int(int datum1, int datum2, int datum3, int datum4)
 {
-	List	   *list = new_list(T_IntList, 4);
+	List	   *list = new_list(T_IntList, 4, false);
 
 	lfirst_int(&list->elements[0]) = datum1;
 	lfirst_int(&list->elements[1]) = datum2;
@@ -261,7 +267,7 @@ list_make4_int(int datum1, int datum2, int datum3, int datum4)
 List *
 list_make1_oid(Oid datum1)
 {
-	List	   *list = new_list(T_OidList, 1);
+	List	   *list = new_list(T_OidList, 1, false);
 
 	lfirst_oid(&list->elements[0]) = datum1;
 	check_list_invariants(list);
@@ -271,7 +277,7 @@ list_make1_oid(Oid datum1)
 List *
 list_make2_oid(Oid datum1, Oid datum2)
 {
-	List	   *list = new_list(T_OidList, 2);
+	List	   *list = new_list(T_OidList, 2, false);
 
 	lfirst_oid(&list->elements[0]) = datum1;
 	lfirst_oid(&list->elements[1]) = datum2;
@@ -282,7 +288,7 @@ list_make2_oid(Oid datum1, Oid datum2)
 List *
 list_make3_oid(Oid datum1, Oid datum2, Oid datum3)
 {
-	List	   *list = new_list(T_OidList, 3);
+	List	   *list = new_list(T_OidList, 3, false);
 
 	lfirst_oid(&list->elements[0]) = datum1;
 	lfirst_oid(&list->elements[1]) = datum2;
@@ -294,7 +300,7 @@ list_make3_oid(Oid datum1, Oid datum2, Oid datum3)
 List *
 list_make4_oid(Oid datum1, Oid datum2, Oid datum3, Oid datum4)
 {
-	List	   *list = new_list(T_OidList, 4);
+	List	   *list = new_list(T_OidList, 4, false);
 
 	lfirst_oid(&list->elements[0]) = datum1;
 	lfirst_oid(&list->elements[1]) = datum2;
@@ -316,9 +322,15 @@ new_head_cell(List *list)
 	/* Enlarge array if necessary */
 	if (list->length >= list->max_length)
 		list = enlarge_list(list, list->length + 1);
-	/* Now shove the existing data over */
-	memmove(&list->elements[1], &list->elements[0],
-			list->length * sizeof(ListCell));
+	if (list->first > 0)
+		list->first -= 1;
+	else
+	{
+		/* Now shove the existing data to the end */
+		list->first = list->max_length - list->length - 1;
+		memmove(&list->elements[list->first + 1], &list->elements[0],
+				list->length * sizeof(ListCell));
+	}
 	list->length++;
 }
 
@@ -332,8 +344,8 @@ static void
 new_tail_cell(List *list)
 {
 	/* Enlarge array if necessary */
-	if (list->length >= list->max_length)
-		list = enlarge_list(list, list->length + 1);
+	if (list->first + list->length >= list->max_length)
+		list = enlarge_list(list, list->first + list->length + 1);
 	list->length++;
 }
 
@@ -350,7 +362,7 @@ lappend(List *list, void *datum)
 	Assert(IsPointerList(list));
 
 	if (list == NIL)
-		list = new_list(T_List, 1);
+		list = new_list(T_List, 1, false);
 	else
 		new_tail_cell(list);
 
@@ -368,7 +380,7 @@ lappend_int(List *list, int datum)
 	Assert(IsIntegerList(list));
 
 	if (list == NIL)
-		list = new_list(T_IntList, 1);
+		list = new_list(T_IntList, 1, false);
 	else
 		new_tail_cell(list);
 
@@ -386,7 +398,7 @@ lappend_oid(List *list, Oid datum)
 	Assert(IsOidList(list));
 
 	if (list == NIL)
-		list = new_list(T_OidList, 1);
+		list = new_list(T_OidList, 1, false);
 	else
 		new_tail_cell(list);
 
@@ -409,15 +421,17 @@ insert_new_cell(List *list, int pos)
 	Assert(pos >= 0 && pos <= list->length);
 
 	/* Enlarge array if necessary */
-	if (list->length >= list->max_length)
-		list = enlarge_list(list, list->length + 1);
+	if (list->first + list->length >= list->max_length)
+		list = enlarge_list(list, list->first + list->length + 1);
 	/* Now shove the existing data over */
-	if (pos < list->length)
-		memmove(&list->elements[pos + 1], &list->elements[pos],
+	if (pos == 0 && list->first > 0)
+		list->first -= 1;
+	else if (pos < list->length)
+		memmove(&list->elements[list->first + pos + 1], &list->elements[list->first + pos],
 				(list->length - pos) * sizeof(ListCell));
 	list->length++;
 
-	return &list->elements[pos];
+	return &list->elements[list->first + pos];
 }
 
 /*
@@ -476,7 +490,7 @@ list_insert_nth_oid(List *list, int pos, Oid datum)
 static ListCell *
 add_new_cell(List *list, ListCell *prev_cell)
 {
-	int			pos = prev_cell - list->elements;
+	int			pos = prev_cell - &list->elements[list->first];
 
 	return insert_new_cell(list, pos + 1);
 }
@@ -546,7 +560,7 @@ lcons(void *datum, List *list)
 	Assert(IsPointerList(list));
 
 	if (list == NIL)
-		list = new_list(T_List, 1);
+		list = new_list(T_List, 1, true);
 	else
 		new_head_cell(list);
 
@@ -564,7 +578,7 @@ lcons_int(int datum, List *list)
 	Assert(IsIntegerList(list));
 
 	if (list == NIL)
-		list = new_list(T_IntList, 1);
+		list = new_list(T_IntList, 1, true);
 	else
 		new_head_cell(list);
 
@@ -582,7 +596,7 @@ lcons_oid(Oid datum, List *list)
 	Assert(IsOidList(list));
 
 	if (list == NIL)
-		list = new_list(T_OidList, 1);
+		list = new_list(T_OidList, 1, true);
 	else
 		new_head_cell(list);
 
@@ -609,15 +623,19 @@ list_concat(List *list1, const List *list2)
 
 	Assert(list1->type == list2->type);
 
-	new_len = list1->length + list2->length;
+	new_len = list1->first + list1->length + list2->length;
 	/* Enlarge array if necessary */
 	if (new_len > list1->max_length)
 		list1 = enlarge_list(list1, new_len);
 
-	/* We use memmove in case list1 and list2 are the same list */
-	memmove(&list1->elements[list1->length], &list2->elements[0],
-			list2->length * sizeof(ListCell));
-	list1->length = new_len;
+	/*
+	 * memcpy here is fine even if the lists are the same. We're never going
+	 * to overwrite used elements.
+	 */
+	memcpy(&list1->elements[list1->first + list1->length],
+		   &list2->elements[list2->first],
+		   list2->length * sizeof(ListCell));
+	list1->length += list2->length;
 
 	check_list_invariants(list1);
 	return list1;
@@ -751,11 +769,19 @@ list_delete_nth_cell(List *list, int n)
 		return NIL;
 	}
 
-	/*
-	 * Otherwise, collapse out the removed element.
-	 */
-	memmove(&list->elements[n], &list->elements[n + 1],
-			(list->length - 1 - n) * sizeof(ListCell));
+	if (n == 0)
+	{
+		list->first += 1;
+	}
+	else
+	{
+		/*
+		 * Otherwise, collapse out the removed element.
+		 */
+		memmove(&list->elements[list->first + n],
+				&list->elements[list->first + n + 1],
+				(list->length - 1 - n) * sizeof(ListCell));
+	}
 	list->length--;
 
 	return list;
@@ -774,7 +800,7 @@ list_delete_cell(List *list, ListCell *cell)
 
 	check_list_invariants(list);
 
-	pos = cell - list->elements;
+	pos = cell - &list->elements[list->first];
 	Assert(pos >= 0 && pos < list->length);
 
 	/*
@@ -788,11 +814,18 @@ list_delete_cell(List *list, ListCell *cell)
 		return NIL;
 	}
 
-	/*
-	 * Otherwise, collapse out the removed element.
-	 */
-	memmove(&list->elements[pos], &list->elements[pos + 1],
-			(list->length - 1 - pos) * sizeof(ListCell));
+	if (pos == 0)
+	{
+		list->first += 1;
+	}
+	else
+	{
+		/*
+		 * Otherwise, collapse out the removed element.
+		 */
+		memmove(&list->elements[list->first + pos], &list->elements[list->first + pos + 1],
+				(list->length - 1 - pos) * sizeof(ListCell));
+	}
 	list->length--;
 
 	return list;
@@ -1333,7 +1366,7 @@ list_free_private(List *list, bool deep)
 
 	if (deep)
 	{
-		for (int i = 0; i < list->length; i++)
+		for (int i = list->first; i < list->length; i++)
 			pfree(lfirst(&list->elements[i]));
 	}
 	pfree(list->elements);
@@ -1383,8 +1416,8 @@ list_copy(const List *oldlist)
 	if (oldlist == NIL)
 		return NIL;
 
-	newlist = new_list(oldlist->type, oldlist->length);
-	memcpy(newlist->elements, oldlist->elements,
+	newlist = new_list(oldlist->type, oldlist->length, false);
+	memcpy(newlist->elements, &oldlist->elements[oldlist->first],
 		   newlist->length * sizeof(ListCell));
 
 	check_list_invariants(newlist);
@@ -1405,8 +1438,8 @@ list_copy_tail(const List *oldlist, int nskip)
 	if (oldlist == NIL || nskip >= oldlist->length)
 		return NIL;
 
-	newlist = new_list(oldlist->type, oldlist->length - nskip);
-	memcpy(newlist->elements, &oldlist->elements[nskip],
+	newlist = new_list(oldlist->type, oldlist->length - nskip, false);
+	memcpy(newlist->elements, &oldlist->elements[oldlist->first + nskip],
 		   newlist->length * sizeof(ListCell));
 
 	check_list_invariants(newlist);
@@ -1431,10 +1464,10 @@ list_copy_deep(const List *oldlist)
 	/* This is only sensible for pointer Lists */
 	Assert(IsA(oldlist, List));
 
-	newlist = new_list(oldlist->type, oldlist->length);
+	newlist = new_list(oldlist->type, oldlist->length, false);
 	for (int i = 0; i < newlist->length; i++)
 		lfirst(&newlist->elements[i]) =
-			copyObjectImpl(lfirst(&oldlist->elements[i]));
+			copyObjectImpl(lfirst(&oldlist->elements[oldlist->first + i]));
 
 	check_list_invariants(newlist);
 	return newlist;
@@ -1472,7 +1505,7 @@ list_qsort(const List *list, list_qsort_comparator cmp)
 	qsort(list_arr, len, sizeof(ListCell *), cmp);
 
 	/* Construct new list (this code is much like list_copy) */
-	newlist = new_list(list->type, len);
+	newlist = new_list(list->type, len, false);
 
 	for (i = 0; i < len; i++)
 		newlist->elements[i] = *list_arr[i];
diff --git a/src/include/nodes/pg_list.h b/src/include/nodes/pg_list.h
index 8c79edd349..c164417e0b 100644
--- a/src/include/nodes/pg_list.h
+++ b/src/include/nodes/pg_list.h
@@ -50,6 +50,7 @@ typedef struct List
 {
 	NodeTag		type;			/* T_List, T_IntList, or T_OidList */
 	int			length;			/* number of elements currently present */
+	int			first;			/* First used cell index */
 	int			max_length;		/* allocated length of elements[] */
 	ListCell   *elements;		/* re-allocatable array of cells */
 } List;
@@ -69,14 +70,14 @@ typedef struct List
 static inline ListCell *
 list_head(const List *l)
 {
-	return l ? &l->elements[0] : NULL;
+	return l ? &l->elements[l->first] : NULL;
 }
 
 /* Fetch address of list's last cell; NULL if empty list */
 static inline ListCell *
 list_tail(const List *l)
 {
-	return l ? &l->elements[l->length - 1] : NULL;
+	return l ? &l->elements[l->first + l->length - 1] : NULL;
 }
 
 /* Fetch address of list's second cell, if it has one, else NULL */
@@ -84,7 +85,7 @@ static inline ListCell *
 list_second_cell(const List *l)
 {
 	if (l && l->length >= 2)
-		return &l->elements[1];
+		return &l->elements[l->first + 1];
 	else
 		return NULL;
 }
@@ -94,7 +95,7 @@ static inline ListCell *
 list_third_cell(const List *l)
 {
 	if (l && l->length >= 3)
-		return &l->elements[2];
+		return &l->elements[l->first + 2];
 	else
 		return NULL;
 }
@@ -104,7 +105,7 @@ static inline ListCell *
 list_fourth_cell(const List *l)
 {
 	if (l && l->length >= 4)
-		return &l->elements[3];
+		return &l->elements[l->first + 3];
 	else
 		return NULL;
 }
@@ -171,7 +172,7 @@ list_nth_cell(const List *list, int n)
 {
 	Assert(list != NIL);
 	Assert(n >= 0 && n < list->length);
-	return &list->elements[n];
+	return &list->elements[list->first + n];
 }
 
 /*
@@ -215,8 +216,8 @@ list_nth_oid(const List *list, int n)
 static inline int
 list_cell_number(const List *l, const ListCell *c)
 {
-	Assert(c >= &l->elements[0] && c < &l->elements[l->length]);
-	return c - l->elements;
+	Assert(c >= &l->elements[l->first] && c < &l->elements[l->first + l->length]);
+	return c - &l->elements[l->first];
 }
 
 /*
@@ -225,13 +226,10 @@ list_cell_number(const List *l, const ListCell *c)
 static inline ListCell *
 lnext(const List *l, const ListCell *c)
 {
-	if (c != NULL)
-	{
-		Assert(c >= &l->elements[0] && c < &l->elements[l->length]);
-		c = c + 1;
-		if (c < &l->elements[l->length])
-			return (ListCell *) c;
-	}
+	Assert(c >= &l->elements[l->first] && c < &l->elements[l->first + l->length]);
+	c = c + 1;
+	if (c < &l->elements[l->first + l->length])
+		return (ListCell *) c;
 	return NULL;
 }
 
@@ -248,7 +246,7 @@ lnext(const List *l, const ListCell *c)
  * and it's very unsafe to change the List object while the loop is iterating.
  */
 #define foreach(cell, l)	\
-	for ((cell) = list_head(l); (cell) != NULL; (cell) = lnext(l, cell))
+	for ((cell) = list_head(l); ((cell) && (cell) < &((List *) l)->elements[((List *) l)->first + ((List *) l)->length]) || (cell = NULL) != NULL; cell++)
 
 /*
  * for_each_cell -