Back to index

glibc  2.9
tst-tsearch.c
Go to the documentation of this file.
00001 /* Test program for tsearch et al.
00002    Copyright (C) 1997, 2000, 2001, 2003 Free Software Foundation, Inc.
00003    This file is part of the GNU C Library.
00004 
00005    The GNU C Library is free software; you can redistribute it and/or
00006    modify it under the terms of the GNU Lesser General Public
00007    License as published by the Free Software Foundation; either
00008    version 2.1 of the License, or (at your option) any later version.
00009 
00010    The GNU C Library is distributed in the hope that it will be useful,
00011    but WITHOUT ANY WARRANTY; without even the implied warranty of
00012    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00013    Lesser General Public License for more details.
00014 
00015    You should have received a copy of the GNU Lesser General Public
00016    License along with the GNU C Library; if not, write to the Free
00017    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
00018    02111-1307 USA.  */
00019 
00020 #ifndef _GNU_SOURCE
00021 # define _GNU_SOURCE 1
00022 #endif
00023 
00024 #include <stdio.h>
00025 #include <stdlib.h>
00026 #include <string.h>
00027 #include <search.h>
00028 #include <tst-stack-align.h>
00029 
00030 #define SEED 0
00031 #define BALANCED 1
00032 #define PASSES 100
00033 
00034 #if BALANCED
00035 #include <math.h>
00036 #define SIZE 1000
00037 #else
00038 #define SIZE 100
00039 #endif
00040 
00041 enum order
00042 {
00043   ascending,
00044   descending,
00045   randomorder
00046 };
00047 
00048 enum action
00049 {
00050   build,
00051   build_and_del,
00052   delete,
00053   find
00054 };
00055 
00056 /* Set to 1 if a test is flunked.  */
00057 static int error = 0;
00058 
00059 /* The keys we add to the tree.  */
00060 static int x[SIZE];
00061 
00062 /* Pointers into the key array, possibly permutated, to define an order
00063    for insertion/removal.  */
00064 static int y[SIZE];
00065 
00066 /* Flags set for each element visited during a tree walk.  */
00067 static int z[SIZE];
00068 
00069 /* Depths for all the elements, to check that the depth is constant for
00070    all three visits.  */
00071 static int depths[SIZE];
00072 
00073 /* Maximum depth during a tree walk.  */
00074 static int max_depth;
00075 
00076 static int stack_align_check[2];
00077 
00078 /* Compare two keys.  */
00079 static int
00080 cmp_fn (const void *a, const void *b)
00081 {
00082   if (!stack_align_check[0])
00083     stack_align_check[0] = TEST_STACK_ALIGN () ? -1 : 1;
00084   return *(const int *) a - *(const int *) b;
00085 }
00086 
00087 /* Permute an array of integers.  */
00088 static void
00089 memfry (int *string)
00090 {
00091   int i;
00092 
00093   for (i = 0; i < SIZE; ++i)
00094     {
00095       int32_t j;
00096       int c;
00097 
00098       j = random () % SIZE;
00099 
00100       c = string[i];
00101       string[i] = string[j];
00102       string[j] = c;
00103     }
00104 }
00105 
00106 static void
00107 walk_action (const void *nodep, const VISIT which, const int depth)
00108 {
00109   int key = **(int **) nodep;
00110 
00111   if (!stack_align_check[1])
00112     stack_align_check[1] = TEST_STACK_ALIGN () ? -1 : 1;
00113 
00114   if (depth > max_depth)
00115     max_depth = depth;
00116   if (which == leaf || which == preorder)
00117     {
00118       ++z[key];
00119       depths[key] = depth;
00120     }
00121   else
00122     {
00123       if (depths[key] != depth)
00124        {
00125          fputs ("Depth for one element is not constant during tree walk.\n",
00126                stdout);
00127        }
00128     }
00129 }
00130 
00131 static void
00132 walk_tree (void *root, int expected_count)
00133 {
00134   int i;
00135 
00136   memset (z, 0, sizeof z);
00137   max_depth = 0;
00138 
00139   twalk (root, walk_action);
00140   for (i = 0; i < expected_count; ++i)
00141     if (z[i] != 1)
00142       {
00143        fputs ("Node was not visited.\n", stdout);
00144        error = 1;
00145       }
00146 
00147 #if BALANCED
00148   if (max_depth > log (expected_count) * 2 + 2)
00149 #else
00150   if (max_depth > expected_count)
00151 #endif
00152     {
00153       fputs ("Depth too large during tree walk.\n", stdout);
00154       error = 1;
00155     }
00156 }
00157 
00158 /* Perform an operation on a tree.  */
00159 static void
00160 mangle_tree (enum order how, enum action what, void **root, int lag)
00161 {
00162   int i;
00163 
00164   if (how == randomorder)
00165     {
00166       for (i = 0; i < SIZE; ++i)
00167        y[i] = i;
00168       memfry (y);
00169     }
00170 
00171   for (i = 0; i < SIZE + lag; ++i)
00172     {
00173       void *elem;
00174       int j, k;
00175 
00176       switch (how)
00177        {
00178        case randomorder:
00179          if (i >= lag)
00180            k = y[i - lag];
00181          else
00182            /* Ensure that the array index is within bounds.  */
00183            k = y[(SIZE - i - 1 + lag) % SIZE];
00184          j = y[i % SIZE];
00185          break;
00186 
00187        case ascending:
00188          k = i - lag;
00189          j = i;
00190          break;
00191 
00192        case descending:
00193          k = SIZE - i - 1 + lag;
00194          j = SIZE - i - 1;
00195          break;
00196 
00197        default:
00198          /* This never should happen, but gcc isn't smart enough to
00199             recognize it.  */
00200          abort ();
00201        }
00202 
00203       switch (what)
00204        {
00205        case build_and_del:
00206        case build:
00207          if (i < SIZE)
00208            {
00209              if (tfind (x + j, (void *const *) root, cmp_fn) != NULL)
00210               {
00211                 fputs ("Found element which is not in tree yet.\n", stdout);
00212                 error = 1;
00213               }
00214              elem = tsearch (x + j, root, cmp_fn);
00215              if (elem == 0
00216                 || tfind (x + j, (void *const *) root, cmp_fn) == NULL)
00217               {
00218                 fputs ("Couldn't find element after it was added.\n",
00219                       stdout);
00220                 error = 1;
00221               }
00222            }
00223 
00224          if (what == build || i < lag)
00225            break;
00226 
00227          j = k;
00228          /* fall through */
00229 
00230        case delete:
00231          elem = tfind (x + j, (void *const *) root, cmp_fn);
00232          if (elem == NULL || tdelete (x + j, root, cmp_fn) == NULL)
00233            {
00234              fputs ("Error deleting element.\n", stdout);
00235              error = 1;
00236            }
00237          break;
00238 
00239        case find:
00240          if (tfind (x + j, (void *const *) root, cmp_fn) == NULL)
00241            {
00242              fputs ("Couldn't find element after it was added.\n", stdout);
00243              error = 1;
00244            }
00245          break;
00246 
00247        }
00248     }
00249 }
00250 
00251 
00252 int
00253 main (int argc, char **argv)
00254 {
00255   int total_error = 0;
00256   static char state[8] = { 1, 2, 3, 4, 5, 6, 7, 8 };
00257   void *root = NULL;
00258   int i, j;
00259 
00260   initstate (SEED, state, 8);
00261 
00262   for (i = 0; i < SIZE; ++i)
00263     x[i] = i;
00264 
00265   /* Do this loop several times to get different permutations for the
00266      random case.  */
00267   fputs ("Series I\n", stdout);
00268   for (i = 0; i < PASSES; ++i)
00269     {
00270       fprintf (stdout, "Pass %d... ", i + 1);
00271       fflush (stdout);
00272       error = 0;
00273 
00274       mangle_tree (ascending, build, &root, 0);
00275       mangle_tree (ascending, find, &root, 0);
00276       mangle_tree (descending, find, &root, 0);
00277       mangle_tree (randomorder, find, &root, 0);
00278       walk_tree (root, SIZE);
00279       mangle_tree (ascending, delete, &root, 0);
00280 
00281       mangle_tree (ascending, build, &root, 0);
00282       walk_tree (root, SIZE);
00283       mangle_tree (descending, delete, &root, 0);
00284 
00285       mangle_tree (ascending, build, &root, 0);
00286       walk_tree (root, SIZE);
00287       mangle_tree (randomorder, delete, &root, 0);
00288 
00289       mangle_tree (descending, build, &root, 0);
00290       mangle_tree (ascending, find, &root, 0);
00291       mangle_tree (descending, find, &root, 0);
00292       mangle_tree (randomorder, find, &root, 0);
00293       walk_tree (root, SIZE);
00294       mangle_tree (descending, delete, &root, 0);
00295 
00296       mangle_tree (descending, build, &root, 0);
00297       walk_tree (root, SIZE);
00298       mangle_tree (descending, delete, &root, 0);
00299 
00300       mangle_tree (descending, build, &root, 0);
00301       walk_tree (root, SIZE);
00302       mangle_tree (randomorder, delete, &root, 0);
00303 
00304       mangle_tree (randomorder, build, &root, 0);
00305       mangle_tree (ascending, find, &root, 0);
00306       mangle_tree (descending, find, &root, 0);
00307       mangle_tree (randomorder, find, &root, 0);
00308       walk_tree (root, SIZE);
00309       mangle_tree (randomorder, delete, &root, 0);
00310 
00311       for (j = 1; j < SIZE; j *= 2)
00312        {
00313          mangle_tree (randomorder, build_and_del, &root, j);
00314        }
00315 
00316       fputs (error ? " failed!\n" : " ok.\n", stdout);
00317       total_error |= error;
00318     }
00319 
00320   fputs ("Series II\n", stdout);
00321   for (i = 1; i < SIZE; i *= 2)
00322     {
00323       fprintf (stdout, "For size %d... ", i);
00324       fflush (stdout);
00325       error = 0;
00326 
00327       mangle_tree (ascending, build_and_del, &root, i);
00328       mangle_tree (descending, build_and_del, &root, i);
00329       mangle_tree (ascending, build_and_del, &root, i);
00330       mangle_tree (descending, build_and_del, &root, i);
00331       mangle_tree (ascending, build_and_del, &root, i);
00332       mangle_tree (descending, build_and_del, &root, i);
00333       mangle_tree (ascending, build_and_del, &root, i);
00334       mangle_tree (descending, build_and_del, &root, i);
00335 
00336       fputs (error ? " failed!\n" : " ok.\n", stdout);
00337       total_error |= error;
00338     }
00339 
00340   for (i = 0; i < 2; ++i)
00341     if (stack_align_check[i] == 0)
00342       {
00343         printf ("stack alignment check %d not run\n", i);
00344         total_error |= 1;
00345       }
00346     else if (stack_align_check[i] != 1)
00347       {
00348         printf ("stack insufficiently aligned in check %d\n", i);
00349         total_error |= 1;
00350       }
00351 
00352   return total_error;
00353 }