stdlib/tst-qsort3.c

   1 /* qsort(_r) tests to trigger worst case for quicksort.
   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 <array_length.h>
  20 #include <errno.h>
  21 #include <getopt.h>
  22 #include <stdbool.h>
  23 #include <stdint.h>
  24 #include <stdio.h>
  25 #include <stdlib.h>
  26 #include <string.h>
  27 #include <support/check.h>
  28 #include <support/support.h>
  29 #include <support/test-driver.h>
  30
  31 typedef enum
  32 {
  33   Sorted,
  34   Random,
  35   Repeated,
  36   Bitonic,
  37   Duplicated,
  38 } arraytype_t;
  39
  40 /* Ratio of total of elements which will be repeated.  */
  41 static const double RepeatedRatio = 0.2;
  42
  43 /* Ratio of duplicated element .  */
  44 static const double DuplicatedRatio = 0.4;
  45
  46 struct array_t
  47 {
  48   arraytype_t type;
  49   const char *name;
  50 } static const arraytypes[] =
  51 {
  52   { Sorted,       "Sorted" },
  53   { Random,       "Random" },
  54   { Repeated,     "Repeated" },
  55   { Bitonic,      "Bitonic" },
  56   { Duplicated,   "Duplicated" },
  57 };
  58
  59 /* Return the index of BASE as interpreted as an array of elements
  60    of size SIZE.  */
  61 static inline void *
  62 arr (void *base, size_t idx, size_t size)
  63 {
  64   return (void*)((uintptr_t)base + (idx * size));
  65 }
  66
  67 /* Functions used to check qsort.  */
  68 static int
  69 uint8_t_cmp (const void *a, const void *b)
  70 {
  71   uint8_t ia = *(uint8_t*)a;
  72   uint8_t ib = *(uint8_t*)b;
  73   return (ia > ib) - (ia < ib);
  74 }
  75
  76 static int
  77 uint16_t_cmp (const void *a, const void *b)
  78 {
  79   uint16_t ia = *(uint16_t*)a;
  80   uint16_t ib = *(uint16_t*)b;
  81   return (ia > ib) - (ia < ib);
  82 }
  83
  84 static int
  85 uint32_t_cmp (const void *a, const void *b)
  86 {
  87   uint32_t ia = *(uint32_t*)a;
  88   uint32_t ib = *(uint32_t*)b;
  89   return (ia > ib) - (ia < ib);
  90 }
  91
  92 static int
  93 uint64_t_cmp (const void *a, const void *b)
  94 {
  95   uint64_t ia = *(uint64_t*)a;
  96   uint64_t ib = *(uint64_t*)b;
  97   return (ia > ib) - (ia < ib);
  98 }
  99
 100 #define LARGE_SIZE 47
 101
 102 static int
 103 large_cmp (const void *a, const void *b)
 104 {
 105   return memcmp (a, b, LARGE_SIZE);
 106 }
 107
 108 /* Function used to check qsort_r.  */
 109 typedef enum
 110 {
 111   UINT8_CMP_T,
 112   UINT16_CMP_T,
 113   UINT32_CMP_T,
 114   UINT64_CMP_T,
 115   LARGE_CMP_T
 116 } type_cmp_t;
 117
 118 static type_cmp_t
 119 uint_t_cmp_type (size_t sz)
 120 {
 121   switch (sz)
 122     {
 123       case sizeof (uint8_t):  return UINT8_CMP_T;
 124       case sizeof (uint16_t): return UINT16_CMP_T;
 125       case sizeof (uint64_t): return UINT64_CMP_T;
 126       case sizeof (uint32_t): return UINT32_CMP_T;
 127       default:                return LARGE_CMP_T;
 128     }
 129 }
 130
 131 static int
 132 uint_t_cmp (const void *a, const void *b, void *arg)
 133 {
 134   type_cmp_t type = *(type_cmp_t*) arg;
 135   switch (type)
 136     {
 137     case UINT8_CMP_T:  return uint8_t_cmp (a, b);
 138     case UINT32_CMP_T: return uint32_t_cmp (a, b);
 139     case UINT16_CMP_T: return uint16_t_cmp (a, b);
 140     case UINT64_CMP_T: return uint64_t_cmp (a, b);
 141     default:           return large_cmp (a, b);
 142     }
 143 }
 144
 145 static void
 146 seq (void *elem, size_t type_size, int value)
 147 {
 148   if (type_size == sizeof (uint8_t))
 149     *(uint8_t*)elem = value;
 150   else if (type_size == sizeof (uint16_t))
 151     *(uint16_t*)elem = value;
 152   else if (type_size == sizeof (uint32_t))
 153     *(uint32_t*)elem = value;
 154   else if (type_size == sizeof (uint64_t))
 155     *(uint64_t*)elem = value;
 156   else
 157     memset (elem, value, type_size);
 158 }
 159
 160 static void
 161 fill_array (void *array, void *refarray, size_t nmemb, size_t type_size,
 162             arraytype_t type)
 163 {
 164   size_t size = nmemb * type_size;
 165
 166   switch (type)
 167     {
 168     case Sorted:
 169       for (size_t i = 0; i < nmemb; i++)
 170         seq (arr (array, i, type_size), type_size, i);
 171       break;
 172
 173     case Random:
 174       arc4random_buf (array, size);
 175       break;
 176
 177     case Repeated:
 178       {
 179         arc4random_buf (array, size);
 180
 181         void *randelem = xmalloc (type_size);
 182         arc4random_buf (randelem, type_size);
 183
 184         /* Repeat REPEATED elements (based on RepeatRatio ratio) in the random
 185            array.  */
 186         size_t repeated = (size_t)(nmemb * RepeatedRatio);
 187         for (size_t i = 0; i < repeated; i++)
 188           {
 189             size_t pos = arc4random_uniform (nmemb - 1);
 190             memcpy (arr (array, pos, type_size), randelem, type_size);
 191           }
 192         free (randelem);
 193       }
 194       break;
 195
 196     case Bitonic:
 197       {
 198         size_t i;
 199         for (i = 0; i < nmemb / 2; i++)
 200           seq (arr (array, i, type_size), type_size, i);
 201         for (     ; i < nmemb;     i++)
 202           seq (arr (array, i, type_size), type_size, (nmemb - 1) - i);
 203       }
 204       break;
 205
 206     case Duplicated:
 207       {
 208         int randelem1 = arc4random ();
 209         for (size_t i = 0; i < nmemb; i++)
 210           seq (arr (array, i, type_size), type_size, randelem1);
 211
 212         size_t duplicates = (size_t)(nmemb * DuplicatedRatio);
 213         int randelem2 = arc4random ();
 214         for (size_t i = 0; i < duplicates; i++)
 215           {
 216             size_t pos = arc4random_uniform (nmemb - 1);
 217             seq (arr (array, pos, type_size), type_size, randelem2);
 218           }
 219       }
 220       break;
 221     }
 222
 223   memcpy (refarray, array, size);
 224 }
 225
 226 typedef int (*cmpfunc_t)(const void *, const void *);
 227
 228 /* Simple insertion sort to use as reference sort.  */
 229 static void
 230 qsort_r_ref (void *p, size_t n, size_t s, __compar_d_fn_t cmp, void *arg)
 231 {
 232   if (n <= 1)
 233     return;
 234
 235   int i = 1;
 236   char tmp[s];
 237   while (i < n)
 238     {
 239       memcpy (tmp, arr (p, i, s), s);
 240       int j = i - 1;
 241       while (j >= 0 && cmp (arr (p, j, s), tmp, arg) > 0)
 242         {
 243           memcpy (arr (p, j + 1, s), arr (p, j, s), s);
 244           j = j - 1;
 245         }
 246       memcpy (arr (p, j + 1, s), tmp, s);
 247       i = i + 1;
 248     }
 249 }
 250
 251 static void
 252 qsort_ref (void *b, size_t n, size_t s, __compar_fn_t cmp)
 253 {
 254   return qsort_r_ref (b, n, s, (__compar_d_fn_t) cmp, NULL);
 255 }
 256
 257 /* Check if ARRAY of total NMEMB element of size SIZE is sorted
 258    based on CMPFUNC.  */
 259 static void
 260 check_array (void *array, void *refarray, size_t nmemb, size_t type_size,
 261              cmpfunc_t cmpfunc)
 262 {
 263   for (size_t i = 1; i < nmemb; i++)
 264     {
 265       int ret = cmpfunc (arr (array, i,   type_size),
 266                          arr (array, i-1, type_size));
 267       TEST_VERIFY_EXIT (ret >= 0);
 268     }
 269
 270   size_t size = nmemb * type_size;
 271   TEST_COMPARE_BLOB (array, size, refarray, size);
 272 }
 273
 274 static void
 275 check_qsort (void *buf, void *refbuf, size_t nelem, size_t type_size,
 276              arraytype_t type, cmpfunc_t cmpfunc)
 277 {
 278   fill_array (buf, refbuf, nelem, type_size, type);
 279
 280   qsort (buf, nelem, type_size, cmpfunc);
 281   qsort_ref (refbuf, nelem, type_size, cmpfunc);
 282
 283   check_array (buf, refbuf, nelem, type_size, cmpfunc);
 284 }
 285
 286 static void
 287 check_qsort_r (void *buf, void *refbuf, size_t nelem, size_t type_size,
 288                arraytype_t type, cmpfunc_t cmpfunc)
 289 {
 290   fill_array (buf, refbuf, nelem, type_size, type);
 291
 292   type_cmp_t typecmp = uint_t_cmp_type (type_size);
 293
 294   qsort_r (buf, nelem, type_size, uint_t_cmp, &typecmp);
 295   qsort_r_ref (refbuf, nelem, type_size, uint_t_cmp, &typecmp);
 296
 297   check_array (buf, refbuf, nelem, type_size, cmpfunc);
 298 }
 299
 300 static int
 301 do_test (void)
 302 {
 303   /* Some random sizes.  */
 304   static const size_t nelems[] = { 0, 1, 7, 20, 32, 100, 256, 1024, 4256 };
 305   size_t max_nelems = 0;
 306   for (int i = 0; i < array_length (nelems); i++)
 307     if (nelems[i] > max_nelems)
 308       max_nelems = nelems[i];
 309
 310   static const struct test_t
 311     {
 312       size_t type_size;
 313       cmpfunc_t cmpfunc;
 314     }
 315   tests[] =
 316     {
 317       { sizeof (uint8_t),  uint8_t_cmp },
 318       { sizeof (uint16_t), uint16_t_cmp },
 319       { sizeof (uint32_t), uint32_t_cmp },
 320       { sizeof (uint64_t), uint64_t_cmp },
 321       /* Test swap with large elements.  */
 322       { LARGE_SIZE,        large_cmp },
 323     };
 324   size_t max_type_size = 0;
 325   for (int i = 0; i < array_length (tests); i++)
 326     if (tests[i].type_size > max_type_size)
 327       max_type_size = tests[i].type_size;
 328
 329   void *buf = reallocarray (NULL, max_nelems, max_type_size);
 330   TEST_VERIFY_EXIT (buf != NULL);
 331   void *refbuf = reallocarray (NULL, max_nelems, max_type_size);
 332   TEST_VERIFY_EXIT (refbuf != NULL);
 333
 334   for (const struct test_t *test = tests; test < array_end (tests); ++test)
 335     {
 336       if (test_verbose > 0)
 337         printf ("info: testing qsort with type_size=%zu\n", test->type_size);
 338       for (const struct array_t *arraytype = arraytypes;
 339            arraytype < array_end (arraytypes);
 340            ++arraytype)
 341         {
 342           if (test_verbose > 0)
 343             printf ("  distribution=%s\n", arraytype->name);
 344           for (const size_t *nelem = nelems;
 345                nelem < array_end (nelems);
 346                ++nelem)
 347             {
 348               if (test_verbose > 0)
 349                 printf ("    nelem=%zu, total size=%zu\n", *nelem,
 350                         *nelem * test->type_size);
 351
 352               check_qsort (buf, refbuf, *nelem, test->type_size,
 353                            arraytype->type, test->cmpfunc);
 354               check_qsort_r (buf, refbuf, *nelem, test->type_size,
 355                              arraytype->type, test->cmpfunc);
 356            }
 357         }
 358     }
 359
 360   free (buf);
 361   free (refbuf);
 362
 363   return 0;
 364 }
 365
 366 #include <support/test-driver.c>