misc/tst-tsearch.c

   1 /* Test program for tsearch et al.
   2    Copyright (C) 1997-2019 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 #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
 227   walk_tree_with (root, expected_count, twalk_with_twalk_r);
 228
 229   /* Compare the two traces.  */
 230   TEST_COMPARE (first_list_size, walk_trace_size (&walk_trace));
 231   for (size_t i = 0; i < first_list_size && i < walk_trace_size (&walk_trace);
 232        ++i)
 233     {
 234       TEST_VERIFY (first_list[i].key == walk_trace_at (&walk_trace, i)->key);
 235       TEST_COMPARE (first_list[i].which, walk_trace_at (&walk_trace, i)->which);
 236       TEST_COMPARE (first_list[i].depth, walk_trace_at (&walk_trace, i)->depth);
 237     }
 238
 239   walk_trace_free (&walk_trace);
 240 }
 241
 242 /* Perform an operation on a tree.  */
 243 static void
 244 mangle_tree (enum order how, enum action what, void **root, int lag)
 245 {
 246   int i;
 247
 248   if (how == randomorder)
 249     {
 250       for (i = 0; i < SIZE; ++i)
 251         y[i] = i;
 252       memfry (y);
 253     }
 254
 255   for (i = 0; i < SIZE + lag; ++i)
 256     {
 257       void *elem;
 258       int j, k;
 259
 260       switch (how)
 261         {
 262         case randomorder:
 263           if (i >= lag)
 264             k = y[i - lag];
 265           else
 266             /* Ensure that the array index is within bounds.  */
 267             k = y[(SIZE - i - 1 + lag) % SIZE];
 268           j = y[i % SIZE];
 269           break;
 270
 271         case ascending:
 272           k = i - lag;
 273           j = i;
 274           break;
 275
 276         case descending:
 277           k = SIZE - i - 1 + lag;
 278           j = SIZE - i - 1;
 279           break;
 280
 281         default:
 282           /* This never should happen, but gcc isn't smart enough to
 283              recognize it.  */
 284           abort ();
 285         }
 286
 287       switch (what)
 288         {
 289         case build_and_del:
 290         case build:
 291           if (i < SIZE)
 292             {
 293               if (tfind (x + j, (void *const *) root, cmp_fn) != NULL)
 294                 {
 295                   fputs ("Found element which is not in tree yet.\n", stdout);
 296                   error = 1;
 297                 }
 298               elem = tsearch (x + j, root, cmp_fn);
 299               if (elem == 0
 300                   || tfind (x + j, (void *const *) root, cmp_fn) == NULL)
 301                 {
 302                   fputs ("Couldn't find element after it was added.\n",
 303                          stdout);
 304                   error = 1;
 305                 }
 306             }
 307
 308           if (what == build || i < lag)
 309             break;
 310
 311           j = k;
 312           /* fall through */
 313
 314         case delete:
 315           elem = tfind (x + j, (void *const *) root, cmp_fn);
 316           if (elem == NULL || tdelete (x + j, root, cmp_fn) == NULL)
 317             {
 318               fputs ("Error deleting element.\n", stdout);
 319               error = 1;
 320             }
 321           break;
 322
 323         case find:
 324           if (tfind (x + j, (void *const *) root, cmp_fn) == NULL)
 325             {
 326               fputs ("Couldn't find element after it was added.\n", stdout);
 327               error = 1;
 328             }
 329           break;
 330
 331         }
 332     }
 333 }
 334
 335
 336 static int
 337 do_test (void)
 338 {
 339   int total_error = 0;
 340   static char state[8] = { 1, 2, 3, 4, 5, 6, 7, 8 };
 341   void *root = NULL;
 342   int i, j;
 343
 344   initstate (SEED, state, 8);
 345
 346   for (i = 0; i < SIZE; ++i)
 347     x[i] = i;
 348
 349   /* Do this loop several times to get different permutations for the
 350      random case.  */
 351   fputs ("Series I\n", stdout);
 352   for (i = 0; i < PASSES; ++i)
 353     {
 354       fprintf (stdout, "Pass %d... ", i + 1);
 355       fflush (stdout);
 356       error = 0;
 357
 358       mangle_tree (ascending, build, &root, 0);
 359       mangle_tree (ascending, find, &root, 0);
 360       mangle_tree (descending, find, &root, 0);
 361       mangle_tree (randomorder, find, &root, 0);
 362       walk_tree (root, SIZE);
 363       mangle_tree (ascending, delete, &root, 0);
 364
 365       mangle_tree (ascending, build, &root, 0);
 366       walk_tree (root, SIZE);
 367       mangle_tree (descending, delete, &root, 0);
 368
 369       mangle_tree (ascending, build, &root, 0);
 370       walk_tree (root, SIZE);
 371       mangle_tree (randomorder, delete, &root, 0);
 372
 373       mangle_tree (descending, build, &root, 0);
 374       mangle_tree (ascending, find, &root, 0);
 375       mangle_tree (descending, find, &root, 0);
 376       mangle_tree (randomorder, find, &root, 0);
 377       walk_tree (root, SIZE);
 378       mangle_tree (descending, delete, &root, 0);
 379
 380       mangle_tree (descending, build, &root, 0);
 381       walk_tree (root, SIZE);
 382       mangle_tree (descending, delete, &root, 0);
 383
 384       mangle_tree (descending, build, &root, 0);
 385       walk_tree (root, SIZE);
 386       mangle_tree (randomorder, delete, &root, 0);
 387
 388       mangle_tree (randomorder, build, &root, 0);
 389       mangle_tree (ascending, find, &root, 0);
 390       mangle_tree (descending, find, &root, 0);
 391       mangle_tree (randomorder, find, &root, 0);
 392       walk_tree (root, SIZE);
 393       mangle_tree (randomorder, delete, &root, 0);
 394
 395       for (j = 1; j < SIZE; j *= 2)
 396         {
 397           mangle_tree (randomorder, build_and_del, &root, j);
 398         }
 399
 400       fputs (error ? " failed!\n" : " ok.\n", stdout);
 401       total_error |= error;
 402     }
 403
 404   fputs ("Series II\n", stdout);
 405   for (i = 1; i < SIZE; i *= 2)
 406     {
 407       fprintf (stdout, "For size %d... ", i);
 408       fflush (stdout);
 409       error = 0;
 410
 411       mangle_tree (ascending, build_and_del, &root, i);
 412       mangle_tree (descending, build_and_del, &root, i);
 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
 420       fputs (error ? " failed!\n" : " ok.\n", stdout);
 421       total_error |= error;
 422     }
 423
 424   for (i = 0; i < 2; ++i)
 425     if (stack_align_check[i] == 0)
 426       {
 427         printf ("stack alignment check %d not run\n", i);
 428         total_error |= 1;
 429       }
 430     else if (stack_align_check[i] != 1)
 431       {
 432         printf ("stack insufficiently aligned in check %d\n", i);
 433         total_error |= 1;
 434       }
 435
 436   return total_error;
 437 }
 438
 439 #define TEST_FUNCTION do_test ()
 440 #include "../test-skeleton.c"