pgsql: Rewrite list_qsort() to avoid trashing its input list.

Rewrite list_qsort() to avoid trashing its input list.

The initial implementation of list_qsort(), from commit ab7271677,
re-used the ListCells of the input list while not touching the List
header. This meant that anybody who still had a pointer to the
original header would now be in possession of a corrupted list,
a problem that seems sure to bite us eventually.

One possible solution is to re-use the original List header as well,
giving the function the semantics of update-in-place. However, that
doesn't seem like a very good idea either given the way that the
function is used in the planner: create_path functions aren't normally
supposed to modify their input lists. It doesn't look like there would
be a problem today, but it's not hard to foresee a time when modifying
a list of Paths in-place could have side-effects on some other append
path.

On the whole, and in view of the likelihood that this function might
be used in other contexts in the future, it seems best to get rid of
the micro-optimization of re-using the input list cells. Just build
a new list.

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

Branch
------
master

Details
-------
https://git.postgresql.org/pg/commitdiff/3cb1b2a8804da8365fe17f687d96b720df4a583d

Modified Files
--------------
src/backend/nodes/list.c | 56 ++++++++++++++++++++++++++++++++++--------------
1 file changed, 40 insertions(+), 16 deletions(-)