From 9edfa27f9604f197ce47d86dc9ec07f14bfb7dde Mon Sep 17 00:00:00 2001 From: Andrew G Cohen Date: Wed, 16 Mar 2022 22:06:49 +0800 Subject: [PATCH] ; Minor improvements to timsort * src/fns.c (sort_list, sort_vector): Improve documentation and variable names. (merge): Replace function inorder with direct use of call2. * src/lisp.h: Remove inorder prototype. * src/sort.c: (struct reloc): Document the order field. (inorder): Uppercase INLINE. (binarysort): Move type declaration. (needmem): New INLINE function. (merge_lo, merge_hi): Use it. (merge_getmem): Remove unnecessary if. (tim_sort): Remove unnecessary if. (reverse_vector): Shift instead of integer divide by 2. --- src/fns.c | 13 +++++++------ src/lisp.h | 1 - src/sort.c | 42 +++++++++++++++++++++--------------------- 3 files changed, 28 insertions(+), 28 deletions(-) diff --git a/src/fns.c b/src/fns.c index 2e8454532cb..a064e02eac4 100644 --- a/src/fns.c +++ b/src/fns.c @@ -2165,8 +2165,9 @@ See also the function `nreverse', which is used more often. */) /* Stably sort LIST using PREDICATE. This converts the list to a - vector, sorts the vector using the TIMSORT algorithm, and converts - back to a list. */ + vector, sorts the vector using the TIMSORT algorithm, and returns + the result converted back to a list. The input list is + destructively reused to hold the sorted result.*/ static Lisp_Object sort_list (Lisp_Object list, Lisp_Object predicate) @@ -2206,11 +2207,11 @@ sort_list (Lisp_Object list, Lisp_Object predicate) static void sort_vector (Lisp_Object vector, Lisp_Object predicate) { - ptrdiff_t len = ASIZE (vector); - if (len < 2) + ptrdiff_t length = ASIZE (vector); + if (length < 2) return; - tim_sort (predicate, XVECTOR (vector)->contents, len); + tim_sort (predicate, XVECTOR (vector)->contents, length); } DEFUN ("sort", Fsort, Ssort, 2, 2, 0, @@ -2256,7 +2257,7 @@ merge (Lisp_Object org_l1, Lisp_Object org_l2, Lisp_Object pred) } Lisp_Object tem; - if (inorder (pred, Fcar (l1), Fcar (l2))) + if (!NILP (call2 (pred, Fcar (l1), Fcar (l2)))) { tem = l1; l1 = Fcdr (l1); diff --git a/src/lisp.h b/src/lisp.h index 43a4589efff..3801aeec3d0 100644 --- a/src/lisp.h +++ b/src/lisp.h @@ -3905,7 +3905,6 @@ extern void syms_of_fns (void); /* Defined in sort.c */ extern void tim_sort (Lisp_Object, Lisp_Object *, const ptrdiff_t); -extern bool inorder (Lisp_Object, Lisp_Object, Lisp_Object); /* Defined in floatfns.c. */ verify (FLT_RADIX == 2 || FLT_RADIX == 16); diff --git a/src/sort.c b/src/sort.c index 33f5d033190..5aa121a419b 100644 --- a/src/sort.c +++ b/src/sort.c @@ -27,7 +27,7 @@ along with GNU Emacs. If not, see . */ which is passed around as an argument to all the subroutines. A "stretch" structure includes a pointer to the run BASE of length LEN along with its POWER (a computed integer used by the powersort - merge strategy that depends on this run and the succeeding run. */ + merge strategy that depends on this run and the succeeding run.) */ #include @@ -64,7 +64,7 @@ struct reloc Lisp_Object **src; Lisp_Object **dst; ptrdiff_t *size; - int order; + int order; /* -1 while in merge_lo; +1 while in merg_hi; 0 otherwise. */ }; @@ -88,10 +88,8 @@ typedef struct ptrdiff_t min_gallop; /* 'A' is temporary storage, able to hold ALLOCED elements, to help - with merges. If temporary storage is passed to the sorting entry - function, 'A' will point to it. Otherwise 'A' initially points - to TEMPARRAY, and subsequently to newly allocated memory if - needed. */ + with merges. 'A' initially points to TEMPARRAY, and subsequently + to newly allocated memory if needed. */ Lisp_Object *a; ptrdiff_t alloced; @@ -112,7 +110,7 @@ typedef struct /* INORDER returns true iff (PREDICATE A B) is non-nil. */ -inline bool +INLINE bool inorder (const Lisp_Object predicate, const Lisp_Object a, const Lisp_Object b) { return !NILP (call2 (predicate, a, b)); @@ -139,18 +137,17 @@ binarysort (merge_state *ms, Lisp_Object *lo, const Lisp_Object *hi, Lisp_Object *l = lo; Lisp_Object *r = start; Lisp_Object pivot = *r; - Lisp_Object *p; eassume (l < r); do { - p = l + ((r - l) >> 1); + Lisp_Object *p = l + ((r - l) >> 1); if (inorder (pred, pivot, *p)) r = p; else l = p + 1; } while (l < r); eassume (l == r); - for (p = start; p > l; --p) + for (Lisp_Object *p = start; p > l; --p) p[0] = p[-1]; *l = pivot; } @@ -468,11 +465,17 @@ merge_getmem (merge_state *ms, const ptrdiff_t need) cycles copying the old data. We just free and alloc again. */ xfree (ms->a); - ms->a = NULL; } - ms->a = (Lisp_Object *) xmalloc (need * word_size); - if (ms->a != NULL) - ms->alloced = need; + ms->a = xmalloc (need * word_size); + ms->alloced = need; +} + + +INLINE void +needmem (merge_state *ms, ptrdiff_t na) +{ + if (na > ms->alloced) + merge_getmem (ms, na); } @@ -489,8 +492,7 @@ merge_lo (merge_state *ms, Lisp_Object *ssa, ptrdiff_t na, Lisp_Object *ssb, eassume (ms && ssa && ssb && na > 0 && nb > 0); eassume (ssa + na == ssb); - na <= ms->alloced ? 0 : merge_getmem (ms, na); - + needmem (ms, na); memcpy (ms->a, ssa, na * word_size); Lisp_Object *dest = ssa; ssa = ms->a; @@ -614,7 +616,7 @@ merge_hi (merge_state *ms, Lisp_Object *ssa, ptrdiff_t na, eassume (ms && ssa && ssb && na > 0 && nb > 0); eassume (ssa + na == ssb); - nb <= ms->alloced ? 0 : merge_getmem(ms, nb); + needmem (ms, nb); Lisp_Object *dest = ssb; dest += nb - 1; memcpy(ms->a, ssb, nb * word_size); @@ -897,7 +899,7 @@ merge_compute_minrun (ptrdiff_t n) static void reverse_vector (Lisp_Object *s, const ptrdiff_t n) { - for (ptrdiff_t i = 0; i < n / 2; i++) + for (ptrdiff_t i = 0; i < n >> 1; i++) { Lisp_Object tem = s[i]; s[i] = s[n - i - 1]; @@ -916,8 +918,6 @@ tim_sort (Lisp_Object predicate, Lisp_Object *seq, const ptrdiff_t length) merge_init (&ms, length, lo, predicate); - if (length < 2) - return; /* March over the array once, left to right, finding natural runs, and extending short natural runs to minrun elements. */ @@ -956,6 +956,6 @@ tim_sort (Lisp_Object predicate, Lisp_Object *seq, const ptrdiff_t length) eassume (ms.pending[0].len == length); lo = ms.pending[0].base; - if (ms.a != ms.temparray && ms.alloced <= ms.listlen >> 1) + if (ms.a != ms.temparray) unbind_to (ms.count, Qnil); } -- 2.39.5