tests/test-tsearch.c

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