GNOME Bugzilla – Bug 630336
few ideas for GList and GHashTable
Last modified: 2018-05-24 12:46:46 UTC
Using GList and GHashTable, I found need for some functions that are missing. Some of them are trivial enhancements, that can be written on few lines, other cannot be written outside without performance loss or use of private structures. Please let me know whether there is any interest for patch for particular functions. I have been thinking about optimization of this task: oldvalue = g_hash_table_lookup (table, key); /* first lookup */ if (something (key, oldvalue, value)) g_hash_table_insert (table, newkey, value); /* second lookup */ This is not effective: You need two lookups, but one lookup may be enough. Now imagine, that the value is GList and you need to do g_list_something with it. You surely don't want to destroy the old list, just store the new list head reference. Reference: bug 596192 You can do it by g_hash_table_steal(), but it requires third lookup. It could be fixed by: - Define g_hash_table_replace(), an alternative of g_hash_table_insert() that does not call destructor of the old value. To get everything in a single lookup, we would need: Solution 1: Make GHashNode available: - Publickly define (probably opaque) GHashNode. - Define g_hash_node_get_key (GHashNode *node), g_hash_node_get_value (GHashNode *node) and g_hash_node_insert_value (GHashNode *node) (with calling destructor of the old value) g_hash_node_replace_value (GHashNode *node) (without calling destructor) (making them inline would create faster code but hardcode the ABI) - It would be nice to make g_hash_table_remove_node() public (e. g. via wrallers g_hash_node_steal and g_hash_node_remove). - Define GHashNode counterpart to existing functions that read key or return return value. Solution 2: Define function for arbitrary value operation in a single step: For example define g_hash_table_lookup_and_alter would() that will have a value processing function as an argument. This solution seems to be uncomforable: Each operation needs custom callback, there is no easy way to automatically call destructor, so the callback would have to call destructor explicitly. g_list_index_custom: Just like g_list_index, but accepts GCompareFunc line g_list_find_custom. G_COMPARE_FUNC and G_EQUAL_FUNC retype of GEqualFunc to GCompareFunc wherever only equity is importang. GEqualFunc: Documentation should refer to instances present in glib (For example: You need to find string in g_list_index_custom. g_str_equal may do exactly what you need.) Reference: https://bugs.freedesktop.org/show_bug.cgi?id=30214
> Solution 1: Make GHashNode available: NAK
I anything, this would be a pair of new GHashTableIter functions: gboolean g_hash_table_iter_lookup (GHashTableIter *iter, gpointer key, gpointer *value); void g_hash_table_iter_replace (GHashTableIter *iter, gpointer value); not really sure its worth it, though. Some people would want to be able to replace the keys, too.
Bug 639634 has another api proposal that might work for you.
g_hash_table_iter_replace has been added meanwhile.
new functions we would need: // return TRUE if key is in the table, and sets iter // if key not in the table, iter is unmodified gboolean g_hash_table_iter_lookup (GHashTable *table, gconstpointer key, GHashTableIter *iter); // if key not in table, copy key and insert, set iter and return TRUE // if key already in table, just set iter and return FALSE (no copy made) gboolean g_hash_table_iter_insert (GHashTable *table, gconstpointer key, GBoxedCopyFunc copy_func, GHashTableIter *iter); // gets value at iter gpointer g_hash_table_iter_get_value (GHashTableIter *iter); The question is what g_hash_table_iter_insert() does about the value. I guess inserting NULL makes a lot of sense, because having an iterator pointing to a key with no value is weird. On the other hand, you would expect _replace() would call destroynotify on the previous value, even if it was NULL, and that might cause trouble... One way around this could be to provide a default value to the iter_insert() operation that would be used if the item did not already exist in the table (in the same way that the key is only copied in this case).
Created attachment 261336 [details] [review] Add more hash iter functions We add new functions g_hash_table_iter_lookup(), g_hash_table_iter_insert() and g_hash_table_iter_get(). These make it possible to avoid double lookups for operations such as lookup-modify-remove or lookup-and-insert-if-not-found.
I'd like to see links to potential real-world users in the GNOME codebase. I think _iter_insert() is a bad name since it's quite different from g_hash_table_insert(). Also the _iter prefix implies they *operate* on GHashTableIter, but really they initialize a new one for you. g_hash_table_cond_insert() ?
(In reply to comment #7) > I'd like to see links to potential real-world users in the GNOME codebase. > > I think _iter_insert() is a bad name since it's quite different from > g_hash_table_insert(). Also the _iter prefix implies they *operate* on > GHashTableIter, but really they initialize a new one for you. They don't. I wasn't happy with that aspect of Ryans api sketch, so I changed it to operate on an iterator, and expect an initialized iter as their first argument.
I don't like the two-step approach. g_hash_table_iter_init() ought to be used to initialise an iterator for iterating. It should not be part of the use of these APIs. I think we could dodge the issue by renaming to g_hash_table_lookup_iter(), etc. I'm not sure I like the implicit insert of NULL. This will cause problems in a lot of reasonable cases (like if your table has objects and your freefunc is g_object_unref). Having to write a g_object_unref0 to care for the edge case between insert_iter() and actually setting the value in the iter is strange. As a 3rd suggestion, perhaps we could rather say that the iter is in some undefined state and you __must__ do a _replace_value() or you corrupt the table. It's not _too_ difficult to get that right...
-- GitLab Migration Automatic Message -- This bug has been migrated to GNOME's GitLab instance and has been closed from further activity. You can subscribe and participate further through the new bug through this link to our GitLab instance: https://gitlab.gnome.org/GNOME/glib/issues/349.