misc/tst-tsearch.c

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