Add back timsort key function handling (bug#69709)

The original timsort code did provide for a key (accessor) function
along with the necessary storage management, but we dropped it because
our `sort` function didn't need it.

Now it's been put back since it seems that it will come in handy after all.

* src/fns.c (sort_list, sort_vector, Fsort): Pass Qnil as key function
to tim_sort.
* src/sort.c (reverse_slice, sortslice_copy)
(sortslice_copy_incr, sortslice_copy_decr, sortslice_memcpy)
(sortslice_memmove, sortslice_advance): New functions.
(sortslice): New type.
(struct stretch, struct reloc, merge_state)
(binarysort, merge_init, merge_markmem, cleanup_mem)
(merge_register_cleanup, merge_getmem, merge_lo, merge_hi, merge_at)
(found_new_run, reverse_sortslice, resolve_fun, tim_sort):
Merge back previously discarded parts from the upstreams timsort code
that dealt with key functions, and adapt them to fit in.

1 files changed, 6 insertions, 6 deletions

diff --git a/src/fns.c b/src/fns.c
index 7faf25b9088..a3ef99f67a8 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -2353,7 +2353,7 @@ See also the function `nreverse', which is used more often.  */)
    is destructively reused to hold the sorted result.  */
 
 static Lisp_Object
-sort_list (Lisp_Object list, Lisp_Object predicate)
+sort_list (Lisp_Object list, Lisp_Object predicate, Lisp_Object keyfunc)
 {
   ptrdiff_t length = list_length (list);
   if (length < 2)
@@ -2369,7 +2369,7 @@ sort_list (Lisp_Object list, Lisp_Object predicate)
 	  result[i] = Fcar (tail);
 	  tail = XCDR (tail);
 	}
-      tim_sort (predicate, result, length);
+      tim_sort (predicate, keyfunc, result, length);
 
       ptrdiff_t i = 0;
       tail = list;
@@ -2388,13 +2388,13 @@ sort_list (Lisp_Object list, Lisp_Object predicate)
    algorithm.  */
 
 static void
-sort_vector (Lisp_Object vector, Lisp_Object predicate)
+sort_vector (Lisp_Object vector, Lisp_Object predicate, Lisp_Object keyfunc)
 {
   ptrdiff_t length = ASIZE (vector);
   if (length < 2)
     return;
 
-  tim_sort (predicate, XVECTOR (vector)->contents, length);
+  tim_sort (predicate, keyfunc, XVECTOR (vector)->contents, length);
 }
 
 DEFUN ("sort", Fsort, Ssort, 2, 2, 0,
@@ -2406,9 +2406,9 @@ the second.  */)
   (Lisp_Object seq, Lisp_Object predicate)
 {
   if (CONSP (seq))
-    seq = sort_list (seq, predicate);
+    seq = sort_list (seq, predicate, Qnil);
   else if (VECTORP (seq))
-    sort_vector (seq, predicate);
+    sort_vector (seq, predicate, Qnil);
   else if (!NILP (seq))
     wrong_type_argument (Qlist_or_vector_p, seq);
   return seq;