From d5492a983cfa048658af8b03f833ddb3c0cf355e Mon Sep 17 00:00:00 2001 From: EST 1999 Jeff Garzik Date: Sun, 24 Jan 1999 06:18:43 +0000 Subject: [PATCH] - Revert previous "fix" (which really just did things a different way). - Sun Jan 24 00:36:22 EST 1999 Jeff Garzik * ghash.c: - Revert previous "fix" (which really just did things a different way). - (g_hash_table_remove): Don't need to support multiple values for a single key. * tests/hash-test.c: Add test where hash function always returns a single value. Add beginnings of tests for g_hash_table_foreach[_remove] and g_hash_table_remove. --- ChangeLog | 13 ++++++++ ChangeLog.pre-2-0 | 13 ++++++++ ChangeLog.pre-2-10 | 13 ++++++++ ChangeLog.pre-2-12 | 13 ++++++++ ChangeLog.pre-2-2 | 13 ++++++++ ChangeLog.pre-2-4 | 13 ++++++++ ChangeLog.pre-2-6 | 13 ++++++++ ChangeLog.pre-2-8 | 13 ++++++++ ghash.c | 96 ++++++++++++++++++------------------------------------ glib/ghash.c | 96 ++++++++++++++++++------------------------------------ tests/hash-test.c | 75 ++++++++++++++++++++++++++++++++++++++++-- 11 files changed, 240 insertions(+), 131 deletions(-) diff --git a/ChangeLog b/ChangeLog index e58858c..afe3eea 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,16 @@ +Sun Jan 24 00:36:22 EST 1999 Jeff Garzik + + * ghash.c: + - Revert previous "fix" (which really just did things a + different way). + - (g_hash_table_remove): Don't need to support multiple values + for a single key. + + * tests/hash-test.c: + Add test where hash function always returns a single value. + Add beginnings of tests for g_hash_table_foreach[_remove] and + g_hash_table_remove. + Sat Jan 23 20:40:06 PST 1999 Manish Singh * gutils.c: removed the #warning about MT without getpwuid_r diff --git a/ChangeLog.pre-2-0 b/ChangeLog.pre-2-0 index e58858c..afe3eea 100644 --- a/ChangeLog.pre-2-0 +++ b/ChangeLog.pre-2-0 @@ -1,3 +1,16 @@ +Sun Jan 24 00:36:22 EST 1999 Jeff Garzik + + * ghash.c: + - Revert previous "fix" (which really just did things a + different way). + - (g_hash_table_remove): Don't need to support multiple values + for a single key. + + * tests/hash-test.c: + Add test where hash function always returns a single value. + Add beginnings of tests for g_hash_table_foreach[_remove] and + g_hash_table_remove. + Sat Jan 23 20:40:06 PST 1999 Manish Singh * gutils.c: removed the #warning about MT without getpwuid_r diff --git a/ChangeLog.pre-2-10 b/ChangeLog.pre-2-10 index e58858c..afe3eea 100644 --- a/ChangeLog.pre-2-10 +++ b/ChangeLog.pre-2-10 @@ -1,3 +1,16 @@ +Sun Jan 24 00:36:22 EST 1999 Jeff Garzik + + * ghash.c: + - Revert previous "fix" (which really just did things a + different way). + - (g_hash_table_remove): Don't need to support multiple values + for a single key. + + * tests/hash-test.c: + Add test where hash function always returns a single value. + Add beginnings of tests for g_hash_table_foreach[_remove] and + g_hash_table_remove. + Sat Jan 23 20:40:06 PST 1999 Manish Singh * gutils.c: removed the #warning about MT without getpwuid_r diff --git a/ChangeLog.pre-2-12 b/ChangeLog.pre-2-12 index e58858c..afe3eea 100644 --- a/ChangeLog.pre-2-12 +++ b/ChangeLog.pre-2-12 @@ -1,3 +1,16 @@ +Sun Jan 24 00:36:22 EST 1999 Jeff Garzik + + * ghash.c: + - Revert previous "fix" (which really just did things a + different way). + - (g_hash_table_remove): Don't need to support multiple values + for a single key. + + * tests/hash-test.c: + Add test where hash function always returns a single value. + Add beginnings of tests for g_hash_table_foreach[_remove] and + g_hash_table_remove. + Sat Jan 23 20:40:06 PST 1999 Manish Singh * gutils.c: removed the #warning about MT without getpwuid_r diff --git a/ChangeLog.pre-2-2 b/ChangeLog.pre-2-2 index e58858c..afe3eea 100644 --- a/ChangeLog.pre-2-2 +++ b/ChangeLog.pre-2-2 @@ -1,3 +1,16 @@ +Sun Jan 24 00:36:22 EST 1999 Jeff Garzik + + * ghash.c: + - Revert previous "fix" (which really just did things a + different way). + - (g_hash_table_remove): Don't need to support multiple values + for a single key. + + * tests/hash-test.c: + Add test where hash function always returns a single value. + Add beginnings of tests for g_hash_table_foreach[_remove] and + g_hash_table_remove. + Sat Jan 23 20:40:06 PST 1999 Manish Singh * gutils.c: removed the #warning about MT without getpwuid_r diff --git a/ChangeLog.pre-2-4 b/ChangeLog.pre-2-4 index e58858c..afe3eea 100644 --- a/ChangeLog.pre-2-4 +++ b/ChangeLog.pre-2-4 @@ -1,3 +1,16 @@ +Sun Jan 24 00:36:22 EST 1999 Jeff Garzik + + * ghash.c: + - Revert previous "fix" (which really just did things a + different way). + - (g_hash_table_remove): Don't need to support multiple values + for a single key. + + * tests/hash-test.c: + Add test where hash function always returns a single value. + Add beginnings of tests for g_hash_table_foreach[_remove] and + g_hash_table_remove. + Sat Jan 23 20:40:06 PST 1999 Manish Singh * gutils.c: removed the #warning about MT without getpwuid_r diff --git a/ChangeLog.pre-2-6 b/ChangeLog.pre-2-6 index e58858c..afe3eea 100644 --- a/ChangeLog.pre-2-6 +++ b/ChangeLog.pre-2-6 @@ -1,3 +1,16 @@ +Sun Jan 24 00:36:22 EST 1999 Jeff Garzik + + * ghash.c: + - Revert previous "fix" (which really just did things a + different way). + - (g_hash_table_remove): Don't need to support multiple values + for a single key. + + * tests/hash-test.c: + Add test where hash function always returns a single value. + Add beginnings of tests for g_hash_table_foreach[_remove] and + g_hash_table_remove. + Sat Jan 23 20:40:06 PST 1999 Manish Singh * gutils.c: removed the #warning about MT without getpwuid_r diff --git a/ChangeLog.pre-2-8 b/ChangeLog.pre-2-8 index e58858c..afe3eea 100644 --- a/ChangeLog.pre-2-8 +++ b/ChangeLog.pre-2-8 @@ -1,3 +1,16 @@ +Sun Jan 24 00:36:22 EST 1999 Jeff Garzik + + * ghash.c: + - Revert previous "fix" (which really just did things a + different way). + - (g_hash_table_remove): Don't need to support multiple values + for a single key. + + * tests/hash-test.c: + Add test where hash function always returns a single value. + Add beginnings of tests for g_hash_table_foreach[_remove] and + g_hash_table_remove. + Sat Jan 23 20:40:06 PST 1999 Manish Singh * gutils.c: removed the #warning about MT without getpwuid_r diff --git a/ghash.c b/ghash.c index 704c4c8..8de3a5c 100644 --- a/ghash.c +++ b/ghash.c @@ -1,6 +1,5 @@ /* 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 @@ -50,17 +49,13 @@ struct _GHashTable static void g_hash_table_resize (GHashTable *hash_table); -static GHashNode* g_hash_table_lookup_node (GHashTable *hash_table, - gconstpointer key, - GHashNode **last_p, - guint *bucket_p); +static GHashNode** g_hash_table_lookup_node (GHashTable *hash_table, + gconstpointer key); 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); @@ -103,17 +98,14 @@ g_hash_table_destroy (GHashTable *hash_table) g_free (hash_table); } -static inline GHashNode* -g_hash_table_lookup_node (GHashTable *hash_table, - gconstpointer key, - GHashNode **last_p, - guint *bucket_p) +static inline GHashNode** +g_hash_table_lookup_node (GHashTable *hash_table, + gconstpointer key) { - GHashNode *node, *last = NULL; - guint bucket; + GHashNode **node; - bucket = G_HASH_BUCKET (hash_table, key); - node = hash_table->nodes [bucket]; + node = &hash_table->nodes + [(* hash_table->hash_func) (key) % hash_table->size]; /* Hash table lookup needs to be fast. * We therefore remove the extra conditional of testing @@ -121,23 +113,12 @@ 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)) - { - last = node; - node = node->next; - } + while (*node && !(*hash_table->key_compare_func) ((*node)->key, key)) + node = &(*node)->next; else - while (node && node->key != key) - { - last = node; - node = node->next; - } + while (*node && (*node)->key != key) + node = &(*node)->next; - if (last_p) - *last_p = last; - if (bucket_p) - *bucket_p = bucket; - return node; } @@ -149,7 +130,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, NULL, NULL); + node = *g_hash_table_lookup_node (hash_table, key); return node ? node->value : NULL; } @@ -159,27 +140,13 @@ g_hash_table_insert (GHashTable *hash_table, gpointer key, gpointer value) { - GHashNode *node, *last; - guint bucket; + GHashNode **node; g_return_if_fail (hash_table != NULL); - - node = g_hash_table_lookup_node (hash_table, key, &last, &bucket); - 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 + node = g_hash_table_lookup_node (hash_table, key); + + if (*node) { /* do not reset node->key in this place, keeping * the old key might be intended. @@ -187,31 +154,32 @@ g_hash_table_insert (GHashTable *hash_table, * can be used otherwise. * * node->key = key; */ - node->value = value; + (*node)->value = value; + } + else + { + *node = g_hash_node_new (key, value); + hash_table->nnodes++; + if (!hash_table->frozen) + g_hash_table_resize (hash_table); } - } void g_hash_table_remove (GHashTable *hash_table, gconstpointer key) { - GHashNode *node, *last; - guint bucket; + GHashNode **node, *dest; 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) { - if (last == NULL) - hash_table->nodes [bucket] = node->next; - else - last->next = node->next; - - g_hash_node_destroy (node); - + dest = *node; + (*node) = dest->next; + g_hash_node_destroy (dest); hash_table->nnodes--; if (!hash_table->frozen) @@ -229,7 +197,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, NULL, NULL); + node = *g_hash_table_lookup_node (hash_table, lookup_key); if (node) { diff --git a/glib/ghash.c b/glib/ghash.c index 704c4c8..8de3a5c 100644 --- a/glib/ghash.c +++ b/glib/ghash.c @@ -1,6 +1,5 @@ /* 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 @@ -50,17 +49,13 @@ struct _GHashTable static void g_hash_table_resize (GHashTable *hash_table); -static GHashNode* g_hash_table_lookup_node (GHashTable *hash_table, - gconstpointer key, - GHashNode **last_p, - guint *bucket_p); +static GHashNode** g_hash_table_lookup_node (GHashTable *hash_table, + gconstpointer key); 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); @@ -103,17 +98,14 @@ g_hash_table_destroy (GHashTable *hash_table) g_free (hash_table); } -static inline GHashNode* -g_hash_table_lookup_node (GHashTable *hash_table, - gconstpointer key, - GHashNode **last_p, - guint *bucket_p) +static inline GHashNode** +g_hash_table_lookup_node (GHashTable *hash_table, + gconstpointer key) { - GHashNode *node, *last = NULL; - guint bucket; + GHashNode **node; - bucket = G_HASH_BUCKET (hash_table, key); - node = hash_table->nodes [bucket]; + node = &hash_table->nodes + [(* hash_table->hash_func) (key) % hash_table->size]; /* Hash table lookup needs to be fast. * We therefore remove the extra conditional of testing @@ -121,23 +113,12 @@ 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)) - { - last = node; - node = node->next; - } + while (*node && !(*hash_table->key_compare_func) ((*node)->key, key)) + node = &(*node)->next; else - while (node && node->key != key) - { - last = node; - node = node->next; - } + while (*node && (*node)->key != key) + node = &(*node)->next; - if (last_p) - *last_p = last; - if (bucket_p) - *bucket_p = bucket; - return node; } @@ -149,7 +130,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, NULL, NULL); + node = *g_hash_table_lookup_node (hash_table, key); return node ? node->value : NULL; } @@ -159,27 +140,13 @@ g_hash_table_insert (GHashTable *hash_table, gpointer key, gpointer value) { - GHashNode *node, *last; - guint bucket; + GHashNode **node; g_return_if_fail (hash_table != NULL); - - node = g_hash_table_lookup_node (hash_table, key, &last, &bucket); - 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 + node = g_hash_table_lookup_node (hash_table, key); + + if (*node) { /* do not reset node->key in this place, keeping * the old key might be intended. @@ -187,31 +154,32 @@ g_hash_table_insert (GHashTable *hash_table, * can be used otherwise. * * node->key = key; */ - node->value = value; + (*node)->value = value; + } + else + { + *node = g_hash_node_new (key, value); + hash_table->nnodes++; + if (!hash_table->frozen) + g_hash_table_resize (hash_table); } - } void g_hash_table_remove (GHashTable *hash_table, gconstpointer key) { - GHashNode *node, *last; - guint bucket; + GHashNode **node, *dest; 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) { - if (last == NULL) - hash_table->nodes [bucket] = node->next; - else - last->next = node->next; - - g_hash_node_destroy (node); - + dest = *node; + (*node) = dest->next; + g_hash_node_destroy (dest); hash_table->nnodes--; if (!hash_table->frozen) @@ -229,7 +197,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, NULL, NULL); + node = *g_hash_table_lookup_node (hash_table, lookup_key); if (node) { diff --git a/tests/hash-test.c b/tests/hash-test.c index 1287f85..6176fd7 100644 --- a/tests/hash-test.c +++ b/tests/hash-test.c @@ -161,7 +161,64 @@ static gint second_hash_cmp (gconstpointer a, gconstpointer b) -static void second_hash_test (void) +static guint one_hash(gconstpointer key) +{ + return 1; +} + + +static void not_even_foreach (gpointer key, + gpointer value, + gpointer user_data) +{ + const char *_key = (const char *) key; + const char *_value = (const char *) value; + int i; + char val [20]; + + g_assert (_key != NULL); + g_assert (*_key != 0); + g_assert (_value != NULL); + g_assert (*_value != 0); + + i = atoi (_key); + g_assert (atoi (_key) > 0); + + sprintf (val, "%d value", i); + g_assert (strcmp (_value, val) == 0); + + g_assert ((i % 2) != 0); + g_assert (i != 3); +} + + +static gboolean remove_even_foreach (gpointer key, + gpointer value, + gpointer user_data) +{ + const char *_key = (const char *) key; + const char *_value = (const char *) value; + int i; + char val [20]; + + g_assert (_key != NULL); + g_assert (*_key != 0); + g_assert (_value != NULL); + g_assert (*_value != 0); + + i = atoi (_key); + g_assert (i > 0); + + sprintf (val, "%d value", i); + g_assert (strcmp (_value, val) == 0); + + return ((i % 2) == 0) ? TRUE : FALSE; +} + + + + +static void second_hash_test (gboolean simple_hash) { int i; char key[20] = "", val[20]="", *v, *orig_key, *orig_val; @@ -170,7 +227,8 @@ static void second_hash_test (void) crcinit (); - h = g_hash_table_new (honeyman_hash, second_hash_cmp); + h = g_hash_table_new (simple_hash ? one_hash : honeyman_hash, + second_hash_cmp); g_assert (h != NULL); for (i=0; i<20; i++) { @@ -197,8 +255,18 @@ static void second_hash_test (void) g_assert (atoi (v) == i); } + /**** future test stuff, yet to be debugged + sprintf (key, "%d", 3); + g_hash_table_remove (h, key); + g_hash_table_foreach_remove (h, remove_even_foreach, NULL); + g_hash_table_foreach (h, not_even_foreach, NULL); + */ + for (i=0; i<20; i++) { + if (((i % 2) == 0) || (i == 3)) + i++; + sprintf (key, "%d", i); g_assert (atoi(key) == i); @@ -290,7 +358,8 @@ main (int argc, g_hash_table_destroy (hash_table); - second_hash_test (); + second_hash_test (TRUE); + second_hash_test (FALSE); direct_hash_test (); return 0; -- 2.7.4