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, 386 insertions, 180 deletions

diff --git a/src/include/nodes/pg_list.h b/src/include/nodes/pg_list.h
index 8dd22e795e..8b1e4fb69e 100644
--- a/src/include/nodes/pg_list.h
+++ b/src/include/nodes/pg_list.h
@@ -1,19 +1,19 @@
 /*-------------------------------------------------------------------------
  *
  * pg_list.h
- *	  interface for PostgreSQL generic linked list package
+ *	  interface for PostgreSQL generic list package
  *
- * This package implements singly-linked homogeneous lists.
+ * Once upon a time, parts of Postgres were written in Lisp and used real
+ * cons-cell lists for major data structures.  When that code was rewritten
+ * in C, we initially had a faithful emulation of cons-cell lists, which
+ * unsurprisingly was a performance bottleneck.  A couple of major rewrites
+ * later, these data structures are actually simple expansible arrays;
+ * but the "List" name and a lot of the notation survives.
  *
- * It is important to have constant-time length, append, and prepend
- * operations. To achieve this, we deal with two distinct data
- * structures:
- *
- *		1. A set of "list cells": each cell contains a data field and
- *		   a link to the next cell in the list or NULL.
- *		2. A single structure containing metadata about the list: the
- *		   type of the list, pointers to the head and tail cells, and
- *		   the length of the list.
+ * One important concession to the original implementation is that an empty
+ * list is always represented by a null pointer (preferentially written NIL).
+ * Non-empty lists have a header, which will not be relocated as long as the
+ * list remains non-empty, and an expansible data array.
  *
  * We support three types of lists:
  *
@@ -40,51 +40,131 @@
 #include "nodes/nodes.h"
 
 
-typedef struct ListCell ListCell;
+typedef union ListCell
+{
+	void	   *ptr_value;
+	int			int_value;
+	Oid			oid_value;
+} ListCell;
 
 typedef struct List
 {
 	NodeTag		type;			/* T_List, T_IntList, or T_OidList */
-	int			length;
-	ListCell   *head;
-	ListCell   *tail;
+	int			length;			/* number of elements currently present */
+	int			max_length;		/* allocated length of elements[] */
+	ListCell   *elements;		/* re-allocatable array of cells */
+	/* We may allocate some cells along with the List header: */
+	ListCell	initial_elements[FLEXIBLE_ARRAY_MEMBER];
+	/* If elements == initial_elements, it's not a separate allocation */
 } List;
 
-struct ListCell
-{
-	union
-	{
-		void	   *ptr_value;
-		int			int_value;
-		Oid			oid_value;
-	}			data;
-	ListCell   *next;
-};
-
 /*
  * The *only* valid representation of an empty list is NIL; in other
- * words, a non-NIL list is guaranteed to have length >= 1 and
- * head/tail != NULL
+ * words, a non-NIL list is guaranteed to have length >= 1.
  */
 #define NIL						((List *) NULL)
 
 /*
- * These routines are used frequently. However, we can't implement
- * them as macros, since we want to avoid double-evaluation of macro
- * arguments.
+ * State structs for various looping macros below.
  */
+typedef struct ForEachState
+{
+	const List *l;				/* list we're looping through */
+	int			i;				/* current element index */
+} ForEachState;
+
+typedef struct ForBothState
+{
+	const List *l1;				/* lists we're looping through */
+	const List *l2;
+	int			i;				/* common element index */
+} ForBothState;
+
+typedef struct ForBothCellState
+{
+	const List *l1;				/* lists we're looping through */
+	const List *l2;
+	int			i1;				/* current element indexes */
+	int			i2;
+} ForBothCellState;
+
+typedef struct ForThreeState
+{
+	const List *l1;				/* lists we're looping through */
+	const List *l2;
+	const List *l3;
+	int			i;				/* common element index */
+} ForThreeState;
+
+typedef struct ForFourState
+{
+	const List *l1;				/* lists we're looping through */
+	const List *l2;
+	const List *l3;
+	const List *l4;
+	int			i;				/* common element index */
+} ForFourState;
+
+typedef struct ForFiveState
+{
+	const List *l1;				/* lists we're looping through */
+	const List *l2;
+	const List *l3;
+	const List *l4;
+	const List *l5;
+	int			i;				/* common element index */
+} ForFiveState;
+
+/*
+ * These routines are small enough, and used often enough, to justify being
+ * inline.
+ */
+
+/* Fetch address of list's first cell; NULL if empty list */
 static inline ListCell *
 list_head(const List *l)
 {
-	return l ? l->head : NULL;
+	return l ? &l->elements[0] : 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;
 }
 
+/* Fetch address of list's second cell, if it has one, else NULL */
 static inline ListCell *
-list_tail(List *l)
+list_second_cell(const List *l)
 {
-	return l ? l->tail : NULL;
+	if (l && l->length >= 2)
+		return &l->elements[1];
+	else
+		return NULL;
 }
 
+/* Fetch address of list's third cell, if it has one, else NULL */
+static inline ListCell *
+list_third_cell(const List *l)
+{
+	if (l && l->length >= 3)
+		return &l->elements[2];
+	else
+		return NULL;
+}
+
+/* Fetch address of list's fourth cell, if it has one, else NULL */
+static inline ListCell *
+list_fourth_cell(const List *l)
+{
+	if (l && l->length >= 4)
+		return &l->elements[3];
+	else
+		return NULL;
+}
+
+/* Fetch list's length */
 static inline int
 list_length(const List *l)
 {
@@ -92,6 +172,11 @@ list_length(const List *l)
 }
 
 /*
+ * Macros to access the data values within List cells.
+ *
+ * Note that with the exception of the "xxx_node" macros, these are
+ * lvalues and can be assigned to.
+ *
  * NB: There is an unfortunate legacy from a previous incarnation of
  * the List API: the macro lfirst() was used to mean "the data in this
  * cons cell". To avoid changing every usage of lfirst(), that meaning
@@ -99,13 +184,12 @@ list_length(const List *l)
  * the data it contains; to get the data in the first cell of a
  * List, use linitial(). Worse, lsecond() is more closely related to
  * linitial() than lfirst(): given a List, lsecond() returns the data
- * in the second cons cell.
+ * in the second list cell.
  */
 
-#define lnext(lc)				((lc)->next)
-#define lfirst(lc)				((lc)->data.ptr_value)
-#define lfirst_int(lc)			((lc)->data.int_value)
-#define lfirst_oid(lc)			((lc)->data.oid_value)
+#define lfirst(lc)				((lc)->ptr_value)
+#define lfirst_int(lc)			((lc)->int_value)
+#define lfirst_oid(lc)			((lc)->oid_value)
 #define lfirst_node(type,lc)	castNode(type, lfirst(lc))
 
 #define linitial(l)				lfirst(list_head(l))
@@ -113,19 +197,19 @@ list_length(const List *l)
 #define linitial_oid(l)			lfirst_oid(list_head(l))
 #define linitial_node(type,l)	castNode(type, linitial(l))
 
-#define lsecond(l)				lfirst(lnext(list_head(l)))
-#define lsecond_int(l)			lfirst_int(lnext(list_head(l)))
-#define lsecond_oid(l)			lfirst_oid(lnext(list_head(l)))
+#define lsecond(l)				lfirst(list_second_cell(l))
+#define lsecond_int(l)			lfirst_int(list_second_cell(l))
+#define lsecond_oid(l)			lfirst_oid(list_second_cell(l))
 #define lsecond_node(type,l)	castNode(type, lsecond(l))
 
-#define lthird(l)				lfirst(lnext(lnext(list_head(l))))
-#define lthird_int(l)			lfirst_int(lnext(lnext(list_head(l))))
-#define lthird_oid(l)			lfirst_oid(lnext(lnext(list_head(l))))
+#define lthird(l)				lfirst(list_third_cell(l))
+#define lthird_int(l)			lfirst_int(list_third_cell(l))
+#define lthird_oid(l)			lfirst_oid(list_third_cell(l))
 #define lthird_node(type,l)		castNode(type, lthird(l))
 
-#define lfourth(l)				lfirst(lnext(lnext(lnext(list_head(l)))))
-#define lfourth_int(l)			lfirst_int(lnext(lnext(lnext(list_head(l)))))
-#define lfourth_oid(l)			lfirst_oid(lnext(lnext(lnext(list_head(l)))))
+#define lfourth(l)				lfirst(list_fourth_cell(l))
+#define lfourth_int(l)			lfirst_int(list_fourth_cell(l))
+#define lfourth_oid(l)			lfirst_oid(list_fourth_cell(l))
 #define lfourth_node(type,l)	castNode(type, lfourth(l))
 
 #define llast(l)				lfirst(list_tail(l))
@@ -136,38 +220,189 @@ list_length(const List *l)
 /*
  * Convenience macros for building fixed-length lists
  */
-#define list_make1(x1)				lcons(x1, NIL)
-#define list_make2(x1,x2)			lcons(x1, list_make1(x2))
-#define list_make3(x1,x2,x3)		lcons(x1, list_make2(x2, x3))
-#define list_make4(x1,x2,x3,x4)		lcons(x1, list_make3(x2, x3, x4))
-#define list_make5(x1,x2,x3,x4,x5)	lcons(x1, list_make4(x2, x3, x4, x5))
-
-#define list_make1_int(x1)			lcons_int(x1, NIL)
-#define list_make2_int(x1,x2)		lcons_int(x1, list_make1_int(x2))
-#define list_make3_int(x1,x2,x3)	lcons_int(x1, list_make2_int(x2, x3))
-#define list_make4_int(x1,x2,x3,x4) lcons_int(x1, list_make3_int(x2, x3, x4))
-#define list_make5_int(x1,x2,x3,x4,x5)	lcons_int(x1, list_make4_int(x2, x3, x4, x5))
-
-#define list_make1_oid(x1)			lcons_oid(x1, NIL)
-#define list_make2_oid(x1,x2)		lcons_oid(x1, list_make1_oid(x2))
-#define list_make3_oid(x1,x2,x3)	lcons_oid(x1, list_make2_oid(x2, x3))
-#define list_make4_oid(x1,x2,x3,x4) lcons_oid(x1, list_make3_oid(x2, x3, x4))
-#define list_make5_oid(x1,x2,x3,x4,x5)	lcons_oid(x1, list_make4_oid(x2, x3, x4, x5))
+#define list_make_ptr_cell(v)	((ListCell) {.ptr_value = (v)})
+#define list_make_int_cell(v)	((ListCell) {.int_value = (v)})
+#define list_make_oid_cell(v)	((ListCell) {.oid_value = (v)})
+
+#define list_make1(x1) \
+	list_make1_impl(T_List, list_make_ptr_cell(x1))
+#define list_make2(x1,x2) \
+	list_make2_impl(T_List, list_make_ptr_cell(x1), list_make_ptr_cell(x2))
+#define list_make3(x1,x2,x3) \
+	list_make3_impl(T_List, list_make_ptr_cell(x1), list_make_ptr_cell(x2), \
+					list_make_ptr_cell(x3))
+#define list_make4(x1,x2,x3,x4) \
+	list_make4_impl(T_List, list_make_ptr_cell(x1), list_make_ptr_cell(x2), \
+					list_make_ptr_cell(x3), list_make_ptr_cell(x4))
+
+#define list_make1_int(x1) \
+	list_make1_impl(T_IntList, list_make_int_cell(x1))
+#define list_make2_int(x1,x2) \
+	list_make2_impl(T_IntList, list_make_int_cell(x1), list_make_int_cell(x2))
+#define list_make3_int(x1,x2,x3) \
+	list_make3_impl(T_IntList, list_make_int_cell(x1), list_make_int_cell(x2), \
+					list_make_int_cell(x3))
+#define list_make4_int(x1,x2,x3,x4) \
+	list_make4_impl(T_IntList, list_make_int_cell(x1), list_make_int_cell(x2), \
+					list_make_int_cell(x3), list_make_int_cell(x4))
+
+#define list_make1_oid(x1) \
+	list_make1_impl(T_OidList, list_make_oid_cell(x1))
+#define list_make2_oid(x1,x2) \
+	list_make2_impl(T_OidList, list_make_oid_cell(x1), list_make_oid_cell(x2))
+#define list_make3_oid(x1,x2,x3) \
+	list_make3_impl(T_OidList, list_make_oid_cell(x1), list_make_oid_cell(x2), \
+					list_make_oid_cell(x3))
+#define list_make4_oid(x1,x2,x3,x4) \
+	list_make4_impl(T_OidList, list_make_oid_cell(x1), list_make_oid_cell(x2), \
+					list_make_oid_cell(x3), list_make_oid_cell(x4))
+
+/*
+ * Locate the n'th cell (counting from 0) of the list.
+ * It is an assertion failure if there is no such cell.
+ */
+static inline ListCell *
+list_nth_cell(const List *list, int n)
+{
+	Assert(list != NIL);
+	Assert(n >= 0 && n < list->length);
+	return &list->elements[n];
+}
+
+/*
+ * Return the pointer value contained in the n'th element of the
+ * specified list. (List elements begin at 0.)
+ */
+static inline void *
+list_nth(const List *list, int n)
+{
+	Assert(IsA(list, List));
+	return lfirst(list_nth_cell(list, n));
+}
+
+/*
+ * Return the integer value contained in the n'th element of the
+ * specified list.
+ */
+static inline int
+list_nth_int(const List *list, int n)
+{
+	Assert(IsA(list, IntList));
+	return lfirst_int(list_nth_cell(list, n));
+}
+
+/*
+ * Return the OID value contained in the n'th element of the specified
+ * list.
+ */
+static inline Oid
+list_nth_oid(const List *list, int n)
+{
+	Assert(IsA(list, OidList));
+	return lfirst_oid(list_nth_cell(list, n));
+}
+
+#define list_nth_node(type,list,n)	castNode(type, list_nth(list, n))
+
+/*
+ * Get the given ListCell's index (from 0) in the given List.
+ */
+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;
+}
+
+/*
+ * Get the address of the next cell after "c" within list "l", or NULL if none.
+ */
+static inline ListCell *
+lnext(const List *l, const ListCell *c)
+{
+	Assert(c >= &l->elements[0] && c < &l->elements[l->length]);
+	c++;
+	if (c < &l->elements[l->length])
+		return (ListCell *) c;
+	else
+		return NULL;
+}
 
 /*
  * foreach -
- *	  a convenience macro which loops through the list
+ *	  a convenience macro for looping through a list
+ *
+ * "cell" must be the name of a "ListCell *" variable; it's made to point
+ * to each List element in turn.  "cell" will be NULL after normal exit from
+ * the loop, but an early "break" will leave it pointing at the current
+ * List element.
+ *
+ * Beware of changing the List object while the loop is iterating.
+ * The current semantics are that we examine successive list indices in
+ * each iteration, so that insertion or deletion of list elements could
+ * cause elements to be re-visited or skipped unexpectedly.  Previous
+ * implementations of foreach() behaved differently.  However, it's safe
+ * to append elements to the List (or in general, insert them after the
+ * current element); such new elements are guaranteed to be visited.
+ * Also, the current element of the List can be deleted, if you use
+ * foreach_delete_current() to do so.  BUT: either of these actions will
+ * invalidate the "cell" pointer for the remainder of the current iteration.
+ */
+#define foreach(cell, lst)	\
+	for (ForEachState cell##__state = {(lst), 0}; \
+		 (cell##__state.l != NIL && \
+		  cell##__state.i < cell##__state.l->length) ? \
+		 (cell = &cell##__state.l->elements[cell##__state.i], true) : \
+		 (cell = NULL, false); \
+		 cell##__state.i++)
+
+/*
+ * foreach_delete_current -
+ *	  delete the current list element from the List associated with a
+ *	  surrounding foreach() loop, returning the new List pointer.
+ *
+ * This is equivalent to list_delete_cell(), but it also adjusts the foreach
+ * loop's state so that no list elements will be missed.  Do not delete
+ * elements from an active foreach loop's list in any other way!
+ */
+#define foreach_delete_current(lst, cell)	\
+	(cell##__state.i--, \
+	 (List *) (cell##__state.l = list_delete_cell(lst, cell)))
+
+/*
+ * foreach_current_index -
+ *	  get the zero-based list index of a surrounding foreach() loop's
+ *	  current element; pass the name of the "ListCell *" iterator variable.
+ *
+ * Beware of using this after foreach_delete_current(); the value will be
+ * out of sync for the rest of the current loop iteration.  Anyway, since
+ * you just deleted the current element, the value is pretty meaningless.
  */
-#define foreach(cell, l)	\
-	for ((cell) = list_head(l); (cell) != NULL; (cell) = lnext(cell))
+#define foreach_current_index(cell)  (cell##__state.i)
 
 /*
  * for_each_cell -
  *	  a convenience macro which loops through a list starting from a
  *	  specified cell
+ *
+ * The caveats for foreach() apply equally here.
  */
-#define for_each_cell(cell, initcell)	\
-	for ((cell) = (initcell); (cell) != NULL; (cell) = lnext(cell))
+#define for_each_cell(cell, lst, initcell)	\
+	for (ForEachState cell##__state = for_each_cell_setup(lst, initcell); \
+		 (cell##__state.l != NIL && \
+		  cell##__state.i < cell##__state.l->length) ? \
+		 (cell = &cell##__state.l->elements[cell##__state.i], true) : \
+		 (cell = NULL, false); \
+		 cell##__state.i++)
+
+static inline ForEachState
+for_each_cell_setup(List *lst, ListCell *initcell)
+{
+	ForEachState r = {lst,
+	initcell ? list_cell_number(lst, initcell) : list_length(lst)};
+
+	return r;
+}
 
 /*
  * forboth -
@@ -175,12 +410,22 @@ list_length(const List *l)
  *	  simultaneously. This macro loops through both lists at the same
  *	  time, stopping when either list runs out of elements. Depending
  *	  on the requirements of the call site, it may also be wise to
- *	  assert that the lengths of the two lists are equal.
+ *	  assert that the lengths of the two lists are equal. (But, if they
+ *	  are not, some callers rely on the ending cell values being separately
+ *	  NULL or non-NULL as defined here; don't try to optimize that.)
+ *
+ * The caveats for foreach() apply equally here.
  */
 #define forboth(cell1, list1, cell2, list2)							\
-	for ((cell1) = list_head(list1), (cell2) = list_head(list2);	\
-		 (cell1) != NULL && (cell2) != NULL;						\
-		 (cell1) = lnext(cell1), (cell2) = lnext(cell2))
+	for (ForBothState cell1##__state = {(list1), (list2), 0}; \
+		 multi_for_advance_cell(cell1, cell1##__state, l1, i), \
+		 multi_for_advance_cell(cell2, cell1##__state, l2, i), \
+		 (cell1 != NULL && cell2 != NULL); \
+		 cell1##__state.i++)
+
+#define multi_for_advance_cell(cell, state, l, i) \
+	(cell = (state.l != NIL && state.i < state.l->length) ? \
+	 &state.l->elements[state.i] : NULL)
 
 /*
  * for_both_cell -
@@ -190,68 +435,96 @@ list_length(const List *l)
  *	  requirements of the call site, it may also be wise to assert that the
  *	  lengths of the two lists are equal, and initcell1 and initcell2 are at
  *	  the same position in the respective lists.
+ *
+ * The caveats for foreach() apply equally here.
  */
-#define for_both_cell(cell1, initcell1, cell2, initcell2)	\
-	for ((cell1) = (initcell1), (cell2) = (initcell2);		\
-		 (cell1) != NULL && (cell2) != NULL;				\
-		 (cell1) = lnext(cell1), (cell2) = lnext(cell2))
+#define for_both_cell(cell1, list1, initcell1, cell2, list2, initcell2)	\
+	for (ForBothCellState cell1##__state = \
+			 for_both_cell_setup(list1, initcell1, list2, initcell2); \
+		 multi_for_advance_cell(cell1, cell1##__state, l1, i1), \
+		 multi_for_advance_cell(cell2, cell1##__state, l2, i2), \
+		 (cell1 != NULL && cell2 != NULL); \
+		 cell1##__state.i1++, cell1##__state.i2++)
+
+static inline ForBothCellState
+for_both_cell_setup(List *list1, ListCell *initcell1,
+					List *list2, ListCell *initcell2)
+{
+	ForBothCellState r = {list1, list2,
+		initcell1 ? list_cell_number(list1, initcell1) : list_length(list1),
+	initcell2 ? list_cell_number(list2, initcell2) : list_length(list2)};
+
+	return r;
+}
 
 /*
  * forthree -
  *	  the same for three lists
  */
-#define forthree(cell1, list1, cell2, list2, cell3, list3)			\
-	for ((cell1) = list_head(list1), (cell2) = list_head(list2), (cell3) = list_head(list3); \
-		 (cell1) != NULL && (cell2) != NULL && (cell3) != NULL;		\
-		 (cell1) = lnext(cell1), (cell2) = lnext(cell2), (cell3) = lnext(cell3))
+#define forthree(cell1, list1, cell2, list2, cell3, list3) \
+	for (ForThreeState cell1##__state = {(list1), (list2), (list3), 0}; \
+		 multi_for_advance_cell(cell1, cell1##__state, l1, i), \
+		 multi_for_advance_cell(cell2, cell1##__state, l2, i), \
+		 multi_for_advance_cell(cell3, cell1##__state, l3, i), \
+		 (cell1 != NULL && cell2 != NULL && cell3 != NULL); \
+		 cell1##__state.i++)
 
 /*
  * forfour -
  *	  the same for four lists
  */
 #define forfour(cell1, list1, cell2, list2, cell3, list3, cell4, list4) \
-	for ((cell1) = list_head(list1), (cell2) = list_head(list2), \
-		 (cell3) = list_head(list3), (cell4) = list_head(list4); \
-		 (cell1) != NULL && (cell2) != NULL && \
-		 (cell3) != NULL && (cell4) != NULL; \
-		 (cell1) = lnext(cell1), (cell2) = lnext(cell2), \
-		 (cell3) = lnext(cell3), (cell4) = lnext(cell4))
+	for (ForFourState cell1##__state = {(list1), (list2), (list3), (list4), 0}; \
+		 multi_for_advance_cell(cell1, cell1##__state, l1, i), \
+		 multi_for_advance_cell(cell2, cell1##__state, l2, i), \
+		 multi_for_advance_cell(cell3, cell1##__state, l3, i), \
+		 multi_for_advance_cell(cell4, cell1##__state, l4, i), \
+		 (cell1 != NULL && cell2 != NULL && cell3 != NULL && cell4 != NULL); \
+		 cell1##__state.i++)
 
 /*
  * forfive -
  *	  the same for five lists
  */
 #define forfive(cell1, list1, cell2, list2, cell3, list3, cell4, list4, cell5, list5) \
-	for ((cell1) = list_head(list1), (cell2) = list_head(list2), \
-		 (cell3) = list_head(list3), (cell4) = list_head(list4), \
-		 (cell5) = list_head(list5); \
-		 (cell1) != NULL && (cell2) != NULL && (cell3) != NULL && \
-		 (cell4) != NULL && (cell5) != NULL; \
-		 (cell1) = lnext(cell1), (cell2) = lnext(cell2), \
-		 (cell3) = lnext(cell3), (cell4) = lnext(cell4), \
-		 (cell5) = lnext(cell5))
+	for (ForFiveState cell1##__state = {(list1), (list2), (list3), (list4), (list5), 0}; \
+		 multi_for_advance_cell(cell1, cell1##__state, l1, i), \
+		 multi_for_advance_cell(cell2, cell1##__state, l2, i), \
+		 multi_for_advance_cell(cell3, cell1##__state, l3, i), \
+		 multi_for_advance_cell(cell4, cell1##__state, l4, i), \
+		 multi_for_advance_cell(cell5, cell1##__state, l5, i), \
+		 (cell1 != NULL && cell2 != NULL && cell3 != NULL && \
+		  cell4 != NULL && cell5 != NULL); \
+		 cell1##__state.i++)
+
+/* Functions in src/backend/nodes/list.c */
+
+extern List *list_make1_impl(NodeTag t, ListCell datum1);
+extern List *list_make2_impl(NodeTag t, ListCell datum1, ListCell datum2);
+extern List *list_make3_impl(NodeTag t, ListCell datum1, ListCell datum2,
+							 ListCell datum3);
+extern List *list_make4_impl(NodeTag t, ListCell datum1, ListCell datum2,
+							 ListCell datum3, ListCell datum4);
 
 extern List *lappend(List *list, void *datum);
 extern List *lappend_int(List *list, int datum);
 extern List *lappend_oid(List *list, Oid datum);
 
-extern ListCell *lappend_cell(List *list, ListCell *prev, void *datum);
-extern ListCell *lappend_cell_int(List *list, ListCell *prev, int datum);
-extern ListCell *lappend_cell_oid(List *list, ListCell *prev, Oid datum);
+extern List *list_insert_nth(List *list, int pos, void *datum);
+extern List *list_insert_nth_int(List *list, int pos, int datum);
+extern List *list_insert_nth_oid(List *list, int pos, Oid datum);
+
+extern void lappend_cell(List *list, ListCell *prev, void *datum);
+extern void lappend_cell_int(List *list, ListCell *prev, int datum);
+extern void lappend_cell_oid(List *list, ListCell *prev, Oid datum);
 
 extern List *lcons(void *datum, List *list);
 extern List *lcons_int(int datum, List *list);
 extern List *lcons_oid(Oid datum, List *list);
 
-extern List *list_concat(List *list1, List *list2);
+extern List *list_concat(List *list1, const List *list2);
 extern List *list_truncate(List *list, int new_size);
 
-extern ListCell *list_nth_cell(const List *list, int n);
-extern void *list_nth(const List *list, int n);
-extern int	list_nth_int(const List *list, int n);
-extern Oid	list_nth_oid(const List *list, int n);
-#define list_nth_node(type,list,n)	castNode(type, list_nth(list, n))
-
 extern bool list_member(const List *list, const void *datum);
 extern bool list_member_ptr(const List *list, const void *datum);
 extern bool list_member_int(const List *list, int datum);
@@ -262,7 +535,8 @@ extern List *list_delete_ptr(List *list, void *datum);
 extern List *list_delete_int(List *list, int datum);
 extern List *list_delete_oid(List *list, Oid datum);
 extern List *list_delete_first(List *list);
-extern List *list_delete_cell(List *list, ListCell *cell, ListCell *prev);
+extern List *list_delete_nth_cell(List *list, int n);
+extern List *list_delete_cell(List *list, ListCell *cell);
 
 extern List *list_union(const List *list1, const List *list2);
 extern List *list_union_ptr(const List *list1, const List *list2);
@@ -284,87 +558,19 @@ extern List *list_append_unique_ptr(List *list, void *datum);
 extern List *list_append_unique_int(List *list, int datum);
 extern List *list_append_unique_oid(List *list, Oid datum);
 
-extern List *list_concat_unique(List *list1, List *list2);
-extern List *list_concat_unique_ptr(List *list1, List *list2);
-extern List *list_concat_unique_int(List *list1, List *list2);
-extern List *list_concat_unique_oid(List *list1, List *list2);
+extern List *list_concat_unique(List *list1, const List *list2);
+extern List *list_concat_unique_ptr(List *list1, const List *list2);
+extern List *list_concat_unique_int(List *list1, const List *list2);
+extern List *list_concat_unique_oid(List *list1, const List *list2);
 
 extern void list_free(List *list);
 extern void list_free_deep(List *list);
 
 extern List *list_copy(const List *list);
 extern List *list_copy_tail(const List *list, int nskip);
+extern List *list_copy_deep(const List *oldlist);
 
 typedef int (*list_qsort_comparator) (const void *a, const void *b);
 extern List *list_qsort(const List *list, list_qsort_comparator cmp);
 
-/*
- * To ease migration to the new list API, a set of compatibility
- * macros are provided that reduce the impact of the list API changes
- * as far as possible. Until client code has been rewritten to use the
- * new list API, the ENABLE_LIST_COMPAT symbol can be defined before
- * including pg_list.h
- */
-#ifdef ENABLE_LIST_COMPAT
-
-#define lfirsti(lc)					lfirst_int(lc)
-#define lfirsto(lc)					lfirst_oid(lc)
-
-#define makeList1(x1)				list_make1(x1)
-#define makeList2(x1, x2)			list_make2(x1, x2)
-#define makeList3(x1, x2, x3)		list_make3(x1, x2, x3)
-#define makeList4(x1, x2, x3, x4)	list_make4(x1, x2, x3, x4)
-
-#define makeListi1(x1)				list_make1_int(x1)
-#define makeListi2(x1, x2)			list_make2_int(x1, x2)
-
-#define makeListo1(x1)				list_make1_oid(x1)
-#define makeListo2(x1, x2)			list_make2_oid(x1, x2)
-
-#define lconsi(datum, list)			lcons_int(datum, list)
-#define lconso(datum, list)			lcons_oid(datum, list)
-
-#define lappendi(list, datum)		lappend_int(list, datum)
-#define lappendo(list, datum)		lappend_oid(list, datum)
-
-#define nconc(l1, l2)				list_concat(l1, l2)
-
-#define nth(n, list)				list_nth(list, n)
-
-#define member(datum, list)			list_member(list, datum)
-#define ptrMember(datum, list)		list_member_ptr(list, datum)
-#define intMember(datum, list)		list_member_int(list, datum)
-#define oidMember(datum, list)		list_member_oid(list, datum)
-
-/*
- * Note that the old lremove() determined equality via pointer
- * comparison, whereas the new list_delete() uses equal(); in order to
- * keep the same behavior, we therefore need to map lremove() calls to
- * list_delete_ptr() rather than list_delete()
- */
-#define lremove(elem, list)			list_delete_ptr(list, elem)
-#define LispRemove(elem, list)		list_delete(list, elem)
-#define lremovei(elem, list)		list_delete_int(list, elem)
-#define lremoveo(elem, list)		list_delete_oid(list, elem)
-
-#define ltruncate(n, list)			list_truncate(list, n)
-
-#define set_union(l1, l2)			list_union(l1, l2)
-#define set_uniono(l1, l2)			list_union_oid(l1, l2)
-#define set_ptrUnion(l1, l2)		list_union_ptr(l1, l2)
-
-#define set_difference(l1, l2)		list_difference(l1, l2)
-#define set_differenceo(l1, l2)		list_difference_oid(l1, l2)
-#define set_ptrDifference(l1, l2)	list_difference_ptr(l1, l2)
-
-#define equali(l1, l2)				equal(l1, l2)
-#define equalo(l1, l2)				equal(l1, l2)
-
-#define freeList(list)				list_free(list)
-
-#define listCopy(list)				list_copy(list)
-
-extern int	length(List *list);
-#endif							/* ENABLE_LIST_COMPAT */
-
 #endif							/* PG_LIST_H */