This is the mail archive of the glibc-cvs@sourceware.org mailing list for the glibc project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

GNU C Library master sources branch azanella/qsort-refactor created. glibc-2.26.9000-1134-g947509b


This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "GNU C Library master sources".

The branch, azanella/qsort-refactor has been created
        at  947509bf8cf4505c920ac0f8cd0288db8b4de9db (commit)

- Log -----------------------------------------------------------------
http://sourceware.org/git/gitweb.cgi?p=glibc.git;a=commitdiff;h=947509bf8cf4505c920ac0f8cd0288db8b4de9db

commit 947509bf8cf4505c920ac0f8cd0288db8b4de9db
Author: Adhemerval Zanella <adhemerval.zanella@linaro.org>
Date:   Tue Jan 16 14:24:53 2018 -0200

    stdlib: Remove undefined behavior from qsort implementation
    
    Internally qsort is implemented on top of __qsort_r by casting the
    function pointer to another type (__compar_fn_t tp __compar_d_fn_t)
    and passing a NULL extra argument.  Casting function pointer with
    different types for subsequent function call is undefined-behaviour
    (C11 6.3.2.3):
    
      "[8] A pointer to a function of one type may be converted to a pointer
      to a function of another type and back again; the result shall compare
      equal to the original pointer. If a converted pointer is used to call
      a function whose type is not compatible with the referenced type,
      the behavior is undefined."
    
    Also 'compatible' in this case also does not apply according to
    6.7.6.3 Function declarators (including prototypes):
    
      "[15] For two function types to be compatible, both shall specify
      compatible return types. (146) Moreover, the parameter type lists,
      if both are present, shall agree in the number of parameters and
      in use of the ellipsis terminator; corresponding parameters shall
      have compatible types. [...]"
    
    Although this works on all architectures glibc supports (mostly because
    it casts function pointers with similar calling conventions), I think
    it is worth to avoid it.  This patch fixes it by adding a common
    implementation (qsort_common.c) which redefines the function based
    on the required types.
    
    For x86_64 (i7-4790K, gcc 7.2.1) shows a slight better performance
    for qsort:
    
    Results for member size 4
      Sorted
      nmemb   |      base |   patched | diff
            32|      1304 |      1257 | -3.60
          4096|    330707 |    302235 | -8.61
         32768|   3300210 |   3020728 | -8.47
        524288|  65673289 |  59306436 | -9.69
    
      Repeated
      nmemb   |      base |   patched | diff
            32|      1885 |      1873 | -0.64
          4096|    951490 |    904864 | -4.90
         32768|   9272366 |   8542801 | -7.87
        524288| 183337854 | 168426795 | -8.13
    
      MostlySorted
      nmemb   |      base |   patched | diff
            32|      1836 |      1776 | -3.27
          4096|    758359 |    709937 | -6.39
         32768|   7199982 |   6855890 | -4.78
        524288| 139242170 | 129385161 | -7.08
    
      Unsorted
      nmemb   |      base |   patched | diff
            32|      2073 |      1941 | -6.37
          4096|   1058383 |    969021 | -8.44
         32768|  10310116 |   9462116 | -8.22
        524288| 202427388 | 186560908 | -7.84
    
    Results for member size 8
      Sorted
      nmemb   |      base |   patched | diff
            32|      1224 |      1205 | -1.55
          4096|    336100 |    325554 | -3.14
         32768|   3539890 |   3264125 | -7.79
        524288|  67268510 |  66107684 | -1.73
    
      Repeated
      nmemb   |      base |   patched | diff
            32|      2096 |      2118 | 1.05
          4096|   1015585 |    979114 | -3.59
         32768|   9871981 |   9028606 | -8.54
        524288| 189710172 | 174903867 | -7.80
    
      MostlySorted
      nmemb   |      base |   patched | diff
            32|      2318 |      2346 | 1.21
          4096|    805051 |    759158 | -5.70
         32768|   8346363 |   7810444 | -6.42
        524288| 143597264 | 135900146 | -5.36
    
      Unsorted
      nmemb   |      base |   patched | diff
            32|      2364 |      2301 | -2.66
          4096|   1076998 |   1014018 | -5.85
         32768|  10442153 |   9888078 | -5.31
        524288| 206235337 | 192479957 | -6.67
    
    Results for member size 32
      Sorted
      nmemb   |      base |   patched | diff
            32|      1214 |      1184 | -2.47
          4096|    332449 |    325865 | -1.98
         32768|   3313274 |   3331750 | 0.56
        524288|  70786673 |  69067176 | -2.43
    
      Repeated
      nmemb   |      base |   patched | diff
            32|      4913 |      4813 | -2.04
          4096|   1693735 |   1624137 | -4.11
         32768|  17054760 |  15896739 | -6.79
        524288| 332149265 | 316328778 | -4.76
    
      MostlySorted
      nmemb   |      base |   patched | diff
            32|      5490 |      5332 | -2.88
          4096|   1394312 |   1312703 | -5.85
         32768|  12743599 |  12360726 | -3.00
        524288| 240249011 | 231603294 | -3.60
    
      Unsorted
      nmemb   |      base |   patched | diff
            32|      6251 |      6047 | -3.26
          4096|   1959306 |   1695241 | -13.48
         32768|  17204840 |  16430388 | -4.50
        524288| 342716199 | 329496913 | -3.86
    
    Checked on x86_64-linux-gnu.
    
    	* stdlib/qsort.c: Move common code to stdlib/qsort_common.c
    	and parametrize the function definition based wether to use
    	the '_r' variant.
    	* stdlib/qsort_common.c: New file.

diff --git a/stdlib/qsort.c b/stdlib/qsort.c
index 2194003..03ab0e5 100644
--- a/stdlib/qsort.c
+++ b/stdlib/qsort.c
@@ -16,17 +16,13 @@
    License along with the GNU C Library; if not, see
    <http://www.gnu.org/licenses/>.  */
 
-/* If you consider tuning this algorithm, you should consult first:
-   Engineering a sort function; Jon Bentley and M. Douglas McIlroy;
-   Software - Practice and Experience; Vol. 23 (11), 1249-1265, 1993.  */
-
 #include <limits.h>
 #include <stdlib.h>
 #include <string.h>
 #include <stdbool.h>
 
-/* Swap SIZE bytes between addresses A and B.  Helper to generic types
-   are provided as an optimization.  */
+/* Swap SIZE bytes between addresses A and B.  These helpers are provided
+   along the generic one as an optimization.  */
 
 typedef void (*swap_t)(void *, void *, size_t);
 
@@ -98,202 +94,14 @@ typedef struct
 #define	POP(low, high)	((void) (--top, (low = top->lo), (high = top->hi)))
 #define	STACK_NOT_EMPTY	(stack < top)
 
-
-/* Order size using quicksort.  This implementation incorporates
-   four optimizations discussed in Sedgewick:
-
-   1. Non-recursive, using an explicit stack of pointer that store the
-      next array partition to sort.  To save time, this maximum amount
-      of space required to store an array of SIZE_MAX is allocated on the
-      stack.  Assuming a 32-bit (64 bit) integer for size_t, this needs
-      only 32 * sizeof(stack_node) == 256 bytes (for 64 bit: 1024 bytes).
-      Pretty cheap, actually.
-
-   2. Chose the pivot element using a median-of-three decision tree.
-      This reduces the probability of selecting a bad pivot value and
-      eliminates certain extraneous comparisons.
-
-   3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
-      insertion sort to order the MAX_THRESH items within each partition.
-      This is a big win, since insertion sort is faster for small, mostly
-      sorted array segments.
-
-   4. The larger of the two sub-partitions is always pushed onto the
-      stack first, with the algorithm then concentrating on the
-      smaller partition.  This *guarantees* no more than log (total_elems)
-      stack size is needed (actually O(1) in this case)!  */
-
-void
-__qsort_r (void *const pbase, size_t total_elems, size_t size,
-	   __compar_d_fn_t cmp, void *arg)
-{
-  char *base_ptr = (char *) pbase;
-
-  const size_t max_thresh = MAX_THRESH * size;
-
-  if (total_elems == 0)
-    /* Avoid lossage with unsigned arithmetic below.  */
-    return;
-
-  swap_t swap = select_swap_func (pbase, size);
-
-  if (total_elems > MAX_THRESH)
-    {
-      char *lo = base_ptr;
-      char *hi = &lo[size * (total_elems - 1)];
-      stack_node stack[STACK_SIZE];
-      stack_node *top = stack;
-
-      PUSH (NULL, NULL);
-
-      while (STACK_NOT_EMPTY)
-        {
-          char *left_ptr;
-          char *right_ptr;
-
-	  /* Select median value from among LO, MID, and HI. Rearrange
-	     LO and HI so the three values are sorted. This lowers the
-	     probability of picking a pathological pivot value and
-	     skips a comparison for both the LEFT_PTR and RIGHT_PTR in
-	     the while loops. */
-
-	  char *mid = lo + size * ((hi - lo) / size >> 1);
-
-	  if ((*cmp) ((void *) mid, (void *) lo, arg) < 0)
-	    swap (mid, lo, size);
-	  if ((*cmp) ((void *) hi, (void *) mid, arg) < 0)
-	    swap (mid, hi, size);
-	  else
-	    goto jump_over;
-	  if ((*cmp) ((void *) mid, (void *) lo, arg) < 0)
-	    swap (mid, lo, size);
-	jump_over:;
-
-	  left_ptr  = lo + size;
-	  right_ptr = hi - size;
-
-	  /* Here's the famous ``collapse the walls'' section of quicksort.
-	     Gotta like those tight inner loops!  They are the main reason
-	     that this algorithm runs much faster than others. */
-	  do
-	    {
-	      while ((*cmp) ((void *) left_ptr, (void *) mid, arg) < 0)
-		left_ptr += size;
-
-	      while ((*cmp) ((void *) mid, (void *) right_ptr, arg) < 0)
-		right_ptr -= size;
-
-	      if (left_ptr < right_ptr)
-		{
-		  swap (left_ptr, right_ptr, size);
-		  if (mid == left_ptr)
-		    mid = right_ptr;
-		  else if (mid == right_ptr)
-		    mid = left_ptr;
-		  left_ptr += size;
-		  right_ptr -= size;
-		}
-	      else if (left_ptr == right_ptr)
-		{
-		  left_ptr += size;
-		  right_ptr -= size;
-		  break;
-		}
-	    }
-	  while (left_ptr <= right_ptr);
-
-          /* Set up pointers for next iteration.  First determine whether
-             left and right partitions are below the threshold size.  If so,
-             ignore one or both.  Otherwise, push the larger partition's
-             bounds on the stack and continue sorting the smaller one. */
-
-          if ((size_t) (right_ptr - lo) <= max_thresh)
-            {
-              if ((size_t) (hi - left_ptr) <= max_thresh)
-		/* Ignore both small partitions. */
-                POP (lo, hi);
-              else
-		/* Ignore small left partition. */
-                lo = left_ptr;
-            }
-          else if ((size_t) (hi - left_ptr) <= max_thresh)
-	    /* Ignore small right partition. */
-            hi = right_ptr;
-          else if ((right_ptr - lo) > (hi - left_ptr))
-            {
-	      /* Push larger left partition indices. */
-              PUSH (lo, right_ptr);
-              lo = left_ptr;
-            }
-          else
-            {
-	      /* Push larger right partition indices. */
-              PUSH (left_ptr, hi);
-              hi = right_ptr;
-            }
-        }
-    }
-
-  /* Once the BASE_PTR array is partially sorted by quicksort the rest
-     is completely sorted using insertion sort, since this is efficient
-     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)
-      swap (tmp_ptr, base_ptr, size);
-
-    /* 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;
-              }
-          }
-      }
-  }
-}
+#define R_VERSION
+#define R_FUNC    __qsort_r
+#include <stdlib/qsort_common.c>
 
 libc_hidden_def (__qsort_r)
 weak_alias (__qsort_r, qsort_r)
 
-void
-qsort (void *b, size_t n, size_t s, __compar_fn_t cmp)
-{
-  return __qsort_r (b, n, s, (__compar_d_fn_t) cmp, NULL);
-}
+#define R_FUNC   qsort
+#include <stdlib/qsort_common.c>
+
 libc_hidden_def (qsort)
diff --git a/stdlib/qsort.c b/stdlib/qsort_common.c
similarity index 67%
copy from stdlib/qsort.c
copy to stdlib/qsort_common.c
index 2194003..666b195 100644
--- a/stdlib/qsort.c
+++ b/stdlib/qsort_common.c
@@ -1,6 +1,6 @@
-/* Copyright (C) 1991-2018 Free Software Foundation, Inc.
+/* Common implementation for both qsort and qsort_r.
+   Copyright (C) 2018 Free Software Foundation, Inc.
    This file is part of the GNU C Library.
-   Written by Douglas C. Schmidt (schmidt@ics.uci.edu).
 
    The GNU C Library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Lesser General Public
@@ -20,84 +20,15 @@
    Engineering a sort function; Jon Bentley and M. Douglas McIlroy;
    Software - Practice and Experience; Vol. 23 (11), 1249-1265, 1993.  */
 
-#include <limits.h>
-#include <stdlib.h>
-#include <string.h>
-#include <stdbool.h>
-
-/* Swap SIZE bytes between addresses A and B.  Helper to generic types
-   are provided as an optimization.  */
-
-typedef void (*swap_t)(void *, void *, size_t);
-
-static inline bool
-check_alignment (const void *base, size_t align)
-{
-  return _STRING_ARCH_unaligned || ((uintptr_t)base % (align - 1)) == 0;
-}
-
-static void
-swap_u32 (void *a, void *b, size_t size)
-{
-  uint32_t tmp = *(uint32_t*) a;
-  *(uint32_t*) a = *(uint32_t*) b;
-  *(uint32_t*) b = tmp;
-}
-
-static void
-swap_u64 (void *a, void *b, size_t size)
-{
-  uint64_t tmp = *(uint64_t*) a;
-  *(uint64_t*) a = *(uint64_t*) b;
-  *(uint64_t*) b = tmp;
-}
-
-static inline void
-swap_generic (void *a, void *b, size_t size)
-{
-  unsigned char tmp[128];
-  do
-    {
-      size_t s = size > sizeof (tmp) ? sizeof (tmp) : size;
-      memcpy (tmp, a, s);
-      a = __mempcpy (a, b, s);
-      b = __mempcpy (b, tmp, s);
-      size -= s;
-    }
-  while (size > 0);
-}
-
-static inline swap_t
-select_swap_func (const void *base, size_t size)
-{
-  if (size == 4 && check_alignment (base, 4))
-    return swap_u32;
-  else if (size == 8 && check_alignment (base, 8))
-    return swap_u64;
-  return swap_generic;
-}
-
-/* Discontinue quicksort algorithm when partition gets below this size.
-   This particular magic number was chosen to work best on a Sun 4/260. */
-#define MAX_THRESH 4
-
-/* Stack node declarations used to store unfulfilled partition obligations. */
-typedef struct
-  {
-    char *lo;
-    char *hi;
-  } stack_node;
-
-/* The next 4 #defines implement a very fast in-line stack abstraction. */
-/* The stack needs log (total_elements) entries (we could even subtract
-   log(MAX_THRESH)).  Since total_elements has type size_t, we get as
-   upper bound for log (total_elements):
-   bits per byte (CHAR_BIT) * sizeof(size_t).  */
-#define STACK_SIZE	(CHAR_BIT * sizeof(size_t))
-#define PUSH(low, high)	((void) ((top->lo = (low)), (top->hi = (high)), ++top))
-#define	POP(low, high)	((void) (--top, (low = top->lo), (high = top->hi)))
-#define	STACK_NOT_EMPTY	(stack < top)
-
+#ifdef R_VERSION
+# define R_CMP_TYPE          __compar_d_fn_t
+# define R_CMP_ARG           , void *arg
+# define R_CMP(p1, p2)       cmp (p1, p2, arg)
+#else
+# define R_CMP_TYPE           __compar_fn_t
+# define R_CMP_ARG
+# define R_CMP(p1, p2)       cmp (p1, p2)
+#endif
 
 /* Order size using quicksort.  This implementation incorporates
    four optimizations discussed in Sedgewick:
@@ -124,17 +55,16 @@ typedef struct
       stack size is needed (actually O(1) in this case)!  */
 
 void
-__qsort_r (void *const pbase, size_t total_elems, size_t size,
-	   __compar_d_fn_t cmp, void *arg)
+R_FUNC (void *pbase, size_t total_elems, size_t size, R_CMP_TYPE cmp R_CMP_ARG)
 {
-  char *base_ptr = (char *) pbase;
-
-  const size_t max_thresh = MAX_THRESH * size;
-
   if (total_elems == 0)
     /* Avoid lossage with unsigned arithmetic below.  */
     return;
 
+  char *base_ptr = (char *) pbase;
+
+  const size_t max_thresh = MAX_THRESH * size;
+
   swap_t swap = select_swap_func (pbase, size);
 
   if (total_elems > MAX_THRESH)
@@ -159,13 +89,13 @@ __qsort_r (void *const pbase, size_t total_elems, size_t size,
 
 	  char *mid = lo + size * ((hi - lo) / size >> 1);
 
-	  if ((*cmp) ((void *) mid, (void *) lo, arg) < 0)
+	  if (R_CMP ((void *) mid, (void *) lo) < 0)
 	    swap (mid, lo, size);
-	  if ((*cmp) ((void *) hi, (void *) mid, arg) < 0)
+	  if (R_CMP ((void *) hi, (void *) mid) < 0)
 	    swap (mid, hi, size);
 	  else
 	    goto jump_over;
-	  if ((*cmp) ((void *) mid, (void *) lo, arg) < 0)
+	  if (R_CMP ((void *) mid, (void *) lo) < 0)
 	    swap (mid, lo, size);
 	jump_over:;
 
@@ -177,10 +107,10 @@ __qsort_r (void *const pbase, size_t total_elems, size_t size,
 	     that this algorithm runs much faster than others. */
 	  do
 	    {
-	      while ((*cmp) ((void *) left_ptr, (void *) mid, arg) < 0)
+	      while (R_CMP ((void *) left_ptr, (void *) mid) < 0)
 		left_ptr += size;
 
-	      while ((*cmp) ((void *) mid, (void *) right_ptr, arg) < 0)
+	      while (R_CMP ((void *) mid, (void *) right_ptr) < 0)
 		right_ptr -= size;
 
 	      if (left_ptr < right_ptr)
@@ -240,12 +170,11 @@ __qsort_r (void *const pbase, size_t total_elems, size_t size,
      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 *thresh = end_ptr < base_ptr + max_thresh ?
+		   end_ptr : base_ptr + max_thresh;
     char *run_ptr;
 
     /* Find smallest element in first threshold and place it at the
@@ -253,7 +182,7 @@ __qsort_r (void *const pbase, size_t total_elems, size_t size,
        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)
+      if (R_CMP ((void *) run_ptr, (void *) tmp_ptr) < 0)
         tmp_ptr = run_ptr;
 
     if (tmp_ptr != base_ptr)
@@ -265,7 +194,7 @@ __qsort_r (void *const pbase, size_t total_elems, size_t size,
     while ((run_ptr += size) <= end_ptr)
       {
 	tmp_ptr = run_ptr - size;
-	while ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0)
+	while (R_CMP ((void *) run_ptr, (void *) tmp_ptr) < 0)
 	  tmp_ptr -= size;
 
 	tmp_ptr += size;
@@ -288,12 +217,9 @@ __qsort_r (void *const pbase, size_t total_elems, size_t size,
   }
 }
 
-libc_hidden_def (__qsort_r)
-weak_alias (__qsort_r, qsort_r)
-
-void
-qsort (void *b, size_t n, size_t s, __compar_fn_t cmp)
-{
-  return __qsort_r (b, n, s, (__compar_d_fn_t) cmp, NULL);
-}
-libc_hidden_def (qsort)
+#undef R_NAME
+#undef R_CMP_TYPE
+#undef R_CMP_ARG
+#undef R_CMP
+#undef R_FUNC
+#undef R_VERSION

http://sourceware.org/git/gitweb.cgi?p=glibc.git;a=commitdiff;h=2ff332e3d3bfe13cfc75bd8f59ee0aad9f3dafbb

commit 2ff332e3d3bfe13cfc75bd8f59ee0aad9f3dafbb
Author: Adhemerval Zanella <adhemerval.zanella@linaro.org>
Date:   Tue Jan 16 11:19:15 2018 -0200

    stdlib: Optimization qsort{_r} swap implementation
    
    This patchs adds a optimized swap operation on qsort based in previous
    msort one.  Instead of byte operation, three variants are provided:
    
      1. Using uint32_t loads and stores.
      2. Using uint64_t loads and stores.
      3. Generic one with a temporary buffer and memcpy/mempcpy.
    
    The 1. and 2. option are selected only either if architecture defines
    _STRING_ARCH_unaligned or if base pointer is aligned to required type.
    This is due based on data for bench-qsort, usually programs calls
    qsort with array with multiple of machine word as element size.
    
    Benchmarking shows an increase performance:
    
    Results for member size 4
      Sorted
      nmemb   |      base |   patched | diff
            32|      1401 |      1958 | 39.76
          4096|    351333 |    368533 | 4.90
         32768|   3369386 |   3131712 | -7.05
        524288|  63192972 |  59807494 | -5.36
    
      MostlySorted
      nmemb   |      base |   patched | diff
            32|      2391 |      2061 | -13.80
          4096|   1124074 |    961816 | -14.43
         32768|  11196607 |   9410438 | -15.95
        524288| 215908169 | 185586732 | -14.04
    
      Unsorted
      nmemb   |      base |   patched | diff
            32|      4993 |      2021 | -59.52
          4096|   1113860 |    963126 | -13.53
         32768|  11251293 |   9518795 | -15.40
        524288| 217252237 | 185072278 | -14.81
    
    Results for member size 8
      Sorted
      nmemb   |      base |   patched | diff
            32|      1296 |      1267 | -2.24
          4096|    359418 |    334852 | -6.83
         32768|   3535229 |   3345157 | -5.38
        524288|  69847251 |  67029358 | -4.03
    
      MostlySorted
      nmemb   |      base |   patched | diff
            32|      2745 |      2340 | -14.75
          4096|   1222082 |   1014314 | -17.00
         32768|  12244800 |   9924706 | -18.95
        524288| 241557971 | 196898760 | -18.49
    
      Unsorted
      nmemb   |      base |   patched | diff
            32|      2972 |      2389 | -19.62
          4096|   1314861 |   1024052 | -22.12
         32768|  12397909 |  10120848 | -18.37
        524288| 241789262 | 193414824 | -20.01
    
    Results for member size 32
      Sorted
      nmemb   |      base |   patched | diff
            32|      1305 |      1287 | -1.38
          4096|    346332 |    347979 | 0.48
         32768|   3458244 |   3408058 | -1.45
        524288|  72793445 |  69973719 | -3.87
    
      MostlySorted
      nmemb   |      base |   patched | diff
            32|      5435 |      4890 | -10.03
          4096|   2032260 |   1688556 | -16.91
         32768|  19909035 |  16419992 | -17.52
        524288| 390339319 | 325921585 | -16.50
    
      Unsorted
      nmemb   |      base |   patched | diff
            32|      5833 |      5351 | -8.26
          4096|   2022531 |   1724961 | -14.71
         32768|  19842888 |  16588545 | -16.40
        524288| 388838382 | 324102703 | -16.65
    
    Checked on x86_64-linux-gnu.
    
    	[BZ #19305].
    	* stdlib/qsort.c (SWAP): Remove.
    	(check_alignment, swap_u32, swap_u64, swap_generic,
    	select_swap_func): New functions.
    	(__qsort_r):

diff --git a/stdlib/qsort.c b/stdlib/qsort.c
index b3a5102..2194003 100644
--- a/stdlib/qsort.c
+++ b/stdlib/qsort.c
@@ -23,20 +23,59 @@
 #include <limits.h>
 #include <stdlib.h>
 #include <string.h>
+#include <stdbool.h>
 
-/* Byte-wise swap two items of size SIZE. */
-#define SWAP(a, b, size)						      \
-  do									      \
-    {									      \
-      size_t __size = (size);						      \
-      char *__a = (a), *__b = (b);					      \
-      do								      \
-	{								      \
-	  char __tmp = *__a;						      \
-	  *__a++ = *__b;						      \
-	  *__b++ = __tmp;						      \
-	} while (--__size > 0);						      \
-    } while (0)
+/* Swap SIZE bytes between addresses A and B.  Helper to generic types
+   are provided as an optimization.  */
+
+typedef void (*swap_t)(void *, void *, size_t);
+
+static inline bool
+check_alignment (const void *base, size_t align)
+{
+  return _STRING_ARCH_unaligned || ((uintptr_t)base % (align - 1)) == 0;
+}
+
+static void
+swap_u32 (void *a, void *b, size_t size)
+{
+  uint32_t tmp = *(uint32_t*) a;
+  *(uint32_t*) a = *(uint32_t*) b;
+  *(uint32_t*) b = tmp;
+}
+
+static void
+swap_u64 (void *a, void *b, size_t size)
+{
+  uint64_t tmp = *(uint64_t*) a;
+  *(uint64_t*) a = *(uint64_t*) b;
+  *(uint64_t*) b = tmp;
+}
+
+static inline void
+swap_generic (void *a, void *b, size_t size)
+{
+  unsigned char tmp[128];
+  do
+    {
+      size_t s = size > sizeof (tmp) ? sizeof (tmp) : size;
+      memcpy (tmp, a, s);
+      a = __mempcpy (a, b, s);
+      b = __mempcpy (b, tmp, s);
+      size -= s;
+    }
+  while (size > 0);
+}
+
+static inline swap_t
+select_swap_func (const void *base, size_t size)
+{
+  if (size == 4 && check_alignment (base, 4))
+    return swap_u32;
+  else if (size == 8 && check_alignment (base, 8))
+    return swap_u64;
+  return swap_generic;
+}
 
 /* Discontinue quicksort algorithm when partition gets below this size.
    This particular magic number was chosen to work best on a Sun 4/260. */
@@ -96,6 +135,8 @@ __qsort_r (void *const pbase, size_t total_elems, size_t size,
     /* Avoid lossage with unsigned arithmetic below.  */
     return;
 
+  swap_t swap = select_swap_func (pbase, size);
+
   if (total_elems > MAX_THRESH)
     {
       char *lo = base_ptr;
@@ -119,13 +160,13 @@ __qsort_r (void *const pbase, size_t total_elems, size_t size,
 	  char *mid = lo + size * ((hi - lo) / size >> 1);
 
 	  if ((*cmp) ((void *) mid, (void *) lo, arg) < 0)
-	    SWAP (mid, lo, size);
+	    swap (mid, lo, size);
 	  if ((*cmp) ((void *) hi, (void *) mid, arg) < 0)
-	    SWAP (mid, hi, size);
+	    swap (mid, hi, size);
 	  else
 	    goto jump_over;
 	  if ((*cmp) ((void *) mid, (void *) lo, arg) < 0)
-	    SWAP (mid, lo, size);
+	    swap (mid, lo, size);
 	jump_over:;
 
 	  left_ptr  = lo + size;
@@ -144,7 +185,7 @@ __qsort_r (void *const pbase, size_t total_elems, size_t size,
 
 	      if (left_ptr < right_ptr)
 		{
-		  SWAP (left_ptr, right_ptr, size);
+		  swap (left_ptr, right_ptr, size);
 		  if (mid == left_ptr)
 		    mid = right_ptr;
 		  else if (mid == right_ptr)
@@ -216,7 +257,7 @@ __qsort_r (void *const pbase, size_t total_elems, size_t size,
         tmp_ptr = run_ptr;
 
     if (tmp_ptr != base_ptr)
-      SWAP (tmp_ptr, base_ptr, size);
+      swap (tmp_ptr, base_ptr, size);
 
     /* Insertion sort, running from left-hand-side up to right-hand-side.  */
 

http://sourceware.org/git/gitweb.cgi?p=glibc.git;a=commitdiff;h=7a8db37160c1be6828160a566d4c115760b66d0e

commit 7a8db37160c1be6828160a566d4c115760b66d0e
Author: Adhemerval Zanella <adhemerval.zanella@linaro.org>
Date:   Tue Jan 16 10:49:43 2018 -0200

    stdlib: Remove use of mergesort on qsort
    
    This patch removes the mergesort optimization on qsort{_r} implementation
    and use the quicksort instead.  The mergesort implementation has some
    issues:
    
      - It is as-safe only for certain types sizes (if total size is less
        than 1 KB with large element sizes also forcing memory allocation)
        which contradicts the function documentation.  Although not required
        by the C standard, it is preferable and doable to have a O(1) space
        qsort implementation.
    
      - The malloc for certain element size and element number adds arbitrary
        latency (might even be worse if malloc is interposed).
    
      - To avoid trigger swap from memory allocation the implementation relies
        on system information that might be virtualized (for instance VMs with
        overcommit memory) which might leads to potentially use of swap even
        if system advertise more memory than actually has.  The check also have
        the downside of issuing syscalls where none is expected (although only
        once per execution).
    
      - The mergesort is suboptimal on already sorted array (BZ#21719).
    
    The quicksort implementation is already optimized to use O(1) space and
    thus can be used to avoid the malloc usage issues.
    
    Using bench-qsort (i7-4790K, gcc 7.2.1) shows the performance difference
    between mergesort (base) and quicksort (patched):
    
    Results for member size 4
      Sorted
      nmemb   |      base |   patched | diff
            32|      1447 |      1401 | -3.18
          4096|    315978 |    351333 | 11.19
         32768|   2559093 |   3369386 | 31.66
        524288|  46228488 |  63192972 | 36.70
    
      MostlySorted
      nmemb   |      base |   patched | diff
            32|      1974 |      2391 | 21.12
          4096|    922332 |   1124074 | 21.87
         32768|   9268671 |  11196607 | 20.80
        524288| 186856297 | 215908169 | 15.55
    
      Unsorted
      nmemb   |      base |   patched | diff
            32|      1978 |      4993 | 152.43
          4096|    916413 |   1113860 | 21.55
         32768|   9270003 |  11251293 | 21.37
        524288| 187606088 | 217252237 | 15.80
    
    Results for member size 8
      Sorted
      nmemb   |      base |   patched | diff
            32|      1424 |      1296 | -8.99
          4096|    299105 |    359418 | 20.16
         32768|   2737859 |   3535229 | 29.12
        524288|  53082807 |  69847251 | 31.58
    
      MostlySorted
      nmemb   |      base |   patched | diff
            32|      2129 |      2745 | 28.93
          4096|    969465 |   1222082 | 26.06
         32768|   9605227 |  12244800 | 27.48
        524288| 193353927 | 241557971 | 24.93
    
      Unsorted
      nmemb   |      base |   patched | diff
            32|      2194 |      2972 | 35.46
          4096|    958610 |   1314861 | 37.16
         32768|   9664246 |  12397909 | 28.29
        524288| 193758429 | 241789262 | 24.79
    
    Results for member size 32
      Sorted
      nmemb   |      base |   patched | diff
            32|      4477 |      1305 | -70.85
          4096|   1109492 |    346332 | -68.78
         32768|  11075976 |   3458244 | -68.78
        524288| 230773658 |  72793445 | -68.46
    
      MostlySorted
      nmemb   |      base |   patched | diff
            32|      5905 |      5435 | -7.96
          4096|   2568895 |   2032260 | -20.89
         32768|  24936755 |  19909035 | -20.16
        524288| 526442900 | 390339319 | -25.85
    
      Unsorted
      nmemb   |      base |   patched | diff
            32|      6004 |      5833 | -2.85
          4096|   2437943 |   2022531 | -17.04
         32768|  24789971 |  19842888 | -19.96
        524288| 525898556 | 388838382 | -26.06
    
    An increase in latency, however some performance difference is due the fact
    mergesort uses a slight improved swap operation than quicksort (which following
    patch addresses).  This change also renders the BZ #21719 fix unrequired (since
    it is to fix the sorted input performance degradation for mergesort).  The
    manual is also updated to indicate the function is not async-cancel safe.
    
    Checked on x86_64-linux-gnu.
    
    	[BZ #21719]
    	* stdlib/Makefile (routines): Remove msort.
    	(CFLAGS-msort.c): Remove rule.
    	* stdlib/msort.c: Remove file.
    	* stdlib/qsort.c (_quicksort): Rename to __qsort_r and add weak_alias
    	to qsort_r.
    	(qsort): New symbol.
    	* manual/argp.texi: Remove qsort @acu* annotation.
    	* manual/locale.texi: Likewise.
    	* manual/search.texi: Likewise.

diff --git a/manual/argp.texi b/manual/argp.texi
index 0023441..b77ad68 100644
--- a/manual/argp.texi
+++ b/manual/argp.texi
@@ -735,7 +735,7 @@ for options, bad phase of the moon, etc.
 @c  hol_set_group ok
 @c   hol_find_entry ok
 @c  hol_sort @mtslocale @acucorrupt
-@c   qsort dup @acucorrupt
+@c   qsort dup
 @c    hol_entry_qcmp @mtslocale
 @c     hol_entry_cmp @mtslocale
 @c      group_cmp ok
diff --git a/manual/locale.texi b/manual/locale.texi
index 60ad2a1..9e742e4 100644
--- a/manual/locale.texi
+++ b/manual/locale.texi
@@ -253,7 +253,7 @@ The symbols in this section are defined in the header file @file{locale.h}.
 @c    calculate_head_size ok
 @c    __munmap ok
 @c    compute_hashval ok
-@c    qsort dup @acucorrupt
+@c    qsort dup
 @c     rangecmp ok
 @c    malloc @ascuheap @acsmem
 @c    strdup @ascuheap @acsmem
@@ -275,7 +275,6 @@ The symbols in this section are defined in the header file @file{locale.h}.
 @c      realloc @ascuheap @acsmem
 @c     realloc @ascuheap @acsmem
 @c     fclose @ascuheap @asulock @acsmem @acsfd @aculock
-@c     qsort @ascuheap @acsmem
 @c      alias_compare dup
 @c    libc_lock_unlock @aculock
 @c   _nl_explode_name @ascuheap @acsmem
diff --git a/manual/search.texi b/manual/search.texi
index 57dad7a..e5097d2 100644
--- a/manual/search.texi
+++ b/manual/search.texi
@@ -159,7 +159,7 @@ To sort an array using an arbitrary comparison function, use the
 
 @deftypefun void qsort (void *@var{array}, size_t @var{count}, size_t @var{size}, comparison_fn_t @var{compare})
 @standards{ISO, stdlib.h}
-@safety{@prelim{}@mtsafe{}@assafe{}@acunsafe{@acucorrupt{}}}
+@safety{@prelim{}@mtsafe{}@assafe{}@acsafe{}}
 The @code{qsort} function sorts the array @var{array}.  The array
 contains @var{count} elements, each of which is of size @var{size}.
 
@@ -199,9 +199,8 @@ Functions}):
 The @code{qsort} function derives its name from the fact that it was
 originally implemented using the ``quick sort'' algorithm.
 
-The implementation of @code{qsort} in this library might not be an
-in-place sort and might thereby use an extra amount of memory to store
-the array.
+The implementation of @code{qsort} in this library is an in-place sort
+and uses O(1) extra space (allocated on the stack).
 @end deftypefun
 
 @node Search/Sort Example
diff --git a/stdlib/Makefile b/stdlib/Makefile
index 6ef20a7..a39a176 100644
--- a/stdlib/Makefile
+++ b/stdlib/Makefile
@@ -34,7 +34,7 @@ headers	:= stdlib.h bits/stdlib.h bits/stdlib-ldbl.h bits/stdlib-float.h      \
 routines	:=							      \
 	atof atoi atol atoll						      \
 	abort								      \
-	bsearch qsort msort						      \
+	bsearch qsort							      \
 	getenv putenv setenv secure-getenv				      \
 	exit on_exit atexit cxa_atexit cxa_finalize old_atexit		      \
 	quick_exit at_quick_exit cxa_at_quick_exit cxa_thread_atexit_impl     \
@@ -135,10 +135,9 @@ extra-test-objs += tst-putenvmod.os
 
 generated += isomac isomac.out tst-putenvmod.so
 
-CFLAGS-bsearch.c += $(uses-callbacks)
-CFLAGS-msort.c += $(uses-callbacks)
-CFLAGS-qsort.c += $(uses-callbacks)
-CFLAGS-system.c += -fexceptions
+CFLAGS-bsearch.c = $(uses-callbacks)
+CFLAGS-qsort.c = $(uses-callbacks)
+CFLAGS-system.c = -fexceptions
 CFLAGS-system.os = -fomit-frame-pointer
 CFLAGS-fmtmsg.c += -fexceptions
 
diff --git a/stdlib/msort.c b/stdlib/msort.c
deleted file mode 100644
index 266c253..0000000
--- a/stdlib/msort.c
+++ /dev/null
@@ -1,310 +0,0 @@
-/* An alternative to qsort, with an identical interface.
-   This file is part of the GNU C Library.
-   Copyright (C) 1992-2018 Free Software Foundation, Inc.
-   Written by Mike Haertel, September 1988.
-
-   The GNU C Library is free software; you can redistribute it and/or
-   modify it under the terms of the GNU Lesser General Public
-   License as published by the Free Software Foundation; either
-   version 2.1 of the License, or (at your option) any later version.
-
-   The GNU C Library is distributed in the hope that it will be useful,
-   but WITHOUT ANY WARRANTY; without even the implied warranty of
-   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
-   Lesser General Public License for more details.
-
-   You should have received a copy of the GNU Lesser General Public
-   License along with the GNU C Library; if not, see
-   <http://www.gnu.org/licenses/>.  */
-
-#include <alloca.h>
-#include <stdint.h>
-#include <stdlib.h>
-#include <string.h>
-#include <unistd.h>
-#include <memcopy.h>
-#include <errno.h>
-#include <atomic.h>
-
-struct msort_param
-{
-  size_t s;
-  size_t var;
-  __compar_d_fn_t cmp;
-  void *arg;
-  char *t;
-};
-static void msort_with_tmp (const struct msort_param *p, void *b, size_t n);
-
-static void
-msort_with_tmp (const struct msort_param *p, void *b, size_t n)
-{
-  char *b1, *b2;
-  size_t n1, n2;
-
-  if (n <= 1)
-    return;
-
-  n1 = n / 2;
-  n2 = n - n1;
-  b1 = b;
-  b2 = (char *) b + (n1 * p->s);
-
-  msort_with_tmp (p, b1, n1);
-  msort_with_tmp (p, b2, n2);
-
-  char *tmp = p->t;
-  const size_t s = p->s;
-  __compar_d_fn_t cmp = p->cmp;
-  void *arg = p->arg;
-  switch (p->var)
-    {
-    case 0:
-      while (n1 > 0 && n2 > 0)
-	{
-	  if ((*cmp) (b1, b2, arg) <= 0)
-	    {
-	      *(uint32_t *) tmp = *(uint32_t *) b1;
-	      b1 += sizeof (uint32_t);
-	      --n1;
-	    }
-	  else
-	    {
-	      *(uint32_t *) tmp = *(uint32_t *) b2;
-	      b2 += sizeof (uint32_t);
-	      --n2;
-	    }
-	  tmp += sizeof (uint32_t);
-	}
-      break;
-    case 1:
-      while (n1 > 0 && n2 > 0)
-	{
-	  if ((*cmp) (b1, b2, arg) <= 0)
-	    {
-	      *(uint64_t *) tmp = *(uint64_t *) b1;
-	      b1 += sizeof (uint64_t);
-	      --n1;
-	    }
-	  else
-	    {
-	      *(uint64_t *) tmp = *(uint64_t *) b2;
-	      b2 += sizeof (uint64_t);
-	      --n2;
-	    }
-	  tmp += sizeof (uint64_t);
-	}
-      break;
-    case 2:
-      while (n1 > 0 && n2 > 0)
-	{
-	  unsigned long *tmpl = (unsigned long *) tmp;
-	  unsigned long *bl;
-
-	  tmp += s;
-	  if ((*cmp) (b1, b2, arg) <= 0)
-	    {
-	      bl = (unsigned long *) b1;
-	      b1 += s;
-	      --n1;
-	    }
-	  else
-	    {
-	      bl = (unsigned long *) b2;
-	      b2 += s;
-	      --n2;
-	    }
-	  while (tmpl < (unsigned long *) tmp)
-	    *tmpl++ = *bl++;
-	}
-      break;
-    case 3:
-      while (n1 > 0 && n2 > 0)
-	{
-	  if ((*cmp) (*(const void **) b1, *(const void **) b2, arg) <= 0)
-	    {
-	      *(void **) tmp = *(void **) b1;
-	      b1 += sizeof (void *);
-	      --n1;
-	    }
-	  else
-	    {
-	      *(void **) tmp = *(void **) b2;
-	      b2 += sizeof (void *);
-	      --n2;
-	    }
-	  tmp += sizeof (void *);
-	}
-      break;
-    default:
-      while (n1 > 0 && n2 > 0)
-	{
-	  if ((*cmp) (b1, b2, arg) <= 0)
-	    {
-	      tmp = (char *) __mempcpy (tmp, b1, s);
-	      b1 += s;
-	      --n1;
-	    }
-	  else
-	    {
-	      tmp = (char *) __mempcpy (tmp, b2, s);
-	      b2 += s;
-	      --n2;
-	    }
-	}
-      break;
-    }
-
-  if (n1 > 0)
-    memcpy (tmp, b1, n1 * s);
-  memcpy (b, p->t, (n - n2) * s);
-}
-
-
-void
-__qsort_r (void *b, size_t n, size_t s, __compar_d_fn_t cmp, void *arg)
-{
-  size_t size = n * s;
-  char *tmp = NULL;
-  struct msort_param p;
-
-  /* For large object sizes use indirect sorting.  */
-  if (s > 32)
-    size = 2 * n * sizeof (void *) + s;
-
-  if (size < 1024)
-    /* The temporary array is small, so put it on the stack.  */
-    p.t = __alloca (size);
-  else
-    {
-      /* We should avoid allocating too much memory since this might
-	 have to be backed up by swap space.  */
-      static long int phys_pages;
-      static int pagesize;
-
-      if (pagesize == 0)
-	{
-	  phys_pages = __sysconf (_SC_PHYS_PAGES);
-
-	  if (phys_pages == -1)
-	    /* Error while determining the memory size.  So let's
-	       assume there is enough memory.  Otherwise the
-	       implementer should provide a complete implementation of
-	       the `sysconf' function.  */
-	    phys_pages = (long int) (~0ul >> 1);
-
-	  /* The following determines that we will never use more than
-	     a quarter of the physical memory.  */
-	  phys_pages /= 4;
-
-	  /* Make sure phys_pages is written to memory.  */
-	  atomic_write_barrier ();
-
-	  pagesize = __sysconf (_SC_PAGESIZE);
-	}
-
-      /* Just a comment here.  We cannot compute
-	   phys_pages * pagesize
-	   and compare the needed amount of memory against this value.
-	   The problem is that some systems might have more physical
-	   memory then can be represented with a `size_t' value (when
-	   measured in bytes.  */
-
-      /* If the memory requirements are too high don't allocate memory.  */
-      if (size / pagesize > (size_t) phys_pages)
-	{
-	  _quicksort (b, n, s, cmp, arg);
-	  return;
-	}
-
-      /* It's somewhat large, so malloc it.  */
-      int save = errno;
-      tmp = malloc (size);
-      __set_errno (save);
-      if (tmp == NULL)
-	{
-	  /* Couldn't get space, so use the slower algorithm
-	     that doesn't need a temporary array.  */
-	  _quicksort (b, n, s, cmp, arg);
-	  return;
-	}
-      p.t = tmp;
-    }
-
-  p.s = s;
-  p.var = 4;
-  p.cmp = cmp;
-  p.arg = arg;
-
-  if (s > 32)
-    {
-      /* Indirect sorting.  */
-      char *ip = (char *) b;
-      void **tp = (void **) (p.t + n * sizeof (void *));
-      void **t = tp;
-      void *tmp_storage = (void *) (tp + n);
-
-      while ((void *) t < tmp_storage)
-	{
-	  *t++ = ip;
-	  ip += s;
-	}
-      p.s = sizeof (void *);
-      p.var = 3;
-      msort_with_tmp (&p, p.t + n * sizeof (void *), n);
-
-      /* tp[0] .. tp[n - 1] is now sorted, copy around entries of
-	 the original array.  Knuth vol. 3 (2nd ed.) exercise 5.2-10.  */
-      char *kp;
-      size_t i;
-      for (i = 0, ip = (char *) b; i < n; i++, ip += s)
-	if ((kp = tp[i]) != ip)
-	  {
-	    size_t j = i;
-	    char *jp = ip;
-	    memcpy (tmp_storage, ip, s);
-
-	    do
-	      {
-		size_t k = (kp - (char *) b) / s;
-		tp[j] = jp;
-		memcpy (jp, kp, s);
-		j = k;
-		jp = kp;
-		kp = tp[k];
-	      }
-	    while (kp != ip);
-
-	    tp[j] = jp;
-	    memcpy (jp, tmp_storage, s);
-	  }
-    }
-  else
-    {
-      if ((s & (sizeof (uint32_t) - 1)) == 0
-	  && ((char *) b - (char *) 0) % __alignof__ (uint32_t) == 0)
-	{
-	  if (s == sizeof (uint32_t))
-	    p.var = 0;
-	  else if (s == sizeof (uint64_t)
-		   && ((char *) b - (char *) 0) % __alignof__ (uint64_t) == 0)
-	    p.var = 1;
-	  else if ((s & (sizeof (unsigned long) - 1)) == 0
-		   && ((char *) b - (char *) 0)
-		      % __alignof__ (unsigned long) == 0)
-	    p.var = 2;
-	}
-      msort_with_tmp (&p, b, n);
-    }
-  free (tmp);
-}
-libc_hidden_def (__qsort_r)
-weak_alias (__qsort_r, qsort_r)
-
-
-void
-qsort (void *b, size_t n, size_t s, __compar_fn_t cmp)
-{
-  return __qsort_r (b, n, s, (__compar_d_fn_t) cmp, NULL);
-}
-libc_hidden_def (qsort)
diff --git a/stdlib/qsort.c b/stdlib/qsort.c
index 264a06b..b3a5102 100644
--- a/stdlib/qsort.c
+++ b/stdlib/qsort.c
@@ -20,7 +20,6 @@
    Engineering a sort function; Jon Bentley and M. Douglas McIlroy;
    Software - Practice and Experience; Vol. 23 (11), 1249-1265, 1993.  */
 
-#include <alloca.h>
 #include <limits.h>
 #include <stdlib.h>
 #include <string.h>
@@ -86,8 +85,8 @@ typedef struct
       stack size is needed (actually O(1) in this case)!  */
 
 void
-_quicksort (void *const pbase, size_t total_elems, size_t size,
-	    __compar_d_fn_t cmp, void *arg)
+__qsort_r (void *const pbase, size_t total_elems, size_t size,
+	   __compar_d_fn_t cmp, void *arg)
 {
   char *base_ptr = (char *) pbase;
 
@@ -247,3 +246,13 @@ _quicksort (void *const pbase, size_t total_elems, size_t size,
       }
   }
 }
+
+libc_hidden_def (__qsort_r)
+weak_alias (__qsort_r, qsort_r)
+
+void
+qsort (void *b, size_t n, size_t s, __compar_fn_t cmp)
+{
+  return __qsort_r (b, n, s, (__compar_d_fn_t) cmp, NULL);
+}
+libc_hidden_def (qsort)

http://sourceware.org/git/gitweb.cgi?p=glibc.git;a=commitdiff;h=a707334fdfcac4ce7b479be6ac8727c45893bdab

commit a707334fdfcac4ce7b479be6ac8727c45893bdab
Author: Adhemerval Zanella <adhemerval.zanella@linaro.org>
Date:   Mon Jan 15 09:20:30 2018 -0200

    stdlib: Add more qsort{_r} coverage
    
    This patch adds a qsort and qsort_t (which glibc current lacks
    coverage).  The test check with random input (created using support
    random) with different internal types (uint8_t, uint16_t, uint32_t,
    and uint64_t) and with different set of element numbers (from 0
    to 262144).
    
    Checked on x86_64-linux-gnu.
    
    	* stdlib/tst-qsort3.c: New file.
    	* stdlib/Makefile (tests): Add tst-qsort3.

diff --git a/stdlib/Makefile b/stdlib/Makefile
index 7c363a6..6ef20a7 100644
--- a/stdlib/Makefile
+++ b/stdlib/Makefile
@@ -84,7 +84,7 @@ tests		:= tst-strtol tst-strtod testmb testrand testsort testdiv   \
 		   tst-cxa_atexit tst-on_exit test-atexit-race 		    \
 		   test-at_quick_exit-race test-cxa_atexit-race             \
 		   test-on_exit-race test-dlclose-exit-race 		    \
-		   tst-makecontext-align
+		   tst-makecontext-align tst-qsort3
 
 tests-internal	:= tst-strtod1i tst-strtod3 tst-strtod4 tst-strtod5i \
 		   tst-tls-atexit tst-tls-atexit-nodelete
diff --git a/stdlib/tst-qsort3.c b/stdlib/tst-qsort3.c
new file mode 100644
index 0000000..e6ddb60
--- /dev/null
+++ b/stdlib/tst-qsort3.c
@@ -0,0 +1,231 @@
+/* qsort(_r) generic tests.
+   Copyright (C) 2017 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, see
+   <http://www.gnu.org/licenses/>.  */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <getopt.h>
+#include <errno.h>
+
+#include <support/check.h>
+#include <support/support.h>
+#include <support/test-driver.h>
+#include <support/support_random.h>
+
+/* Functions used to check qsort.  */
+static int
+uint8_t_cmp (const void *a, const void *b)
+{
+  uint8_t ia = *(uint8_t*)a;
+  uint8_t ib = *(uint8_t*)b;
+  return (ia > ib) - (ia < ib);
+}
+
+static int
+uint16_t_cmp (const void *a, const void *b)
+{
+  uint16_t ia = *(uint16_t*)a;
+  uint16_t ib = *(uint16_t*)b;
+  return (ia > ib) - (ia < ib);
+}
+
+static int
+uint32_t_cmp (const void *a, const void *b)
+{
+  uint32_t ia = *(uint32_t*)a;
+  uint32_t ib = *(uint32_t*)b;
+  return (ia > ib) - (ia < ib);
+}
+
+static int
+uint64_t_cmp (const void *a, const void *b)
+{
+  uint64_t ia = *(uint64_t*)a;
+  uint64_t ib = *(uint64_t*)b;
+  return (ia > ib) - (ia < ib);
+}
+
+/* Function used to check qsort_r.  */
+
+enum type_cmp_t
+{
+  UINT8_CMP_T  = 0,
+  UINT16_CMP_T = 1,
+  UINT32_CMP_T = 2,
+  UINT64_CMP_T = 3,
+};
+
+static enum type_cmp_t
+uint_t_cmp_type (size_t sz)
+{
+  switch (sz)
+    {
+      case sizeof (uint8_t):  return UINT8_CMP_T;
+      case sizeof (uint16_t): return UINT16_CMP_T;
+      case sizeof (uint64_t): return UINT64_CMP_T;
+      case sizeof (uint32_t):
+      default:                return UINT32_CMP_T;
+    }
+}
+
+static int
+uint_t_cmp (const void *a, const void *b, void *arg)
+{
+  enum type_cmp_t type = *(enum type_cmp_t*) arg;
+  switch (type)
+    {
+    case UINT8_CMP_T:  return uint8_t_cmp (a, b);
+    case UINT16_CMP_T: return uint16_t_cmp (a, b);
+    case UINT64_CMP_T: return uint64_t_cmp (a, b);
+    case UINT32_CMP_T:
+    default:           return uint32_t_cmp (a, b);
+    }
+}
+
+static struct mt19937_32 mt;
+
+static void *
+create_array (size_t nmemb, size_t type_size)
+{
+  size_t size = nmemb * type_size;
+  uint8_t *array = xmalloc (size);
+
+  for (size_t i = 0; i < size; i++)
+    array[i] = uniform_uint32_distribution (mt32_rand (&mt), 0, UINT8_MAX);
+
+  return array;
+}
+
+typedef int (*cmpfunc_t)(const void *, const void *);
+
+static void
+check_array (void *array, size_t nmemb, size_t type_size,
+	     cmpfunc_t cmpfunc)
+{
+  for (size_t i = 1; i < nmemb; i++)
+    {
+      void *array_i   = (void*)((uintptr_t)array + i * type_size);
+      void *array_i_1 = (void*)((uintptr_t)array + (i-1) * type_size);
+      int ret;
+      TEST_VERIFY ((ret = cmpfunc (array_i, array_i_1)) >= 0);
+      if (ret < 0)
+	break;
+    }
+}
+
+static uint32_t seed;
+
+#define OPT_SEED 10000
+#define CMDLINE_OPTIONS \
+  { "seed", required_argument, NULL, OPT_SEED },
+
+static void __attribute__ ((used))
+cmdline_process_function (int c)
+{
+  switch (c)
+    {
+      case OPT_SEED:
+	{
+	  unsigned long int value = strtoul (optarg, NULL, 0);
+	  if (errno == ERANGE || value > UINT32_MAX)
+	    {
+	      printf ("error: seed should be a value in range of "
+		      "[0, UINT32_MAX]\n");
+	      exit (EXIT_FAILURE);
+	    }
+	  seed = value;
+	}
+      break;
+    }
+}
+
+#define CMDLINE_PROCESS cmdline_process_function
+
+
+static int
+do_test (void)
+{
+  mt32_seed (&mt, seed);
+  printf ("info: seed=0x%08x\n", seed);
+
+  const size_t elem[] = { 0, 1, 64, 128, 4096, 16384, 262144 };
+  const size_t nelem = sizeof (elem) / sizeof (elem[0]);
+
+  struct test_t
+    {
+      size_t type_size;
+      cmpfunc_t cmpfunc;
+    }
+  tests[] =
+    {
+      { sizeof (uint8_t),  uint8_t_cmp },
+      { sizeof (uint16_t), uint16_t_cmp },
+      { sizeof (uint32_t), uint32_t_cmp },
+      { sizeof (uint64_t), uint64_t_cmp },
+      /* Test swap with large elements.  */
+      { 32,                uint32_t_cmp },
+    };
+  size_t ntests = sizeof (tests) / sizeof (tests[0]);
+
+  for (size_t i = 0; i < ntests; i++)
+    {
+      size_t ts = tests[i].type_size;
+      if (test_verbose > 0)
+        printf ("info: testing qsort with type_size=%zu\n", ts);
+      for (size_t n = 0; n < nelem; n++)
+	{
+	  size_t nmemb = elem[n];
+	  if (test_verbose > 0)
+            printf ("  nmemb=%zu, total size=%zu\n", nmemb, nmemb * ts);
+
+	  void *array = create_array (nmemb, ts);
+
+	  qsort (array, nmemb, ts, tests[i].cmpfunc);
+
+	  check_array (array, nmemb, ts, tests[i].cmpfunc);
+
+	  free (array);
+	}
+    }
+
+  for (size_t i = 0; i < ntests; i++)
+    {
+      size_t ts = tests[i].type_size;
+      if (test_verbose > 0)
+        printf ("info: testing qsort_r type_size=%zu\n", ts);
+      for (size_t n = 0; n < nelem; n++)
+	{
+	  size_t nmemb = elem[n];
+	  if (test_verbose > 0)
+            printf ("  nmemb=%zu, total size=%zu\n", nmemb, nmemb * ts);
+
+	  void *array = create_array (nmemb, ts);
+
+	  enum type_cmp_t type = uint_t_cmp_type (ts);
+	  qsort_r (array, nmemb, ts, uint_t_cmp, &type);
+
+	  check_array (array, nmemb, ts, tests[i].cmpfunc);
+
+	  free (array);
+	}
+    }
+
+  return 0;
+}
+
+#include <support/test-driver.c>

http://sourceware.org/git/gitweb.cgi?p=glibc.git;a=commitdiff;h=99ce2951fdd6a711334dc927f1ecfd9193fdd506

commit 99ce2951fdd6a711334dc927f1ecfd9193fdd506
Author: Adhemerval Zanella <adhemerval.zanella@linaro.org>
Date:   Thu Aug 31 20:24:03 2017 -0300

    benchtests: Add bench-qsort
    
    This patch adds a qsort benchmark.  I tried to model the benchmark taking in
    consideration the possible input variation in both internal element size,
    element numbers, and internal state for 1. real word cases and 2. possible
    scenarios based on hardware characteristics.
    
    For 1. I tracked qsort usage (using a simple preload library to dump its usage
    and a script to pos-process it) on both GCC bootstrap and Firefox.  GCC 8
    bootstrap build shows 51786641 call to qsort with the following characterics:
    
    Key: number of elements:
    key=2 : 39.74
    key=3 : 19.23
    key=4 : 9.77
    key=1 : 8.44
    key=0 : 6.60
    key=5 : 4.40
    key=7 : 2.37
    key=6 : 2.25
    key=9 : 1.48
    key=8 : 0.97
    
    Key: element size in bytes:
    key=8 : 91.74
    key=32 : 3.62
    key=4 : 2.42
    key=40 : 1.20
    key=16 : 0.67
    key=24 : 0.30
    key=48 : 0.05
    key=56 : 0.00
    key=1 : 0.00
    
    Key: total size (number of elements * element size):
    key=16 : 35.98
    key=24 : 18.67
    key=32 : 9.79
    key=8 : 8.28
    key=0 : 6.60
    key=40 : 4.21
    key=64 : 3.15
    key=48 : 2.24
    key=56 : 2.15
    key=80 : 1.45
    
    So for GCC:
    
      - 80% of total qsort usage are done with 10 elements of less.
      - All usages are done element size of maximum of 56 bytes.
      - 90% of calls are done with array of maximum size of 80 bytes or less.
    
    The Firefox usage was done with 2 hours of usage, with first 10 minutes activelly
    openning and closing different types of sites.  It resulted in 21042 calls with
    following characteristics:
    
    Key: number of elements:
    key=7 : 24.40
    key=1 : 10.44
    key=3 : 6.33
    key=4 : 5.81
    key=2 : 5.46
    key=6 : 4.80
    key=17 : 4.54
    key=0 : 3.07
    key=5 : 3.05
    key=9 : 2.51
    key=12 : 2.06
    
    Key: element size in bytes:
    key=8 : 94.49
    key=28 : 4.40
    key=2 : 0.70
    key=16 : 0.19
    key=36 : 0.07
    key=12 : 0.07
    key=40 : 0.07
    key=24 : 0.03
    
    Key: total size (number of elements * element size):
    key=56 : 24.20
    key=8 : 10.27
    key=24 : 6.36
    key=32 : 5.86
    key=16 : 5.46
    key=48 : 4.80
    key=476 : 3.75
    key=0 : 3.07
    key=40 : 3.05
    key=72 : 2.50
    
    So for Firefox:
    
      - 72% of total qsort usage are done with 18 elements of less.
      - All usages are done element size of maximum of 40 bytes.
      - 70% of calls are done with array of maximum size of 476 bytes or less.
    
    For 2. I used the idea of a machine with 3 levels of cache with sizes
    32kb (L1), 256kb (L2), and 4096 (L3).
    
    It resulted in a benchmark with following traits:
    
      * It checks four types of input arrays: sorted, mostly sorted, unsorted, and
        repeated.  For 'sorted' the array is already sorted, 'mostly sorted' the
        array will have a certain number of random elements with random values
        (current ratio used is 20%), for 'unsorted' the array will contain random
        elements from full range based on used type, and for 'repeated' the array
        will have random elements with a certain number (current ratio is 20%) of
        a repeated element distributed randomly.
    
      * Three elements sizes are checked: uint32_t, uint64_t, and an element with
        32 bytes (but using the uint64_t comparison checks).  These element sizes
        are used to 1. to avoid include the comparison function itself and/or
        memory copy in sort benchmark itself, and 2. because key of size_t are the
        most used for both GCC and Firefox.
    
      * Five different element numbers: 64 (which cover mostly of used element
        sizes for both GCC and Firefox), 4096/8192 (which cover 32 KB of L1 for
        32 and 64 bits), 32768/65536 (L2 with 256 KB), and 24288/1048576 (L3 with
        4 MB).  The sizes are configurable by --nelem option.
    
    Checked on x86_64-linux-gnu
    
    	* benchtests/Makefile (stdlib-benchset): Add qsort.
    	* benchtests/bench-qsort.c: New file.

diff --git a/benchtests/Makefile b/benchtests/Makefile
index ff99d25..6d6a5e9 100644
--- a/benchtests/Makefile
+++ b/benchtests/Makefile
@@ -66,7 +66,7 @@ LOCALES := en_US.UTF-8 tr_TR.UTF-8 cs_CZ.UTF-8 fa_IR.UTF-8 fr_FR.UTF-8 \
 include ../gen-locales.mk
 endif
 
-stdlib-benchset := strtod
+stdlib-benchset := strtod qsort
 
 stdio-common-benchset := sprintf
 
diff --git a/benchtests/bench-qsort.c b/benchtests/bench-qsort.c
new file mode 100644
index 0000000..097459b
--- /dev/null
+++ b/benchtests/bench-qsort.c
@@ -0,0 +1,352 @@
+/* Measure qsort function.
+   Copyright (C) 2018 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, see
+   <http://www.gnu.org/licenses/>.  */
+
+#include <stdlib.h>
+#include <assert.h>
+#include <string.h>
+#include <getopt.h>
+#include <unistd.h>
+#include <errno.h>
+
+#include "json-lib.h"
+#include "bench-timing.h"
+#include "bench-util.h"
+
+#include <support/test-driver.h>
+#include <support/support.h>
+#include <support/support_random.h>
+
+#define ARRAY_SIZE(__array) (sizeof (__array) / sizeof (__array[0]))
+
+/* Type of inputs arrays:
+   - Sorted:       array already sorted in placed.
+   - MostlySorted: sorted array with 'MostlySortedRatio * size' elements
+		   in random positions set to random values.
+   - Unsorted:     all elements in array set to random values.
+   - Repeated:     random array with 'RepeatedRation' elements in random
+		   positions set to an unique value.  */
+typedef enum {
+  Sorted                = 0,
+  MostlySorted          = 1,
+  Unsorted              = 2,
+  Repeated              = 3,
+} arraytype_t;
+
+/* Ratio of total of elements which will randomized.  */
+static const double MostlySortedRatio = 0.2;
+
+/* Ratio of total of elements which will be repeated.  */
+static const double RepeatedRatio = 0.2;
+
+struct array_t
+{
+  arraytype_t type;
+  const char *name;
+} arraytypes[] =
+{
+  { Sorted, "Sorted" },
+  { Unsorted, "Unsorted" },
+  { MostlySorted, "MostlySorted" },
+  { Repeated, "Repeated" },
+};
+
+
+typedef int (*cmpfunc_t)(const void *, const void *);
+typedef void (*seq_element_t) (void *, size_t);
+
+static inline void *
+arr (void *base, size_t idx, size_t size)
+{
+  return (void*)((uintptr_t)base + (idx * size));
+}
+
+static struct mt19937_64 mt;
+
+/* Fill the BUFFER with size SIZE in bytes with random uint64_t obtained from
+   the global MT state.  */
+static inline void
+fill_rand (void *buffer, size_t size)
+{
+  uint8_t *array = (uint8_t*)(buffer);
+  for (size_t i = 0; i < size; i++)
+    array[i] = uniform_uint64_distribution (mt64_rand (&mt), 0, UINT8_MAX);
+}
+
+static void *
+create_array (size_t nmemb, size_t type_size, arraytype_t type,
+	      seq_element_t seq)
+{
+  size_t size = nmemb * type_size;
+  void *array = xmalloc (size);
+
+  switch (type)
+    {
+    case Sorted:
+      for (size_t i = 0; i < nmemb; i++)
+	seq (arr (array, i, type_size), i);
+      break;
+
+    case MostlySorted:
+      {
+        for (size_t i = 0; i < nmemb; i++)
+	  seq (arr (array, i, type_size), i);
+
+	/* Change UNSORTED elements (based on MostlySortedRatio ratio)
+	   in the sorted array.  */
+        size_t unsorted = (size_t)(nmemb * MostlySortedRatio);
+	for (size_t i = 0; i < unsorted; i++)
+	  {
+	    size_t pos = uniform_uint64_distribution (mt64_rand (&mt), 0,
+						      nmemb - 1);
+	    fill_rand (arr (array, pos, type_size), type_size);
+	  }
+      }
+      break;
+
+    case Unsorted:
+      fill_rand (array, size);
+      break;
+
+    case Repeated:
+      {
+        fill_rand (array, size);
+
+	void *randelem = xmalloc (type_size);
+	fill_rand (randelem, type_size);
+
+	/* Repeat REPEATED elements (based on RepeatRatio ratio) in the random
+	   array.  */
+        size_t repeated = (size_t)(nmemb * RepeatedRatio);
+	for (size_t i = 0; i < repeated; i++)
+	  {
+	    size_t pos = uniform_uint64_distribution (mt64_rand (&mt), 0,
+						      nmemb - 1);
+	    memcpy (arr (array, pos, type_size), randelem, type_size);
+	  }
+	free (randelem);
+      }
+      break;
+    }
+
+  return array;
+}
+
+/* Functions for uint32_t type.  */
+static int
+cmp_uint32_t (const void *a, const void *b)
+{
+  uint32_t ia = *(uint32_t*)a;
+  uint32_t ib = *(uint32_t*)b;
+  return (ia > ib) - (ia < ib);
+}
+
+static void
+seq_uint32_t (void *base, size_t idx)
+{
+  *(uint32_t *)base = idx;
+}
+
+/* Functions for uint64_t type.  */
+static int
+cmp_uint64_t (const void *a, const void *b)
+{
+  uint64_t ia = *(uint64_t*)a;
+  uint64_t ib = *(uint64_t*)b;
+  return (ia > ib) - (ia < ib);
+}
+
+static void
+seq_uint64_t (void *base, size_t idx)
+{
+  *(uint64_t *)base = idx;
+}
+
+/* Number of elements of determined type to be measured.  */
+static const size_t default_elem[] =
+{
+  256/sizeof(size_t),       /* 64/128 which covers mostly used element number
+			       on GCC build.  */
+  32768/sizeof(size_t),	    /* 4096/8192 to fit on a L1 with 32 KB.  */
+  262144/sizeof(size_t),    /* 32768/65536 to fit on a L2 with 256 KB.  */
+  4194304/sizeof(size_t),   /* 524288/1048576 to fix on a L3 with 4 MB.  */
+};
+
+
+#define OPT_NELEM 10000
+#define OPT_SEED  10001
+#define CMDLINE_OPTIONS \
+  { "nelem", required_argument, NULL, OPT_NELEM }, \
+  { "seed", required_argument, NULL, OPT_SEED },
+
+static const size_t max_nelem = 16;
+static size_t *elems = NULL;
+static size_t nelem = 0;
+static uint64_t seed = 0;
+static bool seed_set = false;
+
+static void __attribute__ ((used))
+cmdline_process_function (int c)
+{
+  switch (c)
+    {
+      /* Handle the --nelem option to run different sizes than DEFAULT_ELEM.
+	 The elements sizes as passed with a ':' as the delimiter, for
+	 instance --nelem 32:128:1024 will ran 32, 128, and 1024 elements.  */
+      case OPT_NELEM:
+        {
+	  elems = xmalloc (max_nelem * sizeof (size_t));
+	  nelem = 0;
+
+	  char *saveptr;
+	  char *token;
+	  token = strtok_r (optarg, ":", &saveptr);
+	  if (token == NULL)
+	    {
+	      printf ("error: invalid --nelem value\n");
+	      exit (EXIT_FAILURE);
+	    }
+	  do
+	    {
+	      if (nelem == max_nelem)
+		{
+		  printf ("error: invalid --nelem value (max elem)\n");
+		  exit (EXIT_FAILURE);
+		}
+	      elems[nelem++] = atol (token);
+	      token = strtok_r (saveptr, ":", &saveptr);
+	    } while (token != NULL);
+        }
+      break;
+
+      /* handle the --seed option to use a different seed than a random one.
+	 The SEED used should be a uint64_t number.  */
+      case OPT_SEED:
+	{
+	  unsigned long int value = strtoull (optarg, NULL, 0);
+	  if (errno == ERANGE || value > UINT64_MAX)
+	    {
+	      printf ("error: seed should be a value in range of "
+		      "[0, UINT64_MAX]\n");
+	      exit (EXIT_FAILURE);
+	    }
+	  seed = value;
+	  seed_set = true;
+	}
+    }
+}
+
+#define CMDLINE_PROCESS cmdline_process_function
+
+static const size_t inner_loop_iters = 16;
+
+struct run_t
+{
+  size_t type_size;
+  cmpfunc_t cmp;
+  seq_element_t seq;
+};
+static const struct run_t runs[] =
+{
+  { sizeof (uint32_t), cmp_uint32_t, seq_uint32_t },
+  { sizeof (uint64_t), cmp_uint64_t, seq_uint64_t },
+  { 32,                cmp_uint64_t, seq_uint64_t },
+};
+
+static int
+do_test (void)
+{
+  if (!seed_set)
+    {
+      /* Use default seed in case of error.  */
+      random_seed (&seed, sizeof (seed));
+    }
+  mt64_seed (&mt, seed);
+
+  json_ctx_t json_ctx;
+
+  json_init (&json_ctx, 0, stdout);
+
+  json_document_begin (&json_ctx);
+  json_attr_string (&json_ctx, "timing_type", TIMING_TYPE);
+
+  json_attr_object_begin (&json_ctx, "functions");
+  json_attr_object_begin (&json_ctx, "qsort");
+  json_attr_uint (&json_ctx, "seed", seed);
+
+  json_array_begin (&json_ctx, "results");
+
+  const size_t *welem = elems == NULL ? default_elem : elems;
+  const size_t wnelem = elems == NULL ? ARRAY_SIZE (default_elem)
+				      : nelem;
+
+  for (int j = 0; j < ARRAY_SIZE (runs); j++)
+    {
+      for (int i = 0; i < ARRAY_SIZE (arraytypes); i++)
+	{
+	  for (int k = 0; k < wnelem; k++)
+	    {
+	      json_element_object_begin (&json_ctx);
+
+	      size_t nmemb = welem[k];
+	      size_t ts = runs[j].type_size;
+	      size_t arraysize = nmemb * ts;
+
+	      json_attr_uint (&json_ctx, "nmemb", nmemb);
+	      json_attr_uint (&json_ctx, "type_size", ts);
+	      json_attr_string (&json_ctx, "property", arraytypes[i].name);
+
+	      void *base = create_array (nmemb, ts, arraytypes[i].type, runs[j].seq);
+	      void *work = xmalloc (arraysize);
+
+	      timing_t total;
+	      TIMING_INIT (total);
+
+	      for (int n = 0; n < inner_loop_iters; n++)
+	        {
+		  memcpy (work, base, arraysize);
+
+	          timing_t start, end, diff;
+	          TIMING_NOW (start);
+	          qsort (work, nmemb, ts, runs[j].cmp);
+	          TIMING_NOW (end);
+
+	          TIMING_DIFF (diff, start, end);
+	          TIMING_ACCUM (total, diff);
+	        }
+
+	     json_attr_uint (&json_ctx, "timings",
+			     (double) total / (double) inner_loop_iters);
+	     json_element_object_end (&json_ctx);
+
+	     free (base);
+	     free (work);
+	   }
+    	}
+    }
+
+  json_array_end (&json_ctx);
+
+  json_attr_object_end (&json_ctx);
+  json_attr_object_end (&json_ctx);
+  json_document_end (&json_ctx);
+
+  return 0;
+}
+
+#define TIMEOUT 600
+#include <support/test-driver.c>

http://sourceware.org/git/gitweb.cgi?p=glibc.git;a=commitdiff;h=84e29aafc42d4c01aaf90f76762e6dc94579b9b0

commit 84e29aafc42d4c01aaf90f76762e6dc94579b9b0
Author: Adhemerval Zanella <adhemerval.zanella@linaro.org>
Date:   Mon Dec 25 10:53:13 2017 -0200

    support: Add Mersenne Twister pseudo-random number generator
    
    This patch adds support routines for pseudo-random number generation
    based on Mersenne Twister.  The libstc++ version is used as based and
    both 32 and 64 bits are provided.  It is used on following qsort tests
    and benchmarks.
    
    I decided to use a Mersenne Twister (MT) instead of random_r internal
    implementation, which uses a linear feedback shift register approach
    with trinomials, because it:
    
      - is used extensivelly in other implementations (like c+11);
      - has a quite larger period (2^219937-1) than the type 4 variantion
        of random (2^63 - 1);
      - does not the RAND_MAX limitation.
    
    Checked on x86_64-linux-gnu.
    
    	* support/Makefile (libsupport-routines): Add support_random.
    	(tests): Add tst-support_random.
    	* support/support_random.c: New file.
    	* support/support_random.h: Likewise.
    	* support/tst-support_random.c: Likewise.

diff --git a/support/Makefile b/support/Makefile
index 1bda81e..8efe577 100644
--- a/support/Makefile
+++ b/support/Makefile
@@ -53,6 +53,7 @@ libsupport-routines = \
   support_format_netent \
   support_isolate_in_subprocess \
   support_record_failure \
+  support_random \
   support_run_diff \
   support_shared_allocate \
   support_test_compare_failure \
@@ -153,6 +154,7 @@ tests = \
   tst-support_record_failure \
   tst-test_compare \
   tst-xreadlink \
+  tst-support_random
 
 ifeq ($(run-built-tests),yes)
 tests-special = \
diff --git a/support/support_random.c b/support/support_random.c
new file mode 100644
index 0000000..f3037a5
--- /dev/null
+++ b/support/support_random.c
@@ -0,0 +1,219 @@
+/* Function for pseudo-random number generation.
+   Copyright (C) 2018 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, see
+   <http://www.gnu.org/licenses/>.  */
+
+#include <assert.h>
+#include <fcntl.h>
+#include <unistd.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <sys/random.h>
+#include <support/support_random.h>
+
+int
+random_seed (void *buf, size_t len)
+{
+  ssize_t ret = getrandom (buf, len, 0);
+  if (ret == len)
+    return 0;
+
+  int fd = open ("/dev/urandom", O_RDONLY);
+  if (fd < 0)
+    return -1;
+  void *end = buf + len;
+  while (buf < end)
+    {
+      ssize_t ret = read (fd, buf, end - buf);
+      if (ret <= 0)
+	break;
+      buf += ret;
+    }
+  close (fd);
+  return buf == end ? 0 : -1;
+}
+
+/* The classic Mersenne Twister. Reference:
+   M. Matsumoto and T. Nishimura, Mersenne Twister: A 623-Dimensionally
+   Equidistributed Uniform Pseudo-Random Number Generator, ACM Transactions
+   on Modeling and Computer Simulation, Vol. 8, No. 1, January 1998, pp 3-30.
+
+   This version is based on libstdc++ std::mt19937{_64}.  */
+
+static const size_t mt32_word_size         = 32;
+static const size_t mt32_mask_bits         = 31;
+static const size_t mt32_state_size        = MT32_STATE_SIZE;
+static const size_t mt32_shift_size        = 397;
+static const uint32_t mt32_xor_mask        = 0x9908b0dfUL;
+static const size_t mt32_tempering_u       = 11;
+static const uint32_t mt32_tempering_d     = 0xffffffffUL;
+static const size_t mt32_tempering_s       = 7;
+static const uint32_t mt32_tempering_b     = 0x9d2c5680UL;
+static const size_t mt32_tempering_t       = 15;
+static const uint32_t mt32_tempering_c     = 0xefc60000UL;
+static const size_t mt32_tempering_l       = 18;
+static const uint32_t mt32_init_multiplier = 1812433253UL;
+static const uint32_t mt32_default_seed    = 5489u;
+
+static void
+mt32_gen_rand (struct mt19937_32 *state)
+{
+  const uint32_t upper_mask = (uint32_t)-1 << mt32_mask_bits;
+  const uint32_t lower_mask = ~upper_mask;
+
+  for (size_t k = 0; k < (mt32_state_size - mt32_shift_size); k++)
+    {
+      uint32_t y = ((state->mt[k] & upper_mask)
+		   | (state->mt[k + 1] & lower_mask));
+      state->mt[k] = (state->mt[k + mt32_shift_size] ^ (y >> 1)
+		     ^ ((y & 0x01) ? mt32_xor_mask : 0));
+    }
+
+  for (size_t k = (mt32_state_size - mt32_shift_size);
+       k < (mt32_state_size - 1); k++)
+    {
+      uint32_t y = ((state->mt[k] & upper_mask)
+		   | (state->mt[k + 1] & lower_mask));
+      state->mt[k] = (state->mt[k + (mt32_shift_size - mt32_state_size)]
+		      ^ (y >> 1) ^ ((y & 0x01) ? mt32_xor_mask : 0));
+    }
+
+  uint32_t y = ((state->mt[mt32_state_size - 1] & upper_mask)
+		| (state->mt[0] & lower_mask));
+  state->mt[mt32_state_size - 1] = (state->mt[mt32_shift_size -1] ^ (y >> 1)
+				    ^ (( y & 0x01) ? mt32_xor_mask : 0));
+  state->p = 0;
+}
+
+void
+mt32_seed (struct mt19937_32 *state, uint32_t seed)
+{
+  /* Generators based on linear-feedback shift-register techniques can not
+     handle all zero initial state (they will output zero continually).  In
+     such cases we use the default initial state).  */
+  if (seed == 0x0)
+    seed = mt32_default_seed;
+
+  state->mt[0] = mt32_default_seed;
+  for (size_t i = 1; i < mt32_state_size; i++)
+    {
+      uint32_t x = state->mt[i - 1];
+      x ^= x >> (mt32_word_size - 2);
+      x *= mt32_init_multiplier;
+      x += i;
+      state->mt[i] = x;
+    }
+  state->p = mt32_state_size;
+}
+
+uint32_t
+mt32_rand (struct mt19937_32 *state)
+{
+  /* Reload the vector - cost is O(n) amortized over n calls.  */
+  if (state->p >= mt32_state_size)
+   mt32_gen_rand (state);
+
+  /* Calculate o(x(i)).  */
+  uint32_t z = state->mt[state->p++];
+  z ^= (z >> mt32_tempering_u) & mt32_tempering_d;
+  z ^= (z << mt32_tempering_s) & mt32_tempering_b;
+  z ^= (z << mt32_tempering_t) & mt32_tempering_c;
+  z ^= (z >> mt32_tempering_l);
+  return z;
+}
+
+
+static const size_t mt64_word_size         = 64;
+static const size_t mt64_mask_bits         = 31;
+static const size_t mt64_state_size        = MT64_STATE_SIZE;
+static const size_t mt64_shift_size        = 156;
+static const uint64_t mt64_xor_mask        = 0xb5026f5aa96619e9ULL;
+static const size_t mt64_tempering_u       = 29;
+static const uint64_t mt64_tempering_d     = 0x5555555555555555ULL;
+static const size_t mt64_tempering_s       = 17;
+static const uint64_t mt64_tempering_b     = 0x71d67fffeda60000ULL;
+static const size_t mt64_tempering_t       = 37;
+static const uint64_t mt64_tempering_c     = 0xfff7eee000000000ULL;
+static const size_t mt64_tempering_l       = 43;
+static const uint64_t mt64_init_multiplier = 6364136223846793005ULL;
+static const uint64_t mt64_default_seed    = 5489u;
+
+static void
+mt64_gen_rand (struct mt19937_64 *state)
+{
+  const uint64_t upper_mask = (uint64_t)-1 << mt64_mask_bits;
+  const uint64_t lower_mask = ~upper_mask;
+
+  for (size_t k = 0; k < (mt64_state_size - mt64_shift_size); k++)
+    {
+      uint64_t y = ((state->mt[k] & upper_mask)
+		   | (state->mt[k + 1] & lower_mask));
+      state->mt[k] = (state->mt[k + mt64_shift_size] ^ (y >> 1)
+		     ^ ((y & 0x01) ? mt64_xor_mask : 0));
+    }
+
+  for (size_t k = (mt64_state_size - mt64_shift_size);
+       k < (mt64_state_size - 1); k++)
+    {
+      uint64_t y = ((state->mt[k] & upper_mask)
+		   | (state->mt[k + 1] & lower_mask));
+      state->mt[k] = (state->mt[k + (mt64_shift_size - mt64_state_size)]
+		      ^ (y >> 1) ^ ((y & 0x01) ? mt64_xor_mask : 0));
+    }
+
+  uint64_t y = ((state->mt[mt64_state_size - 1] & upper_mask)
+		| (state->mt[0] & lower_mask));
+  state->mt[mt64_state_size - 1] = (state->mt[mt64_shift_size -1] ^ (y >> 1)
+				    ^ (( y & 0x01) ? mt64_xor_mask : 0));
+  state->p = 0;
+}
+
+void
+mt64_seed (struct mt19937_64 *state, uint64_t seed)
+{
+  /* Generators based on linear-feedback shift-register techniques can not
+     handle all zero initial state (they will output zero continually).  In
+     such cases we use the default initial state).  */
+  if (seed == 0x0)
+    seed = mt64_default_seed;
+
+  state->mt[0] = mt64_default_seed;
+  for (size_t i = 1; i < mt64_state_size; i++)
+    {
+      uint64_t x = state->mt[i - 1];
+      x ^= x >> (mt64_word_size - 2);
+      x *= mt64_init_multiplier;
+      x += i;
+      state->mt[i] = x;
+    }
+  state->p = mt64_state_size;
+}
+
+uint64_t
+mt64_rand (struct mt19937_64 *state)
+{
+  /* Reload the vector - cost is O(n) amortized over n calls.  */
+  if (state->p >= mt64_state_size)
+   mt64_gen_rand (state);
+
+  /* Calculate o(x(i)).  */
+  uint64_t z = state->mt[state->p++];
+  z ^= (z >> mt64_tempering_u) & mt64_tempering_d;
+  z ^= (z << mt64_tempering_s) & mt64_tempering_b;
+  z ^= (z << mt64_tempering_t) & mt64_tempering_c;
+  z ^= (z >> mt64_tempering_l);
+  return z;
+}
diff --git a/support/support_random.h b/support/support_random.h
new file mode 100644
index 0000000..9d58d51
--- /dev/null
+++ b/support/support_random.h
@@ -0,0 +1,109 @@
+/* Function for pseudo-random number generation.
+   Copyright (C) 2018 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, see
+   <http://www.gnu.org/licenses/>.  */
+
+#ifndef SUPPORT_MT_RAND_H
+#define SUPPORT_MT_RAND_H
+
+#include <stdint.h>
+#include <stdlib.h>
+#include <assert.h>
+
+/* Obtain a random seed at BUF with size of LEN from system random device.
+   It will used getrandom or '/dev/urandom' device case getrandom fails.  */
+int random_seed (void *buf, size_t len);
+
+/* A Mersenne Twister implementation for both uint32_t and uint64_t aimed for
+   fast pseudo-random number generation where rand() is not suffice (due
+   mainly low entropy).
+
+   The usual way to use is:
+
+   uint32_t seed;
+   random_seed (&seed, sizeof (uint32_t));
+
+   mt19937_32 mt;
+   mt32_seed (&mt, seed);
+
+   uint32_t random_number = mt32_rand (&mt);
+
+   If seed is 0 the default one (5489u) is used instead.  Usually the seed
+   should be obtained for a more robust random generation (getrandom or
+   from /dev/{u}random).  */
+
+enum {
+  MT32_STATE_SIZE = 624,
+  MT64_STATE_SIZE = 312
+};
+
+struct mt19937_32
+{
+  uint32_t mt[MT32_STATE_SIZE];
+  size_t p;
+};
+
+struct mt19937_64
+{
+  uint64_t mt[MT64_STATE_SIZE];
+  size_t p;
+};
+
+/* Initialize the mersenne twister STATE with SEED.  If seed is zero the
+   default seed is used (5489u).  */
+void mt32_seed (struct mt19937_32 *state, uint32_t seed);
+void mt64_seed (struct mt19937_64 *state, uint64_t seed);
+/* Output a pseudo-number from mersenned twister STATE.  */
+uint32_t mt32_rand (struct mt19937_32 *state);
+uint64_t mt64_rand (struct mt19937_64 *state);
+
+/* Scales the number NUMBER to the uniformly distributed closed internal
+   [min, max].  */
+static inline int32_t
+uniform_uint32_distribution (int32_t random, uint32_t min, uint32_t max)
+{
+  assert (max >= min);
+  uint32_t range = max - min;
+  /* It assumed that the input random number RANDOM is as larger or equal
+     than the RANGE, so the result will always be downscaled.  */
+  if (range != UINT32_MAX)
+    {
+      uint32_t urange = range + 1;  /* range can be 0.  */
+      uint32_t scaling = UINT32_MAX / urange;
+      random /= scaling;
+    }
+  return random + min;
+}
+
+/* Scales the number NUMBER to the uniformly distributed closed internal
+   [min, max].  */
+static inline uint64_t
+uniform_uint64_distribution (uint64_t random, uint64_t min, uint64_t max)
+{
+  assert (max >= min);
+  uint64_t range = max - min;
+  /* It assumed that the input random number RANDOM is as larger or equal
+     than the RANGE, so the result will always be downscaled.  */
+  if (range != UINT64_MAX)
+    {
+      uint64_t urange = range + 1;  /* range can be 0.  */
+      uint64_t scaling = UINT64_MAX / urange;
+      random /= scaling;
+    }
+  return random + min;
+}
+
+#endif
diff --git a/support/tst-support_random.c b/support/tst-support_random.c
new file mode 100644
index 0000000..3068ca9
--- /dev/null
+++ b/support/tst-support_random.c
@@ -0,0 +1,87 @@
+/* Test the Mersenne Twister random functions.
+   Copyright (C) 2017 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, see
+   <http://www.gnu.org/licenses/>.  */
+
+#include <stdint.h>
+#include <stdio.h>
+
+#include <support/check.h>
+#include <support/support_random.h>
+
+static int
+do_test (void)
+{
+  {
+    struct mt19937_32 mt32;
+    mt32_seed (&mt32, 0);
+    for (int i = 0; i < 9999; ++i)
+      mt32_rand (&mt32);
+    TEST_VERIFY (mt32_rand (&mt32) == 4123659995ul);
+  }
+
+  {
+    struct mt19937_64 mt64;
+    mt64_seed (&mt64, 0);
+    for (int i = 0; i < 9999; ++i)
+      mt64_rand (&mt64);
+    TEST_VERIFY (mt64_rand (&mt64) == UINT64_C(9981545732273789042));
+  }
+
+#define CHECK_UNIFORM_32(min, max)						\
+  ({										\
+    uint32_t v = uniform_uint32_distribution (mt32_rand (&mt32), min, max);	\
+    TEST_VERIFY (v >= min && v <= max);						\
+  })
+
+  {
+    struct mt19937_32 mt32;
+    uint32_t seed;
+    random_seed (&seed, sizeof (seed));
+    mt32_seed (&mt32, seed);
+
+    CHECK_UNIFORM_32 (0, 100);
+    CHECK_UNIFORM_32 (100, 200);
+    CHECK_UNIFORM_32 (100, 1<<10);
+    CHECK_UNIFORM_32 (1<<10, UINT16_MAX);
+    CHECK_UNIFORM_32 (UINT16_MAX, UINT32_MAX);
+  }
+
+#define CHECK_UNIFORM_64(min, max)						\
+  ({										\
+    uint64_t v = uniform_uint64_distribution (mt64_rand (&mt64), min, max);	\
+    TEST_VERIFY (v >= min && v <= max);						\
+  })
+
+  {
+    struct mt19937_64 mt64;
+    uint64_t seed;
+    random_seed (&seed, sizeof (seed));
+    mt64_seed (&mt64, seed);
+
+    CHECK_UNIFORM_64 (0, 100);
+    CHECK_UNIFORM_64 (100, 200);
+    CHECK_UNIFORM_64 (100, 1<<10);
+    CHECK_UNIFORM_64 (1<<10, UINT16_MAX);
+    CHECK_UNIFORM_64 (UINT16_MAX, UINT32_MAX);
+    CHECK_UNIFORM_64 (UINT64_C(1)<<33, UINT64_C(1)<<34);
+    CHECK_UNIFORM_64 (UINT64_C(1)<<34, UINT64_MAX);
+  }
+
+  return 0;
+}
+
+#include <support/test-driver.c>

http://sourceware.org/git/gitweb.cgi?p=glibc.git;a=commitdiff;h=d23a77dae549e95722f62d87d30787387fabff08

commit d23a77dae549e95722f62d87d30787387fabff08
Author: Adhemerval Zanella <adhemerval.zanella@linaro.org>
Date:   Fri Dec 15 09:49:37 2017 -0200

    stdlib: Adjust tst-qsort{2} to libsupport
    
    	* stdlib/tst-qsort.c: Use libsupport.
    	* stdlib/tst-qsort2.c: Likewise.

diff --git a/stdlib/tst-qsort.c b/stdlib/tst-qsort.c
index 2b26e74..c3230fd 100644
--- a/stdlib/tst-qsort.c
+++ b/stdlib/tst-qsort.c
@@ -3,6 +3,8 @@
 #include <stdlib.h>
 #include <tst-stack-align.h>
 
+#include <support/check.h>
+
 struct big { char c[4 * 1024]; };
 
 struct big *array;
@@ -10,7 +12,7 @@ struct big *array_end;
 
 static int align_check;
 
-int
+static int
 compare (void const *a1, void const *b1)
 {
   struct big const *a = a1;
@@ -19,37 +21,34 @@ compare (void const *a1, void const *b1)
   if (!align_check)
     align_check = TEST_STACK_ALIGN () ? -1 : 1;
 
-  if (! (array <= a && a < array_end
-	 && array <= b && b < array_end))
-    {
-      exit (EXIT_FAILURE);
-    }
-  return b->c[0] - a->c[0];
+  TEST_VERIFY_EXIT (array <= a && a < array_end
+		    && array <= b && b < array_end);
+
+  return (b->c[0] - a->c[0]) > 0;
 }
 
 int
-main (int argc, char **argv)
+do_test (void)
 {
-  size_t i;
-  size_t array_members = argv[1] ? atoi (argv[1]) : 50;
-  array = (struct big *) malloc (array_members * sizeof *array);
-  if (array == NULL)
+  const size_t sizes[] = { 8, 16, 24, 48, 96, 192, 384 };
+  const size_t sizes_len = sizeof (sizes) / sizeof (sizes[0]);
+
+  for (size_t s = 0; s < sizes_len; s++)
     {
-      puts ("no memory");
-      exit (EXIT_FAILURE);
-    }
+      array = (struct big *) malloc (sizes[s] * sizeof *array);
+      TEST_VERIFY_EXIT (array != NULL);
 
-  array_end = array + array_members;
-  for (i = 0; i < array_members; i++)
-    array[i].c[0] = i % 128;
+      array_end = array + sizes[s];
+      for (size_t i = 0; i < sizes[s]; i++)
+        array[i].c[0] = i % 128;
 
-  qsort (array, array_members, sizeof *array, compare);
+      qsort (array, sizes[s], sizeof *array, compare);
+      TEST_VERIFY_EXIT (align_check != -1);
 
-  if (align_check == -1)
-    {
-      puts ("stack not sufficiently aligned");
-      exit (EXIT_FAILURE);
+      free (array);
     }
 
   return 0;
 }
+
+#include <support/test-driver.c>
diff --git a/stdlib/tst-qsort2.c b/stdlib/tst-qsort2.c
index 10d1685..595875d 100644
--- a/stdlib/tst-qsort2.c
+++ b/stdlib/tst-qsort2.c
@@ -1,11 +1,13 @@
 #include <stdio.h>
 #include <stdlib.h>
 
-char *array;
-char *array_end;
-size_t member_size;
+#include <support/check.h>
 
-int
+static char *array;
+static char *array_end;
+static size_t member_size;
+
+static int
 compare (const void *a1, const void *b1)
 {
   const char *a = a1;
@@ -25,7 +27,7 @@ compare (const void *a1, const void *b1)
   return 0;
 }
 
-int
+static int
 test (size_t nmemb, size_t size)
 {
   array = malloc (nmemb * size);
@@ -66,24 +68,20 @@ test (size_t nmemb, size_t size)
   return 0;
 }
 
-int
-main (int argc, char **argv)
+static int
+do_test (void)
 {
-  int ret = 0;
-  if (argc >= 3)
-    ret |= test (atoi (argv[1]), atoi (argv[2]));
-  else
-    {
-      ret |= test (10000, 1);
-      ret |= test (200000, 2);
-      ret |= test (2000000, 3);
-      ret |= test (2132310, 4);
-      ret |= test (1202730, 7);
-      ret |= test (1184710, 8);
-      ret |= test (272710, 12);
-      ret |= test (14170, 32);
-      ret |= test (4170, 320);
-    }
+  test (10000, 1);
+  test (200000, 2);
+  test (2000000, 3);
+  test (2132310, 4);
+  test (1202730, 7);
+  test (1184710, 8);
+  test (272710, 12);
+  test (14170, 32);
+  test (4170, 320);
 
-  return ret;
+  return 0;
 }
+
+#include <support/test-driver.c>

-----------------------------------------------------------------------


hooks/post-receive
-- 
GNU C Library master sources


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]