public inbox for glibc-cvs@sourceware.org help / color / mirror / Atom feed
From: Adhemerval Zanella <azanella@sourceware.org> To: glibc-cvs@sourceware.org Subject: [glibc/azanella/qsort-fixes] stdlib: Move insertion sort out qsort Date: Mon, 6 Sep 2021 18:44:57 +0000 (GMT) [thread overview] Message-ID: <20210906184457.ECF9A383940F@sourceware.org> (raw) 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); }
next reply other threads:[~2021-09-06 18:44 UTC|newest] Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top 2021-09-06 18:44 Adhemerval Zanella [this message] -- strict thread matches above, loose matches on Subject: below -- 2021-09-06 18:22 Adhemerval Zanella
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=20210906184457.ECF9A383940F@sourceware.org \ --to=azanella@sourceware.org \ --cc=glibc-cvs@sourceware.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
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).