[glib: 7/8] garray: Fix binary search for non-existent elements on the left

[Emmanuele Bassi <ebassi src gnome org>]

commit c0f13f3cc813a14b270bb43b0baa85d9e6680016
Author: Philip Withnall <withnall endlessm com>
Date:   Tue Jul 16 11:36:28 2019 +0100

    garray: Fix binary search for non-existent elements on the left
    
    If searching for an element which is smaller than every element in the
    array (i.e. the element being searched for is not in the array), the
    previous g_array_binary_search() implementation would underflow in the
    calculation `right = middle - 1`, and end up trying to dereference an
    element way off the right of the array.
    
    Fix that by checking the additions/subtractions before doing them, and
    bailing if the bounds are hit. We don’t need to check `middle <
    G_MAXUINT`, as `middle` is bounded above by `right`, which is always `<=
    _array->len - 1`, and `_array->len <= G_MAXUINT`.
    
    Add some tests for that, and for not-present elements in the middle of
    the array. Previously, the tests only checked for not-present elements
    which were bigger than every element in the array.
    
    Signed-off-by: Philip Withnall <withnall endlessm com>

 glib/garray.c           | 12 +++++++-----
 glib/tests/array-test.c | 51 ++++++++++++++++++++++++++++++++++++++-----------
 2 files changed, 47 insertions(+), 16 deletions(-)
---
diff --git a/glib/garray.c b/glib/garray.c
index 3f13d746f..569cff892 100644
--- a/glib/garray.c
+++ b/glib/garray.c
@@ -848,15 +848,17 @@ g_array_binary_search (GArray        *array,
           middle = left + (right - left) / 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
+          if (val == 0)
             {
               result = TRUE;
               break;
             }
+          else if (val < 0)
+            left = middle + 1;
+          else if (/* val > 0 && */ middle > 0)
+            right = middle - 1;
+          else
+            break;  /* element not found */
         }
     }
 
diff --git a/glib/tests/array-test.c b/glib/tests/array-test.c
index fd8ceb7e1..b26704e25 100644
--- a/glib/tests/array-test.c
+++ b/glib/tests/array-test.c
@@ -677,6 +677,9 @@ test_array_binary_search (void)
 
   g_assert_true (g_array_binary_search (garray, &i, cmpint, NULL));
 
+  i = 0;
+  g_assert_false (g_array_binary_search (garray, &i, cmpint, NULL));
+
   i = 2;
   g_assert_false (g_array_binary_search (garray, &i, cmpint, NULL));
 
@@ -684,26 +687,32 @@ test_array_binary_search (void)
 
   /* Testing array of size 2 */
   garray = g_array_sized_new (FALSE, FALSE, sizeof (guint), 2);
-  for (i = 0; i < 2; i++)
+  for (i = 1; i < 3; i++)
     g_array_append_val (garray, i);
 
-  for (i = 0; i < 2; i++)
+  for (i = 1; i < 3; i++)
     g_assert_true (g_array_binary_search (garray, &i, cmpint, NULL));
 
-  i = 3;
+  i = 0;
+  g_assert_false (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 3 */
   garray = g_array_sized_new (FALSE, FALSE, sizeof (guint), 3);
-  for (i = 0; i < 3; i++)
+  for (i = 1; i < 4; i++)
     g_array_append_val (garray, i);
 
-  for (i = 0; i < 3; i++)
+  for (i = 1; i < 4; i++)
     g_assert_true (g_array_binary_search (garray, &i, cmpint, NULL));
 
-  i = 4;
+  i = 0;
+  g_assert_false (g_array_binary_search (garray, &i, cmpint, NULL));
+
+  i = 5;
   g_assert_false (g_array_binary_search (garray, &i, cmpint, NULL));
 
   g_array_free (garray, TRUE);
@@ -711,24 +720,44 @@ test_array_binary_search (void)
   /* Testing array of size 10000 */
   garray = g_array_sized_new (FALSE, FALSE, sizeof (guint), 10000);
 
-  for (i = 0; i < 10000; i++)
+  for (i = 1; i < 10001; i++)
     g_array_append_val (garray, i);
 
-  for (i = 0; i < 10000; i++)
+  for (i = 1; i < 10001; i++)
     g_assert_true (g_array_binary_search (garray, &i, cmpint, NULL));
 
-  for (i = 0; i < 10000; i++)
+  for (i = 1; i < 10001; i++)
     {
       g_assert_true (g_array_binary_search (garray, &i, cmpint, &matched_index));
-      g_assert_cmpint (i, ==, matched_index);
+      g_assert_cmpint (i, ==, matched_index + 1);
     }
 
   /* Testing negative result */
-  i = 10001;
+  i = 0;
+  g_assert_false (g_array_binary_search (garray, &i, cmpint, NULL));
+  g_assert_false (g_array_binary_search (garray, &i, cmpint, &matched_index));
+
+  i = 10002;
   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);
+
+  /* Test for a not-found element in the middle of the array. */
+  garray = g_array_sized_new (FALSE, FALSE, sizeof (guint), 3);
+  for (i = 1; i < 10; i += 2)
+    g_array_append_val (garray, i);
+
+  i = 0;
+  g_assert_false (g_array_binary_search (garray, &i, cmpint, NULL));
+
+  i = 2;
+  g_assert_false (g_array_binary_search (garray, &i, cmpint, NULL));
+
+  i = 10;
+  g_assert_false (g_array_binary_search (garray, &i, cmpint, NULL));
+
+  g_array_free (garray, TRUE);
 }
 
 static void