Represent Lists as expansible arrays, not chains of cons-cells.

Originally, Postgres Lists were a more or less exact reimplementation of
Lisp lists, which consist of chains of separately-allocated cons cells,
each having a value and a next-cell link.  We'd hacked that once before
(commit d0b4399d8) to add a separate List header, but the data was still
in cons cells.  That makes some operations -- notably list_nth() -- O(N),
and it's bulky because of the next-cell pointers and per-cell palloc
overhead, and it's very cache-unfriendly if the cons cells end up
scattered around rather than being adjacent.

In this rewrite, we still have List headers, but the data is in a
resizable array of values, with no next-cell links.  Now we need at
most two palloc's per List, and often only one, since we can allocate
some values in the same palloc call as the List header.  (Of course,
extending an existing List may require repalloc's to enlarge the array.
But this involves just O(log N) allocations not O(N).)

Of course this is not without downsides.  The key difficulty is that
addition or deletion of a list entry may now cause other entries to
move, which it did not before.

For example, that breaks foreach() and sister macros, which historically
used a pointer to the current cons-cell as loop state.  We can repair
those macros transparently by making their actual loop state be an
integer list index; the exposed "ListCell *" pointer is no longer state
carried across loop iterations, but is just a derived value.  (In
practice, modern compilers can optimize things back to having just one
loop state value, at least for simple cases with inline loop bodies.)
In principle, this is a semantics change for cases where the loop body
inserts or deletes list entries ahead of the current loop index; but
I found no such cases in the Postgres code.

The change is not at all transparent for code that doesn't use foreach()
but chases lists "by hand" using lnext().  The largest share of such
code in the backend is in loops that were maintaining "prev" and "next"
variables in addition to the current-cell pointer, in order to delete
list cells efficiently using list_delete_cell().  However, we no longer
need a previous-cell pointer to delete a list cell efficiently.  Keeping
a next-cell pointer doesn't work, as explained above, but we can improve
matters by changing such code to use a regular foreach() loop and then
using the new macro foreach_delete_current() to delete the current cell.
(This macro knows how to update the associated foreach loop's state so
that no cells will be missed in the traversal.)

There remains a nontrivial risk of code assuming that a ListCell *
pointer will remain good over an operation that could now move the list
contents.  To help catch such errors, list.c can be compiled with a new
define symbol DEBUG_LIST_MEMORY_USAGE that forcibly moves list contents
whenever that could possibly happen.  This makes list operations
significantly more expensive so it's not normally turned on (though it
is on by default if USE_VALGRIND is on).

There are two notable API differences from the previous code:

* lnext() now requires the List's header pointer in addition to the
current cell's address.

* list_delete_cell() no longer requires a previous-cell argument.

These changes are somewhat unfortunate, but on the other hand code using
either function needs inspection to see if it is assuming anything
it shouldn't, so it's not all bad.

Programmers should be aware of these significant performance changes:

* list_nth() and related functions are now O(1); so there's no
major access-speed difference between a list and an array.

* Inserting or deleting a list element now takes time proportional to
the distance to the end of the list, due to moving the array elements.
(However, it typically *doesn't* require palloc or pfree, so except in
long lists it's probably still faster than before.)  Notably, lcons()
used to be about the same cost as lappend(), but that's no longer true
if the list is long.  Code that uses lcons() and list_delete_first()
to maintain a stack might usefully be rewritten to push and pop at the
end of the list rather than the beginning.

* There are now list_insert_nth...() and list_delete_nth...() functions
that add or remove a list cell identified by index.  These have the
data-movement penalty explained above, but there's no search penalty.

* list_concat() and variants now copy the second list's data into
storage belonging to the first list, so there is no longer any
sharing of cells between the input lists.  The second argument is
now declared "const List *" to reflect that it isn't changed.

This patch just does the minimum needed to get the new implementation
in place and fix bugs exposed by the regression tests.  As suggested
by the foregoing, there's a fair amount of followup work remaining to
do.

Also, the ENABLE_LIST_COMPAT macros are finally removed in this
commit.  Code using those should have been gone a dozen years ago.

Patch by me; thanks to David Rowley, Jesper Pedersen, and others
for review.

Discussion: https://postgr.es/m/11587.1550975080@sss.pgh.pa.us

1 files changed, 470 insertions, 346 deletions

diff --git a/src/backend/nodes/list.c b/src/backend/nodes/list.c
index 9897ab127d0..ecc2911496f 100644
--- a/src/backend/nodes/list.c
+++ b/src/backend/nodes/list.c
@@ -1,7 +1,9 @@
 /*-------------------------------------------------------------------------
  *
  * list.c
- *	  implementation for PostgreSQL generic linked list package
+ *	  implementation for PostgreSQL generic list package
+ *
+ * See comments in pg_list.h.
  *
  *
  * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group
@@ -16,10 +18,35 @@
 #include "postgres.h"
 
 #include "nodes/pg_list.h"
+#include "utils/memutils.h"
+
+
+/*
+ * The previous List implementation, since it used a separate palloc chunk
+ * for each cons cell, had the property that adding or deleting list cells
+ * did not move the storage of other existing cells in the list.  Quite a
+ * bit of existing code depended on that, by retaining ListCell pointers
+ * across such operations on a list.  There is no such guarantee in this
+ * implementation, so instead we have debugging support that is meant to
+ * help flush out now-broken assumptions.  Defining DEBUG_LIST_MEMORY_USAGE
+ * while building this file causes the List operations to forcibly move
+ * all cells in a list whenever a cell is added or deleted.  In combination
+ * with MEMORY_CONTEXT_CHECKING and/or Valgrind, this can usually expose
+ * broken code.  It's a bit expensive though, as there's many more palloc
+ * cycles and a lot more data-copying than in a default build.
+ *
+ * By default, we enable this when building for Valgrind.
+ */
+#ifdef USE_VALGRIND
+#define DEBUG_LIST_MEMORY_USAGE
+#endif
 
+/* Overhead for the fixed part of a List header, measured in ListCells */
+#define LIST_HEADER_OVERHEAD  \
+	((int) ((offsetof(List, initial_elements) - 1) / sizeof(ListCell) + 1))
 
 /*
- * Routines to simplify writing assertions about the type of a list; a
+ * Macros to simplify writing assertions about the type of a list; a
  * NIL list is considered to be an empty list of any type.
  */
 #define IsPointerList(l)		((l) == NIL || IsA((l), List))
@@ -37,50 +64,221 @@ check_list_invariants(const List *list)
 		return;
 
 	Assert(list->length > 0);
-	Assert(list->head != NULL);
-	Assert(list->tail != NULL);
+	Assert(list->length <= list->max_length);
+	Assert(list->elements != NULL);
 
 	Assert(list->type == T_List ||
 		   list->type == T_IntList ||
 		   list->type == T_OidList);
-
-	if (list->length == 1)
-		Assert(list->head == list->tail);
-	if (list->length == 2)
-		Assert(list->head->next == list->tail);
-	Assert(list->tail->next == NULL);
 }
 #else
-#define check_list_invariants(l)
+#define check_list_invariants(l)  ((void) 0)
 #endif							/* USE_ASSERT_CHECKING */
 
 /*
- * Return a freshly allocated List. Since empty non-NIL lists are
- * invalid, new_list() also allocates the head cell of the new list:
- * the caller should be sure to fill in that cell's data.
+ * Return a freshly allocated List with room for at least min_size cells.
+ *
+ * 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.
  */
 static List *
-new_list(NodeTag type)
+new_list(NodeTag type, int min_size)
 {
-	List	   *new_list;
-	ListCell   *new_head;
+	List	   *newlist;
+	int			max_size;
 
-	new_head = (ListCell *) palloc(sizeof(*new_head));
-	new_head->next = NULL;
-	/* new_head->data is left undefined! */
+	Assert(min_size > 0);
+
+	/*
+	 * We allocate all the requested cells, and possibly some more, as part of
+	 * the same palloc request as the List header.  This is a big win for the
+	 * typical case of short fixed-length lists.  It can lose if we allocate a
+	 * moderately long list and then it gets extended; we'll be wasting more
+	 * initial_elements[] space than if we'd made the header small.  However,
+	 * rounding up the request as we do in the normal code path provides some
+	 * defense against small extensions.
+	 */
 
-	new_list = (List *) palloc(sizeof(*new_list));
-	new_list->type = type;
-	new_list->length = 1;
-	new_list->head = new_head;
-	new_list->tail = new_head;
+#ifndef DEBUG_LIST_MEMORY_USAGE
 
-	return new_list;
+	/*
+	 * Normally, we set up a list with some extra cells, to allow it to grow
+	 * without a repalloc.  Prefer cell counts chosen to make the total
+	 * allocation a power-of-2, since palloc would round it up to that anyway.
+	 * (That stops being true for very large allocations, but very long lists
+	 * are infrequent, so it doesn't seem worth special logic for such cases.)
+	 *
+	 * The minimum allocation is 8 ListCell units, providing either 4 or 5
+	 * available ListCells depending on the machine's word width.  Counting
+	 * palloc's overhead, this uses the same amount of space as a one-cell
+	 * list did in the old implementation, and less space for any longer list.
+	 *
+	 * We needn't worry about integer overflow; no caller passes min_size
+	 * that's more than twice the size of an existing list, so the size limits
+	 * within palloc will ensure that we don't overflow here.
+	 */
+	max_size = 8;				/* semi-arbitrary small power of 2 */
+	while (max_size < min_size + LIST_HEADER_OVERHEAD)
+		max_size *= 2;
+	max_size -= LIST_HEADER_OVERHEAD;
+#else
+
+	/*
+	 * For debugging, don't allow any extra space.  This forces any cell
+	 * addition to go through enlarge_list() and thus move the existing data.
+	 */
+	max_size = min_size;
+#endif
+
+	newlist = (List *) palloc(offsetof(List, initial_elements) +
+							  max_size * sizeof(ListCell));
+	newlist->type = type;
+	newlist->length = min_size;
+	newlist->max_length = max_size;
+	newlist->elements = newlist->initial_elements;
+
+	return newlist;
 }
 
 /*
- * Allocate a new cell and make it the head of the specified
- * list. Assumes the list it is passed is non-NIL.
+ * Enlarge an existing non-NIL List to have room for at least min_size cells.
+ *
+ * This does *not* update list->length, as some callers would find that
+ * inconvenient.  (list->length had better be the correct number of existing
+ * valid cells, though.)
+ */
+static void
+enlarge_list(List *list, int min_size)
+{
+	int			new_max_len;
+
+	Assert(min_size > list->max_length);	/* else we shouldn't be here */
+
+#ifndef DEBUG_LIST_MEMORY_USAGE
+
+	/*
+	 * As above, we prefer power-of-two total allocations; but here we need
+	 * not account for list header overhead.  The existing max length might
+	 * not be a power of 2, so don't rely on that.
+	 */
+	new_max_len = 16;			/* semi-arbitrary small power of 2 */
+	while (new_max_len < min_size)
+		new_max_len *= 2;
+#else
+	/* As above, don't allocate anything extra */
+	new_max_len = min_size;
+#endif
+
+	if (list->elements == list->initial_elements)
+	{
+		List	   *newlist PG_USED_FOR_ASSERTS_ONLY;
+
+		/*
+		 * Replace original in-line allocation with a separate palloc block.
+		 * Ensure it is in the same memory context as the List header.  (The
+		 * previous List implementation did not offer any guarantees about
+		 * keeping all list cells in the same context, but it seems reasonable
+		 * to create such a guarantee now.)
+		 */
+		list->elements = (ListCell *)
+			MemoryContextAlloc(GetMemoryChunkContext(list),
+							   new_max_len * sizeof(ListCell));
+		memcpy(list->elements, list->initial_elements,
+			   list->length * sizeof(ListCell));
+
+		/*
+		 * Currently, asking aset.c to reduce the allocated size of the List
+		 * header is pointless in terms of reclaiming space, unless the list
+		 * is very long.  However, it seems worth doing anyway to cause the
+		 * no-longer-needed initial_elements[] space to be cleared in
+		 * debugging builds.
+		 */
+		newlist = (List *) repalloc(list, offsetof(List, initial_elements));
+
+		/* That better not have failed, nor moved the list header */
+		Assert(newlist == list);
+	}
+	else
+	{
+#ifndef DEBUG_LIST_MEMORY_USAGE
+		/* Normally, let repalloc deal with enlargement */
+		list->elements = (ListCell *) repalloc(list->elements,
+											   new_max_len * sizeof(ListCell));
+#else
+		/*
+		 * repalloc() might enlarge the space in-place, which we don't want
+		 * for debugging purposes, so forcibly move the data somewhere else.
+		 */
+		ListCell   *newelements;
+
+		newelements = (ListCell *)
+			MemoryContextAlloc(GetMemoryChunkContext(list),
+							   new_max_len * sizeof(ListCell));
+		memcpy(newelements, list->elements,
+			   list->length * sizeof(ListCell));
+		pfree(list->elements);
+		list->elements = newelements;
+#endif
+	}
+
+	list->max_length = new_max_len;
+}
+
+/*
+ * Convenience functions to construct short Lists from given values.
+ * (These are normally invoked via the list_makeN macros.)
+ */
+List *
+list_make1_impl(NodeTag t, ListCell datum1)
+{
+	List	   *list = new_list(t, 1);
+
+	list->elements[0] = datum1;
+	check_list_invariants(list);
+	return list;
+}
+
+List *
+list_make2_impl(NodeTag t, ListCell datum1, ListCell datum2)
+{
+	List	   *list = new_list(t, 2);
+
+	list->elements[0] = datum1;
+	list->elements[1] = datum2;
+	check_list_invariants(list);
+	return list;
+}
+
+List *
+list_make3_impl(NodeTag t, ListCell datum1, ListCell datum2,
+				ListCell datum3)
+{
+	List	   *list = new_list(t, 3);
+
+	list->elements[0] = datum1;
+	list->elements[1] = datum2;
+	list->elements[2] = datum3;
+	check_list_invariants(list);
+	return list;
+}
+
+List *
+list_make4_impl(NodeTag t, ListCell datum1, ListCell datum2,
+				ListCell datum3, ListCell datum4)
+{
+	List	   *list = new_list(t, 4);
+
+	list->elements[0] = datum1;
+	list->elements[1] = datum2;
+	list->elements[2] = datum3;
+	list->elements[3] = datum4;
+	check_list_invariants(list);
+	return list;
+}
+
+/*
+ * Make room for a new head cell in the given (non-NIL) list.
  *
  * The data in the new head cell is undefined; the caller should be
  * sure to fill it in
@@ -88,18 +286,17 @@ new_list(NodeTag type)
 static void
 new_head_cell(List *list)
 {
-	ListCell   *new_head;
-
-	new_head = (ListCell *) palloc(sizeof(*new_head));
-	new_head->next = list->head;
-
-	list->head = new_head;
+	/* Enlarge array if necessary */
+	if (list->length >= list->max_length)
+		enlarge_list(list, list->length + 1);
+	/* Now shove the existing data over */
+	memmove(&list->elements[1], &list->elements[0],
+			list->length * sizeof(ListCell));
 	list->length++;
 }
 
 /*
- * Allocate a new cell and make it the tail of the specified
- * list. Assumes the list it is passed is non-NIL.
+ * Make room for a new tail cell in the given (non-NIL) list.
  *
  * The data in the new tail cell is undefined; the caller should be
  * sure to fill it in
@@ -107,13 +304,9 @@ new_head_cell(List *list)
 static void
 new_tail_cell(List *list)
 {
-	ListCell   *new_tail;
-
-	new_tail = (ListCell *) palloc(sizeof(*new_tail));
-	new_tail->next = NULL;
-
-	list->tail->next = new_tail;
-	list->tail = new_tail;
+	/* Enlarge array if necessary */
+	if (list->length >= list->max_length)
+		enlarge_list(list, list->length + 1);
 	list->length++;
 }
 
@@ -130,11 +323,11 @@ lappend(List *list, void *datum)
 	Assert(IsPointerList(list));
 
 	if (list == NIL)
-		list = new_list(T_List);
+		list = new_list(T_List, 1);
 	else
 		new_tail_cell(list);
 
-	lfirst(list->tail) = datum;
+	lfirst(list_tail(list)) = datum;
 	check_list_invariants(list);
 	return list;
 }
@@ -148,11 +341,11 @@ lappend_int(List *list, int datum)
 	Assert(IsIntegerList(list));
 
 	if (list == NIL)
-		list = new_list(T_IntList);
+		list = new_list(T_IntList, 1);
 	else
 		new_tail_cell(list);
 
-	lfirst_int(list->tail) = datum;
+	lfirst_int(list_tail(list)) = datum;
 	check_list_invariants(list);
 	return list;
 }
@@ -166,82 +359,130 @@ lappend_oid(List *list, Oid datum)
 	Assert(IsOidList(list));
 
 	if (list == NIL)
-		list = new_list(T_OidList);
+		list = new_list(T_OidList, 1);
 	else
 		new_tail_cell(list);
 
-	lfirst_oid(list->tail) = datum;
+	lfirst_oid(list_tail(list)) = datum;
 	check_list_invariants(list);
 	return list;
 }
 
 /*
- * Add a new cell to the list, in the position after 'prev_cell'. The
- * data in the cell is left undefined, and must be filled in by the
- * caller. 'list' is assumed to be non-NIL, and 'prev_cell' is assumed
- * to be non-NULL and a member of 'list'.
+ * Make room for a new cell at position 'pos' (measured from 0).
+ * The data in the cell is left undefined, and must be filled in by the
+ * caller. 'list' is assumed to be non-NIL, and 'pos' must be a valid
+ * list position, ie, 0 <= pos <= list's length.
+ * Returns address of the new cell.
  */
 static ListCell *
-add_new_cell(List *list, ListCell *prev_cell)
+insert_new_cell(List *list, int pos)
 {
-	ListCell   *new_cell;
+	Assert(pos >= 0 && pos <= list->length);
+
+	/* Enlarge array if necessary */
+	if (list->length >= list->max_length)
+		enlarge_list(list, list->length + 1);
+	/* Now shove the existing data over */
+	if (pos < list->length)
+		memmove(&list->elements[pos + 1], &list->elements[pos],
+				(list->length - pos) * sizeof(ListCell));
+	list->length++;
 
-	new_cell = (ListCell *) palloc(sizeof(*new_cell));
-	/* new_cell->data is left undefined! */
-	new_cell->next = prev_cell->next;
-	prev_cell->next = new_cell;
+	return &list->elements[pos];
+}
 
-	if (list->tail == prev_cell)
-		list->tail = new_cell;
+/*
+ * Insert the given datum at position 'pos' (measured from 0) in the list.
+ * 'pos' must be valid, ie, 0 <= pos <= list's length.
+ */
+List *
+list_insert_nth(List *list, int pos, void *datum)
+{
+	if (list == NIL)
+	{
+		Assert(pos == 0);
+		return list_make1(datum);
+	}
+	Assert(IsPointerList(list));
+	lfirst(insert_new_cell(list, pos)) = datum;
+	check_list_invariants(list);
+	return list;
+}
 
-	list->length++;
+List *
+list_insert_nth_int(List *list, int pos, int datum)
+{
+	if (list == NIL)
+	{
+		Assert(pos == 0);
+		return list_make1_int(datum);
+	}
+	Assert(IsIntegerList(list));
+	lfirst_int(insert_new_cell(list, pos)) = datum;
+	check_list_invariants(list);
+	return list;
+}
 
-	return new_cell;
+List *
+list_insert_nth_oid(List *list, int pos, Oid datum)
+{
+	if (list == NIL)
+	{
+		Assert(pos == 0);
+		return list_make1_oid(datum);
+	}
+	Assert(IsOidList(list));
+	lfirst_oid(insert_new_cell(list, pos)) = datum;
+	check_list_invariants(list);
+	return list;
+}
+
+/*
+ * Add a new cell to the list, in the position after 'prev_cell'. The
+ * data in the cell is left undefined, and must be filled in by the
+ * caller. 'list' is assumed to be non-NIL, and 'prev_cell' is assumed
+ * to be non-NULL and a member of 'list'. Returns address of new cell.
+ *
+ * Caution: prev_cell might no longer point into the list after this!
+ */
+static ListCell *
+add_new_cell_after(List *list, ListCell *prev_cell)
+{
+	/* insert_new_cell will assert that this is in-range: */
+	int			pos = prev_cell - list->elements;
+
+	return insert_new_cell(list, pos + 1);
 }
 
 /*
  * Add a new cell to the specified list (which must be non-NIL);
  * it will be placed after the list cell 'prev' (which must be
  * non-NULL and a member of 'list'). The data placed in the new cell
- * is 'datum'. The newly-constructed cell is returned.
+ * is 'datum'.
  */
-ListCell *
+void
 lappend_cell(List *list, ListCell *prev, void *datum)
 {
-	ListCell   *new_cell;
-
 	Assert(IsPointerList(list));
-
-	new_cell = add_new_cell(list, prev);
-	lfirst(new_cell) = datum;
+	lfirst(add_new_cell_after(list, prev)) = datum;
 	check_list_invariants(list);
-	return new_cell;
 }
 
-ListCell *
+void
 lappend_cell_int(List *list, ListCell *prev, int datum)
 {
-	ListCell   *new_cell;
-
 	Assert(IsIntegerList(list));
-
-	new_cell = add_new_cell(list, prev);
-	lfirst_int(new_cell) = datum;
+	lfirst_int(add_new_cell_after(list, prev)) = datum;
 	check_list_invariants(list);
-	return new_cell;
 }
 
-ListCell *
+void
 lappend_cell_oid(List *list, ListCell *prev, Oid datum)
 {
-	ListCell   *new_cell;
-
 	Assert(IsOidList(list));
-
-	new_cell = add_new_cell(list, prev);
-	lfirst_oid(new_cell) = datum;
+	lfirst_oid(add_new_cell_after(list, prev)) = datum;
 	check_list_invariants(list);
-	return new_cell;
 }
 
 /*
@@ -261,11 +502,11 @@ lcons(void *datum, List *list)
 	Assert(IsPointerList(list));
 
 	if (list == NIL)
-		list = new_list(T_List);
+		list = new_list(T_List, 1);
 	else
 		new_head_cell(list);
 
-	lfirst(list->head) = datum;
+	lfirst(list_head(list)) = datum;
 	check_list_invariants(list);
 	return list;
 }
@@ -279,11 +520,11 @@ lcons_int(int datum, List *list)
 	Assert(IsIntegerList(list));
 
 	if (list == NIL)
-		list = new_list(T_IntList);
+		list = new_list(T_IntList, 1);
 	else
 		new_head_cell(list);
 
-	lfirst_int(list->head) = datum;
+	lfirst_int(list_head(list)) = datum;
 	check_list_invariants(list);
 	return list;
 }
@@ -297,41 +538,44 @@ lcons_oid(Oid datum, List *list)
 	Assert(IsOidList(list));
 
 	if (list == NIL)
-		list = new_list(T_OidList);
+		list = new_list(T_OidList, 1);
 	else
 		new_head_cell(list);
 
-	lfirst_oid(list->head) = datum;
+	lfirst_oid(list_head(list)) = datum;
 	check_list_invariants(list);
 	return list;
 }
 
 /*
  * Concatenate list2 to the end of list1, and return list1. list1 is
- * destructively changed. Callers should be sure to use the return
- * value as the new pointer to the concatenated list: the 'list1'
- * input pointer may or may not be the same as the returned pointer.
- *
- * The nodes in list2 are merely appended to the end of list1 in-place
- * (i.e. they aren't copied; the two lists will share some of the same
- * storage). Therefore, invoking list_free() on list2 will also
- * invalidate a portion of list1.
+ * destructively changed, list2 is not. (However, in the case of pointer
+ * lists, list1 and list2 will point to the same structures.) Callers
+ * should be sure to use the return value as the new pointer to the
+ * concatenated list: the 'list1' input pointer may or may not be the
+ * same as the returned pointer.
  */
 List *
-list_concat(List *list1, List *list2)
+list_concat(List *list1, const List *list2)
 {
+	int			new_len;
+
 	if (list1 == NIL)
-		return list2;
+		return list_copy(list2);
 	if (list2 == NIL)
 		return list1;
-	if (list1 == list2)
-		elog(ERROR, "cannot list_concat() a list to itself");
 
 	Assert(list1->type == list2->type);
 
-	list1->length += list2->length;
-	list1->tail->next = list2->head;
-	list1->tail = list2->tail;
+	new_len = list1->length + list2->length;
+	/* Enlarge array if necessary */
+	if (new_len > list1->max_length)
+		enlarge_list(list1, new_len);
+
+	/* Even if list1 == list2, using memcpy should be safe here */
+	memcpy(&list1->elements[list1->length], &list2->elements[0],
+		   list2->length * sizeof(ListCell));
+	list1->length = new_len;
 
 	check_list_invariants(list1);
 	return list1;
@@ -349,93 +593,27 @@ list_concat(List *list1, List *list2)
 List *
 list_truncate(List *list, int new_size)
 {
-	ListCell   *cell;
-	int			n;
-
 	if (new_size <= 0)
 		return NIL;				/* truncate to zero length */
 
 	/* If asked to effectively extend the list, do nothing */
-	if (new_size >= list_length(list))
-		return list;
+	if (new_size < list_length(list))
+		list->length = new_size;
 
-	n = 1;
-	foreach(cell, list)
-	{
-		if (n == new_size)
-		{
-			cell->next = NULL;
-			list->tail = cell;
-			list->length = new_size;
-			check_list_invariants(list);
-			return list;
-		}
-		n++;
-	}
+	/*
+	 * Note: unlike the individual-list-cell deletion functions, we don't move
+	 * the list cells to new storage, even in DEBUG_LIST_MEMORY_USAGE mode.
+	 * This is because none of them can move in this operation, so just like
+	 * in the old cons-cell-based implementation, this function doesn't
+	 * invalidate any pointers to cells of the list.  This is also the reason
+	 * for not wiping the memory of the deleted cells: the old code didn't
+	 * free them either.  Perhaps later we'll tighten this up.
+	 */
 
-	/* keep the compiler quiet; never reached */
-	Assert(false);
 	return list;
 }
 
 /*
- * Locate the n'th cell (counting from 0) of the list.  It is an assertion
- * failure if there is no such cell.
- */
-ListCell *
-list_nth_cell(const List *list, int n)
-{
-	ListCell   *match;
-
-	Assert(list != NIL);
-	Assert(n >= 0);
-	Assert(n < list->length);
-	check_list_invariants(list);
-
-	/* Does the caller actually mean to fetch the tail? */
-	if (n == list->length - 1)
-		return list->tail;
-
-	for (match = list->head; n-- > 0; match = match->next)
-		;
-
-	return match;
-}
-
-/*
- * Return the data value contained in the n'th element of the
- * specified list. (List elements begin at 0.)
- */
-void *
-list_nth(const List *list, int n)
-{
-	Assert(IsPointerList(list));
-	return lfirst(list_nth_cell(list, n));
-}
-
-/*
- * Return the integer value contained in the n'th element of the
- * specified list.
- */
-int
-list_nth_int(const List *list, int n)
-{
-	Assert(IsIntegerList(list));
-	return lfirst_int(list_nth_cell(list, n));
-}
-
-/*
- * Return the OID value contained in the n'th element of the specified
- * list.
- */
-Oid
-list_nth_oid(const List *list, int n)
-{
-	Assert(IsOidList(list));
-	return lfirst_oid(list_nth_cell(list, n));
-}
-
-/*
  * Return true iff 'datum' is a member of the list. Equality is
  * determined via equal(), so callers should ensure that they pass a
  * Node as 'datum'.
@@ -519,16 +697,16 @@ list_member_oid(const List *list, Oid datum)
 }
 
 /*
- * Delete 'cell' from 'list'; 'prev' is the previous element to 'cell'
- * in 'list', if any (i.e. prev == NULL iff list->head == cell)
+ * Delete the n'th cell (counting from 0) in list.
  *
- * The cell is pfree'd, as is the List header if this was the last member.
+ * The List is pfree'd if this was the last member.
  */
 List *
-list_delete_cell(List *list, ListCell *cell, ListCell *prev)
+list_delete_nth_cell(List *list, int n)
 {
 	check_list_invariants(list);
-	Assert(prev != NULL ? lnext(prev) == cell : list_head(list) == cell);
+
+	Assert(n >= 0 && n < list->length);
 
 	/*
 	 * If we're about to delete the last node from the list, free the whole
@@ -542,24 +720,62 @@ list_delete_cell(List *list, ListCell *cell, ListCell *prev)
 	}
 
 	/*
-	 * Otherwise, adjust the necessary list links, deallocate the particular
-	 * node we have just removed, and return the list we were given.
+	 * Otherwise, we normally just collapse out the removed element.  But for
+	 * debugging purposes, move the whole list contents someplace else.
+	 *
+	 * (Note that we *must* keep the contents in the same memory context.)
 	 */
+#ifndef DEBUG_LIST_MEMORY_USAGE
+	memmove(&list->elements[n], &list->elements[n + 1],
+			(list->length - 1 - n) * sizeof(ListCell));
 	list->length--;
+#else
+	{
+		ListCell   *newelems;
+		int			newmaxlen = list->length - 1;
+
+		newelems = (ListCell *)
+			MemoryContextAlloc(GetMemoryChunkContext(list),
+							   newmaxlen * sizeof(ListCell));
+		memcpy(newelems, list->elements, n * sizeof(ListCell));
+		memcpy(&newelems[n], &list->elements[n + 1],
+			   (list->length - 1 - n) * sizeof(ListCell));
+		if (list->elements != list->initial_elements)
+			pfree(list->elements);
+		else
+		{
+			/*
+			 * As in enlarge_list(), tell palloc code we're not using the
+			 * initial_elements space anymore.
+			 */
+			List	   *newlist PG_USED_FOR_ASSERTS_ONLY;
+
+			newlist = (List *) repalloc(list, offsetof(List, initial_elements));
+			Assert(newlist == list);
+		}
+		list->elements = newelems;
+		list->max_length = newmaxlen;
+		list->length--;
+		check_list_invariants(list);
+	}
+#endif
 
-	if (prev)
-		prev->next = cell->next;
-	else
-		list->head = cell->next;
-
-	if (list->tail == cell)
-		list->tail = prev;
-
-	pfree(cell);
 	return list;
 }
 
 /*
+ * Delete 'cell' from 'list'.
+ *
+ * The List is pfree'd if this was the last member.  However, we do not
+ * touch any data the cell might've been pointing to.
+ */
+List *
+list_delete_cell(List *list, ListCell *cell)
+{
+	return list_delete_nth_cell(list, cell - list->elements);
+}
+
+/*
  * Delete the first cell in list that matches datum, if any.
  * Equality is determined via equal().
  */
@@ -567,18 +783,14 @@ List *
 list_delete(List *list, void *datum)
 {
 	ListCell   *cell;
-	ListCell   *prev;
 
 	Assert(IsPointerList(list));
 	check_list_invariants(list);
 
-	prev = NULL;
 	foreach(cell, list)
 	{
 		if (equal(lfirst(cell), datum))
-			return list_delete_cell(list, cell, prev);
-
-		prev = cell;
+			return list_delete_cell(list, cell);
 	}
 
 	/* Didn't find a match: return the list unmodified */
@@ -590,18 +802,14 @@ List *
 list_delete_ptr(List *list, void *datum)
 {
 	ListCell   *cell;
-	ListCell   *prev;
 
 	Assert(IsPointerList(list));
 	check_list_invariants(list);
 
-	prev = NULL;
 	foreach(cell, list)
 	{
 		if (lfirst(cell) == datum)
-			return list_delete_cell(list, cell, prev);
-
-		prev = cell;
+			return list_delete_cell(list, cell);
 	}
 
 	/* Didn't find a match: return the list unmodified */
@@ -613,18 +821,14 @@ List *
 list_delete_int(List *list, int datum)
 {
 	ListCell   *cell;
-	ListCell   *prev;
 
 	Assert(IsIntegerList(list));
 	check_list_invariants(list);
 
-	prev = NULL;
 	foreach(cell, list)
 	{
 		if (lfirst_int(cell) == datum)
-			return list_delete_cell(list, cell, prev);
-
-		prev = cell;
+			return list_delete_cell(list, cell);
 	}
 
 	/* Didn't find a match: return the list unmodified */
@@ -636,18 +840,14 @@ List *
 list_delete_oid(List *list, Oid datum)
 {
 	ListCell   *cell;
-	ListCell   *prev;
 
 	Assert(IsOidList(list));
 	check_list_invariants(list);
 
-	prev = NULL;
 	foreach(cell, list)
 	{
 		if (lfirst_oid(cell) == datum)
-			return list_delete_cell(list, cell, prev);
-
-		prev = cell;
+			return list_delete_cell(list, cell);
 	}
 
 	/* Didn't find a match: return the list unmodified */
@@ -659,8 +859,8 @@ list_delete_oid(List *list, Oid datum)
  *
  * This is useful to replace the Lisp-y code "list = lnext(list);" in cases
  * where the intent is to alter the list rather than just traverse it.
- * Beware that the removed cell is freed, whereas the lnext() coding leaves
- * the original list head intact if there's another pointer to it.
+ * Beware that the list is modified, whereas the Lisp-y coding leaves
+ * the original list head intact in case there's another pointer to it.
  */
 List *
 list_delete_first(List *list)
@@ -670,7 +870,7 @@ list_delete_first(List *list)
 	if (list == NIL)
 		return NIL;				/* would an error be better? */
 
-	return list_delete_cell(list, list_head(list), NULL);
+	return list_delete_nth_cell(list, 0);
 }
 
 /*
@@ -688,7 +888,7 @@ list_delete_first(List *list)
  * in list1 (so it only performs a "union" if list1 is known unique to
  * start with).  Also, if you are about to write "x = list_union(x, y)"
  * you probably want to use list_concat_unique() instead to avoid wasting
- * the list cells of the old x list.
+ * the storage of the old x list.
  *
  * This function could probably be implemented a lot faster if it is a
  * performance bottleneck.
@@ -1013,12 +1213,10 @@ list_append_unique_oid(List *list, Oid datum)
  * This is almost the same functionality as list_union(), but list1 is
  * modified in-place rather than being copied. However, callers of this
  * function may have strict ordering expectations -- i.e. that the relative
- * order of those list2 elements that are not duplicates is preserved. Note
- * also that list2's cells are not inserted in list1, so the analogy to
- * list_concat() isn't perfect.
+ * order of those list2 elements that are not duplicates is preserved.
  */
 List *
-list_concat_unique(List *list1, List *list2)
+list_concat_unique(List *list1, const List *list2)
 {
 	ListCell   *cell;
 
@@ -1040,7 +1238,7 @@ list_concat_unique(List *list1, List *list2)
  * simple pointer equality.
  */
 List *
-list_concat_unique_ptr(List *list1, List *list2)
+list_concat_unique_ptr(List *list1, const List *list2)
 {
 	ListCell   *cell;
 
@@ -1061,7 +1259,7 @@ list_concat_unique_ptr(List *list1, List *list2)
  * This variant of list_concat_unique() operates upon lists of integers.
  */
 List *
-list_concat_unique_int(List *list1, List *list2)
+list_concat_unique_int(List *list1, const List *list2)
 {
 	ListCell   *cell;
 
@@ -1082,7 +1280,7 @@ list_concat_unique_int(List *list1, List *list2)
  * This variant of list_concat_unique() operates upon lists of OIDs.
  */
 List *
-list_concat_unique_oid(List *list1, List *list2)
+list_concat_unique_oid(List *list1, const List *list2)
 {
 	ListCell   *cell;
 
@@ -1105,23 +1303,19 @@ list_concat_unique_oid(List *list1, List *list2)
 static void
 list_free_private(List *list, bool deep)
 {
-	ListCell   *cell;
+	if (list == NIL)
+		return;					/* nothing to do */
 
 	check_list_invariants(list);
 
-	cell = list_head(list);
-	while (cell != NULL)
+	if (deep)
 	{
-		ListCell   *tmp = cell;
-
-		cell = lnext(cell);
-		if (deep)
-			pfree(lfirst(tmp));
-		pfree(tmp);
+		for (int i = 0; i < list->length; i++)
+			pfree(lfirst(&list->elements[i]));
 	}
-
-	if (list)
-		pfree(list);
+	if (list->elements != list->initial_elements)
+		pfree(list->elements);
+	pfree(list);
 }
 
 /*
@@ -1163,37 +1357,13 @@ List *
 list_copy(const List *oldlist)
 {
 	List	   *newlist;
-	ListCell   *newlist_prev;
-	ListCell   *oldlist_cur;
 
 	if (oldlist == NIL)
 		return NIL;
 
-	newlist = new_list(oldlist->type);
-	newlist->length = oldlist->length;
-
-	/*
-	 * Copy over the data in the first cell; new_list() has already allocated
-	 * the head cell itself
-	 */
-	newlist->head->data = oldlist->head->data;
-
-	newlist_prev = newlist->head;
-	oldlist_cur = oldlist->head->next;
-	while (oldlist_cur)
-	{
-		ListCell   *newlist_cur;
-
-		newlist_cur = (ListCell *) palloc(sizeof(*newlist_cur));
-		newlist_cur->data = oldlist_cur->data;
-		newlist_prev->next = newlist_cur;
-
-		newlist_prev = newlist_cur;
-		oldlist_cur = oldlist_cur->next;
-	}
-
-	newlist_prev->next = NULL;
-	newlist->tail = newlist_prev;
+	newlist = new_list(oldlist->type, oldlist->length);
+	memcpy(newlist->elements, oldlist->elements,
+		   newlist->length * sizeof(ListCell));
 
 	check_list_invariants(newlist);
 	return newlist;
@@ -1206,8 +1376,6 @@ List *
 list_copy_tail(const List *oldlist, int nskip)
 {
 	List	   *newlist;
-	ListCell   *newlist_prev;
-	ListCell   *oldlist_cur;
 
 	if (nskip < 0)
 		nskip = 0;				/* would it be better to elog? */
@@ -1215,38 +1383,36 @@ list_copy_tail(const List *oldlist, int nskip)
 	if (oldlist == NIL || nskip >= oldlist->length)
 		return NIL;
 
-	newlist = new_list(oldlist->type);
-	newlist->length = oldlist->length - nskip;
-
-	/*
-	 * Skip over the unwanted elements.
-	 */
-	oldlist_cur = oldlist->head;
-	while (nskip-- > 0)
-		oldlist_cur = oldlist_cur->next;
+	newlist = new_list(oldlist->type, oldlist->length - nskip);
+	memcpy(newlist->elements, &oldlist->elements[nskip],
+		   newlist->length * sizeof(ListCell));
 
-	/*
-	 * Copy over the data in the first remaining cell; new_list() has already
-	 * allocated the head cell itself
-	 */
-	newlist->head->data = oldlist_cur->data;
+	check_list_invariants(newlist);
+	return newlist;
+}
 
-	newlist_prev = newlist->head;
-	oldlist_cur = oldlist_cur->next;
-	while (oldlist_cur)
-	{
-		ListCell   *newlist_cur;
+/*
+ * Return a deep copy of the specified list.
+ *
+ * The list elements are copied via copyObject(), so that this function's
+ * idea of a "deep" copy is considerably deeper than what list_free_deep()
+ * means by the same word.
+ */
+List *
+list_copy_deep(const List *oldlist)
+{
+	List	   *newlist;
 
-		newlist_cur = (ListCell *) palloc(sizeof(*newlist_cur));
-		newlist_cur->data = oldlist_cur->data;
-		newlist_prev->next = newlist_cur;
+	if (oldlist == NIL)
+		return NIL;
 
-		newlist_prev = newlist_cur;
-		oldlist_cur = oldlist_cur->next;
-	}
+	/* This is only sensible for pointer Lists */
+	Assert(IsA(oldlist, List));
 
-	newlist_prev->next = NULL;
-	newlist->tail = newlist_prev;
+	newlist = new_list(oldlist->type, oldlist->length);
+	for (int i = 0; i < newlist->length; i++)
+		lfirst(&newlist->elements[i]) =
+			copyObjectImpl(lfirst(&oldlist->elements[i]));
 
 	check_list_invariants(newlist);
 	return newlist;
@@ -1259,6 +1425,8 @@ list_copy_tail(const List *oldlist, int nskip)
  * fresh copies of any pointed-to data.
  *
  * The comparator function receives arguments of type ListCell **.
+ * (XXX that's really inefficient now, but changing it seems like
+ * material for a standalone patch.)
  */
 List *
 list_qsort(const List *list, list_qsort_comparator cmp)
@@ -1266,7 +1434,6 @@ list_qsort(const List *list, list_qsort_comparator cmp)
 	int			len = list_length(list);
 	ListCell  **list_arr;
 	List	   *newlist;
-	ListCell   *newlist_prev;
 	ListCell   *cell;
 	int			i;
 
@@ -1274,7 +1441,7 @@ list_qsort(const List *list, list_qsort_comparator cmp)
 	if (len == 0)
 		return NIL;
 
-	/* Flatten list cells into an array, so we can use qsort */
+	/* We have to make an array of pointers to satisfy the API */
 	list_arr = (ListCell **) palloc(sizeof(ListCell *) * len);
 	i = 0;
 	foreach(cell, list)
@@ -1283,29 +1450,10 @@ 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);
-	newlist->length = len;
-
-	/*
-	 * Copy over the data in the first cell; new_list() has already allocated
-	 * the head cell itself
-	 */
-	newlist->head->data = list_arr[0]->data;
+	newlist = new_list(list->type, len);
 
-	newlist_prev = newlist->head;
-	for (i = 1; i < len; i++)
-	{
-		ListCell   *newlist_cur;
-
-		newlist_cur = (ListCell *) palloc(sizeof(*newlist_cur));
-		newlist_cur->data = list_arr[i]->data;
-		newlist_prev->next = newlist_cur;
-
-		newlist_prev = newlist_cur;
-	}
-
-	newlist_prev->next = NULL;
-	newlist->tail = newlist_prev;
+	for (i = 0; i < len; i++)
+		newlist->elements[i] = *list_arr[i];
 
 	/* Might as well free the workspace array */
 	pfree(list_arr);
@@ -1313,27 +1461,3 @@ list_qsort(const List *list, list_qsort_comparator cmp)
 	check_list_invariants(newlist);
 	return newlist;
 }
-
-/*
- * Temporary compatibility functions
- *
- * In order to avoid warnings for these function definitions, we need
- * to include a prototype here as well as in pg_list.h. That's because
- * we don't enable list API compatibility in list.c, so we
- * don't see the prototypes for these functions.
- */
-
-/*
- * Given a list, return its length. This is merely defined for the
- * sake of backward compatibility: we can't afford to define a macro
- * called "length", so it must be a function. New code should use the
- * list_length() macro in order to avoid the overhead of a function
- * call.
- */
-int			length(const List *list);
-
-int
-length(const List *list)
-{
-	return list_length(list);
-}