[v6,2/6] stdlib: Move insertion sort out qsort
Checks
Context |
Check |
Description |
redhat-pt-bot/TryBot-apply_patch |
success
|
Patch applied to master at the time it was sent
|
linaro-tcwg-bot/tcwg_glibc_build--master-arm |
success
|
Testing passed
|
linaro-tcwg-bot/tcwg_glibc_build--master-aarch64 |
success
|
Testing passed
|
Commit Message
---
stdlib/qsort.c | 101 ++++++++++++++++++++++++++-----------------------
1 file changed, 54 insertions(+), 47 deletions(-)
Comments
On Tue, Jul 18, 2023 at 9:17 AM Adhemerval Zanella via Libc-alpha
<libc-alpha@sourceware.org> wrote:
>
> ---
> stdlib/qsort.c | 101 ++++++++++++++++++++++++++-----------------------
> 1 file changed, 54 insertions(+), 47 deletions(-)
>
> diff --git a/stdlib/qsort.c b/stdlib/qsort.c
> index 5bcc287c79..77630951df 100644
> --- a/stdlib/qsort.c
> +++ b/stdlib/qsort.c
> @@ -156,6 +156,58 @@ typedef struct
> smaller partition. This *guarantees* no more than log (total_elems)
> stack size is needed (actually O(1) in this case)! */
>
Imo this comment block should be moved down to just before `qsort`.
> +static inline void
> +insertion_sort_qsort_partitions (void *const pbase, size_t total_elems,
> + size_t size, enum swap_type_t swap_func,
nit: swap_func -> swap_type/swap_method.
> + __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)
> @@ -278,51 +330,6 @@ _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_type);
> -
> - /* 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_qsort_partitions (pbase, total_elems, size, swap_type, cmp,
> + arg);
> }
> --
> 2.34.1
>
On 29/08/23 04:39, Noah Goldstein wrote:
> On Tue, Jul 18, 2023 at 9:17 AM Adhemerval Zanella via Libc-alpha
> <libc-alpha@sourceware.org> wrote:
>>
>> ---
>> stdlib/qsort.c | 101 ++++++++++++++++++++++++++-----------------------
>> 1 file changed, 54 insertions(+), 47 deletions(-)
>>
>> diff --git a/stdlib/qsort.c b/stdlib/qsort.c
>> index 5bcc287c79..77630951df 100644
>> --- a/stdlib/qsort.c
>> +++ b/stdlib/qsort.c
>> @@ -156,6 +156,58 @@ typedef struct
>> smaller partition. This *guarantees* no more than log (total_elems)
>> stack size is needed (actually O(1) in this case)! */
>>
>
> Imo this comment block should be moved down to just before `qsort`.
Ack.
>> +static inline void
>> +insertion_sort_qsort_partitions (void *const pbase, size_t total_elems,
>> + size_t size, enum swap_type_t swap_func,
> nit: swap_func -> swap_type/swap_method.
Ack.
>> + __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)
>> @@ -278,51 +330,6 @@ _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_type);
>> -
>> - /* 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_qsort_partitions (pbase, total_elems, size, swap_type, cmp,
>> + arg);
>> }
>> --
>> 2.34.1
>>
@@ -156,6 +156,58 @@ typedef struct
smaller partition. This *guarantees* no more than log (total_elems)
stack size is needed (actually O(1) in this case)! */
+static inline void
+insertion_sort_qsort_partitions (void *const pbase, size_t total_elems,
+ size_t size, enum swap_type_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)
@@ -278,51 +330,6 @@ _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_type);
-
- /* 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_qsort_partitions (pbase, total_elems, size, swap_type, cmp,
+ arg);
}