Back to index

glibc  2.9
Defines | Enumerations | Functions | Variables
tst-tsearch.c File Reference
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <search.h>
#include <tst-stack-align.h>
#include <math.h>

Go to the source code of this file.

Defines

#define _GNU_SOURCE   1
#define SEED   0
#define BALANCED   1
#define PASSES   100
#define SIZE   1000

Enumerations

enum  order { ascending, descending, randomorder }
enum  action { build, build_and_del, delete, find }

Functions

static int cmp_fn (const void *a, const void *b)
static void memfry (int *string)
static void walk_action (const void *nodep, const VISIT which, const int depth)
static void walk_tree (void *root, int expected_count)
static void mangle_tree (enum order how, enum action what, void **root, int lag)
int main (int argc, char **argv)

Variables

static int error = 0
static int x [SIZE]
static int y [SIZE]
static int z [SIZE]
static int depths [SIZE]
static int max_depth
static int stack_align_check [2]

Define Documentation

#define _GNU_SOURCE   1

Definition at line 21 of file tst-tsearch.c.

#define BALANCED   1

Definition at line 31 of file tst-tsearch.c.

#define PASSES   100

Definition at line 32 of file tst-tsearch.c.

#define SEED   0

Definition at line 30 of file tst-tsearch.c.

#define SIZE   1000

Definition at line 36 of file tst-tsearch.c.


Enumeration Type Documentation

enum action
Enumerator:
build 
build_and_del 
delete 
find 

Definition at line 48 of file tst-tsearch.c.

{
  build,
  build_and_del,
  delete,
  find
};
enum order
Enumerator:
ascending 
descending 
randomorder 

Definition at line 41 of file tst-tsearch.c.


Function Documentation

static int cmp_fn ( const void *  a,
const void *  b 
) [static]

Definition at line 80 of file tst-tsearch.c.

{
  if (!stack_align_check[0])
    stack_align_check[0] = TEST_STACK_ALIGN () ? -1 : 1;
  return *(const int *) a - *(const int *) b;
}

Here is the caller graph for this function:

int main ( int  argc,
char **  argv 
)

Definition at line 253 of file tst-tsearch.c.

{
  int total_error = 0;
  static char state[8] = { 1, 2, 3, 4, 5, 6, 7, 8 };
  void *root = NULL;
  int i, j;

  initstate (SEED, state, 8);

  for (i = 0; i < SIZE; ++i)
    x[i] = i;

  /* Do this loop several times to get different permutations for the
     random case.  */
  fputs ("Series I\n", stdout);
  for (i = 0; i < PASSES; ++i)
    {
      fprintf (stdout, "Pass %d... ", i + 1);
      fflush (stdout);
      error = 0;

      mangle_tree (ascending, build, &root, 0);
      mangle_tree (ascending, find, &root, 0);
      mangle_tree (descending, find, &root, 0);
      mangle_tree (randomorder, find, &root, 0);
      walk_tree (root, SIZE);
      mangle_tree (ascending, delete, &root, 0);

      mangle_tree (ascending, build, &root, 0);
      walk_tree (root, SIZE);
      mangle_tree (descending, delete, &root, 0);

      mangle_tree (ascending, build, &root, 0);
      walk_tree (root, SIZE);
      mangle_tree (randomorder, delete, &root, 0);

      mangle_tree (descending, build, &root, 0);
      mangle_tree (ascending, find, &root, 0);
      mangle_tree (descending, find, &root, 0);
      mangle_tree (randomorder, find, &root, 0);
      walk_tree (root, SIZE);
      mangle_tree (descending, delete, &root, 0);

      mangle_tree (descending, build, &root, 0);
      walk_tree (root, SIZE);
      mangle_tree (descending, delete, &root, 0);

      mangle_tree (descending, build, &root, 0);
      walk_tree (root, SIZE);
      mangle_tree (randomorder, delete, &root, 0);

      mangle_tree (randomorder, build, &root, 0);
      mangle_tree (ascending, find, &root, 0);
      mangle_tree (descending, find, &root, 0);
      mangle_tree (randomorder, find, &root, 0);
      walk_tree (root, SIZE);
      mangle_tree (randomorder, delete, &root, 0);

      for (j = 1; j < SIZE; j *= 2)
       {
         mangle_tree (randomorder, build_and_del, &root, j);
       }

      fputs (error ? " failed!\n" : " ok.\n", stdout);
      total_error |= error;
    }

  fputs ("Series II\n", stdout);
  for (i = 1; i < SIZE; i *= 2)
    {
      fprintf (stdout, "For size %d... ", i);
      fflush (stdout);
      error = 0;

      mangle_tree (ascending, build_and_del, &root, i);
      mangle_tree (descending, build_and_del, &root, i);
      mangle_tree (ascending, build_and_del, &root, i);
      mangle_tree (descending, build_and_del, &root, i);
      mangle_tree (ascending, build_and_del, &root, i);
      mangle_tree (descending, build_and_del, &root, i);
      mangle_tree (ascending, build_and_del, &root, i);
      mangle_tree (descending, build_and_del, &root, i);

      fputs (error ? " failed!\n" : " ok.\n", stdout);
      total_error |= error;
    }

  for (i = 0; i < 2; ++i)
    if (stack_align_check[i] == 0)
      {
        printf ("stack alignment check %d not run\n", i);
        total_error |= 1;
      }
    else if (stack_align_check[i] != 1)
      {
        printf ("stack insufficiently aligned in check %d\n", i);
        total_error |= 1;
      }

  return total_error;
}

Here is the call graph for this function:

static void mangle_tree ( enum order  how,
enum action  what,
void **  root,
int  lag 
) [static]

Definition at line 160 of file tst-tsearch.c.

{
  int i;

  if (how == randomorder)
    {
      for (i = 0; i < SIZE; ++i)
       y[i] = i;
      memfry (y);
    }

  for (i = 0; i < SIZE + lag; ++i)
    {
      void *elem;
      int j, k;

      switch (how)
       {
       case randomorder:
         if (i >= lag)
           k = y[i - lag];
         else
           /* Ensure that the array index is within bounds.  */
           k = y[(SIZE - i - 1 + lag) % SIZE];
         j = y[i % SIZE];
         break;

       case ascending:
         k = i - lag;
         j = i;
         break;

       case descending:
         k = SIZE - i - 1 + lag;
         j = SIZE - i - 1;
         break;

       default:
         /* This never should happen, but gcc isn't smart enough to
            recognize it.  */
         abort ();
       }

      switch (what)
       {
       case build_and_del:
       case build:
         if (i < SIZE)
           {
             if (tfind (x + j, (void *const *) root, cmp_fn) != NULL)
              {
                fputs ("Found element which is not in tree yet.\n", stdout);
                error = 1;
              }
             elem = tsearch (x + j, root, cmp_fn);
             if (elem == 0
                || tfind (x + j, (void *const *) root, cmp_fn) == NULL)
              {
                fputs ("Couldn't find element after it was added.\n",
                      stdout);
                error = 1;
              }
           }

         if (what == build || i < lag)
           break;

         j = k;
         /* fall through */

       case delete:
         elem = tfind (x + j, (void *const *) root, cmp_fn);
         if (elem == NULL || tdelete (x + j, root, cmp_fn) == NULL)
           {
             fputs ("Error deleting element.\n", stdout);
             error = 1;
           }
         break;

       case find:
         if (tfind (x + j, (void *const *) root, cmp_fn) == NULL)
           {
             fputs ("Couldn't find element after it was added.\n", stdout);
             error = 1;
           }
         break;

       }
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void memfry ( int string) [static]

Definition at line 89 of file tst-tsearch.c.

{
  int i;

  for (i = 0; i < SIZE; ++i)
    {
      int32_t j;
      int c;

      j = random () % SIZE;

      c = string[i];
      string[i] = string[j];
      string[j] = c;
    }
}

Here is the caller graph for this function:

static void walk_action ( const void *  nodep,
const VISIT  which,
const int  depth 
) [static]

Definition at line 107 of file tst-tsearch.c.

{
  int key = **(int **) nodep;

  if (!stack_align_check[1])
    stack_align_check[1] = TEST_STACK_ALIGN () ? -1 : 1;

  if (depth > max_depth)
    max_depth = depth;
  if (which == leaf || which == preorder)
    {
      ++z[key];
      depths[key] = depth;
    }
  else
    {
      if (depths[key] != depth)
       {
         fputs ("Depth for one element is not constant during tree walk.\n",
               stdout);
       }
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void walk_tree ( void *  root,
int  expected_count 
) [static]

Definition at line 132 of file tst-tsearch.c.

{
  int i;

  memset (z, 0, sizeof z);
  max_depth = 0;

  twalk (root, walk_action);
  for (i = 0; i < expected_count; ++i)
    if (z[i] != 1)
      {
       fputs ("Node was not visited.\n", stdout);
       error = 1;
      }

#if BALANCED
  if (max_depth > log (expected_count) * 2 + 2)
#else
  if (max_depth > expected_count)
#endif
    {
      fputs ("Depth too large during tree walk.\n", stdout);
      error = 1;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:


Variable Documentation

int depths[SIZE] [static]

Definition at line 71 of file tst-tsearch.c.

int error = 0 [static]

Definition at line 57 of file tst-tsearch.c.

int max_depth [static]

Definition at line 74 of file tst-tsearch.c.

int stack_align_check[2] [static]

Definition at line 76 of file tst-tsearch.c.

int x[SIZE] [static]

Definition at line 60 of file tst-tsearch.c.

int y[SIZE] [static]

Definition at line 64 of file tst-tsearch.c.

int z[SIZE] [static]

Definition at line 67 of file tst-tsearch.c.