[gtk/wip/otte/vector: 7/17] Add GdkArray

[Benjamin Otte <otte src gnome org>]

commit bfc640f19160e79c42b351b214ab2d62c0b0ed63
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.
    
    What are the advantages over using GArray or GPtrArray?
    
     * It's typesafe
       Because it works like C++ templates, we can use the actual type of
       the object instead of having to use gpointer.
    
     * It's one less indirection
       instead of 2 indirections via self->array->data, this array is
       embedded, so self->array is the actual data, and just one indirection
       away. This is pretty irrelevant in general, but can be very noticable
       in tight loops.
    
     * It's all inline
       Because the whole API is defined as static inline functions, the
       compiler has full access to everything and can (and does) optimize
       out unnecessary calls, thereby speeding up some operations quite
       significantly, when full optimizations are enabled.
    
     * It has more features
       In particular preallocation allows for avoiding malloc() calls, which
       can again speed up tight loops a lot.
       But there's also splice(), which is very useful when used with
       listmodels.

 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',