Logo Search packages:      
Sourcecode: coreutils version File versions  Download package

test-hash.c

/* -*- buffer-read-only: t -*- vi: set ro: */
/* DO NOT EDIT! GENERATED AUTOMATICALLY! */
#line 1
/*
 * Copyright (C) 2009 Free Software Foundation
 * Written by Jim Meyering
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.  */

#include <config.h>

#include "hash.h"
#include "hash-pjw.h"
#include "inttostr.h"
#include "xalloc.h"

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <unistd.h>

#define STREQ(a, b) (strcmp (a, b) == 0)
#define ARRAY_CARDINALITY(Array) (sizeof (Array) / sizeof *(Array))

#define ASSERT(expr) \
  do                                                       \
    {                                                      \
      if (!(expr))                                               \
      {                                                    \
        fprintf (stderr, "%s:%d: assertion failed\n", __FILE__, __LINE__); \
        fflush (stderr);                                         \
        abort ();                                          \
      }                                                    \
    }                                                      \
  while (0)

static bool
hash_compare_strings (void const *x, void const *y)
{
  ASSERT (x != y);
  return STREQ (x, y) ? true : false;
}

static void
hash_freer (void *x)
{
  free (x);
}

static void
insert_new (Hash_table *ht, void *ent)
{
  void *e = hash_insert (ht, ent);
  ASSERT (e == ent);
}

static bool
walk (void *ent, void *data)
{
  char *str = ent;
  unsigned int *map = data;
  switch (*str)
    {
    case 'a': *map |= 1; return true;
    case 'b': *map |= 2; return true;
    case 'c': *map |= 4; return true;
    }
  *map |= 8;
  return false;
}

static int
get_seed (char const *str, unsigned int *seed)
{
  size_t len = strlen (str);
  if (len == 0 || strspn (str, "0123456789") != len || 10 < len)
    return 1;

  *seed = atoi (str);
  return 0;
}

int
main (int argc, char **argv)
{
  unsigned int i;
  unsigned int k;
  unsigned int table_size[] = {1, 2, 3, 4, 5, 23, 53};
  Hash_table *ht;
  Hash_tuning tuning;

  hash_reset_tuning (&tuning);
  tuning.shrink_threshold = 0.3;
  tuning.shrink_factor = 0.707;
  tuning.growth_threshold = 1.5;
  tuning.growth_factor = 2.0;
  tuning.is_n_buckets = true;

  if (1 < argc)
    {
      unsigned int seed;
      if (get_seed (argv[1], &seed) != 0)
      {
        fprintf (stderr, "invalid seed: %s\n", argv[1]);
        exit (EXIT_FAILURE);
      }

      srand (seed);
    }

  for (i = 0; i < ARRAY_CARDINALITY (table_size); i++)
    {
      size_t sz = table_size[i];
      ht = hash_initialize (sz, NULL, hash_pjw, hash_compare_strings, NULL);
      ASSERT (ht);
      insert_new (ht, "a");
      {
      char *str1 = xstrdup ("a");
      char *str2 = hash_insert (ht, str1);
      ASSERT (str1 != str2);
      ASSERT (STREQ (str1, str2));
      free (str1);
      }
      insert_new (ht, "b");
      insert_new (ht, "c");
      i = 0;
      ASSERT (hash_do_for_each (ht, walk, &i) == 3);
      ASSERT (i == 7);
      {
      void *buf[5] = { NULL };
      ASSERT (hash_get_entries (ht, NULL, 0) == 0);
      ASSERT (hash_get_entries (ht, buf, 5) == 3);
      ASSERT (STREQ (buf[0], "a") || STREQ (buf[0], "b") || STREQ (buf[0], "c"));
      }
      ASSERT (hash_delete (ht, "a"));
      ASSERT (hash_delete (ht, "a") == NULL);
      ASSERT (hash_delete (ht, "b"));
      ASSERT (hash_delete (ht, "c"));

      ASSERT (hash_rehash (ht, 47));
      ASSERT (hash_rehash (ht, 467));

      /* Free an empty table. */
      hash_clear (ht);
      hash_free (ht);

      ht = hash_initialize (sz, NULL, hash_pjw, hash_compare_strings, NULL);
      ASSERT (ht);

      insert_new (ht, "z");
      insert_new (ht, "y");
      insert_new (ht, "x");
      insert_new (ht, "w");
      insert_new (ht, "v");
      insert_new (ht, "u");

      hash_clear (ht);
      ASSERT (hash_get_n_entries (ht) == 0);
      hash_free (ht);

      /* Test pointer hashing.  */
      ht = hash_initialize (sz, NULL, NULL, NULL, NULL);
      ASSERT (ht);
      {
      char *str = xstrdup ("a");
      insert_new (ht, "a");
      insert_new (ht, str);
      ASSERT (hash_lookup (ht, str) == str);
      free (str);
      }
      hash_free (ht);
    }

  hash_reset_tuning (&tuning);
  tuning.shrink_threshold = 0.3;
  tuning.shrink_factor = 0.707;
  tuning.growth_threshold = 1.5;
  tuning.growth_factor = 2.0;
  tuning.is_n_buckets = true;
  /* Invalid tuning.  */
  ht = hash_initialize (4651, &tuning, hash_pjw, hash_compare_strings,
                  hash_freer);
  ASSERT (!ht);

  /* Alternate tuning.  */
  tuning.growth_threshold = 0.89;

  /* Run with default tuning, then with custom tuning settings.  */
  for (k = 0; k < 2; k++)
    {
      Hash_tuning const *tune = (k == 0 ? NULL : &tuning);
      /* Now, each entry is malloc'd.  */
      ht = hash_initialize (4651, tune, hash_pjw,
                      hash_compare_strings, hash_freer);
      ASSERT (ht);
      for (i = 0; i < 10000; i++)
      {
        unsigned int op = rand () % 10;
        switch (op)
          {
          case 0:
          case 1:
          case 2:
          case 3:
          case 4:
          case 5:
            {
            char buf[50];
            char const *p = uinttostr (i, buf);
            insert_new (ht, xstrdup (p));
            }
            break;

          case 6:
            {
            size_t n = hash_get_n_entries (ht);
            ASSERT (hash_rehash (ht, n + rand () % 20));
            }
            break;

          case 7:
            {
            size_t n = hash_get_n_entries (ht);
            size_t delta = rand () % 20;
            if (delta < n)
              ASSERT (hash_rehash (ht, n - delta));
            }
            break;

          case 8:
          case 9:
            {
            /* Delete a random entry.  */
            size_t n = hash_get_n_entries (ht);
            if (n)
              {
                size_t k = rand () % n;
                void const *p;
                void *v;
                for (p = hash_get_first (ht); k;
                   --k, p = hash_get_next (ht, p))
                  {
                  /* empty */
                  }
                ASSERT (p);
                v = hash_delete (ht, p);
                ASSERT (v);
                free (v);
              }
            break;
            }
          }
        ASSERT (hash_table_ok (ht));
      }

      hash_free (ht);
    }

  return 0;
}

Generated by  Doxygen 1.6.0   Back to index