utils: extend binary-search to return the first/last index

binary-search can find an index of a matching entry in a sorted
list. However, if the list contains multiple entries that compare
equal, it can be interesting to find the first/last entry. For example,
if you want to append new items after the last.

Extend binary search to optionally continue the binary search
to determine the range that compares equal.

3 files changed, 167 insertions, 24 deletions

diff --git a/libnm-core/nm-core-internal.h b/libnm-core/nm-core-internal.h
index 5a27d43886..15e5dc2a14 100644
--- a/libnm-core/nm-core-internal.h
+++ b/libnm-core/nm-core-internal.h
@@ -241,7 +241,13 @@ GPtrArray *_nm_utils_copy_object_array (const GPtrArray *array);
 
 gssize _nm_utils_ptrarray_find_first (gconstpointer *list, gssize len, gconstpointer needle);
 
-gssize _nm_utils_ptrarray_find_binary_search (gconstpointer *list, gsize len, gconstpointer needle, GCompareDataFunc cmpfcn, gpointer user_data);
+gssize _nm_utils_ptrarray_find_binary_search (gconstpointer *list,
+                                              gsize len,
+                                              gconstpointer needle,
+                                              GCompareDataFunc cmpfcn,
+                                              gpointer user_data,
+                                              gssize *out_idx_first,
+                                              gssize *out_idx_last);
 gssize _nm_utils_array_find_binary_search (gconstpointer list, gsize elem_size, gsize len, gconstpointer needle, GCompareDataFunc cmpfcn, gpointer user_data);
 
 GSList *    _nm_utils_strv_to_slist (char **strv, gboolean deep_copy);
diff --git a/libnm-core/nm-utils.c b/libnm-core/nm-utils.c
index 73035e5ecb..1e631c2c99 100644
--- a/libnm-core/nm-utils.c
+++ b/libnm-core/nm-utils.c
@@ -646,36 +646,82 @@ _nm_utils_ptrarray_find_first (gconstpointer *list, gssize len, gconstpointer ne
 }
 
 gssize
-_nm_utils_ptrarray_find_binary_search (gconstpointer *list, gsize len, gconstpointer needle, GCompareDataFunc cmpfcn, gpointer user_data)
-{
-	gssize imin, imax, imid;
+_nm_utils_ptrarray_find_binary_search (gconstpointer *list,
+                                       gsize len,
+                                       gconstpointer needle,
+                                       GCompareDataFunc cmpfcn,
+                                       gpointer user_data,
+                                       gssize *out_idx_first,
+                                       gssize *out_idx_last)
+{
+	gssize imin, imax, imid, i2min, i2max, i2mid;
 	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 (len > 0) {
+		imax = len - 1;
+
+		while (imin <= imax) {
+			imid = imin + (imax - imin) / 2;
+
+			cmp = cmpfcn (list[imid], needle, user_data);
+			if (cmp == 0) {
+				/* we found a matching entry at index imid.
+				 *
+				 * Does the caller request the first/last index as well (in case that
+				 * there are multiple entries which compare equal). */
+
+				if (out_idx_first) {
+					i2min = imin;
+					i2max = imid + 1;
+					while (i2min <= i2max) {
+						i2mid = i2min + (i2max - i2min) / 2;
+
+						cmp = cmpfcn (list[i2mid], needle, user_data);
+						if (cmp == 0)
+							i2max = i2mid -1;
+						else {
+							nm_assert (cmp < 0);
+							i2min = i2mid + 1;
+						}
+					}
+					*out_idx_first = i2min;
+				}
+				if (out_idx_last) {
+					i2min = imid + 1;
+					i2max = imax;
+					while (i2min <= i2max) {
+						i2mid = i2min + (i2max - i2min) / 2;
+
+						cmp = cmpfcn (list[i2mid], needle, user_data);
+						if (cmp == 0)
+							i2min = i2mid + 1;
+						else {
+							nm_assert (cmp > 0);
+							i2max = i2mid - 1;
+						}
+					}
+					*out_idx_last = i2min - 1;
+				}
+				return imid;
+			}
 
-		if (cmp < 0)
-			imin = imid + 1;
-		else
-			imax = imid - 1;
+			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;
+	imin = ~imin;
+	NM_SET_OUT (out_idx_first, imin);
+	NM_SET_OUT (out_idx_last, imin);
+	return imin;
 }
 
 gssize
diff --git a/libnm-core/tests/test-general.c b/libnm-core/tests/test-general.c
index 21337a9d40..88eb4bc85f 100644
--- a/libnm-core/tests/test-general.c
+++ b/libnm-core/tests/test-general.c
@@ -6149,7 +6149,7 @@ static void
 _test_find_binary_search_do (const int *array, gsize len)
 {
 	gsize i;
-	gssize idx;
+	gssize idx, idx_first, idx_last;
 	gs_free gconstpointer *parray = g_new (gconstpointer, len);
 	const int NEEDLE = 0;
 	gconstpointer pneedle = GINT_TO_POINTER (NEEDLE);
@@ -6160,10 +6160,10 @@ _test_find_binary_search_do (const int *array, gsize len)
 
 	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)
+	idx = _nm_utils_ptrarray_find_binary_search (parray, len, pneedle, _test_find_binary_search_cmp, NULL, &idx_first, &idx_last);
+	if (expected_result >= 0) {
 		g_assert_cmpint (expected_result, ==, idx);
-	else {
+	} else {
 		gssize idx2 = ~idx;
 		g_assert_cmpint (idx, <, 0);
 
@@ -6172,6 +6172,8 @@ _test_find_binary_search_do (const int *array, gsize 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);
 	}
+	g_assert_cmpint (idx, ==, idx_first);
+	g_assert_cmpint (idx, ==, idx_last);
 	for (i = 0; i < len; i++) {
 		int cmp;
 
@@ -6273,6 +6275,94 @@ test_nm_utils_ptrarray_find_binary_search (void)
 }
 
 /*****************************************************************************/
+
+#define BIN_SEARCH_W_DUPS_LEN    100
+#define BIN_SEARCH_W_DUPS_JITTER 10
+
+static int
+_test_bin_search2_cmp (gconstpointer pa,
+                       gconstpointer pb,
+                       gpointer user_data)
+{
+	int a = GPOINTER_TO_INT (pa);
+	int b = GPOINTER_TO_INT (pb);
+
+	g_assert (a >= 0 && a <= BIN_SEARCH_W_DUPS_LEN + BIN_SEARCH_W_DUPS_JITTER);
+	g_assert (b >= 0 && b <= BIN_SEARCH_W_DUPS_LEN + BIN_SEARCH_W_DUPS_JITTER);
+	NM_CMP_DIRECT (a, b);
+	return 0;
+}
+
+static int
+_test_bin_search2_cmp_p (gconstpointer pa,
+                         gconstpointer pb,
+                         gpointer user_data)
+{
+	return _test_bin_search2_cmp (*((gpointer *) pa), *((gpointer *) pb), NULL);
+}
+
+static void
+test_nm_utils_ptrarray_find_binary_search_with_duplicates (void)
+{
+	gssize idx, idx2, idx_first2, idx_first, idx_last;
+	int i_test, i_len, i;
+	gssize j;
+	gconstpointer arr[BIN_SEARCH_W_DUPS_LEN];
+	const int N_TEST = 10;
+
+	for (i_test = 0; i_test < N_TEST; i_test++) {
+		for (i_len = 0; i_len < BIN_SEARCH_W_DUPS_LEN; i_len++) {
+
+			/* fill with random numbers... surely there are some duplicates
+			 * there... or maybe even there are none... */
+			for (i = 0; i < i_len; i++)
+				arr[i] = GINT_TO_POINTER (nmtst_get_rand_int () % (i_len + BIN_SEARCH_W_DUPS_JITTER));
+			g_qsort_with_data (arr,
+			                   i_len,
+			                   sizeof (gpointer),
+			                   _test_bin_search2_cmp_p,
+			                   NULL);
+			for (i = 0; i < i_len + BIN_SEARCH_W_DUPS_JITTER; i++) {
+				gconstpointer p = GINT_TO_POINTER (i);
+
+				idx = _nm_utils_ptrarray_find_binary_search (arr, i_len, p, _test_bin_search2_cmp, NULL, &idx_first, &idx_last);
+
+				idx_first2 = _nm_utils_ptrarray_find_first (arr, i_len, p);
+
+				idx2 = _nm_utils_array_find_binary_search (arr, sizeof (gpointer), i_len, &p, _test_bin_search2_cmp_p, NULL);
+				g_assert_cmpint (idx, ==, idx2);
+
+				if (idx_first2 < 0) {
+					g_assert_cmpint (idx, <, 0);
+					g_assert_cmpint (idx, ==, idx_first);
+					g_assert_cmpint (idx, ==, idx_last);
+					idx = ~idx;
+					g_assert_cmpint (idx, >=, 0);
+					g_assert_cmpint (idx, <=, i_len);
+					if (i_len == 0)
+						g_assert_cmpint (idx, ==, 0);
+					else {
+						g_assert (idx == i_len || GPOINTER_TO_INT (arr[idx]) > i);
+						g_assert (idx == 0     || GPOINTER_TO_INT (arr[idx - 1]) < i);
+					}
+				} else {
+					g_assert_cmpint (idx_first, ==, idx_first2);
+					g_assert_cmpint (idx_first, >=, 0);
+					g_assert_cmpint (idx_last, <, i_len);
+					g_assert_cmpint (idx_first, <=, idx_last);
+					g_assert_cmpint (idx, >=, idx_first);
+					g_assert_cmpint (idx, <=, idx_last);
+					for (j = idx_first; j < idx_last; j++)
+						g_assert (GPOINTER_TO_INT (arr[j]) == i);
+					g_assert (idx_first == 0 || GPOINTER_TO_INT (arr[idx_first - 1]) < i);
+					g_assert (idx_last == i_len - 1 || GPOINTER_TO_INT (arr[idx_last + 1]) > i);
+				}
+			}
+		}
+	}
+}
+
+/*****************************************************************************/
 static void
 test_nm_utils_enum_from_str_do (GType type, const char *str,
                                 gboolean exp_result, int exp_flags,
@@ -6962,6 +7052,7 @@ int main (int argc, char **argv)
 	g_test_add_func ("/core/general/_glib_compat_g_ptr_array_insert", test_g_ptr_array_insert);
 	g_test_add_func ("/core/general/_glib_compat_g_hash_table_get_keys_as_array", test_g_hash_table_get_keys_as_array);
 	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_ptrarray_find_binary_search_with_duplicates", test_nm_utils_ptrarray_find_binary_search_with_duplicates);
 	g_test_add_func ("/core/general/_nm_utils_strstrdictkey", test_nm_utils_strstrdictkey);
 	g_test_add_func ("/core/general/nm_ptrarray_len", test_nm_ptrarray_len);