GNOME Bugzilla – Bug 573623
[API] Array binary search utility function
Last modified: 2009-03-02 15:21:04 UTC
Hi, attached is a patch that adds an array binary search utility function to core/gstutils. This is useful for all our element-internal seek/index tables to provide faster searching. Currently all (or almost all?) elements are doing a linear search although the array is sorted, resulting in a longer search time for no reason.
Created attachment 129780 [details] [review] binsearch.diff Please review, I'd like to commit this ASAP :)
Looks cool. I like that the prototype is the same as qsort().
Looks useful. Some nitpicks (feel free to ignore any or all): - GstSearchMode docs say "The different types of URI direction." (and should have a Since: tag) - gst_search_mode_get_type() should be g_type_class_ref()'ed in init_post() in gst/gst.c - naming: I think it'd be nice to avoid abbreviations like 'binsearch' (there's no chance in hell anyone is going to fit a call into one line of code anyway, so we may just as well spell it out, no?) - "total_elements" => "num_elements"? - "size" => "element_size" ? - "GCompareDataFunc search_func" - is a GCompareDataFunc really the most appropriate, or shouldn't we rather define our own? (GCompareDataFunc implies that search_data is of the same type as array elements, doesn't it? Might be confusing ...) - docs: "comparision" => comparison
Thanks, I've changed all this except the GCompareDataFunc. I've clarified in the docs that the search_data is always passed as second argument to that function and thus is not required to be the same type as the array elements. commit 3c6448c64e519fd1ca2c75966d37cbbae975c7e2 Author: Sebastian Dröge <sebastian.droege@collabora.co.uk> Date: Mon Mar 2 16:17:45 2009 +0100 API: Add gst_util_array_binary_search() for binary searchs on a sorted array This will be mostly useful in all elements that have some kind of internal seek/index table. Currently almost all of them (or even all of them) are using a linear search although the used array is already sorted, wasting some CPU time without good reason. Fixes bug #573623.