public inbox for glibc-cvs@sourceware.org
help / color / mirror / Atom feed
* [glibc/azanella/qsort-fixes] stdlib: Move insertion sort out qsort
@ 2021-09-06 18:22 Adhemerval Zanella
0 siblings, 0 replies; 2+ messages in thread
From: Adhemerval Zanella @ 2021-09-06 18:22 UTC (permalink / raw)
To: glibc-cvs
https://sourceware.org/git/gitweb.cgi?p=glibc.git;h=19dcfbc19e2497cac35e76c5b190a7466c09c507
commit 19dcfbc19e2497cac35e76c5b190a7466c09c507
Author: Adhemerval Zanella <adhemerval.zanella@linaro.org>
Date: Fri May 7 00:39:22 2021 -0300
stdlib: Move insertion sort out qsort
Diff:
---
stdlib/qsort.c | 100 ++++++++++++++++++++++++++++++---------------------------
1 file changed, 53 insertions(+), 47 deletions(-)
diff --git a/stdlib/qsort.c b/stdlib/qsort.c
index d3e11ec3c1..a6c78d6101 100644
--- a/stdlib/qsort.c
+++ b/stdlib/qsort.c
@@ -149,6 +149,58 @@ typedef struct
smaller partition. This *guarantees* no more than log (total_elems)
stack size is needed (actually O(1) in this case)! */
+static void
+insertion_sort (void *const pbase, size_t total_elems, size_t size,
+ swap_func_t swap_func,
+ __compar_d_fn_t cmp, void *arg)
+{
+ char *base_ptr = (char *) pbase;
+ char *const end_ptr = &base_ptr[size * (total_elems - 1)];
+ char *tmp_ptr = base_ptr;
+#define min(x, y) ((x) < (y) ? (x) : (y))
+ const size_t max_thresh = MAX_THRESH * size;
+ char *thresh = min(end_ptr, base_ptr + max_thresh);
+ char *run_ptr;
+
+ /* Find smallest element in first threshold and place it at the
+ array's beginning. This is the smallest array element,
+ and the operation speeds up insertion sort's inner loop. */
+
+ for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size)
+ if (cmp (run_ptr, tmp_ptr, arg) < 0)
+ tmp_ptr = run_ptr;
+
+ if (tmp_ptr != base_ptr)
+ do_swap (tmp_ptr, base_ptr, size, swap_func);
+
+ /* Insertion sort, running from left-hand-side up to right-hand-side. */
+
+ run_ptr = base_ptr + size;
+ while ((run_ptr += size) <= end_ptr)
+ {
+ tmp_ptr = run_ptr - size;
+ while (cmp (run_ptr, tmp_ptr, arg) < 0)
+ tmp_ptr -= size;
+
+ tmp_ptr += size;
+ if (tmp_ptr != run_ptr)
+ {
+ char *trav;
+
+ trav = run_ptr + size;
+ while (--trav >= run_ptr)
+ {
+ char c = *trav;
+ char *hi, *lo;
+
+ for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo)
+ *hi = *lo;
+ *hi = c;
+ }
+ }
+ }
+}
+
void
_quicksort (void *const pbase, size_t total_elems, size_t size,
__compar_d_fn_t cmp, void *arg)
@@ -271,51 +323,5 @@ _quicksort (void *const pbase, size_t total_elems, size_t size,
for partitions below MAX_THRESH size. BASE_PTR points to the beginning
of the array to sort, and END_PTR points at the very last element in
the array (*not* one beyond it!). */
-
-#define min(x, y) ((x) < (y) ? (x) : (y))
-
- {
- char *const end_ptr = &base_ptr[size * (total_elems - 1)];
- char *tmp_ptr = base_ptr;
- char *thresh = min(end_ptr, base_ptr + max_thresh);
- char *run_ptr;
-
- /* Find smallest element in first threshold and place it at the
- array's beginning. This is the smallest array element,
- and the operation speeds up insertion sort's inner loop. */
-
- for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size)
- if ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0)
- tmp_ptr = run_ptr;
-
- if (tmp_ptr != base_ptr)
- do_swap (tmp_ptr, base_ptr, size, swap_func);
-
- /* Insertion sort, running from left-hand-side up to right-hand-side. */
-
- run_ptr = base_ptr + size;
- while ((run_ptr += size) <= end_ptr)
- {
- tmp_ptr = run_ptr - size;
- while ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0)
- tmp_ptr -= size;
-
- tmp_ptr += size;
- if (tmp_ptr != run_ptr)
- {
- char *trav;
-
- trav = run_ptr + size;
- while (--trav >= run_ptr)
- {
- char c = *trav;
- char *hi, *lo;
-
- for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo)
- *hi = *lo;
- *hi = c;
- }
- }
- }
- }
+ insertion_sort (pbase, total_elems, size, swap_func, cmp, arg);
}
^ permalink raw reply [flat|nested] 2+ messages in thread
* [glibc/azanella/qsort-fixes] stdlib: Move insertion sort out qsort
@ 2021-09-06 18:44 Adhemerval Zanella
0 siblings, 0 replies; 2+ messages in thread
From: Adhemerval Zanella @ 2021-09-06 18:44 UTC (permalink / raw)
To: glibc-cvs
https://sourceware.org/git/gitweb.cgi?p=glibc.git;h=19dcfbc19e2497cac35e76c5b190a7466c09c507
commit 19dcfbc19e2497cac35e76c5b190a7466c09c507
Author: Adhemerval Zanella <adhemerval.zanella@linaro.org>
Date: Fri May 7 00:39:22 2021 -0300
stdlib: Move insertion sort out qsort
Diff:
---
stdlib/qsort.c | 100 ++++++++++++++++++++++++++++++---------------------------
1 file changed, 53 insertions(+), 47 deletions(-)
diff --git a/stdlib/qsort.c b/stdlib/qsort.c
index d3e11ec3c1..a6c78d6101 100644
--- a/stdlib/qsort.c
+++ b/stdlib/qsort.c
@@ -149,6 +149,58 @@ typedef struct
smaller partition. This *guarantees* no more than log (total_elems)
stack size is needed (actually O(1) in this case)! */
+static void
+insertion_sort (void *const pbase, size_t total_elems, size_t size,
+ swap_func_t swap_func,
+ __compar_d_fn_t cmp, void *arg)
+{
+ char *base_ptr = (char *) pbase;
+ char *const end_ptr = &base_ptr[size * (total_elems - 1)];
+ char *tmp_ptr = base_ptr;
+#define min(x, y) ((x) < (y) ? (x) : (y))
+ const size_t max_thresh = MAX_THRESH * size;
+ char *thresh = min(end_ptr, base_ptr + max_thresh);
+ char *run_ptr;
+
+ /* Find smallest element in first threshold and place it at the
+ array's beginning. This is the smallest array element,
+ and the operation speeds up insertion sort's inner loop. */
+
+ for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size)
+ if (cmp (run_ptr, tmp_ptr, arg) < 0)
+ tmp_ptr = run_ptr;
+
+ if (tmp_ptr != base_ptr)
+ do_swap (tmp_ptr, base_ptr, size, swap_func);
+
+ /* Insertion sort, running from left-hand-side up to right-hand-side. */
+
+ run_ptr = base_ptr + size;
+ while ((run_ptr += size) <= end_ptr)
+ {
+ tmp_ptr = run_ptr - size;
+ while (cmp (run_ptr, tmp_ptr, arg) < 0)
+ tmp_ptr -= size;
+
+ tmp_ptr += size;
+ if (tmp_ptr != run_ptr)
+ {
+ char *trav;
+
+ trav = run_ptr + size;
+ while (--trav >= run_ptr)
+ {
+ char c = *trav;
+ char *hi, *lo;
+
+ for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo)
+ *hi = *lo;
+ *hi = c;
+ }
+ }
+ }
+}
+
void
_quicksort (void *const pbase, size_t total_elems, size_t size,
__compar_d_fn_t cmp, void *arg)
@@ -271,51 +323,5 @@ _quicksort (void *const pbase, size_t total_elems, size_t size,
for partitions below MAX_THRESH size. BASE_PTR points to the beginning
of the array to sort, and END_PTR points at the very last element in
the array (*not* one beyond it!). */
-
-#define min(x, y) ((x) < (y) ? (x) : (y))
-
- {
- char *const end_ptr = &base_ptr[size * (total_elems - 1)];
- char *tmp_ptr = base_ptr;
- char *thresh = min(end_ptr, base_ptr + max_thresh);
- char *run_ptr;
-
- /* Find smallest element in first threshold and place it at the
- array's beginning. This is the smallest array element,
- and the operation speeds up insertion sort's inner loop. */
-
- for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size)
- if ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0)
- tmp_ptr = run_ptr;
-
- if (tmp_ptr != base_ptr)
- do_swap (tmp_ptr, base_ptr, size, swap_func);
-
- /* Insertion sort, running from left-hand-side up to right-hand-side. */
-
- run_ptr = base_ptr + size;
- while ((run_ptr += size) <= end_ptr)
- {
- tmp_ptr = run_ptr - size;
- while ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0)
- tmp_ptr -= size;
-
- tmp_ptr += size;
- if (tmp_ptr != run_ptr)
- {
- char *trav;
-
- trav = run_ptr + size;
- while (--trav >= run_ptr)
- {
- char c = *trav;
- char *hi, *lo;
-
- for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo)
- *hi = *lo;
- *hi = c;
- }
- }
- }
- }
+ insertion_sort (pbase, total_elems, size, swap_func, cmp, arg);
}
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2021-09-06 18:44 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-09-06 18:22 [glibc/azanella/qsort-fixes] stdlib: Move insertion sort out qsort Adhemerval Zanella
2021-09-06 18:44 Adhemerval Zanella
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).