shared: move nm_utils_ptrarray_find_binary_search() to shared utils

2 files changed, 89 insertions, 0 deletions

diff --git a/shared/nm-utils/nm-shared-utils.c b/shared/nm-utils/nm-shared-utils.c
index a9c7ab7e9d..34c93c8108 100644
--- a/shared/nm-utils/nm-shared-utils.c
+++ b/shared/nm-utils/nm-shared-utils.c
@@ -1350,6 +1350,87 @@ nm_utils_strv_make_deep_copied (const char **strv)
 
 /*****************************************************************************/
 
+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 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) {
+		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;
+		}
+	}
+
+	/* return the inverse of @imin. This is a negative number, but
+	 * also is ~imin the position where the value should be inserted. */
+	imin = ~imin;
+	NM_SET_OUT (out_idx_first, imin);
+	NM_SET_OUT (out_idx_last, imin);
+	return imin;
+}
+
+/*****************************************************************************/
+
 /**
  * nm_utils_array_find_binary_search:
  * @list: the list to search. It must be sorted according to @cmpfcn ordering.
diff --git a/shared/nm-utils/nm-shared-utils.h b/shared/nm-utils/nm-shared-utils.h
index feb93f2c5a..6ee77b989f 100644
--- a/shared/nm-utils/nm-shared-utils.h
+++ b/shared/nm-utils/nm-shared-utils.h
@@ -557,6 +557,14 @@ nm_utils_strv_make_deep_copied_nonnull (const char **strv)
 
 /*****************************************************************************/
 
+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,