/*
- * Copyright (C) 2009 Free Software Foundation
+ * Copyright (C) 2009-2014 Free Software Foundation, Inc.
* Written by Jim Meyering
*
* This program is free software: you can redistribute it and/or modify
#include "hash.h"
#include "hash-pjw.h"
#include "inttostr.h"
-#include "xalloc.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
+#include "macros.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)
{
}
static void
-insert_new (Hash_table *ht, void *ent)
+insert_new (Hash_table *ht, const void *ent)
{
void *e = hash_insert (ht, ent);
ASSERT (e == ent);
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 (void)
+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];
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);
+ char *str1 = strdup ("a");
+ char *str2;
+ ASSERT (str1);
+ str2 = hash_insert (ht, str1);
+ ASSERT (str1 != str2);
+ ASSERT (STREQ (str1, str2));
+ free (str1);
}
insert_new (ht, "b");
insert_new (ht, "c");
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"));
+ 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);
hash_clear (ht);
ASSERT (hash_get_n_entries (ht) == 0);
hash_free (ht);
- }
-
- /* Now, each entry is malloc'd. */
- ht = hash_initialize (4651, NULL, 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));
+ /* Test pointer hashing. */
+ ht = hash_initialize (sz, NULL, NULL, NULL, NULL);
+ ASSERT (ht);
+ {
+ char *str = strdup ("a");
+ ASSERT (str);
+ insert_new (ht, "a");
+ insert_new (ht, str);
+ ASSERT (hash_lookup (ht, str) == str);
+ free (str);
+ }
+ hash_free (ht);
}
- hash_free (ht);
-
hash_reset_tuning (&tuning);
tuning.shrink_threshold = 0.3;
tuning.shrink_factor = 0.707;
tuning.is_n_buckets = true;
/* Invalid tuning. */
ht = hash_initialize (4651, &tuning, hash_pjw, hash_compare_strings,
- hash_freer);
+ hash_freer);
ASSERT (!ht);
/* Alternate tuning. */
tuning.growth_threshold = 0.89;
- ht = hash_initialize (4651, &tuning, hash_pjw, hash_compare_strings,
- hash_freer);
- ASSERT (ht);
- for (i = 0; i < 10000; i++)
+
+ /* Run with default tuning, then with custom tuning settings. */
+ for (k = 0; k < 2; k++)
{
- 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;
+ 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);
+ char *p_dup = strdup (p);
+ ASSERT (p_dup);
+ insert_new (ht, p_dup);
+ }
+ break;
- case 6:
- {
- size_t n = hash_get_n_entries (ht);
- ASSERT (hash_rehash (ht, n + rand () % 20));
- }
- 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 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));
- }
+ case 8:
+ case 9:
+ {
+ /* Delete a random entry. */
+ size_t n = hash_get_n_entries (ht);
+ if (n)
+ {
+ size_t kk = rand () % n;
+ void const *p;
+ void *v;
+ for (p = hash_get_first (ht); kk;
+ --kk, 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);
+ hash_free (ht);
+ }
return 0;
}
projects / gnulib.git / blobdiff