From 2ef43de2af9dbb1b1ea583639c7339afe9c09af0 Mon Sep 17 00:00:00 2001 From: Tim Janik Date: Mon, 25 Jun 2007 14:44:41 +0000 Subject: [PATCH] g_hash_table_find(), g_hash_table_foreach(): document performance caveats Mon Jun 25 16:43:13 2007 Tim Janik * glib/ghash.c: g_hash_table_find(), g_hash_table_foreach(): document performance caveats for linear order searches. svn path=/trunk/; revision=5587 --- ChangeLog | 5 +++++ glib/ghash.c | 18 +++++++++++++++--- 2 files changed, 20 insertions(+), 3 deletions(-) diff --git a/ChangeLog b/ChangeLog index 97ee40d3..16c08e79 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,8 @@ +Mon Jun 25 16:43:13 2007 Tim Janik + + * glib/ghash.c: g_hash_table_find(), g_hash_table_foreach(): + document performance caveats for linear order searches. + 2007-06-22 Mathias Hasselmann * glib/gstring.c: Use memcpy in g_string_append_vprintf (#57693). diff --git a/glib/ghash.c b/glib/ghash.c index 8eea09a2..30dbce5e 100644 --- a/glib/ghash.c +++ b/glib/ghash.c @@ -660,6 +660,9 @@ g_hash_table_foreach_remove_or_steal (GHashTable *hash_table, * be modified while iterating over it (you can't add/remove * items). To remove all items matching a predicate, use * g_hash_table_foreach_remove(). + * + * See g_hash_table_find() for performance caveats for linear + * order searches in contrast to g_hash_table_lookup(). **/ void g_hash_table_foreach (GHashTable *hash_table, @@ -686,10 +689,19 @@ g_hash_table_foreach (GHashTable *hash_table, * Calls the given function for key/value pairs in the #GHashTable until * @predicate returns %TRUE. The function is passed the key and value of * each pair, and the given @user_data parameter. The hash table may not - * be modified while iterating over it (you can't add/remove items). + * be modified while iterating over it (you can't add/remove items). + * + * Note, that hash tables are really only optimized for forward lookups, + * i.e. g_hash_table_lookup(). + * So code that frequently issues g_hash_table_find() or + * g_hash_table_foreach() (e.g. in the order of once per every entry in a + * hash table) should probably be reworked to use additional or different + * data structures for reverse lookups (keep in mind that an O(n) find/foreach + * operation issued for all n values in a hash table ends up needing O(n*n) + * operations). * - * Return value: The value of the first key/value pair is returned, for which - * func evaluates to %TRUE. If no pair with the requested property is found, + * Return value: The value of the first key/value pair is returned, for which + * func evaluates to %TRUE. If no pair with the requested property is found, * %NULL is returned. * * Since: 2.4 -- 2.34.1