stdlib/tst-qsort5.c

   1 /* Adversarial test for qsort_r.
   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 /* The approach follows Douglas McIlroy, A Killer Adversary for
  20    Quicksort.  Software—Practice and Experience 29 (1999) 341-344.
  21    Downloaded <http://www.cs.dartmouth.edu/~doug/mdmspe.pdf>
  22    (2023-11-17).  */
  23
  24 #include <math.h>
  25 #include <stdlib.h>
  26 #include <stdio.h>
  27 #include <support/check.h>
  28 #include <support/support.h>
  29
  30 struct context
  31 {
  32   /* Called the gas value in the paper.  This value is larger than all
  33      other values (length minus one will do), so comparison with any
  34      decided value has a known result.  */
  35   int undecided_value;
  36
  37   /* If comparing undecided values, one of them as to be assigned a
  38      value to ensure consistency with future comparisons.  This is the
  39      value that will be used.  Starts out at zero.  */
  40   int next_decided;
  41
  42   /* Used to trick pivot selection.  Deciding the value for the last
  43      seen undcided value in a decided/undecided comparison happens
  44      to trick the many qsort implementations.  */
  45   int last_undecided_index;
  46
  47   /* This array contains the actually asigned values.  The call to
  48      qsort_r sorts a different array that contains indices into this
  49      array.  */
  50   int *decided_values;
  51 };
  52
  53 static int
  54 compare_opponent (const void *l1, const void *r1, void *ctx1)
  55 {
  56   const int *l = l1;
  57   const int *r = r1;
  58   struct context *ctx = ctx1;
  59   int rvalue = ctx->decided_values[*r];
  60   int lvalue = ctx->decided_values[*l];
  61
  62   if (lvalue == ctx->undecided_value)
  63     {
  64       if (rvalue == ctx->undecided_value)
  65         {
  66           /* Both values are undecided.  In this case, make a decision
  67              for the last-used undecided value.  This is tweak is very
  68              specific to quicksort.  */
  69           if (*l == ctx->last_undecided_index)
  70             {
  71               ctx->decided_values[*l] = ctx->next_decided;
  72               ++ctx->next_decided;
  73               /* The undecided value or *r is greater.  */
  74               return -1;
  75             }
  76           else
  77             {
  78               ctx->decided_values[*r] = ctx->next_decided;
  79               ++ctx->next_decided;
  80               /* The undecided value for *l is greater.  */
  81               return 1;
  82             }
  83         }
  84       else
  85         {
  86           ctx->last_undecided_index = *l;
  87           return 1;
  88         }
  89     }
  90   else
  91     {
  92       /* *l is a decided value.  */
  93       if (rvalue == ctx->undecided_value)
  94         {
  95           ctx->last_undecided_index = *r;
  96           /* The undecided value for *r is greater.  */
  97           return -1;
  98         }
  99       else
 100         return lvalue - rvalue;
 101     }
 102 }
 103
 104 /* Return a pointer to the adversarial permutation of length N.  */
 105 static int *
 106 create_permutation (size_t n)
 107 {
 108   struct context ctx =
 109     {
 110       .undecided_value = n - 1, /* Larger than all other values.  */
 111       .decided_values = xcalloc (n, sizeof (int)),
 112     };
 113   for (size_t i = 0; i < n; ++i)
 114     ctx.decided_values[i] = ctx.undecided_value;
 115   int *scratch = xcalloc (n, sizeof (int));
 116   for (size_t i = 0; i < n; ++i)
 117     scratch[i] = i;
 118   qsort_r (scratch, n, sizeof (*scratch), compare_opponent, &ctx);
 119   free (scratch);
 120   return ctx.decided_values;
 121 }
 122
 123 /* Callback function for qsort which counts the number of invocations
 124    in *CLOSURE.  */
 125 static int
 126 compare_counter (const void *l1, const void *r1, void *closure)
 127 {
 128   const int *l = l1;
 129   const int *r = r1;
 130   unsigned long long int *counter = closure;
 131   ++*counter;
 132   return *l - *r;
 133 }
 134
 135 /* Count the comparisons required for an adversarial permutation of
 136    length N.  */
 137 static unsigned long long int
 138 count_comparisons (size_t n)
 139 {
 140   int *array = create_permutation (n);
 141   unsigned long long int counter = 0;
 142   qsort_r (array, n, sizeof (*array), compare_counter, &counter);
 143   free (array);
 144   return counter;
 145 }
 146
 147 /* Check the scaling factor for one adversarial permutation of length
 148    N, and report some statistics.  */
 149 static void
 150 check_one_n (size_t n)
 151 {
 152   unsigned long long int count = count_comparisons (n);
 153   double factor = count / (n * log (count));
 154   printf ("info: length %zu: %llu comparisons ~ %f * n * log (n)\n",
 155           n, count, factor);
 156   /* This is an arbitrary factor which is true for the current
 157      implementation across a wide range of sizes.  */
 158   TEST_VERIFY (factor <= 4.5);
 159 }
 160
 161 static int
 162 do_test (void)
 163 {
 164   check_one_n (100);
 165   check_one_n (1000);
 166   for (int i = 1; i <= 15; ++i)
 167     check_one_n (i * 10 * 1000);
 168   return 0;
 169 }
 170
 171 #include <support/test-driver.c>