diff options
Diffstat (limited to 'tests/hash-test.c')
| -rw-r--r-- | tests/hash-test.c | 205 |
1 files changed, 183 insertions, 22 deletions
diff --git a/tests/hash-test.c b/tests/hash-test.c index cd968cd09..1287f859b 100644 --- a/tests/hash-test.c +++ b/tests/hash-test.c @@ -1,5 +1,6 @@ /* GLIB - Library of useful routines for C programming * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald + * Copyright (C) 1999 The Free Software Foundation * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Library General Public @@ -18,34 +19,22 @@ */ #undef G_LOG_DOMAIN +#ifdef HAVE_CONFIG_H +# include <config.h> +#endif + +#if STDC_HEADERS #include <stdio.h> #include <string.h> -#include "glib.h" +#include <stdlib.h> +#endif -int array[10000]; -gboolean failed = FALSE; +#include <glib.h> -#define TEST(m,cond) G_STMT_START { failed = !(cond); \ -if (failed) \ - { if (!m) \ - g_print ("\n(%s:%d) failed for: %s\n", __FILE__, __LINE__, ( # cond )); \ - else \ - g_print ("\n(%s:%d) failed for: %s: (%s)\n", __FILE__, __LINE__, ( # cond ), (gchar*)m); \ - } \ -else \ - g_print ("."); fflush (stdout); \ -} G_STMT_END -#define C2P(c) ((gpointer) ((long) (c))) -#define P2C(p) ((gchar) ((long) (p))) -#define GLIB_TEST_STRING "el dorado " -#define GLIB_TEST_STRING_5 "el do" +int array[10000]; -typedef struct { - guint age; - gchar name[40]; -} GlibTestInfo; static gboolean @@ -69,7 +58,7 @@ my_hash_callback_remove_test (gpointer key, int *d = value; if ((*d) % 2) - g_print ("bad!\n"); + g_assert_not_reached (); } static void @@ -95,6 +84,175 @@ my_hash_compare (gconstpointer a, } + +/* + * This is a simplified version of the pathalias hashing function. + * Thanks to Steve Belovin and Peter Honeyman + * + * hash a string into a long int. 31 bit crc (from andrew appel). + * the crc table is computed at run time by crcinit() -- we could + * precompute, but it takes 1 clock tick on a 750. + * + * This fast table calculation works only if POLY is a prime polynomial + * in the field of integers modulo 2. Since the coefficients of a + * 32-bit polynomial won't fit in a 32-bit word, the high-order bit is + * implicit. IT MUST ALSO BE THE CASE that the coefficients of orders + * 31 down to 25 are zero. Happily, we have candidates, from + * E. J. Watson, "Primitive Polynomials (Mod 2)", Math. Comp. 16 (1962): + * x^32 + x^7 + x^5 + x^3 + x^2 + x^1 + x^0 + * x^31 + x^3 + x^0 + * + * We reverse the bits to get: + * 111101010000000000000000000000001 but drop the last 1 + * f 5 0 0 0 0 0 0 + * 010010000000000000000000000000001 ditto, for 31-bit crc + * 4 8 0 0 0 0 0 0 + */ + +#define POLY 0x48000000L /* 31-bit polynomial (avoids sign problems) */ + +static guint CrcTable[128]; + +/* + - crcinit - initialize tables for hash function + */ +static void crcinit(void) +{ + int i, j; + guint sum; + + for (i = 0; i < 128; ++i) { + sum = 0L; + for (j = 7 - 1; j >= 0; --j) + if (i & (1 << j)) + sum ^= POLY >> j; + CrcTable[i] = sum; + } +} + +/* + - hash - Honeyman's nice hashing function + */ +static guint honeyman_hash(gconstpointer key) +{ + const gchar *name = (const gchar *) key; + gint size; + guint sum = 0; + + g_assert (name != NULL); + g_assert (*name != 0); + + size = strlen(name); + + while (size--) { + sum = (sum >> 7) ^ CrcTable[(sum ^ (*name++)) & 0x7f]; + } + + return(sum); +} + + +static gint second_hash_cmp (gconstpointer a, gconstpointer b) +{ + gint rc = (strcmp (a, b) == 0); + + return rc; +} + + + +static void second_hash_test (void) +{ + int i; + char key[20] = "", val[20]="", *v, *orig_key, *orig_val; + GHashTable *h; + gboolean found; + + crcinit (); + + h = g_hash_table_new (honeyman_hash, second_hash_cmp); + g_assert (h != NULL); + for (i=0; i<20; i++) + { + sprintf (key, "%d", i); + g_assert (atoi (key) == i); + + sprintf (val, "%d value", i); + g_assert (atoi (val) == i); + + g_hash_table_insert (h, g_strdup (key), g_strdup (val)); + } + + g_assert (g_hash_table_size (h) == 20); + + for (i=0; i<20; i++) + { + sprintf (key, "%d", i); + g_assert (atoi(key) == i); + + v = (char *) g_hash_table_lookup (h, key); + + g_assert (v != NULL); + g_assert (*v != 0); + g_assert (atoi (v) == i); + } + + for (i=0; i<20; i++) + { + sprintf (key, "%d", i); + g_assert (atoi(key) == i); + + sprintf (val, "%d value", i); + g_assert (atoi (val) == i); + + orig_key = orig_val = NULL; + found = g_hash_table_lookup_extended (h, key, + (gpointer)&orig_key, + (gpointer)&orig_val); + g_assert (found); + + g_assert (orig_key != NULL); + g_assert (strcmp (key, orig_key) == 0); + g_free (orig_key); + + g_assert (orig_val != NULL); + g_assert (strcmp (val, orig_val) == 0); + g_free (orig_val); + } + + g_hash_table_destroy (h); +} + + +static void direct_hash_test (void) +{ + gint i, rc; + GHashTable *h; + + h = g_hash_table_new (NULL, NULL); + g_assert (h != NULL); + for (i=1; i<=20; i++) + { + g_hash_table_insert (h, GINT_TO_POINTER (i), + GINT_TO_POINTER (i + 42)); + } + + g_assert (g_hash_table_size (h) == 20); + + for (i=1; i<=20; i++) + { + rc = GPOINTER_TO_INT ( + g_hash_table_lookup (h, GINT_TO_POINTER (i))); + + g_assert (rc != 0); + g_assert ((rc - 42) == i); + } + + g_hash_table_destroy (h); +} + + + int main (int argc, char *argv[]) @@ -132,6 +290,9 @@ main (int argc, g_hash_table_destroy (hash_table); + second_hash_test (); + direct_hash_test (); + return 0; } |