GNOME Bugzilla – Bug 617254
Missing g_sequence_lookup
Last modified: 2010-12-20 16:32:28 UTC
I need a function to lookup an item inside a GSequence. Of course I first though g_sequence_search() would be that, but it turned out to have the worst naming ever. So I would like to propose adding: GSequenceIter * g_sequence_lookup (GSequence *self, gpointer data, GCompareDataFunc cmp_func, gpointer cmp_data); That function will return the first item found where cmp_func returns 0, or end iter (or NULL?) if not found. Of course g_sequence_lookup_iter() variant can also be added.
Created attachment 159973 [details] [review] proposed patch
Created attachment 159974 [details] [review] proposed patch
Why does g_sequence_search() have the "worst naming ever". See bug 548666.
Because it doesn't really search an item, but tell where that item would need to be inserted using g_sequence_insert_before. I found that really confusing... But anyway, I understand that the example in bug #548666 comment #8 works, that's what I'm doing atm, but I think that trick is not trivial (at least adding the example code in the API doc is needed), it clearly deserve an helper API for that. The reason I didn't implement g_sequence_lookup() like that, is simply that it's a wast of time to search for next item, then get the prev one, it is calling the cmp function more than needed. Also in the case the sequence has many items equal, we just don't know if the user prefer having the first iter or the last iter equal, so I prefer giving no guarantee in the API and save some calls to cmp() function, then user can use _prev() and _next() if he wants.
I'm not sure I understand the argument about calling the compare function too much. The prev() function doesn't call the compare function, and searching for the _last_ of a bunch of items is just as fast as searching for the first one. So it seems to me that there are these cases: - If there is only one item in the sequence, then the overhead is just one call to prev() - If there are multiple items that compare equal, then there are three cases: - You don't want a particular one. In that case, just calling prev() works - You want a particular one. In that case there is no way around scanning through all the items that compare equal and scanning backwards is just as fast as scanning forwards. - You want the first one. In that case, yes, we could do better with a function that searches directly for the first item. However, in that case, my question is, what are you trying to do?
(In reply to comment #5) > - If there is only one item in the sequence, then the overhead is just one call > to prev() Actually 1 call to next() + one call to prev() + one call to compare() in the implementation you did in bug 548666#c8. I agree it's not much (well, depends on the implementation of compare func) but still would be nice to avoid, ad I did in the attached patch. > - If there are multiple items that compare equal, then there are three cases: > > - You don't want a particular one. In that case, just calling prev() > works In that case g_sequence_search() called too much the compare() and next() function. Time wasted. > - You want a particular one. In that case there is no way around > scanning through all the items that compare equal and scanning backwards > is just as fast as scanning forwards. right > - You want the first one. In that case, yes, we could do better with a > function that searches directly for the first item. However, in that > case, my question is, what are you trying to do? Returning the first item is more consistent with list implementations, as GSequence's API try to be... Anyway, I think we have 3 choices: 1) Do not add a function that lookup an item, then we should add a code example in the doc of g_sequence_search() to tell how to use it to find an item. 2) Add a function like the one in bug #548666#c8 3) Apply the patches I attached here, which is the same as point 2 in the API, but slightly more optimized.
As proof that g_sequence_search() is not enough, and we really need a function that return an item: In my app I did the work around proposed in bug #548666 comment#8, and it leaded to weird crashes... that function does not take care if the sequence is empty, in which case the search will return end iter, and getting its prev will also return end iter... and so the compare func will get the data of end iter and crash. So really, we need a dedicated function for this.
I'm not really opposed to adding a new convenience function if that's useful, but I am not a glib maintainer and I can't approve or disapprove anything regarding it.
Patch can be found in that branch: http://git.collabora.co.uk/?p=user/xclaesse/glib.git;a=shortlog;h=refs/heads/bug617254
Looks like a harmless enough api addition. It would be good to add a note to the _search and _search_iter api docs along the lines of: If you are simply searching for an existing element of the sequence, consider using g_sequence_lookup().
Here is a branch rebased on master with a note in g_sequence_search() doc: http://git.collabora.co.uk/?p=user/xclaesse/glib.git;a=shortlog;h=refs/heads/sequence-lookup Is this fine for merging?
Yes, looks ok.
Cool, thanks for the review. Merged into master.