misc/tst-tsearch.c

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