From d741d3e7a344622e5a534c34e9e2c0488b2fea4d Mon Sep 17 00:00:00 2001 From: Matthias Clasen Date: Sat, 15 Dec 2007 03:54:09 +0000 Subject: [PATCH] Add hash table iterators. (#500507, Jean-Yves Lefort) 2007-12-14 Matthias Clasen * glib/glib.symbols: * glib/ghash.[hc]: Add hash table iterators. (#500507, Jean-Yves Lefort) * tests/hash-test.c: Test iterators. svn path=/trunk/; revision=6130 --- ChangeLog | 8 + docs/reference/ChangeLog | 5 + docs/reference/glib/glib-sections.txt | 6 + docs/reference/glib/tmpl/hash_tables.sgml | 51 +++++- glib/ghash.c | 258 ++++++++++++++++++++++++++++++ glib/ghash.h | 22 +++ glib/glib.symbols | 5 + tests/hash-test.c | 84 ++++++++-- 8 files changed, 421 insertions(+), 18 deletions(-) diff --git a/ChangeLog b/ChangeLog index b3ebc28..a6a0cff 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,11 @@ +2007-12-14 Matthias Clasen + + * glib/glib.symbols: + * glib/ghash.[hc]: Add hash table iterators. (#500507, + Jean-Yves Lefort) + + * tests/hash-test.c: Test iterators. + 2007-12-13 Mathias Hasselmann Give exmples in error message unsupported case-changing escape diff --git a/docs/reference/ChangeLog b/docs/reference/ChangeLog index d9a14c0..1f335d6 100644 --- a/docs/reference/ChangeLog +++ b/docs/reference/ChangeLog @@ -1,3 +1,8 @@ +2007-12-14 Matthias Clasen + + * glib/tmpl/hash_tables.sgml: + * glib/glib-sections.txt: Add hash iterator functions + 2007-12-10 Matthias Clasen * gio/gio-sections.txt: diff --git a/docs/reference/glib/glib-sections.txt b/docs/reference/glib/glib-sections.txt index e54f028..ed81477 100644 --- a/docs/reference/glib/glib-sections.txt +++ b/docs/reference/glib/glib-sections.txt @@ -2015,6 +2015,12 @@ g_hash_table_thaw g_hash_table_destroy g_hash_table_ref g_hash_table_unref +GHashTableIter +g_hash_table_iter_init +g_hash_table_iter_next +g_hash_table_iter_get_hash_table +g_hash_table_iter_remove +g_hash_table_iter_steal g_direct_equal diff --git a/docs/reference/glib/tmpl/hash_tables.sgml b/docs/reference/glib/tmpl/hash_tables.sgml index ac844a4..44b9248 100644 --- a/docs/reference/glib/tmpl/hash_tables.sgml +++ b/docs/reference/glib/tmpl/hash_tables.sgml @@ -40,7 +40,9 @@ and g_hash_table_lookup_extended(). To remove a key and value, use g_hash_table_remove(). -To call a function for each key and value pair use g_hash_table_foreach(). +To call a function for each key and value pair use g_hash_table_foreach() +or use a iterator to iterate over the key/value pairs in the hash table, see +#GHashTableIter. To destroy a #GHashTable use g_hash_table_destroy(). @@ -96,7 +98,7 @@ hash functions which can be used when the key is a #gpointer, #gint, and #gchar* respectively. -FIXME: Need more here. + The hash values should be evenly distributed over a fairly large range? The modulus is taken with the hash table size (a prime number) to find the 'bucket' to place each key into. @@ -338,6 +340,51 @@ This function is deprecated and will be removed in the next major @hash_table: + + + + + +@iter: +@hash_table: + + + + + + + +@iter: +@key: +@value: +@Returns: + + + + + + + +@iter: +@Returns: + + + + + + + +@iter: + + + + + + + +@iter: + + diff --git a/glib/ghash.c b/glib/ghash.c index 25597c3..3f90399 100644 --- a/glib/ghash.c +++ b/glib/ghash.c @@ -56,10 +56,28 @@ struct _GHashTable GHashFunc hash_func; GEqualFunc key_equal_func; volatile gint ref_count; +#ifndef G_DISABLE_ASSERT + /* + * Tracks the structure of the hash table, not its contents: is only + * incremented when a node is added or removed (is not incremented + * when the key or data of a node is modified). + */ + int version; +#endif GDestroyNotify key_destroy_func; GDestroyNotify value_destroy_func; }; +typedef struct +{ + GHashTable *hash_table; + GHashNode *prev_node; + GHashNode *node; + int position; + gboolean pre_advanced; + int version; +} RealIter; + /* * g_hash_table_lookup_node: * @hash_table: our #GHashTable @@ -332,6 +350,9 @@ g_hash_table_new_full (GHashFunc hash_func, hash_table->hash_func = hash_func ? hash_func : g_direct_hash; hash_table->key_equal_func = key_equal_func; hash_table->ref_count = 1; +#ifndef G_DISABLE_ASSERT + hash_table->version = 0; +#endif hash_table->key_destroy_func = key_destroy_func; hash_table->value_destroy_func = value_destroy_func; hash_table->nodes = g_new0 (GHashNode*, hash_table->size); @@ -339,6 +360,214 @@ g_hash_table_new_full (GHashFunc hash_func, return hash_table; } +/** + * g_hash_table_iter_init: + * @iter: an uninitialized #GHashTableIter. + * @hash_table: a #GHashTable. + * + * Initializes a key/value pair iterator and associates it with + * @hash_table. Modifying the hash table after calling this function + * invalidates the returned iterator. + * + * + * GHashTableIter iter; + * gpointer key, value; + * + * g_hash_table_iter_init(&iter, hash_table); + * while (g_hash_table_iter_next(&iter, &key, &value)) { + * /* do something with key and value */ + * } + * + * + * Since: 2.16 + **/ +void +g_hash_table_iter_init (GHashTableIter *iter, + GHashTable *hash_table) +{ + RealIter *ri = (RealIter *) iter; + + g_return_if_fail (iter != NULL); + g_return_if_fail (hash_table != NULL); + + ri->hash_table = hash_table; + ri->prev_node = NULL; + ri->node = NULL; + ri->position = -1; + ri->pre_advanced = FALSE; +#ifndef G_DISABLE_ASSERT + ri->version = hash_table->version; +#endif +} + +/** + * g_hash_table_iter_next: + * @iter: an initialized #GHashTableIter. + * @key: a location to store the key, or %NULL. + * @value: a location to store the value, or %NULL. + * + * Advances @iter and retrieves the key and/or value that are now + * pointed to as a result of this advancement. If %FALSE is returned, + * @key and @value are not set, and the iterator becomes invalid. + * + * Return value: %FALSE if the end of the #GHashTable has been reached. + * + * Since: 2.16 + **/ +gboolean +g_hash_table_iter_next (GHashTableIter *iter, + gpointer *key, + gpointer *value) +{ + RealIter *ri = (RealIter *) iter; + + g_return_val_if_fail (iter != NULL, FALSE); + g_return_val_if_fail (ri->version == ri->hash_table->version, FALSE); + + if (ri->pre_advanced) + { + ri->pre_advanced = FALSE; + + if (ri->node == NULL) + return FALSE; + } + else + { + if (ri->node != NULL) + { + ri->prev_node = ri->node; + ri->node = ri->node->next; + } + + while (ri->node == NULL) + { + ri->position++; + if (ri->position >= ri->hash_table->size) + return FALSE; + + ri->prev_node = NULL; + ri->node = ri->hash_table->nodes[ri->position]; + } + } + + if (key != NULL) + *key = ri->node->key; + if (value != NULL) + *value = ri->node->value; + + return TRUE; +} + +/** + * g_hash_table_iter_get_hash_table: + * @iter: an initialized #GHashTableIter. + * + * Returns the #GHashTable associated with @iter. + * + * Return value: the #GHashTable associated with @iter. + * + * Since: 2.16 + **/ +GHashTable * +g_hash_table_iter_get_hash_table (GHashTableIter *iter) +{ + g_return_val_if_fail (iter != NULL, NULL); + + return ((RealIter *) iter)->hash_table; +} + +static void +iter_remove_or_steal (RealIter *ri, gboolean notify) +{ + GHashNode *prev; + GHashNode *node; + int position; + + g_return_if_fail (ri != NULL); + g_return_if_fail (ri->version == ri->hash_table->version); + g_return_if_fail (ri->node != NULL); + + prev = ri->prev_node; + node = ri->node; + position = ri->position; + + /* pre-advance the iterator since we will remove the node */ + + ri->node = ri->node->next; + /* ri->prev_node is still the correct previous node */ + + while (ri->node == NULL) + { + ri->position++; + if (ri->position >= ri->hash_table->size) + break; + + ri->prev_node = NULL; + ri->node = ri->hash_table->nodes[ri->position]; + } + + ri->pre_advanced = TRUE; + + /* remove the node */ + + if (prev != NULL) + prev->next = node->next; + else + ri->hash_table->nodes[position] = node->next; + + if (notify) + { + if (ri->hash_table->key_destroy_func) + ri->hash_table->key_destroy_func(node->key); + if (ri->hash_table->value_destroy_func) + ri->hash_table->value_destroy_func(node->value); + } + + g_slice_free (GHashNode, node); + + ri->hash_table->nnodes--; +} + +/** + * g_hash_table_iter_remove(): + * @iter: an initialized #GHashTableIter. + * + * Removes the key/value pair currently pointed to by the iterator + * from its associated #GHashTable. Can only be called after + * g_hash_table_iter_next() returned %TRUE, and cannot be called more + * than once for the same key/value pair. + * + * If the #GHashTable was created using g_hash_table_new_full(), the + * key and value are freed using the supplied destroy functions, otherwise + * you have to make sure that any dynamically allocated values are freed + * yourself. + * + * Since: 2.16 + **/ +void +g_hash_table_iter_remove (GHashTableIter *iter) +{ + iter_remove_or_steal ((RealIter *) iter, TRUE); +} + +/** + * g_hash_table_iter_steal(): + * @iter: an initialized #GHashTableIter. + * + * Removes the key/value pair currently pointed to by the iterator + * from its associated #GHashTable, without calling the key and value + * destroy functions. Can only be called after + * g_hash_table_iter_next() returned %TRUE, and cannot be called more + * than once for the same key/value pair. + * + * Since: 2.16 + **/ +void +g_hash_table_iter_steal (GHashTableIter *iter) +{ + iter_remove_or_steal ((RealIter *) iter, FALSE); +} + /** * g_hash_table_ref: @@ -531,6 +760,10 @@ g_hash_table_insert_internal (GHashTable *hash_table, *node_ptr = node; hash_table->nnodes++; g_hash_table_maybe_resize (hash_table); + +#ifndef G_DISABLE_ASSERT + hash_table->version++; +#endif } } @@ -606,6 +839,10 @@ g_hash_table_remove_internal (GHashTable *hash_table, g_hash_table_remove_node (hash_table, &node_ptr, notify); g_hash_table_maybe_resize (hash_table); +#ifndef G_DISABLE_ASSERT + hash_table->version++; +#endif + return TRUE; } @@ -665,6 +902,11 @@ g_hash_table_remove_all (GHashTable *hash_table) { g_return_if_fail (hash_table != NULL); +#ifndef G_DISABLE_ASSERT + if (hash_table->nnodes != 0) + hash_table->version++; +#endif + g_hash_table_remove_all_nodes (hash_table, TRUE); g_hash_table_maybe_resize (hash_table); } @@ -683,6 +925,11 @@ g_hash_table_steal_all (GHashTable *hash_table) { g_return_if_fail (hash_table != NULL); +#ifndef G_DISABLE_ASSERT + if (hash_table->nnodes != 0) + hash_table->version++; +#endif + g_hash_table_remove_all_nodes (hash_table, FALSE); g_hash_table_maybe_resize (hash_table); } @@ -726,6 +973,11 @@ g_hash_table_foreach_remove_or_steal (GHashTable *hash_table, g_hash_table_maybe_resize (hash_table); +#ifndef G_DISABLE_ASSERT + if (deleted > 0) + hash_table->version++; +#endif + return deleted; } @@ -741,6 +993,9 @@ g_hash_table_foreach_remove_or_steal (GHashTable *hash_table, * the #GHashTable, they are used to free the memory allocated for the removed * keys and values. * + * See #GHashTableIterator for an alternative way to loop over the + * key/value pairs in the hash table. + * * Return value: the number of key/value pairs removed. **/ guint @@ -764,6 +1019,9 @@ g_hash_table_foreach_remove (GHashTable *hash_table, * If the function returns %TRUE, then the key/value pair is removed from the * #GHashTable, but no key or value destroy functions are called. * + * See #GHashTableIterator for an alternative way to loop over the + * key/value pairs in the hash table. + * * Return value: the number of key/value pairs removed. **/ guint diff --git a/glib/ghash.h b/glib/ghash.h index 8542665..17ca7de 100644 --- a/glib/ghash.h +++ b/glib/ghash.h @@ -38,6 +38,19 @@ typedef gboolean (*GHRFunc) (gpointer key, gpointer value, gpointer user_data); +typedef struct _GHashTableIter GHashTableIter; + +struct _GHashTableIter +{ + /*< private >*/ + gpointer dummy1; + gpointer dummy2; + gpointer dummy3; + int dummy4; + gboolean dummy5; + gpointer dummy6; +}; + /* Hash tables */ GHashTable* g_hash_table_new (GHashFunc hash_func, @@ -81,6 +94,15 @@ guint g_hash_table_size (GHashTable *hash_table); GList * g_hash_table_get_keys (GHashTable *hash_table); GList * g_hash_table_get_values (GHashTable *hash_table); +void g_hash_table_iter_init (GHashTableIter *iter, + GHashTable *hash_table); +gboolean g_hash_table_iter_next (GHashTableIter *iter, + gpointer *key, + gpointer *value); +GHashTable* g_hash_table_iter_get_hash_table (GHashTableIter *iter); +void g_hash_table_iter_remove (GHashTableIter *iter); +void g_hash_table_iter_steal (GHashTableIter *iter); + /* keeping hash tables alive */ GHashTable* g_hash_table_ref (GHashTable *hash_table); void g_hash_table_unref (GHashTable *hash_table); diff --git a/glib/glib.symbols b/glib/glib.symbols index d1fa33d..c9674b7 100644 --- a/glib/glib.symbols +++ b/glib/glib.symbols @@ -385,6 +385,11 @@ g_hash_table_replace g_hash_table_size g_hash_table_steal g_hash_table_steal_all +g_hash_table_iter_init +g_hash_table_iter_next +g_hash_table_iter_get_hash_table +g_hash_table_iter_remove +g_hash_table_iter_steal #endif #endif diff --git a/tests/hash-test.c b/tests/hash-test.c index 80c2ffb..23411c3 100644 --- a/tests/hash-test.c +++ b/tests/hash-test.c @@ -44,7 +44,50 @@ int array[10000]; +static void +fill_hash_table_and_array (GHashTable *hash_table) +{ + int i; + for (i = 0; i < 10000; i++) + { + array[i] = i; + g_hash_table_insert (hash_table, &array[i], &array[i]); + } +} + +static void +init_result_array (int result_array[10000]) +{ + int i; + + for (i = 0; i < 10000; i++) + result_array[i] = -1; +} + +static void +verify_result_array (int array[10000]) +{ + int i; + + for (i = 0; i < 10000; i++) + g_assert (array[i] == i); +} + +static void +handle_pair (gpointer key, gpointer value, int result_array[10000]) +{ + int n; + + g_assert (key == value); + + n = *((int *) value); + + g_assert (n >= 0 && n < 10000); + g_assert (result_array[n] == -1); + + result_array[n] = n; +} static gboolean my_hash_callback_remove (gpointer key, @@ -75,8 +118,7 @@ my_hash_callback (gpointer key, gpointer value, gpointer user_data) { - int *d = value; - *d = 1; + handle_pair (key, value, user_data); } static guint @@ -347,13 +389,12 @@ main (int argc, gint *pvalue; GList *keys, *values; gint keys_len, values_len; + GHashTableIter iter; + gpointer ikey, ivalue; + int result_array[10000]; hash_table = g_hash_table_new (my_hash, my_hash_equal); - for (i = 0; i < 10000; i++) - { - array[i] = i; - g_hash_table_insert (hash_table, &array[i], &array[i]); - } + fill_hash_table_and_array (hash_table); pvalue = g_hash_table_find (hash_table, find_first, &value); if (!pvalue || *pvalue != value) g_assert_not_reached(); @@ -373,21 +414,32 @@ main (int argc, g_list_free (keys); g_list_free (values); - - g_hash_table_foreach (hash_table, my_hash_callback, NULL); + init_result_array (result_array); + g_hash_table_iter_init (&iter, hash_table); for (i = 0; i < 10000; i++) - if (array[i] == 0) - g_assert_not_reached(); + { + g_assert (g_hash_table_iter_next (&iter, &ikey, &ivalue)); + + handle_pair (ikey, ivalue, result_array); + + if (i % 2) + g_hash_table_iter_remove (&iter); + } + g_assert (! g_hash_table_iter_next (&iter, &ikey, &ivalue)); + g_assert (g_hash_table_size (hash_table) == 5000); + verify_result_array (result_array); + + fill_hash_table_and_array (hash_table); + + init_result_array (result_array); + g_hash_table_foreach (hash_table, my_hash_callback, result_array); + verify_result_array (result_array); for (i = 0; i < 10000; i++) g_hash_table_remove (hash_table, &array[i]); - for (i = 0; i < 10000; i++) - { - array[i] = i; - g_hash_table_insert (hash_table, &array[i], &array[i]); - } + fill_hash_table_and_array (hash_table); if (g_hash_table_foreach_remove (hash_table, my_hash_callback_remove, NULL) != 5000 || g_hash_table_size (hash_table) != 5000) -- 2.7.4