tests/test-tsearch.c

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