]> git.eshelyaron.com Git - emacs.git/commit
Add back timsort key function handling (bug#69709)
authorMattias EngdegÄrd <mattiase@acm.org>
Mon, 18 Mar 2024 18:56:20 +0000 (19:56 +0100)
committerEshel Yaron <me@eshelyaron.com>
Fri, 29 Mar 2024 12:33:29 +0000 (13:33 +0100)
commitfa17cd0c7dc7c3042fbc03259504239c5d11406e
tree7845ef3ec4ab28d8bf8fe0fa5e97ae68580ad803
parent876dee2cdb89cb56219ef336aeb38a22d5cba92e
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.

(cherry picked from commit a52f1121a3589af8f89828e04d66f1215c361bcf)
src/fns.c
src/lisp.h
src/sort.c