stdlib/tst-qsort4.c

   1 /* Test the heapsort implementation behind qsort.
   2    Copyright (C) 2023 Free Software Foundation, Inc.
   3    This file is part of the GNU C Library.
   4
   5    The GNU C Library is free software; you can redistribute it and/or
   6    modify it under the terms of the GNU Lesser General Public
   7    License as published by the Free Software Foundation; either
   8    version 2.1 of the License, or (at your option) any later version.
   9
  10    The GNU C Library is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13    Lesser General Public License for more details.
  14
  15    You should have received a copy of the GNU Lesser General Public
  16    License along with the GNU C Library; if not, see
  17    <http://www.gnu.org/licenses/>.  */
  18
  19 #include "qsort.c"
  20
  21 #include <stdio.h>
  22 #include <support/check.h>
  23 #include <support/support.h>
  24
  25 static int
  26 cmp (const void *a1, const void *b1, void *closure)
  27 {
  28   const signed char *a = a1;
  29   const signed char *b = b1;
  30   return *a - *b;
  31 }
  32
  33 /* Wrapper around heapsort_r that set ups the required variables.  */
  34 static void
  35 heapsort_wrapper (void *const pbase, size_t total_elems, size_t size,
  36                   __compar_d_fn_t cmp, void *arg)
  37 {
  38   char *base_ptr = (char *) pbase;
  39   char *lo = base_ptr;
  40   char *hi = &lo[size * (total_elems - 1)];
  41
  42   if (total_elems <= 1)
  43     /* Avoid lossage with unsigned arithmetic below.  */
  44     return;
  45
  46   enum swap_type_t swap_type;
  47   if (is_aligned (pbase, size, 8))
  48     swap_type = SWAP_WORDS_64;
  49   else if (is_aligned (pbase, size, 4))
  50     swap_type = SWAP_WORDS_32;
  51   else
  52     swap_type = SWAP_BYTES;
  53   heapsort_r (lo, hi, size, swap_type, cmp, arg);
  54 }
  55
  56 static void
  57 check_one_sort (signed char *array, int length)
  58 {
  59   signed char *copy = xmalloc (length);
  60   memcpy (copy, array, length);
  61   heapsort_wrapper (copy, length, 1, cmp, NULL);
  62
  63   /* Verify that the result is sorted.  */
  64   for (int i = 1; i < length; ++i)
  65     if (copy[i] < copy[i - 1])
  66       {
  67         support_record_failure ();
  68         printf ("error: sorting failure for length %d at offset %d\n",
  69                 length, i - 1);
  70         printf ("input:");
  71         for (int i = 0; i < length; ++i)
  72           printf (" %d", array[i]);
  73         printf ("\noutput:");
  74         for (int i = 0; i < length; ++i)
  75           printf (" %d", copy[i]);
  76         putchar ('\n');
  77         break;
  78       }
  79
  80   /* Verify that no elements went away or were added.  */
  81   {
  82     int expected_counts[256];
  83     for (int i = 0; i < length; ++i)
  84       ++expected_counts[array[i] & 0xff];
  85     int actual_counts[256];
  86     for (int i = 0; i < length; ++i)
  87       ++actual_counts[copy[i] & 0xff];
  88     for (int i = 0; i < 256; ++i)
  89       TEST_COMPARE (expected_counts[i], expected_counts[i]);
  90   }
  91
  92   free (copy);
  93 }
  94
  95 /* Enumerate all possible combinations of LENGTH elements.  */
  96 static void
  97 check_combinations (int length, signed char *start, int offset)
  98 {
  99   if (offset == length)
 100     check_one_sort (start, length);
 101   else
 102     for (int i = 0; i < length; ++i)
 103       {
 104         start[offset] = i;
 105         check_combinations(length, start, offset + 1);
 106       }
 107 }
 108
 109 static int
 110 do_test (void)
 111 {
 112   /* A random permutation of 20 values.  */
 113   check_one_sort ((signed char[20]) {5, 12, 16, 10, 14, 11, 9, 13, 8, 15,
 114                                      0, 17, 3, 7, 1, 18, 2, 19, 4, 6}, 20);
 115
 116
 117   /* A permutation that appeared during adversarial testing for the
 118      quicksort pass.  */
 119   check_one_sort ((signed char[16]) {15, 3, 4, 2, 1, 0, 8, 7, 6, 5, 14,
 120                                      13, 12, 11, 10, 9}, 16);
 121
 122   /* Array lengths 2 and less are not handled by heapsort_r and
 123      deferred to insertion sort.  */
 124   for (int i = 3; i <= 8; ++i)
 125     {
 126       signed char *buf = xmalloc (i);
 127       check_combinations (i, buf, 0);
 128       free (buf);
 129     }
 130
 131   return 0;
 132 }
 133
 134 #include <support/test-driver.c>