tests/test-tsearch.c

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