misc/tst-tsearch.c

   1 /* Test program for tsearch et al.
   2    Copyright (C) 1997, 2000 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 Library General Public License as
   7    published by the Free Software Foundation; either version 2 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    Library General Public License for more details.
  14
  15    You should have received a copy of the GNU Library General Public
  16    License along with the GNU C Library; see the file COPYING.LIB.  If not,
  17    write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18    Boston, MA 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             k = y[SIZE - i - 1 + lag];
 175           j = y[i];
 176           break;
 177
 178         case ascending:
 179           k = i - lag;
 180           j = i;
 181           break;
 182
 183         case descending:
 184           k = SIZE - i - 1 + lag;
 185           j = SIZE - i - 1;
 186           break;
 187
 188         default:
 189           /* This never should happen, but gcc isn't smart enough to
 190              recognize it.  */
 191           abort ();
 192         }
 193
 194       switch (what)
 195         {
 196         case build_and_del:
 197         case build:
 198           if (i < SIZE)
 199             {
 200               if (tfind (x + j, (void *const *) root, cmp_fn) != NULL)
 201                 {
 202                   fputs ("Found element which is not in tree yet.\n", stdout);
 203                   error = 1;
 204                 }
 205               elem = tsearch (x + j, root, cmp_fn);
 206               if (elem == 0
 207                   || tfind (x + j, (void *const *) root, cmp_fn) == NULL)
 208                 {
 209                   fputs ("Couldn't find element after it was added.\n",
 210                          stdout);
 211                   error = 1;
 212                 }
 213             }
 214
 215           if (what == build || i < lag)
 216             break;
 217
 218           j = k;
 219           /* fall through */
 220
 221         case delete:
 222           elem = tfind (x + j, (void *const *) root, cmp_fn);
 223           if (elem == NULL || tdelete (x + j, root, cmp_fn) == NULL)
 224             {
 225               fputs ("Error deleting element.\n", stdout);
 226               error = 1;
 227             }
 228           break;
 229
 230         case find:
 231           if (tfind (x + j, (void *const *) root, cmp_fn) == NULL)
 232             {
 233               fputs ("Couldn't find element after it was added.\n", stdout);
 234               error = 1;
 235             }
 236           break;
 237
 238         }
 239     }
 240 }
 241
 242
 243 int
 244 main (int argc, char **argv)
 245 {
 246   int total_error = 0;
 247   static char state[8] = { 1, 2, 3, 4, 5, 6, 7, 8 };
 248   void *root = NULL;
 249   int i, j;
 250
 251   initstate (SEED, state, 8);
 252
 253   for (i = 0; i < SIZE; ++i)
 254     x[i] = i;
 255
 256   /* Do this loop several times to get different permutations for the
 257      random case.  */
 258   fputs ("Series I\n", stdout);
 259   for (i = 0; i < PASSES; ++i)
 260     {
 261       fprintf (stdout, "Pass %d... ", i + 1);
 262       fflush (stdout);
 263       error = 0;
 264
 265       mangle_tree (ascending, build, &root, 0);
 266       mangle_tree (ascending, find, &root, 0);
 267       mangle_tree (descending, find, &root, 0);
 268       mangle_tree (randomorder, find, &root, 0);
 269       walk_tree (root, SIZE);
 270       mangle_tree (ascending, delete, &root, 0);
 271
 272       mangle_tree (ascending, build, &root, 0);
 273       walk_tree (root, SIZE);
 274       mangle_tree (descending, delete, &root, 0);
 275
 276       mangle_tree (ascending, build, &root, 0);
 277       walk_tree (root, SIZE);
 278       mangle_tree (randomorder, delete, &root, 0);
 279
 280       mangle_tree (descending, build, &root, 0);
 281       mangle_tree (ascending, find, &root, 0);
 282       mangle_tree (descending, find, &root, 0);
 283       mangle_tree (randomorder, find, &root, 0);
 284       walk_tree (root, SIZE);
 285       mangle_tree (descending, delete, &root, 0);
 286
 287       mangle_tree (descending, build, &root, 0);
 288       walk_tree (root, SIZE);
 289       mangle_tree (descending, delete, &root, 0);
 290
 291       mangle_tree (descending, build, &root, 0);
 292       walk_tree (root, SIZE);
 293       mangle_tree (randomorder, delete, &root, 0);
 294
 295       mangle_tree (randomorder, build, &root, 0);
 296       mangle_tree (ascending, find, &root, 0);
 297       mangle_tree (descending, find, &root, 0);
 298       mangle_tree (randomorder, find, &root, 0);
 299       walk_tree (root, SIZE);
 300       mangle_tree (randomorder, delete, &root, 0);
 301
 302       for (j = 1; j < SIZE; j *= 2)
 303         {
 304           mangle_tree (randomorder, build_and_del, &root, j);
 305         }
 306
 307       fputs (error ? " failed!\n" : " ok.\n", stdout);
 308       total_error |= error;
 309     }
 310
 311   fputs ("Series II\n", stdout);
 312   for (i = 1; i < SIZE; i *= 2)
 313     {
 314       fprintf (stdout, "For size %d... ", i);
 315       fflush (stdout);
 316       error = 0;
 317
 318       mangle_tree (ascending, build_and_del, &root, i);
 319       mangle_tree (descending, build_and_del, &root, i);
 320       mangle_tree (ascending, build_and_del, &root, i);
 321       mangle_tree (descending, build_and_del, &root, i);
 322       mangle_tree (ascending, build_and_del, &root, i);
 323       mangle_tree (descending, build_and_del, &root, i);
 324       mangle_tree (ascending, build_and_del, &root, i);
 325       mangle_tree (descending, build_and_del, &root, i);
 326
 327       fputs (error ? " failed!\n" : " ok.\n", stdout);
 328       total_error |= error;
 329     }
 330
 331   return total_error;
 332 }