From 448e792b0a9b092f9593eaa51e16acd8abe54c76 Mon Sep 17 00:00:00 2001 From: Jeff Garzik Date: Sun, 24 Jan 1999 04:18:11 +0000 Subject: [PATCH] - Fixed bug that overwrote nodes in hash buckets instead of adding them to Sat Jan 23 22:45:59 1999 Jeff Garzik * ghash.c (g_hash_table_lookup_node, g_hash_table_lookup, g_hash_table_insert, g_hash_table_remove, g_hash_table_lookup_extended): - Fixed bug that overwrote nodes in hash buckets instead of adding them to the hash bucket node list. Hash tables now work as advertised. (g_hash_table_resize): - Use g_new0 instead of manual init. - Space out code a bit for readability. (g_hash_nodes_destroy): - Replaced "if (!hash_node) return;" with "if (hash_node) {do stuff}". Testing takes up less code space than explicit call to 'return' before end of function. (look at gcc -S) Updated module header copyright to 1999. New module macro G_HASH_BUCKET for (table,key)->bucket lookups. * tests/hash-test.c: - Add two new tests, one with strings as the keys and values, and one with ints as the keys and values. Tests indirect (strings) and direct (ints) hashing. - Cleanup unused junk left over from testglib.c. - Converted a g_print call to g_assert_not_reached. - Updated copyright to 1999. * testglib.c, tests/string-test.c: - Init 'tmp_string' var to NULL, silencing uninit-var warning. --- ChangeLog | 33 +++++++++ ChangeLog.pre-2-0 | 33 +++++++++ ChangeLog.pre-2-10 | 33 +++++++++ ChangeLog.pre-2-12 | 33 +++++++++ ChangeLog.pre-2-2 | 33 +++++++++ ChangeLog.pre-2-4 | 33 +++++++++ ChangeLog.pre-2-6 | 33 +++++++++ ChangeLog.pre-2-8 | 33 +++++++++ ghash.c | 131 ++++++++++++++++++++------------- glib/ghash.c | 131 ++++++++++++++++++++------------- testglib.c | 2 +- tests/hash-test.c | 205 ++++++++++++++++++++++++++++++++++++++++++++++------ tests/string-test.c | 2 +- tests/testglib.c | 2 +- 14 files changed, 612 insertions(+), 125 deletions(-) diff --git a/ChangeLog b/ChangeLog index 8e3d620..d6f25cb 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,36 @@ +Sat Jan 23 22:45:59 1999 Jeff Garzik + + * ghash.c (g_hash_table_lookup_node, g_hash_table_lookup, + g_hash_table_insert, g_hash_table_remove, + g_hash_table_lookup_extended): + - Fixed bug that overwrote nodes in hash buckets instead of + adding them to the hash bucket node list. + Hash tables now work as advertised. + + (g_hash_table_resize): + - Use g_new0 instead of manual init. + - Space out code a bit for readability. + + (g_hash_nodes_destroy): + - Replaced "if (!hash_node) return;" with + "if (hash_node) {do stuff}". + Testing takes up less code space than explicit call to + 'return' before end of function. (look at gcc -S) + + Updated module header copyright to 1999. + New module macro G_HASH_BUCKET for (table,key)->bucket lookups. + + * tests/hash-test.c: + - Add two new tests, one with strings as the keys and values, and + one with ints as the keys and values. Tests indirect (strings) + and direct (ints) hashing. + - Cleanup unused junk left over from testglib.c. + - Converted a g_print call to g_assert_not_reached. + - Updated copyright to 1999. + + * testglib.c, tests/string-test.c: + - Init 'tmp_string' var to NULL, silencing uninit-var warning. + 1999-01-23 Raja R Harinath * gutils.c (g_get_any_init) [HAVE_GETPWUID_R]: diff --git a/ChangeLog.pre-2-0 b/ChangeLog.pre-2-0 index 8e3d620..d6f25cb 100644 --- a/ChangeLog.pre-2-0 +++ b/ChangeLog.pre-2-0 @@ -1,3 +1,36 @@ +Sat Jan 23 22:45:59 1999 Jeff Garzik + + * ghash.c (g_hash_table_lookup_node, g_hash_table_lookup, + g_hash_table_insert, g_hash_table_remove, + g_hash_table_lookup_extended): + - Fixed bug that overwrote nodes in hash buckets instead of + adding them to the hash bucket node list. + Hash tables now work as advertised. + + (g_hash_table_resize): + - Use g_new0 instead of manual init. + - Space out code a bit for readability. + + (g_hash_nodes_destroy): + - Replaced "if (!hash_node) return;" with + "if (hash_node) {do stuff}". + Testing takes up less code space than explicit call to + 'return' before end of function. (look at gcc -S) + + Updated module header copyright to 1999. + New module macro G_HASH_BUCKET for (table,key)->bucket lookups. + + * tests/hash-test.c: + - Add two new tests, one with strings as the keys and values, and + one with ints as the keys and values. Tests indirect (strings) + and direct (ints) hashing. + - Cleanup unused junk left over from testglib.c. + - Converted a g_print call to g_assert_not_reached. + - Updated copyright to 1999. + + * testglib.c, tests/string-test.c: + - Init 'tmp_string' var to NULL, silencing uninit-var warning. + 1999-01-23 Raja R Harinath * gutils.c (g_get_any_init) [HAVE_GETPWUID_R]: diff --git a/ChangeLog.pre-2-10 b/ChangeLog.pre-2-10 index 8e3d620..d6f25cb 100644 --- a/ChangeLog.pre-2-10 +++ b/ChangeLog.pre-2-10 @@ -1,3 +1,36 @@ +Sat Jan 23 22:45:59 1999 Jeff Garzik + + * ghash.c (g_hash_table_lookup_node, g_hash_table_lookup, + g_hash_table_insert, g_hash_table_remove, + g_hash_table_lookup_extended): + - Fixed bug that overwrote nodes in hash buckets instead of + adding them to the hash bucket node list. + Hash tables now work as advertised. + + (g_hash_table_resize): + - Use g_new0 instead of manual init. + - Space out code a bit for readability. + + (g_hash_nodes_destroy): + - Replaced "if (!hash_node) return;" with + "if (hash_node) {do stuff}". + Testing takes up less code space than explicit call to + 'return' before end of function. (look at gcc -S) + + Updated module header copyright to 1999. + New module macro G_HASH_BUCKET for (table,key)->bucket lookups. + + * tests/hash-test.c: + - Add two new tests, one with strings as the keys and values, and + one with ints as the keys and values. Tests indirect (strings) + and direct (ints) hashing. + - Cleanup unused junk left over from testglib.c. + - Converted a g_print call to g_assert_not_reached. + - Updated copyright to 1999. + + * testglib.c, tests/string-test.c: + - Init 'tmp_string' var to NULL, silencing uninit-var warning. + 1999-01-23 Raja R Harinath * gutils.c (g_get_any_init) [HAVE_GETPWUID_R]: diff --git a/ChangeLog.pre-2-12 b/ChangeLog.pre-2-12 index 8e3d620..d6f25cb 100644 --- a/ChangeLog.pre-2-12 +++ b/ChangeLog.pre-2-12 @@ -1,3 +1,36 @@ +Sat Jan 23 22:45:59 1999 Jeff Garzik + + * ghash.c (g_hash_table_lookup_node, g_hash_table_lookup, + g_hash_table_insert, g_hash_table_remove, + g_hash_table_lookup_extended): + - Fixed bug that overwrote nodes in hash buckets instead of + adding them to the hash bucket node list. + Hash tables now work as advertised. + + (g_hash_table_resize): + - Use g_new0 instead of manual init. + - Space out code a bit for readability. + + (g_hash_nodes_destroy): + - Replaced "if (!hash_node) return;" with + "if (hash_node) {do stuff}". + Testing takes up less code space than explicit call to + 'return' before end of function. (look at gcc -S) + + Updated module header copyright to 1999. + New module macro G_HASH_BUCKET for (table,key)->bucket lookups. + + * tests/hash-test.c: + - Add two new tests, one with strings as the keys and values, and + one with ints as the keys and values. Tests indirect (strings) + and direct (ints) hashing. + - Cleanup unused junk left over from testglib.c. + - Converted a g_print call to g_assert_not_reached. + - Updated copyright to 1999. + + * testglib.c, tests/string-test.c: + - Init 'tmp_string' var to NULL, silencing uninit-var warning. + 1999-01-23 Raja R Harinath * gutils.c (g_get_any_init) [HAVE_GETPWUID_R]: diff --git a/ChangeLog.pre-2-2 b/ChangeLog.pre-2-2 index 8e3d620..d6f25cb 100644 --- a/ChangeLog.pre-2-2 +++ b/ChangeLog.pre-2-2 @@ -1,3 +1,36 @@ +Sat Jan 23 22:45:59 1999 Jeff Garzik + + * ghash.c (g_hash_table_lookup_node, g_hash_table_lookup, + g_hash_table_insert, g_hash_table_remove, + g_hash_table_lookup_extended): + - Fixed bug that overwrote nodes in hash buckets instead of + adding them to the hash bucket node list. + Hash tables now work as advertised. + + (g_hash_table_resize): + - Use g_new0 instead of manual init. + - Space out code a bit for readability. + + (g_hash_nodes_destroy): + - Replaced "if (!hash_node) return;" with + "if (hash_node) {do stuff}". + Testing takes up less code space than explicit call to + 'return' before end of function. (look at gcc -S) + + Updated module header copyright to 1999. + New module macro G_HASH_BUCKET for (table,key)->bucket lookups. + + * tests/hash-test.c: + - Add two new tests, one with strings as the keys and values, and + one with ints as the keys and values. Tests indirect (strings) + and direct (ints) hashing. + - Cleanup unused junk left over from testglib.c. + - Converted a g_print call to g_assert_not_reached. + - Updated copyright to 1999. + + * testglib.c, tests/string-test.c: + - Init 'tmp_string' var to NULL, silencing uninit-var warning. + 1999-01-23 Raja R Harinath * gutils.c (g_get_any_init) [HAVE_GETPWUID_R]: diff --git a/ChangeLog.pre-2-4 b/ChangeLog.pre-2-4 index 8e3d620..d6f25cb 100644 --- a/ChangeLog.pre-2-4 +++ b/ChangeLog.pre-2-4 @@ -1,3 +1,36 @@ +Sat Jan 23 22:45:59 1999 Jeff Garzik + + * ghash.c (g_hash_table_lookup_node, g_hash_table_lookup, + g_hash_table_insert, g_hash_table_remove, + g_hash_table_lookup_extended): + - Fixed bug that overwrote nodes in hash buckets instead of + adding them to the hash bucket node list. + Hash tables now work as advertised. + + (g_hash_table_resize): + - Use g_new0 instead of manual init. + - Space out code a bit for readability. + + (g_hash_nodes_destroy): + - Replaced "if (!hash_node) return;" with + "if (hash_node) {do stuff}". + Testing takes up less code space than explicit call to + 'return' before end of function. (look at gcc -S) + + Updated module header copyright to 1999. + New module macro G_HASH_BUCKET for (table,key)->bucket lookups. + + * tests/hash-test.c: + - Add two new tests, one with strings as the keys and values, and + one with ints as the keys and values. Tests indirect (strings) + and direct (ints) hashing. + - Cleanup unused junk left over from testglib.c. + - Converted a g_print call to g_assert_not_reached. + - Updated copyright to 1999. + + * testglib.c, tests/string-test.c: + - Init 'tmp_string' var to NULL, silencing uninit-var warning. + 1999-01-23 Raja R Harinath * gutils.c (g_get_any_init) [HAVE_GETPWUID_R]: diff --git a/ChangeLog.pre-2-6 b/ChangeLog.pre-2-6 index 8e3d620..d6f25cb 100644 --- a/ChangeLog.pre-2-6 +++ b/ChangeLog.pre-2-6 @@ -1,3 +1,36 @@ +Sat Jan 23 22:45:59 1999 Jeff Garzik + + * ghash.c (g_hash_table_lookup_node, g_hash_table_lookup, + g_hash_table_insert, g_hash_table_remove, + g_hash_table_lookup_extended): + - Fixed bug that overwrote nodes in hash buckets instead of + adding them to the hash bucket node list. + Hash tables now work as advertised. + + (g_hash_table_resize): + - Use g_new0 instead of manual init. + - Space out code a bit for readability. + + (g_hash_nodes_destroy): + - Replaced "if (!hash_node) return;" with + "if (hash_node) {do stuff}". + Testing takes up less code space than explicit call to + 'return' before end of function. (look at gcc -S) + + Updated module header copyright to 1999. + New module macro G_HASH_BUCKET for (table,key)->bucket lookups. + + * tests/hash-test.c: + - Add two new tests, one with strings as the keys and values, and + one with ints as the keys and values. Tests indirect (strings) + and direct (ints) hashing. + - Cleanup unused junk left over from testglib.c. + - Converted a g_print call to g_assert_not_reached. + - Updated copyright to 1999. + + * testglib.c, tests/string-test.c: + - Init 'tmp_string' var to NULL, silencing uninit-var warning. + 1999-01-23 Raja R Harinath * gutils.c (g_get_any_init) [HAVE_GETPWUID_R]: diff --git a/ChangeLog.pre-2-8 b/ChangeLog.pre-2-8 index 8e3d620..d6f25cb 100644 --- a/ChangeLog.pre-2-8 +++ b/ChangeLog.pre-2-8 @@ -1,3 +1,36 @@ +Sat Jan 23 22:45:59 1999 Jeff Garzik + + * ghash.c (g_hash_table_lookup_node, g_hash_table_lookup, + g_hash_table_insert, g_hash_table_remove, + g_hash_table_lookup_extended): + - Fixed bug that overwrote nodes in hash buckets instead of + adding them to the hash bucket node list. + Hash tables now work as advertised. + + (g_hash_table_resize): + - Use g_new0 instead of manual init. + - Space out code a bit for readability. + + (g_hash_nodes_destroy): + - Replaced "if (!hash_node) return;" with + "if (hash_node) {do stuff}". + Testing takes up less code space than explicit call to + 'return' before end of function. (look at gcc -S) + + Updated module header copyright to 1999. + New module macro G_HASH_BUCKET for (table,key)->bucket lookups. + + * tests/hash-test.c: + - Add two new tests, one with strings as the keys and values, and + one with ints as the keys and values. Tests indirect (strings) + and direct (ints) hashing. + - Cleanup unused junk left over from testglib.c. + - Converted a g_print call to g_assert_not_reached. + - Updated copyright to 1999. + + * testglib.c, tests/string-test.c: + - Init 'tmp_string' var to NULL, silencing uninit-var warning. + 1999-01-23 Raja R Harinath * gutils.c (g_get_any_init) [HAVE_GETPWUID_R]: diff --git a/ghash.c b/ghash.c index ed564e1..704c4c8 100644 --- a/ghash.c +++ b/ghash.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 @@ -49,13 +50,17 @@ struct _GHashTable static void g_hash_table_resize (GHashTable *hash_table); -static GHashNode** g_hash_table_lookup_node (GHashTable *hash_table, - gconstpointer key); +static GHashNode* g_hash_table_lookup_node (GHashTable *hash_table, + gconstpointer key, + GHashNode **last_p, + guint *bucket_p); static GHashNode* g_hash_node_new (gpointer key, gpointer value); static void g_hash_node_destroy (GHashNode *hash_node); static void g_hash_nodes_destroy (GHashNode *hash_node); +#define G_HASH_BUCKET(table,key) \ + ((* (table)->hash_func) (key) % (table)->size) G_LOCK_DECLARE_STATIC (g_hash_global); @@ -98,14 +103,17 @@ g_hash_table_destroy (GHashTable *hash_table) g_free (hash_table); } -static inline GHashNode** -g_hash_table_lookup_node (GHashTable *hash_table, - gconstpointer key) +static inline GHashNode* +g_hash_table_lookup_node (GHashTable *hash_table, + gconstpointer key, + GHashNode **last_p, + guint *bucket_p) { - GHashNode **node; + GHashNode *node, *last = NULL; + guint bucket; - node = &hash_table->nodes - [(* hash_table->hash_func) (key) % hash_table->size]; + bucket = G_HASH_BUCKET (hash_table, key); + node = hash_table->nodes [bucket]; /* Hash table lookup needs to be fast. * We therefore remove the extra conditional of testing @@ -113,12 +121,23 @@ g_hash_table_lookup_node (GHashTable *hash_table, * the inner loop. */ if (hash_table->key_compare_func) - while (*node && !(*hash_table->key_compare_func) ((*node)->key, key)) - node = &(*node)->next; + while (node && !(*hash_table->key_compare_func) (node->key, key)) + { + last = node; + node = node->next; + } else - while (*node && (*node)->key != key) - node = &(*node)->next; + while (node && node->key != key) + { + last = node; + node = node->next; + } + if (last_p) + *last_p = last; + if (bucket_p) + *bucket_p = bucket; + return node; } @@ -130,7 +149,7 @@ g_hash_table_lookup (GHashTable *hash_table, g_return_val_if_fail (hash_table != NULL, NULL); - node = *g_hash_table_lookup_node (hash_table, key); + node = g_hash_table_lookup_node (hash_table, key, NULL, NULL); return node ? node->value : NULL; } @@ -140,13 +159,27 @@ g_hash_table_insert (GHashTable *hash_table, gpointer key, gpointer value) { - GHashNode **node; + GHashNode *node, *last; + guint bucket; g_return_if_fail (hash_table != NULL); + + node = g_hash_table_lookup_node (hash_table, key, &last, &bucket); - node = g_hash_table_lookup_node (hash_table, key); - - if (*node) + if (node == NULL) + { + node = g_hash_node_new (key, value); + + if (last == NULL) + hash_table->nodes [bucket] = node; + else + last->next = node; + + hash_table->nnodes++; + if (!hash_table->frozen) + g_hash_table_resize (hash_table); + } + else { /* do not reset node->key in this place, keeping * the old key might be intended. @@ -154,35 +187,36 @@ g_hash_table_insert (GHashTable *hash_table, * can be used otherwise. * * node->key = key; */ - (*node)->value = value; - } - else - { - *node = g_hash_node_new (key, value); - hash_table->nnodes++; - if (!hash_table->frozen) - g_hash_table_resize (hash_table); + node->value = value; } + } void g_hash_table_remove (GHashTable *hash_table, gconstpointer key) { - GHashNode **node, *dest; + GHashNode *node, *last; + guint bucket; g_return_if_fail (hash_table != NULL); - while (*(node = g_hash_table_lookup_node (hash_table, key))) + node = g_hash_table_lookup_node (hash_table, key, &last, &bucket); + + if (node) { - dest = *node; - (*node) = dest->next; - g_hash_node_destroy (dest); + if (last == NULL) + hash_table->nodes [bucket] = node->next; + else + last->next = node->next; + + g_hash_node_destroy (node); + hash_table->nnodes--; - } - if (!hash_table->frozen) - g_hash_table_resize (hash_table); + if (!hash_table->frozen) + g_hash_table_resize (hash_table); + } } gboolean @@ -195,7 +229,7 @@ g_hash_table_lookup_extended (GHashTable *hash_table, g_return_val_if_fail (hash_table != NULL, FALSE); - node = *g_hash_table_lookup_node (hash_table, lookup_key); + node = g_hash_table_lookup_node (hash_table, lookup_key, NULL, NULL); if (node) { @@ -320,16 +354,15 @@ g_hash_table_resize (GHashTable *hash_table) new_size = CLAMP(g_spaced_primes_closest (hash_table->nnodes), HASH_TABLE_MIN_SIZE, HASH_TABLE_MAX_SIZE); - new_nodes = g_new (GHashNode*, new_size); - - for (i = 0; i < new_size; i++) - new_nodes[i] = NULL; + new_nodes = g_new0 (GHashNode*, new_size); for (i = 0; i < hash_table->size; i++) for (node = hash_table->nodes[i]; node; node = next) { next = node->next; + hash_val = (* hash_table->hash_func) (node->key) % new_size; + node->next = new_nodes[hash_val]; new_nodes[hash_val] = node; } @@ -381,18 +414,16 @@ g_hash_node_destroy (GHashNode *hash_node) static void g_hash_nodes_destroy (GHashNode *hash_node) { - GHashNode *node; - - if (!hash_node) - return; - - node = hash_node; + if (hash_node) + { + GHashNode *node = hash_node; - while (node->next) - node = node->next; + while (node->next) + node = node->next; - G_LOCK (g_hash_global); - node->next = node_free_list; - node_free_list = hash_node; - G_UNLOCK (g_hash_global); + G_LOCK (g_hash_global); + node->next = node_free_list; + node_free_list = hash_node; + G_UNLOCK (g_hash_global); + } } diff --git a/glib/ghash.c b/glib/ghash.c index ed564e1..704c4c8 100644 --- a/glib/ghash.c +++ b/glib/ghash.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 @@ -49,13 +50,17 @@ struct _GHashTable static void g_hash_table_resize (GHashTable *hash_table); -static GHashNode** g_hash_table_lookup_node (GHashTable *hash_table, - gconstpointer key); +static GHashNode* g_hash_table_lookup_node (GHashTable *hash_table, + gconstpointer key, + GHashNode **last_p, + guint *bucket_p); static GHashNode* g_hash_node_new (gpointer key, gpointer value); static void g_hash_node_destroy (GHashNode *hash_node); static void g_hash_nodes_destroy (GHashNode *hash_node); +#define G_HASH_BUCKET(table,key) \ + ((* (table)->hash_func) (key) % (table)->size) G_LOCK_DECLARE_STATIC (g_hash_global); @@ -98,14 +103,17 @@ g_hash_table_destroy (GHashTable *hash_table) g_free (hash_table); } -static inline GHashNode** -g_hash_table_lookup_node (GHashTable *hash_table, - gconstpointer key) +static inline GHashNode* +g_hash_table_lookup_node (GHashTable *hash_table, + gconstpointer key, + GHashNode **last_p, + guint *bucket_p) { - GHashNode **node; + GHashNode *node, *last = NULL; + guint bucket; - node = &hash_table->nodes - [(* hash_table->hash_func) (key) % hash_table->size]; + bucket = G_HASH_BUCKET (hash_table, key); + node = hash_table->nodes [bucket]; /* Hash table lookup needs to be fast. * We therefore remove the extra conditional of testing @@ -113,12 +121,23 @@ g_hash_table_lookup_node (GHashTable *hash_table, * the inner loop. */ if (hash_table->key_compare_func) - while (*node && !(*hash_table->key_compare_func) ((*node)->key, key)) - node = &(*node)->next; + while (node && !(*hash_table->key_compare_func) (node->key, key)) + { + last = node; + node = node->next; + } else - while (*node && (*node)->key != key) - node = &(*node)->next; + while (node && node->key != key) + { + last = node; + node = node->next; + } + if (last_p) + *last_p = last; + if (bucket_p) + *bucket_p = bucket; + return node; } @@ -130,7 +149,7 @@ g_hash_table_lookup (GHashTable *hash_table, g_return_val_if_fail (hash_table != NULL, NULL); - node = *g_hash_table_lookup_node (hash_table, key); + node = g_hash_table_lookup_node (hash_table, key, NULL, NULL); return node ? node->value : NULL; } @@ -140,13 +159,27 @@ g_hash_table_insert (GHashTable *hash_table, gpointer key, gpointer value) { - GHashNode **node; + GHashNode *node, *last; + guint bucket; g_return_if_fail (hash_table != NULL); + + node = g_hash_table_lookup_node (hash_table, key, &last, &bucket); - node = g_hash_table_lookup_node (hash_table, key); - - if (*node) + if (node == NULL) + { + node = g_hash_node_new (key, value); + + if (last == NULL) + hash_table->nodes [bucket] = node; + else + last->next = node; + + hash_table->nnodes++; + if (!hash_table->frozen) + g_hash_table_resize (hash_table); + } + else { /* do not reset node->key in this place, keeping * the old key might be intended. @@ -154,35 +187,36 @@ g_hash_table_insert (GHashTable *hash_table, * can be used otherwise. * * node->key = key; */ - (*node)->value = value; - } - else - { - *node = g_hash_node_new (key, value); - hash_table->nnodes++; - if (!hash_table->frozen) - g_hash_table_resize (hash_table); + node->value = value; } + } void g_hash_table_remove (GHashTable *hash_table, gconstpointer key) { - GHashNode **node, *dest; + GHashNode *node, *last; + guint bucket; g_return_if_fail (hash_table != NULL); - while (*(node = g_hash_table_lookup_node (hash_table, key))) + node = g_hash_table_lookup_node (hash_table, key, &last, &bucket); + + if (node) { - dest = *node; - (*node) = dest->next; - g_hash_node_destroy (dest); + if (last == NULL) + hash_table->nodes [bucket] = node->next; + else + last->next = node->next; + + g_hash_node_destroy (node); + hash_table->nnodes--; - } - if (!hash_table->frozen) - g_hash_table_resize (hash_table); + if (!hash_table->frozen) + g_hash_table_resize (hash_table); + } } gboolean @@ -195,7 +229,7 @@ g_hash_table_lookup_extended (GHashTable *hash_table, g_return_val_if_fail (hash_table != NULL, FALSE); - node = *g_hash_table_lookup_node (hash_table, lookup_key); + node = g_hash_table_lookup_node (hash_table, lookup_key, NULL, NULL); if (node) { @@ -320,16 +354,15 @@ g_hash_table_resize (GHashTable *hash_table) new_size = CLAMP(g_spaced_primes_closest (hash_table->nnodes), HASH_TABLE_MIN_SIZE, HASH_TABLE_MAX_SIZE); - new_nodes = g_new (GHashNode*, new_size); - - for (i = 0; i < new_size; i++) - new_nodes[i] = NULL; + new_nodes = g_new0 (GHashNode*, new_size); for (i = 0; i < hash_table->size; i++) for (node = hash_table->nodes[i]; node; node = next) { next = node->next; + hash_val = (* hash_table->hash_func) (node->key) % new_size; + node->next = new_nodes[hash_val]; new_nodes[hash_val] = node; } @@ -381,18 +414,16 @@ g_hash_node_destroy (GHashNode *hash_node) static void g_hash_nodes_destroy (GHashNode *hash_node) { - GHashNode *node; - - if (!hash_node) - return; - - node = hash_node; + if (hash_node) + { + GHashNode *node = hash_node; - while (node->next) - node = node->next; + while (node->next) + node = node->next; - G_LOCK (g_hash_global); - node->next = node_free_list; - node_free_list = hash_node; - G_UNLOCK (g_hash_global); + G_LOCK (g_hash_global); + node->next = node_free_list; + node_free_list = hash_node; + G_UNLOCK (g_hash_global); + } } diff --git a/testglib.c b/testglib.c index 3d63ebb..2c4c87b 100644 --- a/testglib.c +++ b/testglib.c @@ -283,7 +283,7 @@ main (int argc, gint morenums[10] = { 8, 9, 7, 0, 3, 2, 5, 1, 4, 6}; gchar *string; - gchar *mem[10000], *tmp_string, *tmp_string_2; + gchar *mem[10000], *tmp_string = NULL, *tmp_string_2; gint i, j; GArray *garray; GPtrArray *gparray; diff --git a/tests/hash-test.c b/tests/hash-test.c index cd968cd..1287f85 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 +#endif + +#if STDC_HEADERS #include #include -#include "glib.h" +#include +#endif -int array[10000]; -gboolean failed = FALSE; +#include -#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; } diff --git a/tests/string-test.c b/tests/string-test.c index 228e964..1936e2b 100644 --- a/tests/string-test.c +++ b/tests/string-test.c @@ -53,7 +53,7 @@ main (int argc, { GStringChunk *string_chunk; - gchar *tmp_string, *tmp_string_2; + gchar *tmp_string = NULL, *tmp_string_2; gint i; GString *string1, *string2; diff --git a/tests/testglib.c b/tests/testglib.c index 3d63ebb..2c4c87b 100644 --- a/tests/testglib.c +++ b/tests/testglib.c @@ -283,7 +283,7 @@ main (int argc, gint morenums[10] = { 8, 9, 7, 0, 3, 2, 5, 1, 4, 6}; gchar *string; - gchar *mem[10000], *tmp_string, *tmp_string_2; + gchar *mem[10000], *tmp_string = NULL, *tmp_string_2; gint i, j; GArray *garray; GPtrArray *gparray; -- 2.7.4