GNOME Bugzilla – Bug 756316
GSequence should provide fast api to check if empty
Last modified: 2015-10-15 19:55:38 UTC
Often I find myself adding short-circuits to avoid costly lookups (even when using GSequence). Especially when a GCompareFunc is expensive. So people don't do the wrong thing here and call !g_sequence_get_length(), we should provide API that does the fast O(1) thing. if (g_sequence_get_begin_iter (seq) == g_sequence_get_end_iter (seq)) vs if (g_sequence_is_empty (seq)) While I generally don't advise using data-structures you don't understand the implementation of, i do think this makes the code more approachable to those not familiar with the implementation. Willing to provide a quick patch if the suggestion isn't immediately nixed :)
Aha, it turns out get_length() is actually faster than the comparison above, so that further shows how valuable this could be. get_length() has a direct pointer to end iter, and then walks to the root (node->parent->parent, etc), which then has access to the number of nodes directly. Compare to get_begin_iter() which has to walk to the root and then to the left. So two things: O(h) is the fastest we can do here, where h is the height of the tree. We want to use !get_length() to do only half the work of comparing begin and end iters.
And of course I'm dumb again. We can just check pointers on seq->end_node.
I think we should have such an API and we shouldn't let you write it ;-P
Created attachment 312980 [details] [review] O(1) implementation of g_sequence_is_empty() agreed, but here is something.
Created attachment 312981 [details] [review] O(1) implementation of g_sequence_is_empty() dont check right, we are the end iter.
Created attachment 312982 [details] [review] O(1) implementation of g_sequence_is_empty() simplify test case last update i swear ;)
Created attachment 312984 [details] [review] O(1) implementation of g_sequence_is_empty() Jasper didn't like my copying of the previous gtk-doc (and he's right). So breaking my promise and updating again with slightly less insulting documentation.
Anyone mind acking this? Seems like relatively easy verification.
Review of attachment 312984 [details] [review]: Other than that cosmetic fix, looks good to me. Feel free to push with that cleanup ::: glib/tests/sequence.c @@ +1364,3 @@ + + seq = g_sequence_new (NULL); + g_assert_cmpint (TRUE, ==, g_sequence_is_empty (seq)); Would be nicer to use g_assert_true and g_assert_false, instead of comparing booleans as integers