[gtk/wip/otte/sortlistmodel: 115/154] Add GtkVector

[Benjamin Otte <otte src gnome org>]

commit aa2416430beb5bafeb476ab454f9cf33ef746ca2
Author: Benjamin Otte <otte redhat com>
Date:   Thu Jul 2 17:23:09 2020 +0200

    Add GtkVector
    
    This is a scary idea where you #define a bunch of preprocessor values
    and then #include "gtkvectorimpl.c" and end up with a dynamic array for
    that data type.

 gtk/gtkvectorimpl.c        | 219 +++++++++++++++++++++++++++++++++++++++++++++
 testsuite/gtk/meson.build  |   1 +
 testsuite/gtk/vector.c     |  69 ++++++++++++++
 testsuite/gtk/vectorimpl.c | 108 ++++++++++++++++++++++
 4 files changed, 397 insertions(+)
---
diff --git a/gtk/gtkvectorimpl.c b/gtk/gtkvectorimpl.c
new file mode 100644
index 0000000000..2a0714f38d
--- /dev/null
+++ b/gtk/gtkvectorimpl.c
@@ -0,0 +1,219 @@
+/*
+ * Copyright © 2020 Benjamin Otte
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library 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
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * Authors: Benjamin Otte <otte gnome org>
+ */
+
+#include <glib.h>
+
+G_BEGIN_DECLS
+
+#ifndef GTK_VECTOR_TYPE_NAME
+#define GTK_VECTOR_TYPE_NAME GtkVector
+#endif
+
+#ifndef GTK_VECTOR_NAME
+#define GTK_VECTOR_NAME gtk_vector
+#endif
+
+#ifndef GTK_VECTOR_ELEMENT_TYPE
+#define GTK_VECTOR_ELEMENT_TYPE gpointer
+#endif
+
+#ifdef GTK_VECTOR_PREALLOC
+#if GTK_VECTOR_PREALLOC == 0
+#undef GTK_VECTOR_PREALLOC
+#endif
+#endif
+
+/* make this readable */
+#define _T_ GTK_VECTOR_ELEMENT_TYPE
+#define GtkVector GTK_VECTOR_TYPE_NAME
+#define gtk_vector_paste_more(GTK_VECTOR_NAME, func_name) GTK_VECTOR_NAME ## _ ## func_name
+#define gtk_vector_paste(GTK_VECTOR_NAME, func_name) gtk_vector_paste_more (GTK_VECTOR_NAME, func_name)
+#define gtk_vector(func_name) gtk_vector_paste (GTK_VECTOR_NAME, func_name)
+
+typedef struct GtkVector GtkVector;
+
+struct GtkVector
+{
+  _T_ *start;
+  _T_ *end;
+  _T_ *end_allocation;
+#ifdef GTK_VECTOR_PREALLOC
+  _T_ preallocated[GTK_VECTOR_PREALLOC];
+#endif
+};
+
+/* no G_GNUC_UNUSED here, if you don't use an array type, remove it. */
+static inline void
+gtk_vector(init) (GtkVector *self)
+{
+#ifdef GTK_VECTOR_PREALLOC
+  self->start = self->preallocated;
+  self->end = self->start;
+  self->end_allocation = self->start + GTK_VECTOR_PREALLOC;
+#else
+  self->start = NULL;
+  self->end = NULL;
+  self->end_allocation = NULL;
+#endif
+}
+
+static inline void
+gtk_vector(free_elements) (_T_ *start,
+                           _T_ *end)
+{
+#ifdef GTK_VECTOR_FREE_FUNC
+  _T_ *e;
+  for (e = start; e < end; e++)
+    GTK_VECTOR_FREE_FUNC (*e);
+#endif
+}
+
+/* no G_GNUC_UNUSED here */
+static inline void
+gtk_vector(clear) (GtkVector *self)
+{
+  gtk_vector(free_elements) (self->start, self->end);
+
+#ifdef GTK_VECTOR_PREALLOC
+  if (self->start != self->preallocated)
+    g_free (self->start);
+#endif
+  gtk_vector(init) (self);
+}
+
+G_GNUC_UNUSED static inline _T_ *
+gtk_vector(get_data) (GtkVector *self)
+{
+  return self->start;
+}
+
+G_GNUC_UNUSED static inline _T_ *
+gtk_vector(index) (GtkVector *self,
+                   gsize      pos)
+{
+  return self->start + pos;
+}
+
+G_GNUC_UNUSED static inline gsize
+gtk_vector(get_capacity) (GtkVector *self)
+{
+  return self->end_allocation - self->start;
+}
+
+G_GNUC_UNUSED static inline gsize
+gtk_vector(get_size) (GtkVector *self)
+{
+  return self->end - self->start;
+}
+
+G_GNUC_UNUSED static inline gboolean
+gtk_vector(is_empty) (GtkVector *self)
+{
+  return self->end == self->start;
+}
+
+G_GNUC_UNUSED static void
+gtk_vector(reserve) (GtkVector *self,
+                        gsize      n)
+{
+  gsize new_size, size;
+
+  if (n <= gtk_vector(get_capacity) (self))
+    return;
+
+  size = gtk_vector(get_size) (self);
+  new_size = 1 << g_bit_storage (MAX (n, 16) - 1);
+
+#ifdef GTK_VECTOR_PREALLOC
+  if (self->start == self->preallocated)
+    {
+      self->start = g_new (_T_, new_size);
+      memcpy (self->start, self->preallocated, sizeof (_T_) * size);
+    }
+  else
+#endif
+    self->start = g_renew (_T_, self->start, new_size);
+
+  self->end = self->start + size;
+  self->end_allocation = self->start + new_size;
+}
+
+G_GNUC_UNUSED static void
+gtk_vector(splice) (GtkVector *self,
+                    gsize      pos,
+                    gsize      removed,
+                    _T_       *additions,
+                    gsize      added)
+{
+  gssize size = gtk_vector(get_size) (self);
+
+  g_assert (pos + removed <= size);
+
+  gtk_vector(free_elements) (gtk_vector(index) (self, pos),
+                             gtk_vector(index) (self, pos + removed));
+
+  gtk_vector(reserve) (self, size - removed + added);
+
+  if (pos + removed < size && removed != added)
+    memmove (gtk_vector(index) (self, pos + added),
+             gtk_vector(index) (self, pos + removed),
+             (size - pos - removed) * sizeof (_T_));
+
+  if (added)
+    memcpy (gtk_vector(index) (self, pos),
+            additions,
+            added * sizeof (_T_));
+
+  /* might overflow, but does the right thing */
+  self->end += added - removed;
+}
+
+G_GNUC_UNUSED static void
+gtk_vector(append) (GtkVector *self,
+                    _T_        value)
+{
+  gtk_vector(splice) (self, 
+                      gtk_vector(get_size) (self),
+                      0,
+                      &value,
+                      1);
+}
+
+G_GNUC_UNUSED static _T_ 
+gtk_vector(get) (GtkVector *self,
+                 gsize      pos)
+{
+  return *gtk_vector(index) (self, pos);
+}
+
+
+#ifndef GTK_VECTOR_NO_UNDEF
+
+#undef _T_
+#undef GtkVector
+#undef gtk_vector_paste_more
+#undef gtk_vector_paste
+#undef gtk_vector
+
+#undef GTK_VECTOR_PREALLOC
+#undef GTK_VECTOR_ELEMENT_TYPE
+#undef GTK_VECTOR_NAME
+#undef GTK_VECTOR_TYPE_NAME
+
+#endif
diff --git a/testsuite/gtk/meson.build b/testsuite/gtk/meson.build
index 8f1828aa0c..e1d8eac4ab 100644
--- a/testsuite/gtk/meson.build
+++ b/testsuite/gtk/meson.build
@@ -118,6 +118,7 @@ tests = [
   { 'name': 'typename' },
   { 'name': 'displayclose' },
   { 'name': 'revealer-size' },
+  { 'name': 'vector' },
   { 'name': 'widgetorder' },
   { 'name': 'widget-refcount' },
 ]
diff --git a/testsuite/gtk/vector.c b/testsuite/gtk/vector.c
new file mode 100644
index 0000000000..5f47c9572e
--- /dev/null
+++ b/testsuite/gtk/vector.c
@@ -0,0 +1,69 @@
+/*
+ * Copyright © 2020 Benjamin Otte
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library 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
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * Authors: Benjamin Otte <otte gnome org>
+ */
+
+#include <locale.h>
+
+#include <gtk/gtk.h>
+
+static void
+int_free_func (int data)
+{
+}
+
+#define GTK_VECTOR_ELEMENT_TYPE int
+#define GTK_VECTOR_NAME int_vector
+#define GTK_VECTOR_TYPE_NAME IntVector
+#include "vectorimpl.c"
+
+#define GTK_VECTOR_ELEMENT_TYPE int
+#define GTK_VECTOR_NAME pre_int_vector
+#define GTK_VECTOR_TYPE_NAME PreIntVector
+#define GTK_VECTOR_PREALLOC 100
+#include "vectorimpl.c"
+
+#define GTK_VECTOR_ELEMENT_TYPE int
+#define GTK_VECTOR_NAME free_int_vector
+#define GTK_VECTOR_TYPE_NAME FreeIntVector
+#define GTK_VECTOR_FREE_FUNC int_free_func
+#include "vectorimpl.c"
+
+#define GTK_VECTOR_ELEMENT_TYPE int
+#define GTK_VECTOR_NAME pre_free_int_vector
+#define GTK_VECTOR_TYPE_NAME PreFreeIntVector
+#define GTK_VECTOR_PREALLOC 100
+#define GTK_VECTOR_FREE_FUNC int_free_func
+#include "vectorimpl.c"
+
+int
+main (int argc, char *argv[])
+{
+  g_test_init (&argc, &argv, NULL);
+  setlocale (LC_ALL, "C");
+
+  g_test_add_func ("/intvector/simple", int_vector_test_simple);
+  g_test_add_func ("/intvector/prealloc/simple", pre_int_vector_test_simple);
+  g_test_add_func ("/intvector/freefunc/simple", free_int_vector_test_simple);
+  g_test_add_func ("/intvector/prealloc_freefunc_simple", pre_free_int_vector_test_simple);
+  g_test_add_func ("/intvector/splice", int_vector_test_splice);
+  g_test_add_func ("/intvector/prealloc/splice", pre_int_vector_test_splice);
+  g_test_add_func ("/intvector/freefunc/splice", free_int_vector_test_splice);
+  g_test_add_func ("/intvector/prealloc_freefunc_splice", pre_free_int_vector_test_splice);
+
+  return g_test_run ();
+}
diff --git a/testsuite/gtk/vectorimpl.c b/testsuite/gtk/vectorimpl.c
new file mode 100644
index 0000000000..3b0c0f905a
--- /dev/null
+++ b/testsuite/gtk/vectorimpl.c
@@ -0,0 +1,108 @@
+/*
+ * Copyright © 2020 Benjamin Otte
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library 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
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * Authors: Benjamin Otte <otte gnome org>
+ */
+
+#include <gtk/gtk.h>
+
+#define GTK_VECTOR_NO_UNDEF
+
+#include "../../gtk/gtkvectorimpl.c"
+
+static void
+gtk_vector(test_simple) (void)
+{
+  GtkVector v;
+  gsize i;
+
+  gtk_vector(init) (&v);
+
+  for (i = 0; i < 1000; i++)
+    {
+      g_assert_cmpint (gtk_vector(get_size) (&v), ==, i);
+      g_assert_cmpint (gtk_vector(get_size) (&v), <=, gtk_vector(get_capacity) (&v));
+      gtk_vector(append) (&v, i);
+    }
+  g_assert_cmpint (gtk_vector(get_size) (&v), ==, i);
+  g_assert_cmpint (gtk_vector(get_size) (&v), <=, gtk_vector(get_capacity) (&v));
+
+  for (i = 0; i < 1000; i++)
+    {
+      g_assert_cmpint (gtk_vector(get) (&v, i), ==, i);
+    }
+
+  gtk_vector(clear) (&v);
+}
+
+static void
+gtk_vector(test_splice) (void)
+{
+  GtkVector v;
+  gsize i, j, sum;
+  gsize pos, add, remove;
+  int additions[4] = { 0, 1, 2, 3 };
+
+  gtk_vector(init) (&v);
+  sum = 0;
+
+  for (i = 0; i < 1000; i++)
+    {
+      gsize old_size = gtk_vector(get_size) (&v);
+
+      pos = g_random_int_range (0, old_size + 1);
+      g_assert (pos <= old_size);
+      remove = g_random_int_range (0, 4);
+      remove = MIN (remove, old_size - pos);
+      add = g_random_int_range (0, 4);
+
+      for (j = 0; j < remove; j++)
+        sum -= gtk_vector(get) (&v, pos + j);
+      for (j = 0; j < add; j++)
+        sum += ++additions[j];
+
+      gtk_vector(splice) (&v, pos, remove, additions, add);
+      {
+        gsize total = 0;
+        for (j = 0; j < gtk_vector(get_size) (&v); j++)
+          total += gtk_vector(get) (&v, j);
+        g_assert_cmpint (total, ==, sum);
+      }
+
+      g_assert_cmpint (gtk_vector(get_size) (&v), ==, old_size + add - remove);
+      g_assert_cmpint (gtk_vector(get_size) (&v), <=, gtk_vector(get_capacity) (&v));
+      for (j = 0; j < add; j++)
+        g_assert_cmpint (gtk_vector(get) (&v, pos + j), ==, additions[j]);
+    }
+
+  for (i = 0; i < gtk_vector(get_size) (&v); i++)
+    {
+      sum -= gtk_vector(get) (&v, i);
+    }
+  g_assert_cmpint (sum, ==, 0);
+}
+
+#undef _T_
+#undef GtkVector
+#undef gtk_vector_paste_more
+#undef gtk_vector_paste
+#undef gtk_vector
+
+#undef GTK_VECTOR_PREALLOC
+#undef GTK_VECTOR_ELEMENT_TYPE
+#undef GTK_VECTOR_NAME
+#undef GTK_VECTOR_TYPE_NAME
+