stdlib/tst-qsort4.c

   1 /* Test the heapsort implementation behind qsort.
   2    Copyright (C) 2023-2024 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 static void
  34 check_one_sort (signed char *array, int length)
  35 {
  36   signed char *copy = xmalloc (length);
  37   memcpy (copy, array, length);
  38   heapsort_r (copy, length - 1, 1, cmp, NULL);
  39
  40   /* Verify that the result is sorted.  */
  41   for (int i = 1; i < length; ++i)
  42     if (copy[i] < copy[i - 1])
  43       {
  44         support_record_failure ();
  45         printf ("error: sorting failure for length %d at offset %d\n",
  46                 length, i - 1);
  47         printf ("input:");
  48         for (int i = 0; i < length; ++i)
  49           printf (" %d", array[i]);
  50         printf ("\noutput:");
  51         for (int i = 0; i < length; ++i)
  52           printf (" %d", copy[i]);
  53         putchar ('\n');
  54         break;
  55       }
  56
  57   /* Verify that no elements went away or were added.  */
  58   {
  59     int expected_counts[256];
  60     for (int i = 0; i < length; ++i)
  61       ++expected_counts[array[i] & 0xff];
  62     int actual_counts[256];
  63     for (int i = 0; i < length; ++i)
  64       ++actual_counts[copy[i] & 0xff];
  65     for (int i = 0; i < 256; ++i)
  66       TEST_COMPARE (expected_counts[i], expected_counts[i]);
  67   }
  68
  69   free (copy);
  70 }
  71
  72 /* Enumerate all possible combinations of LENGTH elements.  */
  73 static void
  74 check_combinations (int length, signed char *start, int offset)
  75 {
  76   if (offset == length)
  77     check_one_sort (start, length);
  78   else
  79     for (int i = 0; i < length; ++i)
  80       {
  81         start[offset] = i;
  82         check_combinations(length, start, offset + 1);
  83       }
  84 }
  85
  86 static int
  87 do_test (void)
  88 {
  89   /* A random permutation of 20 values.  */
  90   check_one_sort ((signed char[20]) {5, 12, 16, 10, 14, 11, 9, 13, 8, 15,
  91                                      0, 17, 3, 7, 1, 18, 2, 19, 4, 6}, 20);
  92
  93
  94   /* A permutation that appeared during adversarial testing for the
  95      quicksort pass.  */
  96   check_one_sort ((signed char[16]) {15, 3, 4, 2, 1, 0, 8, 7, 6, 5, 14,
  97                                      13, 12, 11, 10, 9}, 16);
  98
  99   /* Array lengths 2 and less are not handled by heapsort_r and
 100      deferred to insertion sort.  */
 101   for (int i = 3; i <= 8; ++i)
 102     {
 103       signed char *buf = xmalloc (i);
 104       check_combinations (i, buf, 0);
 105       free (buf);
 106     }
 107
 108   return 0;
 109 }
 110
 111 #include <support/test-driver.c>