[glib: 1/2] Add g_array_binary_search() to garray API

[Emmanuele Bassi <ebassi src gnome org>]

commit 104fca78cd0faf3fbc8768bcc296a2da56b0de6d
Author: Emmanuel Fleury <emmanuel fleury u-bordeaux fr>
Date:   Thu May 16 14:34:58 2019 +0200

    Add g_array_binary_search() to garray API
    
    Original code written by Christian Hergert
    
    Fix issue #373

 docs/reference/glib/glib-sections.txt |   1 +
 glib/garray.c                         |  81 ++++++++++++++++++++++++++
 glib/garray.h                         |   5 ++
 glib/tests/array-test.c               | 103 ++++++++++++++++++++++++++++++++++
 4 files changed, 190 insertions(+)
---
diff --git a/docs/reference/glib/glib-sections.txt b/docs/reference/glib/glib-sections.txt
index 2ab5b17fa..142cc7773 100644
--- a/docs/reference/glib/glib-sections.txt
+++ b/docs/reference/glib/glib-sections.txt
@@ -2626,6 +2626,7 @@ g_array_remove_index_fast
 g_array_remove_range
 g_array_sort
 g_array_sort_with_data
+g_array_binary_search
 g_array_index
 g_array_set_size
 g_array_set_clear_func
diff --git a/glib/garray.c b/glib/garray.c
index 2b35a9e0e..29be5f7ef 100644
--- a/glib/garray.c
+++ b/glib/garray.c
@@ -785,6 +785,87 @@ g_array_sort_with_data (GArray           *farray,
                      user_data);
 }
 
+/**
+ * g_array_binary_search:
+ * @array: a #GArray.
+ * @target: a pointer to the item to look up.
+ * @compare_func: A #GCompareFunc used to locate @target.
+ * @out_match_index: (optional) (out caller-allocates): return location
+ *    for the index of the element, if found.
+ *
+ * Checks whether @target exists in @array by performing a binary
+ * search based on the given comparison function @compare_func which
+ * get pointers to items as arguments. If the element is found, %TRUE
+ * is returned and the element’s index is returned in @out_match_index
+ * (if non-%NULL). Otherwise, %FALSE is returned and @out_match_index
+ * is undefined. If @target exists multiple times in @array, the index
+ * of the first instance is returned. This search is using a binary
+ * search, so the @array must absolutely be sorted to return a correct
+ * result (if not, the function may produce false-negative).
+ *
+ * This example defines a comparison function and search an element in a #GArray:
+ * |[<!-- language="C" -->
+ * static gint*
+ * cmpint (gconstpointer a, gconstpointer b)
+ * {
+ *   const gint *_a = a;
+ *   const gint *_b = b;
+ *
+ *   return *_a - *_b;
+ * }
+ * ...
+ * gint i = 424242;
+ * guint matched_index;
+ * gboolean result = g_array_binary_search (garray, &i, cmpint, &matched_index);
+ * ...
+ * ]|
+ *
+ * Returns: %TRUE if @target is one of the elements of @array, %FALSE otherwise.
+ *
+ * Since: 2.62
+ */
+gboolean
+g_array_binary_search (GArray        *array,
+                       gconstpointer  target,
+                       GCompareFunc   compare_func,
+                       guint         *out_match_index)
+{
+  gboolean result = FALSE;
+  GRealArray *_array = (GRealArray *) array;
+  guint left, middle, right;
+  gint val;
+
+  g_return_val_if_fail (_array != NULL, FALSE);
+  g_return_val_if_fail (compare_func != NULL, FALSE);
+
+  if (G_LIKELY(_array->len))
+    {
+      left = 0;
+      right = _array->len - 1;
+
+      while (left <= right)
+        {
+          middle = (left + right) / 2;
+
+          val = compare_func (_array->data + (_array->elt_size * middle), target);
+          if (val < 0)
+            left = middle + 1;
+          else if (val > 0)
+            right = middle - 1;
+          else
+            {
+              result = TRUE;
+              break;
+            }
+        }
+    }
+
+  if (result && out_match_index != NULL)
+    *out_match_index = middle;
+
+  return result;
+}
+
 /* Returns the smallest power of 2 greater than n, or n if
  * such power does not fit in a guint
  */
diff --git a/glib/garray.h b/glib/garray.h
index c4ec4aeaa..3e7ce7732 100644
--- a/glib/garray.h
+++ b/glib/garray.h
@@ -119,6 +119,11 @@ GLIB_AVAILABLE_IN_ALL
 void    g_array_sort_with_data    (GArray           *array,
                                   GCompareDataFunc  compare_func,
                                   gpointer          user_data);
+GLIB_AVAILABLE_IN_2_62
+gboolean g_array_binary_search    (GArray           *array,
+                                   gconstpointer     target,
+                                   GCompareFunc      compare_func,
+                                   guint            *out_match_index);
 GLIB_AVAILABLE_IN_ALL
 void    g_array_set_clear_func    (GArray           *array,
                                    GDestroyNotify    clear_func);
diff --git a/glib/tests/array-test.c b/glib/tests/array-test.c
index b896b2d16..6405d8003 100644
--- a/glib/tests/array-test.c
+++ b/glib/tests/array-test.c
@@ -628,6 +628,108 @@ array_clear_func (void)
   g_assert_cmpint (num_clear_func_invocations, ==, 10);
 }
 
+/* Defining a comparison function for testing g_array_binary_search() */
+static gint
+cmpint (gconstpointer a, gconstpointer b)
+{
+  const gint *_a = a;
+  const gint *_b = b;
+
+  return *_a - *_b;
+}
+
+/* Testing g_array_binary_search() function */
+static void
+test_array_binary_search (void)
+{
+  GArray *garray;
+  guint i, matched_index;
+
+  if (g_test_undefined ())
+    {
+      /* Testing degenerated cases */
+      garray = g_array_sized_new (FALSE, FALSE, sizeof (guint), 0);
+      g_test_expect_message (G_LOG_DOMAIN, G_LOG_LEVEL_CRITICAL,
+                             "*assertion*!= NULL*");
+      g_assert_false (g_array_binary_search (NULL, &i, cmpint, NULL));
+      g_test_assert_expected_messages ();
+
+      g_test_expect_message (G_LOG_DOMAIN, G_LOG_LEVEL_CRITICAL,
+                             "*assertion*!= NULL*");
+      g_assert_false (g_array_binary_search (garray, &i, NULL, NULL));
+      g_test_assert_expected_messages ();
+      g_array_free (garray, TRUE);
+    }
+
+  /* Testing array of size 0 */
+  garray = g_array_sized_new (FALSE, FALSE, sizeof (guint), 0);
+
+  i = 1;
+  g_assert_false (g_array_binary_search (garray, &i, cmpint, NULL));
+
+  g_array_free (garray, TRUE);
+
+  /* Testing array of size 1 */
+  garray = g_array_sized_new (FALSE, FALSE, sizeof (guint), 1);
+  i = 1;
+  g_array_append_val (garray, i);
+
+  g_assert_true (g_array_binary_search (garray, &i, cmpint, NULL));
+
+  i = 2;
+  g_assert_false (g_array_binary_search (garray, &i, cmpint, NULL));
+
+  g_array_free (garray, TRUE);
+
+  /* Testing array of size 2 */
+  garray = g_array_sized_new (FALSE, FALSE, sizeof (guint), 2);
+  for (i = 0; i < 2; i++)
+    g_array_append_val (garray, i);
+
+  for (i = 0; i < 2; i++)
+    g_assert_true (g_array_binary_search (garray, &i, cmpint, NULL));
+
+  i = 3;
+  g_assert_false (g_array_binary_search (garray, &i, cmpint, NULL));
+
+  g_array_free (garray, TRUE);
+
+  /* Testing array of size 3 */
+  garray = g_array_sized_new (FALSE, FALSE, sizeof (guint), 3);
+  for (i = 0; i < 3; i++)
+    g_array_append_val (garray, i);
+
+  for (i = 0; i < 3; i++)
+    g_assert_true (g_array_binary_search (garray, &i, cmpint, NULL));
+
+  i = 4;
+  g_assert_false (g_array_binary_search (garray, &i, cmpint, NULL));
+
+  g_array_free (garray, TRUE);
+
+  /* Testing array of size 10000 */
+  garray = g_array_sized_new (FALSE, FALSE, sizeof (guint), 10000);
+
+  for (i = 0; i < 10000; i++)
+    g_array_append_val (garray, i);
+
+  for (i = 0; i < 10000; i++)
+    g_assert_true (g_array_binary_search (garray, &i, cmpint, NULL));
+
+  for (i = 0; i < 10000; i++)
+    {
+      g_assert_true (g_array_binary_search (garray, &i, cmpint, &matched_index));
+      g_assert_cmpint (i, ==, matched_index);
+    }
+
+  /* Testing negative result */
+  i = 10001;
+  g_assert_false (g_array_binary_search (garray, &i, cmpint, NULL));
+  g_assert_false (g_array_binary_search (garray, &i, cmpint, &matched_index));
+
+  g_array_free (garray, TRUE);
+}
+
 static void
 pointer_array_add (void)
 {
@@ -1546,6 +1648,7 @@ main (int argc, char *argv[])
   g_test_add_func ("/array/new/zero-terminated", array_new_zero_terminated);
   g_test_add_func ("/array/ref-count", array_ref_count);
   g_test_add_func ("/array/clear-func", array_clear_func);
+  g_test_add_func ("/array/binary-search", test_array_binary_search);
 
   for (i = 0; i < G_N_ELEMENTS (array_configurations); i++)
     {