misc/tst-tsearch.c

   1 /* Test program for tsearch et al.
   2    Copyright (C) 1997-2015 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
  29 #define SEED 0
  30 #define BALANCED 1
  31 #define PASSES 100
  32
  33 #if BALANCED
  34 #include <math.h>
  35 #define SIZE 1000
  36 #else
  37 #define SIZE 100
  38 #endif
  39
  40 enum order
  41 {
  42   ascending,
  43   descending,
  44   randomorder
  45 };
  46
  47 enum action
  48 {
  49   build,
  50   build_and_del,
  51   delete,
  52   find
  53 };
  54
  55 /* Set to 1 if a test is flunked.  */
  56 static int error = 0;
  57
  58 /* The keys we add to the tree.  */
  59 static int x[SIZE];
  60
  61 /* Pointers into the key array, possibly permutated, to define an order
  62    for insertion/removal.  */
  63 static int y[SIZE];
  64
  65 /* Flags set for each element visited during a tree walk.  */
  66 static int z[SIZE];
  67
  68 /* Depths for all the elements, to check that the depth is constant for
  69    all three visits.  */
  70 static int depths[SIZE];
  71
  72 /* Maximum depth during a tree walk.  */
  73 static int max_depth;
  74
  75 static int stack_align_check[2];
  76
  77 /* Compare two keys.  */
  78 static int
  79 cmp_fn (const void *a, const void *b)
  80 {
  81   if (!stack_align_check[0])
  82     stack_align_check[0] = TEST_STACK_ALIGN () ? -1 : 1;
  83   return *(const int *) a - *(const int *) b;
  84 }
  85
  86 /* Permute an array of integers.  */
  87 static void
  88 memfry (int *string)
  89 {
  90   int i;
  91
  92   for (i = 0; i < SIZE; ++i)
  93     {
  94       int32_t j;
  95       int c;
  96
  97       j = random () % SIZE;
  98
  99       c = string[i];
 100       string[i] = string[j];
 101       string[j] = c;
 102     }
 103 }
 104
 105 static void
 106 walk_action (const void *nodep, const VISIT which, const int depth)
 107 {
 108   int key = **(int **) nodep;
 109
 110   if (!stack_align_check[1])
 111     stack_align_check[1] = TEST_STACK_ALIGN () ? -1 : 1;
 112
 113   if (depth > max_depth)
 114     max_depth = depth;
 115   if (which == leaf || which == preorder)
 116     {
 117       ++z[key];
 118       depths[key] = depth;
 119     }
 120   else
 121     {
 122       if (depths[key] != depth)
 123         {
 124           fputs ("Depth for one element is not constant during tree walk.\n",
 125                  stdout);
 126         }
 127     }
 128 }
 129
 130 static void
 131 walk_tree (void *root, int expected_count)
 132 {
 133   int i;
 134
 135   memset (z, 0, sizeof z);
 136   max_depth = 0;
 137
 138   twalk (root, walk_action);
 139   for (i = 0; i < expected_count; ++i)
 140     if (z[i] != 1)
 141       {
 142         fputs ("Node was not visited.\n", stdout);
 143         error = 1;
 144       }
 145
 146 #if BALANCED
 147   if (max_depth > log (expected_count) * 2 + 2)
 148 #else
 149   if (max_depth > expected_count)
 150 #endif
 151     {
 152       fputs ("Depth too large during tree walk.\n", stdout);
 153       error = 1;
 154     }
 155 }
 156
 157 /* Perform an operation on a tree.  */
 158 static void
 159 mangle_tree (enum order how, enum action what, void **root, int lag)
 160 {
 161   int i;
 162
 163   if (how == randomorder)
 164     {
 165       for (i = 0; i < SIZE; ++i)
 166         y[i] = i;
 167       memfry (y);
 168     }
 169
 170   for (i = 0; i < SIZE + lag; ++i)
 171     {
 172       void *elem;
 173       int j, k;
 174
 175       switch (how)
 176         {
 177         case randomorder:
 178           if (i >= lag)
 179             k = y[i - lag];
 180           else
 181             /* Ensure that the array index is within bounds.  */
 182             k = y[(SIZE - i - 1 + lag) % SIZE];
 183           j = y[i % SIZE];
 184           break;
 185
 186         case ascending:
 187           k = i - lag;
 188           j = i;
 189           break;
 190
 191         case descending:
 192           k = SIZE - i - 1 + lag;
 193           j = SIZE - i - 1;
 194           break;
 195
 196         default:
 197           /* This never should happen, but gcc isn't smart enough to
 198              recognize it.  */
 199           abort ();
 200         }
 201
 202       switch (what)
 203         {
 204         case build_and_del:
 205         case build:
 206           if (i < SIZE)
 207             {
 208               if (tfind (x + j, (void *const *) root, cmp_fn) != NULL)
 209                 {
 210                   fputs ("Found element which is not in tree yet.\n", stdout);
 211                   error = 1;
 212                 }
 213               elem = tsearch (x + j, root, cmp_fn);
 214               if (elem == 0
 215                   || tfind (x + j, (void *const *) root, cmp_fn) == NULL)
 216                 {
 217                   fputs ("Couldn't find element after it was added.\n",
 218                          stdout);
 219                   error = 1;
 220                 }
 221             }
 222
 223           if (what == build || i < lag)
 224             break;
 225
 226           j = k;
 227           /* fall through */
 228
 229         case delete:
 230           elem = tfind (x + j, (void *const *) root, cmp_fn);
 231           if (elem == NULL || tdelete (x + j, root, cmp_fn) == NULL)
 232             {
 233               fputs ("Error deleting element.\n", stdout);
 234               error = 1;
 235             }
 236           break;
 237
 238         case find:
 239           if (tfind (x + j, (void *const *) root, cmp_fn) == NULL)
 240             {
 241               fputs ("Couldn't find element after it was added.\n", stdout);
 242               error = 1;
 243             }
 244           break;
 245
 246         }
 247     }
 248 }
 249
 250
 251 int
 252 main (int argc, char **argv)
 253 {
 254   int total_error = 0;
 255   static char state[8] = { 1, 2, 3, 4, 5, 6, 7, 8 };
 256   void *root = NULL;
 257   int i, j;
 258
 259   initstate (SEED, state, 8);
 260
 261   for (i = 0; i < SIZE; ++i)
 262     x[i] = i;
 263
 264   /* Do this loop several times to get different permutations for the
 265      random case.  */
 266   fputs ("Series I\n", stdout);
 267   for (i = 0; i < PASSES; ++i)
 268     {
 269       fprintf (stdout, "Pass %d... ", i + 1);
 270       fflush (stdout);
 271       error = 0;
 272
 273       mangle_tree (ascending, build, &root, 0);
 274       mangle_tree (ascending, find, &root, 0);
 275       mangle_tree (descending, find, &root, 0);
 276       mangle_tree (randomorder, find, &root, 0);
 277       walk_tree (root, SIZE);
 278       mangle_tree (ascending, delete, &root, 0);
 279
 280       mangle_tree (ascending, build, &root, 0);
 281       walk_tree (root, SIZE);
 282       mangle_tree (descending, delete, &root, 0);
 283
 284       mangle_tree (ascending, build, &root, 0);
 285       walk_tree (root, SIZE);
 286       mangle_tree (randomorder, delete, &root, 0);
 287
 288       mangle_tree (descending, build, &root, 0);
 289       mangle_tree (ascending, find, &root, 0);
 290       mangle_tree (descending, find, &root, 0);
 291       mangle_tree (randomorder, find, &root, 0);
 292       walk_tree (root, SIZE);
 293       mangle_tree (descending, delete, &root, 0);
 294
 295       mangle_tree (descending, build, &root, 0);
 296       walk_tree (root, SIZE);
 297       mangle_tree (descending, delete, &root, 0);
 298
 299       mangle_tree (descending, build, &root, 0);
 300       walk_tree (root, SIZE);
 301       mangle_tree (randomorder, delete, &root, 0);
 302
 303       mangle_tree (randomorder, build, &root, 0);
 304       mangle_tree (ascending, find, &root, 0);
 305       mangle_tree (descending, find, &root, 0);
 306       mangle_tree (randomorder, find, &root, 0);
 307       walk_tree (root, SIZE);
 308       mangle_tree (randomorder, delete, &root, 0);
 309
 310       for (j = 1; j < SIZE; j *= 2)
 311         {
 312           mangle_tree (randomorder, build_and_del, &root, j);
 313         }
 314
 315       fputs (error ? " failed!\n" : " ok.\n", stdout);
 316       total_error |= error;
 317     }
 318
 319   fputs ("Series II\n", stdout);
 320   for (i = 1; i < SIZE; i *= 2)
 321     {
 322       fprintf (stdout, "For size %d... ", i);
 323       fflush (stdout);
 324       error = 0;
 325
 326       mangle_tree (ascending, build_and_del, &root, i);
 327       mangle_tree (descending, build_and_del, &root, i);
 328       mangle_tree (ascending, build_and_del, &root, i);
 329       mangle_tree (descending, build_and_del, &root, i);
 330       mangle_tree (ascending, build_and_del, &root, i);
 331       mangle_tree (descending, build_and_del, &root, i);
 332       mangle_tree (ascending, build_and_del, &root, i);
 333       mangle_tree (descending, build_and_del, &root, i);
 334
 335       fputs (error ? " failed!\n" : " ok.\n", stdout);
 336       total_error |= error;
 337     }
 338
 339   for (i = 0; i < 2; ++i)
 340     if (stack_align_check[i] == 0)
 341       {
 342         printf ("stack alignment check %d not run\n", i);
 343         total_error |= 1;
 344       }
 345     else if (stack_align_check[i] != 1)
 346       {
 347         printf ("stack insufficiently aligned in check %d\n", i);
 348         total_error |= 1;
 349       }
 350
 351   return total_error;
 352 }