diff mbox series

[v4,2/6] stdlib: Move insertion sort out qsort

Message ID 20230711190722.4028821-3-adhemerval.zanella@linaro.org
State Superseded
Headers
Series Use introsort for 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-aarch64 success Testing passed
linaro-tcwg-bot/tcwg_glibc_check--master-aarch64 success Testing passed
linaro-tcwg-bot/tcwg_glibc_check--master-arm success Testing passed

Commit Message

Adhemerval Zanella Netto July 11, 2023, 7:07 p.m. UTC 
  ---
 stdlib/qsort.c | 100 ++++++++++++++++++++++++++-----------------------
 1 file changed, 53 insertions(+), 47 deletions(-)

Comments

Noah Goldstein July 11, 2023, 11:46 p.m. UTC | #1 
On Tue, Jul 11, 2023 at 2:09 PM Adhemerval Zanella via Libc-alpha
<libc-alpha@sourceware.org> wrote:
>
> ---
>  stdlib/qsort.c | 100 ++++++++++++++++++++++++++-----------------------
>  1 file changed, 53 insertions(+), 47 deletions(-)
>
> diff --git a/stdlib/qsort.c b/stdlib/qsort.c
> index 8a3331fdb4..00637208ab 100644
> --- a/stdlib/qsort.c
> +++ b/stdlib/qsort.c
> @@ -153,6 +153,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 (void *const pbase, size_t total_elems, size_t size,

Maybe a less generic name would be better. Something like:
"insertion_sort_qsort_partions" to indicate this is not just standard
insertion sort but a helper for qsort. Just thinking about a reader
grepping around in a year or so.
> +                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)
> @@ -275,51 +327,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);
>  }
> --
> 2.34.1
>
Andreas Schwab July 12, 2023, 7:28 a.m. UTC | #2 
On Jul 11 2023, Noah Goldstein via Libc-alpha wrote:

> Maybe a less generic name would be better. Something like:
> "insertion_sort_qsort_partions" to indicate this is not just standard

s/partions/partitions/
Adhemerval Zanella Netto July 12, 2023, 8:35 p.m. UTC | #3 
On 11/07/23 20:46, Noah Goldstein wrote:
> On Tue, Jul 11, 2023 at 2:09 PM Adhemerval Zanella via Libc-alpha
> <libc-alpha@sourceware.org> wrote:
>>
>> ---
>>  stdlib/qsort.c | 100 ++++++++++++++++++++++++++-----------------------
>>  1 file changed, 53 insertions(+), 47 deletions(-)
>>
>> diff --git a/stdlib/qsort.c b/stdlib/qsort.c
>> index 8a3331fdb4..00637208ab 100644
>> --- a/stdlib/qsort.c
>> +++ b/stdlib/qsort.c
>> @@ -153,6 +153,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 (void *const pbase, size_t total_elems, size_t size,
> 
> Maybe a less generic name would be better. Something like:
> "insertion_sort_qsort_partions" to indicate this is not just standard
> insertion sort but a helper for qsort. Just thinking about a reader
> grepping around in a year or so.

Fair enough, I will change it.

>> +                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)
>> @@ -275,51 +327,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);
>>  }
>> --
>> 2.34.1
>>
diff mbox series

Patch

diff --git a/stdlib/qsort.c b/stdlib/qsort.c
index 8a3331fdb4..00637208ab 100644
--- a/stdlib/qsort.c
+++ b/stdlib/qsort.c
@@ -153,6 +153,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 (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)
@@ -275,51 +327,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);
 }