misc/tst-tsearch.c

   1 /* Test program for tsearch et al.
   2    Copyright (C) 1997-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    <https://www.gnu.org/licenses/>.  */
  18
  19 #ifndef _GNU_SOURCE
  20 # define _GNU_SOURCE    1
  21 #endif
  22
  23 #include <stdio.h>
  24 #include <stdlib.h>
  25 #include <string.h>
  26 #include <search.h>
  27 #include <tst-stack-align.h>
  28 #include <support/check.h>
  29
  30 #define SEED 0
  31 #define BALANCED 1
  32 #define PASSES 100
  33
  34 #if BALANCED
  35 #include <math.h>
  36 #define SIZE 1000
  37 #else
  38 #define SIZE 100
  39 #endif
  40
  41 enum order
  42 {
  43   ascending,
  44   descending,
  45   randomorder
  46 };
  47
  48 enum action
  49 {
  50   build,
  51   build_and_del,
  52   delete,
  53   find
  54 };
  55
  56 /* Set to 1 if a test is flunked.  */
  57 static int error = 0;
  58
  59 /* The keys we add to the tree.  */
  60 static int x[SIZE];
  61
  62 /* Pointers into the key array, possibly permutated, to define an order
  63    for insertion/removal.  */
  64 static int y[SIZE];
  65
  66 /* Flags set for each element visited during a tree walk.  */
  67 static int z[SIZE];
  68
  69 /* Depths for all the elements, to check that the depth is constant for
  70    all three visits.  */
  71 static int depths[SIZE];
  72
  73 /* Maximum depth during a tree walk.  */
  74 static int max_depth;
  75
  76 static int stack_align_check[2];
  77
  78 /* Used to compare walk traces between the two implementations.  */
  79 struct walk_trace_element
  80 {
  81   const void *key;
  82   VISIT which;
  83   int depth;
  84 };
  85 #define DYNARRAY_STRUCT walk_trace_list
  86 #define DYNARRAY_ELEMENT struct walk_trace_element
  87 #define DYNARRAY_PREFIX walk_trace_
  88 #define DYNARRAY_INITIAL_SIZE 0
  89 #include <malloc/dynarray-skeleton.c>
  90 static struct walk_trace_list walk_trace;
  91
  92 /* Compare two keys.  */
  93 static int
  94 cmp_fn (const void *a, const void *b)
  95 {
  96   if (!stack_align_check[0])
  97     stack_align_check[0] = TEST_STACK_ALIGN () ? -1 : 1;
  98   return *(const int *) a - *(const int *) b;
  99 }
 100
 101 /* Permute an array of integers.  */
 102 static void
 103 memfry (int *string)
 104 {
 105   int i;
 106
 107   for (i = 0; i < SIZE; ++i)
 108     {
 109       int32_t j;
 110       int c;
 111
 112       j = random () % SIZE;
 113
 114       c = string[i];
 115       string[i] = string[j];
 116       string[j] = c;
 117     }
 118 }
 119
 120 struct twalk_with_twalk_r_closure
 121 {
 122   void (*action) (const void *, VISIT, int);
 123   int depth;
 124 };
 125
 126 static void
 127 twalk_with_twalk_r_action (const void *nodep, VISIT which, void *closure0)
 128 {
 129   struct twalk_with_twalk_r_closure *closure = closure0;
 130
 131   switch (which)
 132     {
 133     case leaf:
 134       closure->action (nodep, which, closure->depth);
 135       break;
 136     case preorder:
 137       closure->action (nodep, which, closure->depth);
 138       ++closure->depth;
 139       break;
 140     case postorder:
 141       /* The preorder action incremented the depth.  */
 142       closure->action (nodep, which, closure->depth - 1);
 143       break;
 144     case endorder:
 145       --closure->depth;
 146       closure->action (nodep, which, closure->depth);
 147       break;
 148     }
 149 }
 150
 151 static void
 152 twalk_with_twalk_r (const void *root,
 153                     void (*action) (const void *, VISIT, int))
 154 {
 155   struct twalk_with_twalk_r_closure closure = { action, 0 };
 156   twalk_r (root, twalk_with_twalk_r_action, &closure);
 157   TEST_COMPARE (closure.depth, 0);
 158 }
 159
 160 static void
 161 walk_action (const void *nodep, const VISIT which, const int depth)
 162 {
 163   int key = **(int **) nodep;
 164
 165   walk_trace_add (&walk_trace,
 166                   (struct walk_trace_element) { nodep, which, depth });
 167
 168   if (!stack_align_check[1])
 169     stack_align_check[1] = TEST_STACK_ALIGN () ? -1 : 1;
 170
 171   if (depth > max_depth)
 172     max_depth = depth;
 173   if (which == leaf || which == preorder)
 174     {
 175       ++z[key];
 176       depths[key] = depth;
 177     }
 178   else
 179     {
 180       if (depths[key] != depth)
 181         {
 182           fputs ("Depth for one element is not constant during tree walk.\n",
 183                  stdout);
 184         }
 185     }
 186 }
 187
 188 static void
 189 walk_tree_with (void *root, int expected_count,
 190                 void (*walk) (const void *,
 191                               void (*) (const void *, VISIT, int)))
 192 {
 193   int i;
 194
 195   memset (z, 0, sizeof z);
 196   max_depth = 0;
 197
 198   walk (root, walk_action);
 199   for (i = 0; i < expected_count; ++i)
 200     if (z[i] != 1)
 201       {
 202         fputs ("Node was not visited.\n", stdout);
 203         error = 1;
 204       }
 205
 206 #if BALANCED
 207   if (max_depth > log (expected_count) * 2 + 2)
 208 #else
 209   if (max_depth > expected_count)
 210 #endif
 211     {
 212       fputs ("Depth too large during tree walk.\n", stdout);
 213       error = 1;
 214     }
 215 }
 216
 217 static void
 218 walk_tree (void *root, int expected_count)
 219 {
 220   walk_trace_clear (&walk_trace);
 221   walk_tree_with (root, expected_count, twalk);
 222   TEST_VERIFY (!walk_trace_has_failed (&walk_trace));
 223   size_t first_list_size;
 224   struct walk_trace_element *first_list
 225     = walk_trace_finalize (&walk_trace, &first_list_size);
 226   TEST_VERIFY_EXIT (first_list != NULL);
 227
 228   walk_tree_with (root, expected_count, twalk_with_twalk_r);
 229   TEST_VERIFY (!walk_trace_has_failed (&walk_trace));
 230
 231   /* Compare the two traces.  */
 232   TEST_COMPARE (first_list_size, walk_trace_size (&walk_trace));
 233   for (size_t i = 0; i < first_list_size && i < walk_trace_size (&walk_trace);
 234        ++i)
 235     {
 236       TEST_VERIFY (first_list[i].key == walk_trace_at (&walk_trace, i)->key);
 237       TEST_COMPARE (first_list[i].which, walk_trace_at (&walk_trace, i)->which);
 238       TEST_COMPARE (first_list[i].depth, walk_trace_at (&walk_trace, i)->depth);
 239     }
 240
 241   walk_trace_free (&walk_trace);
 242 }
 243
 244 /* Perform an operation on a tree.  */
 245 static void
 246 mangle_tree (enum order how, enum action what, void **root, int lag)
 247 {
 248   int i;
 249
 250   if (how == randomorder)
 251     {
 252       for (i = 0; i < SIZE; ++i)
 253         y[i] = i;
 254       memfry (y);
 255     }
 256
 257   for (i = 0; i < SIZE + lag; ++i)
 258     {
 259       void *elem;
 260       int j, k;
 261
 262       switch (how)
 263         {
 264         case randomorder:
 265           if (i >= lag)
 266             k = y[i - lag];
 267           else
 268             /* Ensure that the array index is within bounds.  */
 269             k = y[(SIZE - i - 1 + lag) % SIZE];
 270           j = y[i % SIZE];
 271           break;
 272
 273         case ascending:
 274           k = i - lag;
 275           j = i;
 276           break;
 277
 278         case descending:
 279           k = SIZE - i - 1 + lag;
 280           j = SIZE - i - 1;
 281           break;
 282
 283         default:
 284           /* This never should happen, but gcc isn't smart enough to
 285              recognize it.  */
 286           abort ();
 287         }
 288
 289       switch (what)
 290         {
 291         case build_and_del:
 292         case build:
 293           if (i < SIZE)
 294             {
 295               if (tfind (x + j, (void *const *) root, cmp_fn) != NULL)
 296                 {
 297                   fputs ("Found element which is not in tree yet.\n", stdout);
 298                   error = 1;
 299                 }
 300               elem = tsearch (x + j, root, cmp_fn);
 301               if (elem == 0
 302                   || tfind (x + j, (void *const *) root, cmp_fn) == NULL)
 303                 {
 304                   fputs ("Couldn't find element after it was added.\n",
 305                          stdout);
 306                   error = 1;
 307                 }
 308             }
 309
 310           if (what == build || i < lag)
 311             break;
 312
 313           j = k;
 314           /* fall through */
 315
 316         case delete:
 317           elem = tfind (x + j, (void *const *) root, cmp_fn);
 318           if (elem == NULL || tdelete (x + j, root, cmp_fn) == NULL)
 319             {
 320               fputs ("Error deleting element.\n", stdout);
 321               error = 1;
 322             }
 323           break;
 324
 325         case find:
 326           if (tfind (x + j, (void *const *) root, cmp_fn) == NULL)
 327             {
 328               fputs ("Couldn't find element after it was added.\n", stdout);
 329               error = 1;
 330             }
 331           break;
 332
 333         }
 334     }
 335 }
 336
 337
 338 static int
 339 do_test (void)
 340 {
 341   int total_error = 0;
 342   static char state[8] = { 1, 2, 3, 4, 5, 6, 7, 8 };
 343   void *root = NULL;
 344   int i, j;
 345
 346   initstate (SEED, state, 8);
 347
 348   for (i = 0; i < SIZE; ++i)
 349     x[i] = i;
 350
 351   /* Do this loop several times to get different permutations for the
 352      random case.  */
 353   fputs ("Series I\n", stdout);
 354   for (i = 0; i < PASSES; ++i)
 355     {
 356       fprintf (stdout, "Pass %d... ", i + 1);
 357       fflush (stdout);
 358       error = 0;
 359
 360       mangle_tree (ascending, build, &root, 0);
 361       mangle_tree (ascending, find, &root, 0);
 362       mangle_tree (descending, find, &root, 0);
 363       mangle_tree (randomorder, find, &root, 0);
 364       walk_tree (root, SIZE);
 365       mangle_tree (ascending, delete, &root, 0);
 366
 367       mangle_tree (ascending, build, &root, 0);
 368       walk_tree (root, SIZE);
 369       mangle_tree (descending, delete, &root, 0);
 370
 371       mangle_tree (ascending, build, &root, 0);
 372       walk_tree (root, SIZE);
 373       mangle_tree (randomorder, delete, &root, 0);
 374
 375       mangle_tree (descending, build, &root, 0);
 376       mangle_tree (ascending, find, &root, 0);
 377       mangle_tree (descending, find, &root, 0);
 378       mangle_tree (randomorder, find, &root, 0);
 379       walk_tree (root, SIZE);
 380       mangle_tree (descending, delete, &root, 0);
 381
 382       mangle_tree (descending, build, &root, 0);
 383       walk_tree (root, SIZE);
 384       mangle_tree (descending, delete, &root, 0);
 385
 386       mangle_tree (descending, build, &root, 0);
 387       walk_tree (root, SIZE);
 388       mangle_tree (randomorder, delete, &root, 0);
 389
 390       mangle_tree (randomorder, build, &root, 0);
 391       mangle_tree (ascending, find, &root, 0);
 392       mangle_tree (descending, find, &root, 0);
 393       mangle_tree (randomorder, find, &root, 0);
 394       walk_tree (root, SIZE);
 395       mangle_tree (randomorder, delete, &root, 0);
 396
 397       for (j = 1; j < SIZE; j *= 2)
 398         {
 399           mangle_tree (randomorder, build_and_del, &root, j);
 400         }
 401
 402       fputs (error ? " failed!\n" : " ok.\n", stdout);
 403       total_error |= error;
 404     }
 405
 406   fputs ("Series II\n", stdout);
 407   for (i = 1; i < SIZE; i *= 2)
 408     {
 409       fprintf (stdout, "For size %d... ", i);
 410       fflush (stdout);
 411       error = 0;
 412
 413       mangle_tree (ascending, build_and_del, &root, i);
 414       mangle_tree (descending, build_and_del, &root, i);
 415       mangle_tree (ascending, build_and_del, &root, i);
 416       mangle_tree (descending, build_and_del, &root, i);
 417       mangle_tree (ascending, build_and_del, &root, i);
 418       mangle_tree (descending, build_and_del, &root, i);
 419       mangle_tree (ascending, build_and_del, &root, i);
 420       mangle_tree (descending, build_and_del, &root, i);
 421
 422       fputs (error ? " failed!\n" : " ok.\n", stdout);
 423       total_error |= error;
 424     }
 425
 426   for (i = 0; i < 2; ++i)
 427     if (stack_align_check[i] == 0)
 428       {
 429         printf ("stack alignment check %d not run\n", i);
 430         total_error |= 1;
 431       }
 432     else if (stack_align_check[i] != 1)
 433       {
 434         printf ("stack insufficiently aligned in check %d\n", i);
 435         total_error |= 1;
 436       }
 437
 438   return total_error;
 439 }
 440
 441 #define TEST_FUNCTION do_test ()
 442 #include "../test-skeleton.c"