[gtk/wip/otte/vector: 207/218] Add GdkArray

[Benjamin Otte <otte src gnome org>]

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

    Add GdkArray
    
    This is a scary idea where you #define a bunch of preprocessor values
    and then #include "gdkarrayimpl.c" and end up with a dynamic array for
    that data type.
    
    See https://en.wikipedia.org/wiki/X_Macro for what's going on.

 gdk/gdkarrayimpl.c        | 219 ++++++++++++++++++++++++++++++++++++++++++++++
 testsuite/gdk/array.c     |  69 +++++++++++++++
 testsuite/gdk/arrayimpl.c | 108 +++++++++++++++++++++++
 testsuite/gdk/meson.build |   1 +
 4 files changed, 397 insertions(+)
---
diff --git a/gdk/gdkarrayimpl.c b/gdk/gdkarrayimpl.c
new file mode 100644
index 0000000000..238dd5d2b8
--- /dev/null
+++ b/gdk/gdkarrayimpl.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 GDK_ARRAY_TYPE_NAME
+#define GDK_ARRAY_TYPE_NAME GdkArray
+#endif
+
+#ifndef GDK_ARRAY_NAME
+#define GDK_ARRAY_NAME gdk_array
+#endif
+
+#ifndef GDK_ARRAY_ELEMENT_TYPE
+#define GDK_ARRAY_ELEMENT_TYPE gpointer
+#endif
+
+#ifdef GDK_ARRAY_PREALLOC
+#if GDK_ARRAY_PREALLOC == 0
+#undef GDK_ARRAY_PREALLOC
+#endif
+#endif
+
+/* make this readable */
+#define _T_ GDK_ARRAY_ELEMENT_TYPE
+#define GdkArray GDK_ARRAY_TYPE_NAME
+#define gdk_array_paste_more(GDK_ARRAY_NAME, func_name) GDK_ARRAY_NAME ## _ ## func_name
+#define gdk_array_paste(GDK_ARRAY_NAME, func_name) gdk_array_paste_more (GDK_ARRAY_NAME, func_name)
+#define gdk_array(func_name) gdk_array_paste (GDK_ARRAY_NAME, func_name)
+
+typedef struct GdkArray GdkArray;
+
+struct GdkArray
+{
+  _T_ *start;
+  _T_ *end;
+  _T_ *end_allocation;
+#ifdef GDK_ARRAY_PREALLOC
+  _T_ preallocated[GDK_ARRAY_PREALLOC];
+#endif
+};
+
+/* no G_GNUC_UNUSED here, if you don't use an array type, remove it. */
+static inline void
+gdk_array(init) (GdkArray *self)
+{
+#ifdef GDK_ARRAY_PREALLOC
+  self->start = self->preallocated;
+  self->end = self->start;
+  self->end_allocation = self->start + GDK_ARRAY_PREALLOC;
+#else
+  self->start = NULL;
+  self->end = NULL;
+  self->end_allocation = NULL;
+#endif
+}
+
+static inline void
+gdk_array(free_elements) (_T_ *start,
+                          _T_ *end)
+{
+#ifdef GDK_ARRAY_FREE_FUNC
+  _T_ *e;
+  for (e = start; e < end; e++)
+    GDK_ARRAY_FREE_FUNC (*e);
+#endif
+}
+
+/* no G_GNUC_UNUSED here */
+static inline void
+gdk_array(clear) (GdkArray *self)
+{
+  gdk_array(free_elements) (self->start, self->end);
+
+#ifdef GDK_ARRAY_PREALLOC
+  if (self->start != self->preallocated)
+#endif
+    g_free (self->start);
+  gdk_array(init) (self);
+}
+
+G_GNUC_UNUSED static inline _T_ *
+gdk_array(get_data) (GdkArray *self)
+{
+  return self->start;
+}
+
+G_GNUC_UNUSED static inline _T_ *
+gdk_array(index) (GdkArray *self,
+                  gsize      pos)
+{
+  return self->start + pos;
+}
+
+G_GNUC_UNUSED static inline gsize
+gdk_array(get_capacity) (GdkArray *self)
+{
+  return self->end_allocation - self->start;
+}
+
+G_GNUC_UNUSED static inline gsize
+gdk_array(get_size) (GdkArray *self)
+{
+  return self->end - self->start;
+}
+
+G_GNUC_UNUSED static inline gboolean
+gdk_array(is_empty) (GdkArray *self)
+{
+  return self->end == self->start;
+}
+
+G_GNUC_UNUSED static void
+gdk_array(reserve) (GdkArray *self,
+                    gsize      n)
+{
+  gsize new_size, size;
+
+  if (n <= gdk_array(get_capacity) (self))
+    return;
+
+  size = gdk_array(get_size) (self);
+  new_size = 1 << g_bit_storage (MAX (n, 16) - 1);
+
+#ifdef GDK_ARRAY_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
+gdk_array(splice) (GdkArray *self,
+                   gsize      pos,
+                   gsize      removed,
+                   _T_       *additions,
+                   gsize      added)
+{
+  gssize size = gdk_array(get_size) (self);
+
+  g_assert (pos + removed <= size);
+
+  gdk_array(free_elements) (gdk_array(index) (self, pos),
+                            gdk_array(index) (self, pos + removed));
+
+  gdk_array(reserve) (self, size - removed + added);
+
+  if (pos + removed < size && removed != added)
+    memmove (gdk_array(index) (self, pos + added),
+             gdk_array(index) (self, pos + removed),
+             (size - pos - removed) * sizeof (_T_));
+
+  if (added)
+    memcpy (gdk_array(index) (self, pos),
+            additions,
+            added * sizeof (_T_));
+
+  /* might overflow, but does the right thing */
+  self->end += added - removed;
+}
+
+G_GNUC_UNUSED static void
+gdk_array(append) (GdkArray *self,
+                   _T_        value)
+{
+  gdk_array(splice) (self, 
+                     gdk_array(get_size) (self),
+                     0,
+                     &value,
+                     1);
+}
+
+G_GNUC_UNUSED static _T_ 
+gdk_array(get) (GdkArray *self,
+                gsize      pos)
+{
+  return *gdk_array(index) (self, pos);
+}
+
+
+#ifndef GDK_ARRAY_NO_UNDEF
+
+#undef _T_
+#undef GdkArray
+#undef gdk_array_paste_more
+#undef gdk_array_paste
+#undef gdk_array
+
+#undef GDK_ARRAY_PREALLOC
+#undef GDK_ARRAY_ELEMENT_TYPE
+#undef GDK_ARRAY_NAME
+#undef GDK_ARRAY_TYPE_NAME
+
+#endif
diff --git a/testsuite/gdk/array.c b/testsuite/gdk/array.c
new file mode 100644
index 0000000000..d513b31a82
--- /dev/null
+++ b/testsuite/gdk/array.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 GDK_ARRAY_ELEMENT_TYPE int
+#define GDK_ARRAY_NAME int_array
+#define GDK_ARRAY_TYPE_NAME IntVector
+#include "arrayimpl.c"
+
+#define GDK_ARRAY_ELEMENT_TYPE int
+#define GDK_ARRAY_NAME pre_int_array
+#define GDK_ARRAY_TYPE_NAME PreIntVector
+#define GDK_ARRAY_PREALLOC 100
+#include "arrayimpl.c"
+
+#define GDK_ARRAY_ELEMENT_TYPE int
+#define GDK_ARRAY_NAME free_int_array
+#define GDK_ARRAY_TYPE_NAME FreeIntVector
+#define GDK_ARRAY_FREE_FUNC int_free_func
+#include "arrayimpl.c"
+
+#define GDK_ARRAY_ELEMENT_TYPE int
+#define GDK_ARRAY_NAME pre_free_int_array
+#define GDK_ARRAY_TYPE_NAME PreFreeIntVector
+#define GDK_ARRAY_PREALLOC 100
+#define GDK_ARRAY_FREE_FUNC int_free_func
+#include "arrayimpl.c"
+
+int
+main (int argc, char *argv[])
+{
+  g_test_init (&argc, &argv, NULL);
+  setlocale (LC_ALL, "C");
+
+  g_test_add_func ("/intarray/simple", int_array_test_simple);
+  g_test_add_func ("/intarray/prealloc/simple", pre_int_array_test_simple);
+  g_test_add_func ("/intarray/freefunc/simple", free_int_array_test_simple);
+  g_test_add_func ("/intarray/prealloc_freefunc_simple", pre_free_int_array_test_simple);
+  g_test_add_func ("/intarray/splice", int_array_test_splice);
+  g_test_add_func ("/intarray/prealloc/splice", pre_int_array_test_splice);
+  g_test_add_func ("/intarray/freefunc/splice", free_int_array_test_splice);
+  g_test_add_func ("/intarray/prealloc_freefunc_splice", pre_free_int_array_test_splice);
+
+  return g_test_run ();
+}
diff --git a/testsuite/gdk/arrayimpl.c b/testsuite/gdk/arrayimpl.c
new file mode 100644
index 0000000000..f9320cb113
--- /dev/null
+++ b/testsuite/gdk/arrayimpl.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 GDK_ARRAY_NO_UNDEF
+
+#include "../../gdk/gdkarrayimpl.c"
+
+static void
+gdk_array(test_simple) (void)
+{
+  GdkArray v;
+  gsize i;
+
+  gdk_array(init) (&v);
+
+  for (i = 0; i < 1000; i++)
+    {
+      g_assert_cmpint (gdk_array(get_size) (&v), ==, i);
+      g_assert_cmpint (gdk_array(get_size) (&v), <=, gdk_array(get_capacity) (&v));
+      gdk_array(append) (&v, i);
+    }
+  g_assert_cmpint (gdk_array(get_size) (&v), ==, i);
+  g_assert_cmpint (gdk_array(get_size) (&v), <=, gdk_array(get_capacity) (&v));
+
+  for (i = 0; i < 1000; i++)
+    {
+      g_assert_cmpint (gdk_array(get) (&v, i), ==, i);
+    }
+
+  gdk_array(clear) (&v);
+}
+
+static void
+gdk_array(test_splice) (void)
+{
+  GdkArray v;
+  gsize i, j, sum;
+  gsize pos, add, remove;
+  int additions[4] = { 0, 1, 2, 3 };
+
+  gdk_array(init) (&v);
+  sum = 0;
+
+  for (i = 0; i < 1000; i++)
+    {
+      gsize old_size = gdk_array(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 -= gdk_array(get) (&v, pos + j);
+      for (j = 0; j < add; j++)
+        sum += ++additions[j];
+
+      gdk_array(splice) (&v, pos, remove, additions, add);
+      {
+        gsize total = 0;
+        for (j = 0; j < gdk_array(get_size) (&v); j++)
+          total += gdk_array(get) (&v, j);
+        g_assert_cmpint (total, ==, sum);
+      }
+
+      g_assert_cmpint (gdk_array(get_size) (&v), ==, old_size + add - remove);
+      g_assert_cmpint (gdk_array(get_size) (&v), <=, gdk_array(get_capacity) (&v));
+      for (j = 0; j < add; j++)
+        g_assert_cmpint (gdk_array(get) (&v, pos + j), ==, additions[j]);
+    }
+
+  for (i = 0; i < gdk_array(get_size) (&v); i++)
+    {
+      sum -= gdk_array(get) (&v, i);
+    }
+  g_assert_cmpint (sum, ==, 0);
+}
+
+#undef _T_
+#undef GdkArray
+#undef gdk_array_paste_more
+#undef gdk_array_paste
+#undef gdk_array
+
+#undef GDK_ARRAY_PREALLOC
+#undef GDK_ARRAY_ELEMENT_TYPE
+#undef GDK_ARRAY_NAME
+#undef GDK_ARRAY_TYPE_NAME
+
diff --git a/testsuite/gdk/meson.build b/testsuite/gdk/meson.build
index 003e77172b..bd7744ee0e 100644
--- a/testsuite/gdk/meson.build
+++ b/testsuite/gdk/meson.build
@@ -2,6 +2,7 @@ testexecdir = join_paths(installed_test_bindir, 'gdk')
 testdatadir = join_paths(installed_test_datadir, 'gdk')
 
 tests = [
+  'array',
   'cairo',
   'clipboard',
   'display',