[gnome-builder] git: add line cache helper

[Christian Hergert <chergert src gnome org>]

commit 04b2508d0f8128d359783c12b12c920fd31ff421
Author: Christian Hergert <chergert redhat com>
Date:   Fri Jan 18 15:54:59 2019 -0800

    git: add line cache helper
    
    This can be used to store marks about lines, so that we can keep that
    state separated from other state in the change monitor.

 src/plugins/git/line-cache.c | 176 +++++++++++++++++++++++++++++++++++++++++++
 src/plugins/git/line-cache.h |  57 ++++++++++++++
 src/plugins/git/meson.build  |   1 +
 3 files changed, 234 insertions(+)
---
diff --git a/src/plugins/git/line-cache.c b/src/plugins/git/line-cache.c
new file mode 100644
index 000000000..af5779f8c
--- /dev/null
+++ b/src/plugins/git/line-cache.c
@@ -0,0 +1,176 @@
+/* line-cache.c
+ *
+ * Copyright 2019 Christian Hergert <chergert redhat com>
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ * SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+#define G_LOG_DOMAIN "line-cache"
+
+#include "config.h"
+
+#include <stdlib.h>
+
+#include "line-cache.h"
+
+struct _LineCache
+{
+  GArray *lines;
+};
+
+LineCache *
+line_cache_new (void)
+{
+  LineCache *self;
+
+  self = g_slice_new0 (LineCache);
+  self->lines = g_array_new (FALSE, FALSE, sizeof (LineEntry));
+
+  return self;
+}
+
+void
+line_cache_free (LineCache *self)
+{
+  g_clear_pointer (&self->lines, g_array_unref);
+  g_slice_free (LineCache, self);
+}
+
+static LineEntry *
+get_entry (LineCache *self,
+           gint       line)
+{
+  LineEntry empty = {0};
+  gint i;
+
+  /* Our access pattern is usally either the head (0) or somewhere
+   * near the end (ideally the end). So we try to access the elements
+   * in that order to avoid needless spinning.
+   */
+
+  if (line == 0)
+    {
+      if (self->lines->len == 0 ||
+          g_array_index (self->lines, LineEntry, 0).line != 0)
+        g_array_insert_val (self->lines, 0, empty);
+
+      return &g_array_index (self->lines, LineEntry, 0);
+    }
+
+  for (i = self->lines->len - 1; i >= 0; i--)
+    {
+      LineEntry *entry = &g_array_index (self->lines, LineEntry, i);
+
+      if (entry->line == line)
+        return entry;
+
+      if (entry->line < line)
+        break;
+    }
+
+  if (i < 0 || i < self->lines->len)
+    i++;
+
+  g_assert (i >= 0);
+  g_assert (i <= self->lines->len);
+
+  empty.line = line;
+  g_array_insert_val (self->lines, i, empty);
+  return &g_array_index (self->lines, LineEntry, i);
+}
+
+void
+line_cache_mark_range (LineCache *self,
+                       gint       start_line,
+                       gint       end_line,
+                       LineMark   mark)
+{
+  g_assert (self != NULL);
+  g_assert (end_line >= start_line);
+  g_assert (mark != 0);
+
+  do
+    {
+      LineEntry *entry = get_entry (self, start_line);
+      entry->mark |= mark;
+      start_line++;
+    }
+  while (start_line < end_line);
+}
+
+static gint
+compare_by_line (gconstpointer a,
+                 gconstpointer b)
+{
+  const gint *line = a;
+  const LineEntry *entry = b;
+
+  return *line - entry->line;
+}
+
+LineMark
+line_cache_get_mark (LineCache *self,
+                     gint       line)
+{
+
+  const LineEntry *ret;
+
+  ret = bsearch (&line, (gconstpointer)self->lines->data,
+                 self->lines->len, sizeof (LineEntry),
+                 (GCompareFunc)compare_by_line);
+
+  return ret ? ret->mark : 0;
+}
+
+static 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);
+
+      if (entry->line >= start_line && entry->line <= end_line)
+        return entry;
+    }
+
+  return NULL;
+}
+
+void
+line_cache_foreach_in_range (LineCache *self,
+                             gint       start_line,
+                             gint       end_line,
+                             GFunc      callback,
+                             gpointer   user_data)
+{
+  const LineEntry *base;
+  const LineEntry *end;
+  const LineEntry *entry = NULL;
+
+  if (self->lines->len == 0)
+    return;
+
+  base = &g_array_index (self->lines, LineEntry, 0);
+  end = base + self->lines->len;
+
+  if ((entry = line_cache_first_in_range (self, start_line, end_line)))
+    {
+      for (; entry < end && entry->line <= end_line; entry++)
+        callback ((gpointer)entry, user_data);
+    }
+}
diff --git a/src/plugins/git/line-cache.h b/src/plugins/git/line-cache.h
new file mode 100644
index 000000000..aad874817
--- /dev/null
+++ b/src/plugins/git/line-cache.h
@@ -0,0 +1,57 @@
+/* line-cache.h
+ *
+ * Copyright 2019 Christian Hergert <chergert redhat com>
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ * SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+#pragma once
+
+#include <glib-object.h>
+
+G_BEGIN_DECLS
+
+typedef struct _LineCache LineCache;
+
+typedef enum
+{
+  LINE_MARK_ADDED            = 1 << 0,
+  LINE_MARK_REMOVED          = 1 << 1,
+  LINE_MARK_CHANGED          = 1 << 2,
+  LINE_MARK_PREVIOUS_REMOVED = 1 << 3,
+} LineMark;
+
+typedef struct
+{
+  guint line : 28;
+  guint mark : 4;
+} LineEntry;
+
+LineCache *line_cache_new              (void);
+void       line_cache_free             (LineCache *self);
+void       line_cache_mark_range       (LineCache *self,
+                                        gint       start_line,
+                                        gint       end_line,
+                                        LineMark   mark);
+void       line_cache_foreach_in_range (LineCache *self,
+                                        gint       start_line,
+                                        gint       end_line,
+                                        GFunc      callback,
+                                        gpointer   user_data);
+LineMark   line_cache_get_mark         (LineCache *self,
+                                        gint       line);
+
+G_END_DECLS
diff --git a/src/plugins/git/meson.build b/src/plugins/git/meson.build
index 29d471a14..752fef709 100644
--- a/src/plugins/git/meson.build
+++ b/src/plugins/git/meson.build
@@ -14,6 +14,7 @@ plugins_sources += files([
   'gbp-git-vcs-config.c',
   'gbp-git-vcs-initializer.c',
   'gbp-git-workbench-addin.c',
+  'line-cache.c',
 ])
 
 plugin_git_resources = gnome.compile_resources(