tests/test-tsearch.c

   1 /* Test program for tsearch et al.
   2    Copyright (C) 1997, 2000-2001, 2007-2008 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 License as
   7    published by the Free Software Foundation; either version 3 of the
   8    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 License
  16    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
  17
  18 #include <config.h>
  19
  20 #include <search.h>
  21
  22 #include <stdint.h>
  23 #include <stdio.h>
  24 #include <stdlib.h>
  25 #include <string.h>
  26
  27 #define SEED 0
  28 #if HAVE_TSEARCH
  29 /* The system's tsearch() is not expected to keep the tree balanced.  */
  30 # define BALANCED 0
  31 #else
  32 /* The gnulib replacement tsearch() should keep the tree balanced.  */
  33 # define BALANCED 1
  34 #endif
  35 #define PASSES 100
  36
  37 #if BALANCED
  38 #include <math.h>
  39 #define SIZE 1000
  40 #else
  41 #define SIZE 100
  42 #endif
  43
  44 #undef random
  45 #define random() (int) ((unsigned int) rand () >> 3)
  46
  47 enum order
  48 {
  49   ascending,
  50   descending,
  51   randomorder
  52 };
  53
  54 enum action
  55 {
  56   build,
  57   build_and_del,
  58   delete,
  59   find
  60 };
  61
  62 /* Set to 1 if a test is flunked.  */
  63 static int error = 0;
  64
  65 /* The keys we add to the tree.  */
  66 static int x[SIZE];
  67
  68 /* Pointers into the key array, possibly permutated, to define an order
  69    for insertion/removal.  */
  70 static int y[SIZE];
  71
  72 /* Flags set for each element visited during a tree walk.  */
  73 static int z[SIZE];
  74
  75 /* Depths for all the elements, to check that the depth is constant for
  76    all three visits.  */
  77 static int depths[SIZE];
  78
  79 /* Maximum depth during a tree walk.  */
  80 static int max_depth;
  81
  82 /* Compare two keys.  */
  83 static int
  84 cmp_fn (const void *a, const void *b)
  85 {
  86   return *(const int *) a - *(const int *) b;
  87 }
  88
  89 /* Permute an array of integers.  */
  90 static void
  91 memfry (int *string)
  92 {
  93   int i;
  94
  95   for (i = 0; i < SIZE; ++i)
  96     {
  97       int32_t j;
  98       int c;
  99
 100       j = random () % SIZE;
 101
 102       c = string[i];
 103       string[i] = string[j];
 104       string[j] = c;
 105     }
 106 }
 107
 108 static void
 109 walk_action (const void *nodep, const VISIT which, const int depth)
 110 {
 111   int key = **(int **) nodep;
 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 #if HAVE_INITSTATE
 260   initstate (SEED, state, 8);
 261 #endif
 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 }