From 3c6448c64e519fd1ca2c75966d37cbbae975c7e2 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Sebastian=20Dr=C3=B6ge?= Date: Mon, 2 Mar 2009 16:17:45 +0100 Subject: [PATCH] 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. --- docs/gst/gstreamer-sections.txt | 4 ++ gst/gst.c | 1 + gst/gstutils.c | 88 ++++++++++++++++++++++++++++++++++ gst/gstutils.h | 18 +++++++ tests/check/gst/gstutils.c | 103 ++++++++++++++++++++++++++++++++++++++++ win32/common/libgstreamer.def | 2 + 6 files changed, 216 insertions(+) diff --git a/docs/gst/gstreamer-sections.txt b/docs/gst/gstreamer-sections.txt index c9ebe19..1bc5655 100644 --- a/docs/gst/gstreamer-sections.txt +++ b/docs/gst/gstreamer-sections.txt @@ -2363,10 +2363,14 @@ gst_util_seqnum_compare gst_util_set_object_arg gst_util_set_value_from_string gst_util_get_timestamp +GstSearchMode +gst_util_array_binary_search GST_HAVE_UNALIGNED_ACCESS gst_util_guint64_to_gdouble gst_util_gdouble_to_guint64 +GST_TYPE_SEARCH_MODE +gst_search_mode_get_type
diff --git a/gst/gst.c b/gst/gst.c index d6fa0d4..4085e3d 100644 --- a/gst/gst.c +++ b/gst/gst.c @@ -1073,6 +1073,7 @@ init_post (GOptionContext * context, GOptionGroup * group, gpointer data, g_type_class_ref (gst_uri_type_get_type ()); g_type_class_ref (gst_parse_error_get_type ()); g_type_class_ref (gst_parse_flags_get_type ()); + g_type_class_ref (gst_search_mode_get_type ()); gst_structure_get_type (); _gst_value_initialize (); diff --git a/gst/gstutils.c b/gst/gstutils.c index 7c02f2a..a5ab233 100644 --- a/gst/gstutils.c +++ b/gst/gstutils.c @@ -3624,3 +3624,91 @@ gst_util_get_timestamp (void) return GST_TIMEVAL_TO_TIME (now); #endif } + +/** + * gst_util_array_binary_search: + * @array: the sorted input array + * @num_elements: number of elements in the array + * @element_size: size of every element in bytes + * @search_func: function to compare two elements, @search_data will always be passed as second argument + * @mode: search mode that should be used + * @search_data: element that should be found + * @user_data: data to pass to @search_func + * + * Searches inside @array for @search_data by using the comparison function + * @search_func. @array must be sorted ascending. + * + * As @search_data is always passed as second argument to @search_func it's + * not required that @search_data has the same type as the array elements. + * + * The complexity of this search function is O(log (num_elements)). + * + * Returns: The address of the found element or %NULL if nothing was found + * + * Since: 0.10.23 + */ +gpointer +gst_util_array_binary_search (gpointer array, guint num_elements, + gsize element_size, GCompareDataFunc search_func, GstSearchMode mode, + gconstpointer search_data, gpointer user_data) +{ + glong left = 0, right = num_elements - 1, m; + gint ret; + guint8 *data = (guint8 *) array; + + g_return_val_if_fail (array != NULL, NULL); + g_return_val_if_fail (element_size > 0, NULL); + g_return_val_if_fail (search_func != NULL, NULL); + + /* 0. No elements => return NULL */ + if (num_elements == 0) + return NULL; + + /* 1. If search_data is before the 0th element return the 0th element */ + ret = search_func (data, search_data, user_data); + if ((ret >= 0 && mode == GST_SEARCH_MODE_AFTER) || ret == 0) + return data; + else if (ret > 0) + return NULL; + + /* 2. If search_data is after the last element return the last element */ + ret = + search_func (data + (num_elements - 1) * element_size, search_data, + user_data); + if ((ret <= 0 && mode == GST_SEARCH_MODE_BEFORE) || ret == 0) + return data + (num_elements - 1) * element_size; + else if (ret < 0) + return NULL; + + /* 3. else binary search */ + while (TRUE) { + m = left + (right - left) / 2; + + ret = search_func (data + m * element_size, search_data, user_data); + + if (ret == 0) { + return data + m * element_size; + } else if (ret < 0) { + left = m + 1; + } else { + right = m - 1; + } + + /* No exact match found */ + if (right < left) { + if (mode == GST_SEARCH_MODE_EXACT) { + return NULL; + } else if (mode == GST_SEARCH_MODE_AFTER) { + if (ret < 0) + return (m < num_elements) ? data + (m + 1) * element_size : NULL; + else + return data + m * element_size; + } else { + if (ret < 0) + return data + m * element_size; + else + return (m > 0) ? data + (m - 1) * element_size : NULL; + } + } + } +} diff --git a/gst/gstutils.h b/gst/gstutils.h index 9a434bf..e2f5301 100644 --- a/gst/gstutils.h +++ b/gst/gstutils.h @@ -1134,6 +1134,24 @@ GstElement * gst_parse_bin_from_description_full (const gchar * b GstClockTime gst_util_get_timestamp (void); +/** + * GstSearchMode: + * @GST_SEARCH_MODE_EXACT : Only search for exact matches. + * @GST_SEARCH_MODE_BEFORE: Search for an exact match or the element just before. + * @GST_SEARCH_MODE_AFTER : Search for an exact match or the element just after. + * + * The different search modes. + * + * Since: 0.10.23 + */ +typedef enum { + GST_SEARCH_MODE_EXACT = 0, + GST_SEARCH_MODE_BEFORE, + GST_SEARCH_MODE_AFTER +} GstSearchMode; + +gpointer gst_util_array_binary_search (gpointer array, guint num_elements, gsize element_size, GCompareDataFunc search_func, GstSearchMode mode, gconstpointer search_data, gpointer user_data); + G_END_DECLS #endif /* __GST_UTILS_H__ */ diff --git a/tests/check/gst/gstutils.c b/tests/check/gst/gstutils.c index 3b619a0..a98b112 100644 --- a/tests/check/gst/gstutils.c +++ b/tests/check/gst/gstutils.c @@ -610,6 +610,108 @@ GST_START_TEST (test_set_value_from_string) GST_END_TEST; +static gint +_binary_search_compare (guint32 * a, guint32 * b) +{ + return *a - *b; +} + +GST_START_TEST (test_binary_search) +{ + guint32 data[257]; + guint32 *match; + guint32 search_element = 121 * 2; + guint i; + + for (i = 0; i < 257; i++) + data[i] = (i + 1) * 2; + + match = + (guint32 *) gst_util_array_binary_search (data, 257, sizeof (guint32), + (GCompareDataFunc) _binary_search_compare, GST_SEARCH_MODE_EXACT, + &search_element, NULL); + fail_unless (match != NULL); + fail_unless_equals_int (match - data, 120); + + match = + (guint32 *) gst_util_array_binary_search (data, 257, sizeof (guint32), + (GCompareDataFunc) _binary_search_compare, GST_SEARCH_MODE_BEFORE, + &search_element, NULL); + fail_unless (match != NULL); + fail_unless_equals_int (match - data, 120); + + match = + (guint32 *) gst_util_array_binary_search (data, 257, sizeof (guint32), + (GCompareDataFunc) _binary_search_compare, GST_SEARCH_MODE_AFTER, + &search_element, NULL); + fail_unless (match != NULL); + fail_unless_equals_int (match - data, 120); + + search_element = 0; + match = + (guint32 *) gst_util_array_binary_search (data, 257, sizeof (guint32), + (GCompareDataFunc) _binary_search_compare, GST_SEARCH_MODE_EXACT, + &search_element, NULL); + fail_unless (match == NULL); + + match = + (guint32 *) gst_util_array_binary_search (data, 257, sizeof (guint32), + (GCompareDataFunc) _binary_search_compare, GST_SEARCH_MODE_AFTER, + &search_element, NULL); + fail_unless (match != NULL); + fail_unless_equals_int (match - data, 0); + + match = + (guint32 *) gst_util_array_binary_search (data, 257, sizeof (guint32), + (GCompareDataFunc) _binary_search_compare, GST_SEARCH_MODE_BEFORE, + &search_element, NULL); + fail_unless (match == NULL); + + search_element = 1000; + match = + (guint32 *) gst_util_array_binary_search (data, 257, sizeof (guint32), + (GCompareDataFunc) _binary_search_compare, GST_SEARCH_MODE_EXACT, + &search_element, NULL); + fail_unless (match == NULL); + + match = + (guint32 *) gst_util_array_binary_search (data, 257, sizeof (guint32), + (GCompareDataFunc) _binary_search_compare, GST_SEARCH_MODE_AFTER, + &search_element, NULL); + fail_unless (match == NULL); + + match = + (guint32 *) gst_util_array_binary_search (data, 257, sizeof (guint32), + (GCompareDataFunc) _binary_search_compare, GST_SEARCH_MODE_BEFORE, + &search_element, NULL); + fail_unless (match != NULL); + fail_unless_equals_int (match - data, 256); + + search_element = 121 * 2 - 1; + match = + (guint32 *) gst_util_array_binary_search (data, 257, sizeof (guint32), + (GCompareDataFunc) _binary_search_compare, GST_SEARCH_MODE_EXACT, + &search_element, NULL); + fail_unless (match == NULL); + + match = + (guint32 *) gst_util_array_binary_search (data, 257, sizeof (guint32), + (GCompareDataFunc) _binary_search_compare, GST_SEARCH_MODE_AFTER, + &search_element, NULL); + fail_unless (match != NULL); + fail_unless_equals_int (match - data, 120); + + match = + (guint32 *) gst_util_array_binary_search (data, 257, sizeof (guint32), + (GCompareDataFunc) _binary_search_compare, GST_SEARCH_MODE_BEFORE, + &search_element, NULL); + fail_unless (match != NULL); + fail_unless_equals_int (match - data, 119); + +} + +GST_END_TEST; + static Suite * gst_utils_suite (void) { @@ -630,6 +732,7 @@ gst_utils_suite (void) tcase_add_test (tc_chain, test_element_found_tags); tcase_add_test (tc_chain, test_element_unlink); tcase_add_test (tc_chain, test_set_value_from_string); + tcase_add_test (tc_chain, test_binary_search); return s; } diff --git a/win32/common/libgstreamer.def b/win32/common/libgstreamer.def index 80b56b4..274c934 100644 --- a/win32/common/libgstreamer.def +++ b/win32/common/libgstreamer.def @@ -784,6 +784,7 @@ EXPORTS gst_registry_xml_write_cache gst_resource_error_get_type gst_resource_error_quark + gst_search_mode_get_type gst_seek_flags_get_type gst_seek_type_get_type gst_segment_clip @@ -970,6 +971,7 @@ EXPORTS gst_uri_protocol_is_supported gst_uri_protocol_is_valid gst_uri_type_get_type + gst_util_array_binary_search gst_util_dump_mem gst_util_gdouble_to_guint64 gst_util_get_timestamp -- 2.7.4