[gnome-builder] git: use binary-search to locate first entry in range

[Christian Hergert <chergert src gnome org>]

commit 17ceb219f3b2bb326653a5118daf043b1862d9a2
Author: Christian Hergert <chergert redhat com>
Date:   Fri Jan 18 16:08:38 2019 -0800

    git: use binary-search to locate first entry in range

 src/plugins/git/line-cache.c | 40 ++++++++++++++++++++++++++++++++++------
 1 file changed, 34 insertions(+), 6 deletions(-)
---
diff --git a/src/plugins/git/line-cache.c b/src/plugins/git/line-cache.c
index af5779f8c..62df8ead1 100644
--- a/src/plugins/git/line-cache.c
+++ b/src/plugins/git/line-cache.c
@@ -135,17 +135,45 @@ line_cache_get_mark (LineCache *self,
   return ret ? ret->mark : 0;
 }
 
-static LineEntry *
+static const LineEntry *
 line_cache_first_in_range (LineCache *self,
                            gint       start_line,
                            gint       end_line)
 {
-  for (guint i = 0; i < self->lines->len; i++)
-    {
-      LineEntry *entry = &g_array_index (self->lines, LineEntry, i);
+  gint L;
+  gint R;
 
-      if (entry->line >= start_line && entry->line <= end_line)
-        return entry;
+  if (self->lines->len == 0)
+    return NULL;
+
+  L = 0;
+  R = self->lines->len - 1;
+
+  while (L <= R)
+    {
+      gint m = (L + R) / 2;
+      const LineEntry *entry = &g_array_index (self->lines, LineEntry, m);
+
+      if (entry->line < start_line)
+        {
+          L = m + 1;
+          continue;
+        }
+      else if (entry->line > end_line)
+        {
+          R = m - 1;
+          continue;
+        }
+
+      for (gint p = m; p >= 0; p--)
+        {
+          const LineEntry *prev = &g_array_index (self->lines, LineEntry, p);
+
+          if (prev->line >= start_line)
+            entry = prev;
+        }
+
+      return entry;
     }
 
   return NULL;