libnm: add _nm_utils_ptrarray_find_binary_search() helper

3 files changed, 140 insertions, 0 deletions

diff --git a/libnm-core/nm-core-internal.h b/libnm-core/nm-core-internal.h
index 27288df022..f9ae42ecdd 100644
--- a/libnm-core/nm-core-internal.h
+++ b/libnm-core/nm-core-internal.h
@@ -114,6 +114,8 @@ GPtrArray *_nm_utils_copy_object_array (const GPtrArray *array);
 
 gssize _nm_utils_ptrarray_find_first (gpointer *list, gssize len, gconstpointer needle);
 
+gssize _nm_utils_ptrarray_find_binary_search (gpointer *list, gsize len, gpointer needle, GCompareDataFunc cmpfcn, gpointer user_data);
+
 gboolean    _nm_utils_string_in_list   (const char *str,
                                         const char **valid_strings);
 
diff --git a/libnm-core/nm-utils.c b/libnm-core/nm-utils.c
index 8ce59b0eeb..f9325e2a47 100644
--- a/libnm-core/nm-utils.c
+++ b/libnm-core/nm-utils.c
@@ -657,6 +657,39 @@ _nm_utils_ptrarray_find_first (gpointer *list, gssize len, gconstpointer needle)
 	return -1;
 }
 
+gssize
+_nm_utils_ptrarray_find_binary_search (gpointer *list, gsize len, gpointer needle, GCompareDataFunc cmpfcn, gpointer user_data)
+{
+	gssize imin, imax, imid;
+	int cmp;
+
+	g_return_val_if_fail (list || !len, ~((gssize) 0));
+	g_return_val_if_fail (cmpfcn, ~((gssize) 0));
+
+	imin = 0;
+	if (len == 0)
+		return ~imin;
+
+	imax = len - 1;
+
+	while (imin <= imax) {
+		imid = imin + (imax - imin) / 2;
+
+		cmp = cmpfcn (list[imid], needle, user_data);
+		if (cmp == 0)
+			return imid;
+
+		if (cmp < 0)
+			imin = imid + 1;
+		else
+			imax = imid - 1;
+	}
+
+	/* return the inverse of @imin. This is a negative number, but
+	 * also is ~imin the position where the value should be inserted. */
+	return ~imin;
+}
+
 GVariant *
 _nm_utils_bytes_to_dbus (const GValue *prop_value)
 {
diff --git a/libnm-core/tests/test-general.c b/libnm-core/tests/test-general.c
index 2f330357d6..082015c040 100644
--- a/libnm-core/tests/test-general.c
+++ b/libnm-core/tests/test-general.c
@@ -4484,6 +4484,110 @@ test_g_ptr_array_insert (void)
 
 /******************************************************************************/
 
+static int
+_test_find_binary_search_cmp (gconstpointer a, gconstpointer b, gpointer dummy)
+{
+	int ia, ib;
+
+	ia = GPOINTER_TO_INT (a);
+	ib = GPOINTER_TO_INT (b);
+
+	if (ia == ib)
+		return 0;
+	if (ia < ib)
+		return -1;
+	return 1;
+}
+
+static void
+_test_find_binary_search_do (const int *array, gsize len)
+{
+	gsize i;
+	gssize idx;
+	gs_free gpointer *parray = g_new (gpointer, len);
+	const int needle = 0;
+	gpointer pneedle = GINT_TO_POINTER (needle);
+	gssize expected_result;
+
+	for (i = 0; i < len; i++)
+		parray[i] = GINT_TO_POINTER (array[i]);
+
+	expected_result = _nm_utils_ptrarray_find_first (parray, len, pneedle);
+
+	idx = _nm_utils_ptrarray_find_binary_search (parray, len, pneedle, _test_find_binary_search_cmp, NULL);
+	if (expected_result >= 0)
+		g_assert_cmpint (expected_result, ==, idx);
+	else {
+		gssize idx2 = ~idx;
+		g_assert_cmpint (idx, <, 0);
+
+		g_assert (idx2 >= 0);
+		g_assert (idx2 <= len);
+		g_assert (idx2 - 1 < 0 || _test_find_binary_search_cmp (parray[idx2 - 1], pneedle, NULL) < 0);
+		g_assert (idx2 >= len || _test_find_binary_search_cmp (parray[idx2], pneedle, NULL) > 0);
+	}
+	for (i = 0; i < len; i++) {
+		int cmp;
+
+		cmp = _test_find_binary_search_cmp (parray[i], pneedle, NULL);
+		if (cmp == 0) {
+			g_assert (pneedle == parray[i]);
+			g_assert (idx >= 0);
+			g_assert (i == idx);
+		} else {
+			g_assert (pneedle != parray[i]);
+			if (cmp < 0) {
+				if (idx < 0)
+					g_assert (i < ~idx);
+				else
+					g_assert (i < idx);
+			} else {
+				if (idx < 0)
+					g_assert (i >= ~idx);
+				else
+					g_assert (i >= idx);
+			}
+		}
+	}
+}
+#define test_find_binary_search_do(...) \
+	G_STMT_START { \
+		const int _array[] = { __VA_ARGS__ } ; \
+		_test_find_binary_search_do (_array, G_N_ELEMENTS (_array)); \
+	} G_STMT_END
+
+static void
+test_nm_utils_ptrarray_find_binary_search (void)
+{
+#define _NOT(idx) (~ ((gssize) (idx)))
+	test_find_binary_search_do (            0);
+	test_find_binary_search_do (        -1, 0);
+	test_find_binary_search_do (    -2, -1, 0);
+	test_find_binary_search_do (-3, -2, -1, 0);
+	test_find_binary_search_do (            0, 1);
+	test_find_binary_search_do (            0, 1, 2);
+	test_find_binary_search_do (        -1, 0, 1, 2);
+	test_find_binary_search_do (    -2, -1, 0, 1, 2);
+	test_find_binary_search_do (-3, -2, -1, 0, 1, 2);
+	test_find_binary_search_do (-3, -2, -1, 0, 1, 2);
+	test_find_binary_search_do (-3, -2, -1, 0, 1, 2, 3);
+	test_find_binary_search_do (-3, -2, -1, 0, 1, 2, 3, 4);
+
+	test_find_binary_search_do (        -1);
+	test_find_binary_search_do (    -2, -1);
+	test_find_binary_search_do (-3, -2, -1);
+	test_find_binary_search_do (            1);
+	test_find_binary_search_do (            1, 2);
+	test_find_binary_search_do (        -1, 1, 2);
+	test_find_binary_search_do (    -2, -1, 1, 2);
+	test_find_binary_search_do (-3, -2, -1, 1, 2);
+	test_find_binary_search_do (-3, -2, -1, 1, 2);
+	test_find_binary_search_do (-3, -2, -1, 1, 2, 3);
+	test_find_binary_search_do (-3, -2, -1, 1, 2, 3, 4);
+}
+
+/******************************************************************************/
+
 NMTST_DEFINE ();
 
 int main (int argc, char **argv)
@@ -4587,6 +4691,7 @@ int main (int argc, char **argv)
 	g_test_add_func ("/core/general/_nm_utils_ascii_str_to_int64", test_nm_utils_ascii_str_to_int64);
 	g_test_add_func ("/core/general/nm_utils_is_power_of_two", test_nm_utils_is_power_of_two);
 	g_test_add_func ("/core/general/_glib_compat_g_ptr_array_insert", test_g_ptr_array_insert);
+	g_test_add_func ("/core/general/_nm_utils_ptrarray_find_binary_search", test_nm_utils_ptrarray_find_binary_search);
 
 	g_test_add_func ("/core/general/_nm_utils_dns_option_validate", test_nm_utils_dns_option_validate);
 	g_test_add_func ("/core/general/_nm_utils_dns_option_find_idx", test_nm_utils_dns_option_find_idx);