testsuite: Add more filterlistmodel tests

These ones try to be exhaustive and randomly catch weird cases.

As such, the tests are more complicated and harder to grasp.
Sorry.

demos/gtk-demo/demo.gresource.xml

@@ -226,6 +226,7 @@
     <file>listview_minesweeper.c</file>
     <file>listview_settings.c</file>
     <file>listview_weather.c</file>
+    <file>listview_words.c</file>
     <file>list_store.c</file>
     <file>markup.c</file>
     <file>modelbutton.c</file>

demos/gtk-demo/listview_words.c

@@ -0,0 +1,241 @@
+/* Lists/Words
+ *
+ * This demo shows filtering a long list - of words.
+ *
+ * You should have the file `/usr/share/dict/words` installed for
+ * this demo to work.
+ */
+
+#include <gtk/gtk.h>
+
+static GtkWidget *window = NULL;
+static GtkWidget *progress;
+
+const char *factory_text =
+"<?xml version='1.0' encoding='UTF-8'?>\n"
+"<interface>\n"
+"  <template class='GtkListItem'>\n"
+"    <property name='child'>\n"
+"      <object class='GtkLabel'>\n"
+"        <property name='ellipsize'>end</property>\n"
+"        <property name='xalign'>0</property>\n"
+"        <binding name='label'>\n"
+"          <lookup name='string' type='GtkStringObject'>\n"
+"            <lookup name='item'>GtkListItem</lookup>\n"
+"          </lookup>\n"
+"        </binding>\n"
+"      </object>\n"
+"    </property>\n"
+"  </template>\n"
+"</interface>\n";
+
+static void
+update_title_cb (GtkFilterListModel *model)
+{
+  guint total;
+  char *title;
+  guint pending;
+
+  total = g_list_model_get_n_items (gtk_filter_list_model_get_model (model));
+  pending = gtk_filter_list_model_get_pending (model);
+
+  title = g_strdup_printf ("%u lines", g_list_model_get_n_items (G_LIST_MODEL (model)));
+
+  gtk_widget_set_visible (progress, pending != 0);
+  gtk_progress_bar_set_fraction (GTK_PROGRESS_BAR (progress), (total - pending) / (double) total);
+  gtk_window_set_title (GTK_WINDOW (window), title);
+  g_free (title);
+}
+
+static void
+read_lines_cb (GObject      *object,
+               GAsyncResult *result,
+               gpointer      data)
+{
+  GBufferedInputStream *stream = G_BUFFERED_INPUT_STREAM (object);
+  GtkStringList *stringlist = data;
+  GError *error = NULL;
+  gsize size;
+  GPtrArray *lines;
+  gssize n_filled;
+  const char *buffer, *newline;
+
+  n_filled = g_buffered_input_stream_fill_finish (stream, result, &error);
+  if (n_filled < 0)
+    {
+      g_print ("Could not read data: %s\n", error->message);
+      g_clear_error (&error);
+      return;
+    }
+
+  buffer = g_buffered_input_stream_peek_buffer (stream, &size);
+
+  if (n_filled == 0)
+    {
+      if (size)
+        gtk_string_list_take (stringlist, g_utf8_make_valid (buffer, size));
+      return;
+    }
+
+  lines = NULL;
+  while ((newline = memchr (buffer, '\n', size)))
+    {
+      if (newline > buffer)
+        {
+          if (lines == NULL)
+            lines = g_ptr_array_new_with_free_func (g_free);
+          g_ptr_array_add (lines, g_utf8_make_valid (buffer, newline - buffer));
+        }
+      if (g_input_stream_skip (G_INPUT_STREAM (stream), newline - buffer + 1, NULL, &error) < 0)
+        {
+          g_clear_error (&error);
+          break;
+        }
+      buffer = g_buffered_input_stream_peek_buffer (stream, &size);
+    }
+  if (lines == NULL)
+    {
+      g_buffered_input_stream_set_buffer_size (stream, g_buffered_input_stream_get_buffer_size (stream) + 4096);
+    }
+  else
+    {
+      g_ptr_array_add (lines, NULL);
+      gtk_string_list_splice (stringlist, g_list_model_get_n_items (G_LIST_MODEL (stringlist)), 0, (const char **) lines->pdata);
+      g_ptr_array_free (lines, TRUE);
+    }
+
+  g_buffered_input_stream_fill_async (stream, -1, G_PRIORITY_HIGH_IDLE, NULL, read_lines_cb, data);
+}
+               
+static void
+file_is_open_cb (GObject      *file,
+                 GAsyncResult *result,
+                 gpointer      data)
+{
+  GError *error = NULL;
+  GFileInputStream *file_stream;
+  GBufferedInputStream *stream;
+
+  file_stream = g_file_read_finish (G_FILE (file), result, &error);
+  if (file_stream == NULL)
+    {
+      g_print ("Could not open file: %s\n", error->message);
+      g_error_free (error);
+      return;
+    }
+
+  stream = G_BUFFERED_INPUT_STREAM (g_buffered_input_stream_new (G_INPUT_STREAM (file_stream)));
+  g_buffered_input_stream_fill_async (stream, -1, G_PRIORITY_HIGH_IDLE, NULL, read_lines_cb, data);
+  g_object_unref (stream);
+}
+
+static void
+load_file (GtkStringList *list,
+           GFile         *file)
+{
+  gtk_string_list_splice (list, 0, g_list_model_get_n_items (G_LIST_MODEL (list)), NULL);
+  g_file_read_async (file, G_PRIORITY_HIGH_IDLE, NULL, file_is_open_cb, list);
+}
+
+static void
+file_selected_cb (GtkWidget     *button,
+                  GtkStringList *stringlist)
+{
+  GFile *file = gtk_file_chooser_get_file (GTK_FILE_CHOOSER (button));
+
+  if (file)
+    {
+      load_file (stringlist, file);
+      g_object_unref (file);
+    }
+}
+
+GtkWidget *
+do_listview_words (GtkWidget *do_widget)
+{
+  if (window == NULL)
+    {
+      GtkWidget *header, *listview, *sw, *vbox, *search_entry, *open_button, *overlay;
+      GtkFilterListModel *filter_model;
+      GtkNoSelection *selection;
+      GtkStringList *stringlist;
+      GtkFilter *filter;
+      GtkExpression *expression;
+      GFile *file;
+
+      file = g_file_new_for_path ("/usr/share/dict/words");
+      if (g_file_query_exists (file, NULL))
+        {
+          stringlist = gtk_string_list_new (NULL);
+          load_file (stringlist, file);
+        }
+      else
+        {
+          char **words;
+          words = g_strsplit ("lorem ipsum dolor sit amet consectetur adipisci elit sed eiusmod tempor incidunt labore et dolore magna aliqua ut enim ad minim veniam quis nostrud exercitation ullamco laboris nisi ut aliquid ex ea commodi consequat", " ", -1);
+          stringlist = gtk_string_list_new ((const char **) words);
+          g_strfreev (words);
+        }
+
+      filter = gtk_string_filter_new ();
+      expression = gtk_property_expression_new (GTK_TYPE_STRING_OBJECT, NULL, "string");
+      gtk_string_filter_set_expression (GTK_STRING_FILTER (filter), expression);
+      gtk_expression_unref (expression);
+      filter_model = gtk_filter_list_model_new (G_LIST_MODEL (stringlist), filter);
+      gtk_filter_list_model_set_incremental (filter_model, TRUE);
+
+      window = gtk_window_new ();
+      gtk_window_set_default_size (GTK_WINDOW (window), 400, 600);
+
+      header = gtk_header_bar_new ();
+      gtk_header_bar_set_show_title_buttons (GTK_HEADER_BAR (header), TRUE);
+      open_button = gtk_file_chooser_button_new ("_Open", GTK_FILE_CHOOSER_ACTION_OPEN);
+      g_signal_connect (open_button, "file-set", G_CALLBACK (file_selected_cb), stringlist);
+      gtk_header_bar_pack_start (GTK_HEADER_BAR (header), open_button);
+      gtk_window_set_titlebar (GTK_WINDOW (window), header);
+
+      gtk_window_set_display (GTK_WINDOW (window),
+                              gtk_widget_get_display (do_widget));
+      g_object_add_weak_pointer (G_OBJECT (window), (gpointer*)&window);
+
+      vbox = gtk_box_new (GTK_ORIENTATION_VERTICAL, 0);
+      gtk_window_set_child (GTK_WINDOW (window), vbox);
+
+      search_entry = gtk_search_entry_new ();
+      g_object_bind_property (search_entry, "text", filter, "search", 0);
+      gtk_box_append (GTK_BOX (vbox), search_entry);
+
+      overlay = gtk_overlay_new ();
+      gtk_box_append (GTK_BOX (vbox), overlay);
+
+      progress = gtk_progress_bar_new ();
+      gtk_widget_set_halign (progress, GTK_ALIGN_FILL);
+      gtk_widget_set_valign (progress, GTK_ALIGN_START);
+      gtk_widget_set_hexpand (progress, TRUE);
+      gtk_overlay_add_overlay (GTK_OVERLAY (overlay), progress);
+
+      sw = gtk_scrolled_window_new ();
+      gtk_overlay_set_child (GTK_OVERLAY (overlay), sw);
+
+      listview = gtk_list_view_new_with_factory (
+          gtk_builder_list_item_factory_new_from_bytes (NULL,
+              g_bytes_new_static (factory_text, strlen (factory_text))));
+      gtk_scrolled_window_set_child (GTK_SCROLLED_WINDOW (sw), listview);
+      selection = gtk_no_selection_new (G_LIST_MODEL (filter_model));
+      gtk_list_view_set_model (GTK_LIST_VIEW (listview), G_LIST_MODEL (selection));
+      g_object_unref (selection);
+
+      g_signal_connect (filter_model, "items-changed", G_CALLBACK (update_title_cb), progress);
+      g_signal_connect (filter_model, "notify::pending", G_CALLBACK (update_title_cb), progress);
+      update_title_cb (filter_model);
+
+      g_object_unref (filter_model);
+    }
+
+  if (!gtk_widget_get_visible (window))
+    gtk_widget_show (window);
+  else
+    gtk_window_destroy (GTK_WINDOW (window));
+
+  return window;
+}

demos/gtk-demo/meson.build

@@ -49,6 +49,7 @@ demos = files([
   'listview_minesweeper.c',
   'listview_settings.c',
   'listview_weather.c',
+  'listview_words.c',
   'markup.c',
   'modelbutton.c',
   'overlay.c',

docs/reference/gtk/gtk4-sections.txt

@@ -1547,6 +1547,9 @@ gtk_filter_list_model_set_model
 gtk_filter_list_model_get_model
 gtk_filter_list_model_set_filter
 gtk_filter_list_model_get_filter
+gtk_filter_list_model_set_incremental
+gtk_filter_list_model_get_incremental
+gtk_filter_list_model_get_pending
 <SUBSECTION Standard>
 GTK_FILTER_LIST_MODEL
 GTK_IS_FILTER_LIST_MODEL

gtk/gtk.h

@@ -44,6 +44,7 @@
 #include <gtk/gtkappchooserbutton.h>
 #include <gtk/gtkapplication.h>
 #include <gtk/gtkapplicationwindow.h>
+#include <gtk/gtkarraystore.h>
 #include <gtk/gtkaspectframe.h>
 #include <gtk/gtkassistant.h>
 #include <gtk/gtkbinlayout.h>

gtk/gtkarrayimplprivate.h

@@ -1,137 +0,0 @@
-#ifndef __GTK_ARRAY_IMPL_PRIVATE_H__
-#define __GTK_ARRAY_IMPL_PRIVATE_H__
-
-
-/* This is a dumbed-down GPtrArray, which takes some stack
- * space to use. When using this, the general case should always
- * be that the number of elements is lower than reserved_size.
- * The GPtrArray should only be used in extreme cases.
- */
-
-typedef struct
-{
-  guint reserved_size;
-  guint len;
-  void **stack_space;
-  GPtrArray *ptr_array;
-
-} GtkArray;
-
-
-static inline void
-gtk_array_init (GtkArray   *self,
-                void     **stack_space,
-                guint      reserved_size)
-{
-  self->reserved_size = reserved_size;
-  self->len = 0;
-  self->stack_space = stack_space;
-  self->ptr_array = NULL;
-}
-
-static inline void *
-gtk_array_index (const GtkArray *self,
-                 guint           index)
-{
-  g_assert (index < self->len);
-
-  if (G_LIKELY (!self->ptr_array))
-    return self->stack_space[index];
-
-  return g_ptr_array_index (self->ptr_array, index);
-}
-
-static inline void
-gtk_array_add (GtkArray *self,
-               void     *element)
-{
-  if (G_LIKELY (self->len < self->reserved_size))
-    {
-      self->stack_space[self->len] = element;
-      self->len++;
-      return;
-    }
-
-  /* Need to fall back to the GPtrArray */
-  if (G_UNLIKELY (!self->ptr_array))
-    {
-      self->ptr_array = g_ptr_array_new_full (self->len + 1, NULL);
-      memcpy (self->ptr_array->pdata, self->stack_space, sizeof (void *) * self->len);
-      self->ptr_array->len = self->len;
-    }
-
-  g_ptr_array_add (self->ptr_array, element);
-  self->len++; /* We still count self->len */
-}
-
-static inline void
-gtk_array_insert (GtkArray *self,
-                  guint     index,
-                  void     *element)
-{
-  if (index >= self->len)
-    {
-      gtk_array_add (self, element);
-      return;
-    }
-
-  if (G_LIKELY (self->len < self->reserved_size))
-    {
-      memmove (self->stack_space + index + 1, self->stack_space + index,
-               sizeof (void *) * (self->len - index));
-      self->stack_space[index] = element;
-      self->len++;
-      return;
-    }
-
-  if (G_UNLIKELY (!self->ptr_array))
-    {
-      self->ptr_array = g_ptr_array_new_full (self->len + 1, NULL);
-      memcpy (self->ptr_array->pdata, self->stack_space, sizeof (void *) * self->len);
-      self->ptr_array->len = self->len;
-    }
-
-  g_assert (self->ptr_array);
-  g_ptr_array_insert (self->ptr_array, index, element);
-  self->len++;
-}
-
-static inline void
-gtk_array_free (GtkArray       *self,
-                GDestroyNotify  element_free_func)
-{
-  guint i;
-
-  if (G_LIKELY (!self->ptr_array))
-    {
-      if (element_free_func)
-        {
-          for (i = 0; i < self->len; i++)
-            element_free_func (self->stack_space[i]);
-        }
-
-      return;
-    }
-
-  g_assert (self->ptr_array);
-
-  if (element_free_func)
-    {
-      for (i = 0; i < self->ptr_array->len; i++)
-        element_free_func (g_ptr_array_index (self->ptr_array, i));
-    }
-
-  g_ptr_array_free (self->ptr_array, TRUE);
-}
-
-static inline void **
-gtk_array_get_data (GtkArray *self)
-{
-  if (G_LIKELY (!self->ptr_array))
-    return self->stack_space;
-
-  return self->ptr_array->pdata;
-}
-
-
-#endif

gtk/gtkarraystore.c

@@ -0,0 +1,221 @@
+/*
+ * 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 "config.h"
+
+#include "gtkarraystore.h"
+
+#define GTK_VECTOR_ELEMENT_TYPE GObject *
+#define GTK_VECTOR_FREE_FUNC g_object_unref
+#include "gtkvectorimpl.c"
+
+/**
+ * SECTION:gtkarraystore
+ * @title: GtkArrayStore
+ * @short_description: A simple array implementation of #GListModel
+ *
+ * #GtkArrayStore is a simple implementation of #GListModel that stores all
+ * items in memory.
+ *
+ * It provides appending, deletions, and lookups in O(1) time and insertions
+ * in O(N) time. it is implemented using an array.
+ */
+
+/**
+ * GtkArrayStore:
+ *
+ * #GtkArrayStore is an opaque data structure and can only be accessed
+ * using the following functions.
+ **/
+
+struct _GtkArrayStore
+{
+  GObject parent_instance;
+
+  GtkVector items;
+};
+
+static void gtk_array_store_iface_init (GListModelInterface *iface);
+
+G_DEFINE_TYPE_WITH_CODE (GtkArrayStore, gtk_array_store, G_TYPE_OBJECT,
+                         G_IMPLEMENT_INTERFACE (G_TYPE_LIST_MODEL, gtk_array_store_iface_init));
+
+static void
+gtk_array_store_dispose (GObject *object)
+{
+  GtkArrayStore *self = GTK_ARRAY_STORE (object);
+
+  gtk_vector_clear (&self->items);
+
+  G_OBJECT_CLASS (gtk_array_store_parent_class)->dispose (object);
+}
+
+static void
+gtk_array_store_class_init (GtkArrayStoreClass *klass)
+{
+  GObjectClass *object_class = G_OBJECT_CLASS (klass);
+
+  object_class->dispose = gtk_array_store_dispose;
+}
+
+static GType
+gtk_array_store_get_item_type (GListModel *list)
+{
+  return G_TYPE_OBJECT;
+}
+
+static guint
+gtk_array_store_get_n_items (GListModel *list)
+{
+  GtkArrayStore *self = GTK_ARRAY_STORE (list);
+
+  return gtk_vector_get_size (&self->items);
+}
+
+static gpointer
+gtk_array_store_get_item (GListModel *list,
+                          guint       position)
+{
+  GtkArrayStore *self = GTK_ARRAY_STORE (list);
+
+  if (position >= gtk_vector_get_size (&self->items))
+    return NULL;
+
+  return g_object_ref (gtk_vector_get (&self->items, position));
+}
+
+static void
+gtk_array_store_iface_init (GListModelInterface *iface)
+{
+  iface->get_item_type = gtk_array_store_get_item_type;
+  iface->get_n_items = gtk_array_store_get_n_items;
+  iface->get_item = gtk_array_store_get_item;
+}
+
+static void
+gtk_array_store_init (GtkArrayStore *self)
+{
+  gtk_vector_init (&self->items);
+}
+
+/**
+ * gtk_array_store_new:
+ * @item_type: the #GType of items in the list
+ *
+ * Creates a new #GtkArrayStore with items of type @item_type. @item_type
+ * must be a subclass of #GObject.
+ *
+ * Returns: a new #GtkArrayStore
+ */
+GtkArrayStore *
+gtk_array_store_new (void)
+{
+  return g_object_new (GTK_TYPE_ARRAY_STORE, NULL);
+}
+
+/**
+ * gtk_array_store_append:
+ * @self: a #GtkArrayStore
+ * @item: (type GObject): the new item
+ *
+ * Appends @item to @self. @item must be of type #GtkArrayStore:item-type.
+ *
+ * This function takes a ref on @item.
+ *
+ * Use gtk_array_store_splice() to append multiple items at the same time
+ * efficiently.
+ */
+void
+gtk_array_store_append (GtkArrayStore *self,
+                        gpointer       item)
+{
+  guint position;
+
+  g_return_if_fail (GTK_IS_ARRAY_STORE (self));
+
+  position = gtk_vector_get_size (&self->items);
+  gtk_vector_append (&self->items, g_object_ref (item));
+  g_list_model_items_changed (G_LIST_MODEL (self), position, 0, 1);
+}
+
+/**
+ * gtk_array_store_remove_all:
+ * @self: a #GtkArrayStore
+ *
+ * Removes all items from @self.
+ *
+ * Since: 2.44
+ */
+void
+gtk_array_store_remove_all (GtkArrayStore *self)
+{
+  guint n_items;
+
+  g_return_if_fail (GTK_IS_ARRAY_STORE (self));
+
+  n_items = gtk_vector_get_size (&self->items);
+  gtk_vector_clear (&self->items);
+
+  g_list_model_items_changed (G_LIST_MODEL (self), 0, n_items, 0);
+}
+
+/**
+ * gtk_array_store_splice:
+ * @self: a #GtkArrayStore
+ * @position: the position at which to make the change
+ * @n_removals: the number of items to remove
+ * @additions: (array length=n_additions) (element-type GObject): the items to add
+ * @n_additions: the number of items to add
+ *
+ * Changes @self by removing @n_removals items and adding @n_additions
+ * items to it. @additions must contain @n_additions items of type
+ * #GtkArrayStore:item-type.  %NULL is not permitted.
+ *
+ * This function is more efficient than gtk_array_store_insert() and
+ * gtk_array_store_remove(), because it only emits
+ * #GListModel::items-changed once for the change.
+ *
+ * This function takes a ref on each item in @additions.
+ *
+ * The parameters @position and @n_removals must be correct (ie:
+ * @position + @n_removals must be less than or equal to the length of
+ * the list at the time this function is called).
+ *
+ * Since: 2.44
+ */
+void
+gtk_array_store_splice (GtkArrayStore *self,
+                        guint       position,
+                        guint       n_removals,
+                        gpointer   *additions,
+                        guint       n_additions)
+{
+  guint i;
+
+  g_return_if_fail (GTK_IS_ARRAY_STORE (self));
+  g_return_if_fail (position + n_removals >= position); /* overflow */
+  g_return_if_fail (position + n_removals <= gtk_vector_get_size (&self->items));
+
+  for (i = 0; i < n_additions; i++)
+    g_object_ref (additions[i]);
+
+  gtk_vector_splice (&self->items, position, n_removals, (GObject **) additions, n_additions);
+
+  g_list_model_items_changed (G_LIST_MODEL (self), position, n_removals, n_additions);
+}

gtk/gtkarraystore.h

@@ -0,0 +1,54 @@
+/*
+ * 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>
+ */
+
+#ifndef __GTK_ARRAY_STORE_H__
+#define __GTK_ARRAY_STORE_H__
+
+#if !defined (__GTK_H_INSIDE__) && !defined (GTK_COMPILATION)
+#error "Only <gtk/gtk.h> can be included directly."
+#endif
+
+#include <gdk/gdk.h>
+
+G_BEGIN_DECLS
+
+#define GTK_TYPE_ARRAY_STORE (gtk_array_store_get_type ())
+GDK_AVAILABLE_IN_ALL
+G_DECLARE_FINAL_TYPE(GtkArrayStore, gtk_array_store, GTK, ARRAY_STORE, GObject)
+
+GDK_AVAILABLE_IN_ALL
+GtkArrayStore *         gtk_array_store_new                             (void);
+
+GDK_AVAILABLE_IN_ALL
+void                    gtk_array_store_append                          (GtkArrayStore  *store,
+                                                                         gpointer        item);
+
+GDK_AVAILABLE_IN_ALL
+void                    gtk_array_store_remove_all                      (GtkArrayStore  *store);
+
+GDK_AVAILABLE_IN_ALL
+void                    gtk_array_store_splice                          (GtkArrayStore  *store,
+                                                                         guint           position,
+                                                                         guint           n_removals,
+                                                                         gpointer       *additions,
+                                                                         guint           n_additions);
+
+G_END_DECLS
+
+#endif /* __GTK_ARRAY_STORE_H__ */

gtk/gtkcssprovider.c

@@ -391,9 +391,9 @@ gtk_css_provider_init (GtkCssProvider *css_provider)
 }
 
 static void
-verify_tree_match_results (GtkCssProvider *provider,
-                           GtkCssNode     *node,
-                           GtkArray       *tree_rules)
+verify_tree_match_results (GtkCssProvider        *provider,
+                           GtkCssNode            *node,
+                           GtkCssSelectorMatches *tree_rules)
 {
 #ifdef VERIFY_TREE
   GtkCssProviderPrivate *priv = gtk_css_provider_get_instance_private (provider);
@@ -407,9 +407,9 @@ verify_tree_match_results (GtkCssProvider *provider,
 
       ruleset = &g_array_index (priv->rulesets, GtkCssRuleset, i);
 
-      for (j = 0; j < tree_rules->len; j++)
+      for (j = 0; j < gtk_css_selector_matches_get_size (tree_rules); j++)
 	{
-	  if (ruleset == gtk_array_index (tree_rules, j))
+	  if (ruleset == gtk_css_selector_matches_get (tree_rules, j))
 	    {
 	      found = TRUE;
 	      break;
@@ -459,22 +459,21 @@ gtk_css_style_provider_lookup (GtkStyleProvider             *provider,
   GtkCssRuleset *ruleset;
   guint j;
   int i;
-  GtkArray tree_rules_array;
-  GtkCssRuleset *rules_stack[32];
+  GtkCssSelectorMatches tree_rules;
 
   if (_gtk_css_selector_tree_is_empty (priv->tree))
     return;
 
-  gtk_array_init (&tree_rules_array, (void**)rules_stack, 32);
-  _gtk_css_selector_tree_match_all (priv->tree, filter, node, &tree_rules_array);
+  gtk_css_selector_matches_init (&tree_rules);
+  _gtk_css_selector_tree_match_all (priv->tree, filter, node, &tree_rules);
 
-  if (tree_rules_array.len > 0)
+  if (!gtk_css_selector_matches_is_empty (&tree_rules))
     {
-      verify_tree_match_results (css_provider, node, &tree_rules_array);
+      verify_tree_match_results (css_provider, node, &tree_rules);
 
-      for (i = tree_rules_array.len - 1; i >= 0; i--)
+      for (i = gtk_css_selector_matches_get_size (&tree_rules) - 1; i >= 0; i--)
         {
-          ruleset = gtk_array_index (&tree_rules_array, i);
+          ruleset = gtk_css_selector_matches_get (&tree_rules, i);
 
           if (ruleset->styles == NULL)
             continue;
@@ -493,9 +492,8 @@ gtk_css_style_provider_lookup (GtkStyleProvider             *provider,
                                    ruleset->styles[j].value);
             }
         }
-
-      gtk_array_free (&tree_rules_array, NULL);
     }
+  gtk_css_selector_matches_clear (&tree_rules);
 
   if (change)
     *change = gtk_css_selector_tree_get_change_all (priv->tree, filter, node);

gtk/gtkcssselector.c

@@ -24,7 +24,6 @@
 
 #include "gtkcssprovider.h"
 #include "gtkstylecontextprivate.h"
-#include "gtkarrayimplprivate.h"
 
 #include <errno.h>
 #if defined(_MSC_VER) && _MSC_VER >= 1500
@@ -152,14 +151,14 @@ gtk_css_selector_tree_get_matches (const GtkCssSelectorTree *tree)
 }
 
 static void
-gtk_array_insert_sorted (GtkArray *array,
-                         gpointer  data)
+gtk_css_selector_matches_insert_sorted (GtkCssSelectorMatches *matches,
+                                        gpointer               data)
 {
   guint i;
 
-  for (i = 0; i < array->len; i++)
+  for (i = 0; i < gtk_css_selector_matches_get_size (matches); i++)
     {
-      gpointer elem = gtk_array_index (array, i);
+      gpointer elem = gtk_css_selector_matches_get (matches, i);
 
       if (data == elem)
         return;
@@ -168,7 +167,7 @@ gtk_array_insert_sorted (GtkArray *array,
         break;
     }
 
-  gtk_array_insert (array, i, data);
+  gtk_css_selector_matches_splice (matches, i, 0, (gpointer[1]) { data }, 1);
 }
 
 static inline gboolean
@@ -1877,7 +1876,7 @@ gtk_css_selector_tree_get_change (const GtkCssSelectorTree     *tree,
 
 static void
 gtk_css_selector_tree_found_match (const GtkCssSelectorTree  *tree,
-                                   GtkArray                  *results)
+                                   GtkCssSelectorMatches     *results)
 {
   int i;
   gpointer *matches;
@@ -1887,7 +1886,7 @@ gtk_css_selector_tree_found_match (const GtkCssSelectorTree  *tree,
     return;
 
   for (i = 0; matches[i] != NULL; i++)
-    gtk_array_insert_sorted (results, matches[i]);
+    gtk_css_selector_matches_insert_sorted (results, matches[i]);
 }
 
 static gboolean
@@ -1895,7 +1894,7 @@ gtk_css_selector_tree_match (const GtkCssSelectorTree      *tree,
                              const GtkCountingBloomFilter  *filter,
                              gboolean                       match_filter,
                              GtkCssNode                    *node,
-                             GtkArray                      *results)
+                             GtkCssSelectorMatches         *results)
 {
   const GtkCssSelectorTree *prev;
   GtkCssNode *child;
@@ -1932,7 +1931,7 @@ void
 _gtk_css_selector_tree_match_all (const GtkCssSelectorTree     *tree,
                                   const GtkCountingBloomFilter *filter,
                                   GtkCssNode                   *node,
-                                  GtkArray                     *out_tree_rules)
+                                  GtkCssSelectorMatches        *out_tree_rules)
 {
   const GtkCssSelectorTree *iter;
 
@@ -2117,8 +2116,7 @@ subdivide_infos (GByteArray                 *array,
   GHashTableIter iter;
   guint max_count;
   gpointer key, value;
-  void *exact_matches_stack[8];
-  GtkArray exact_matches_array;
+  GtkCssSelectorMatches exact_matches;
   gint32 res;
   guint i;
 
@@ -2160,7 +2158,7 @@ subdivide_infos (GByteArray                 *array,
   matched_infos = g_alloca (sizeof (GtkCssSelectorRuleSetInfo *) * n_infos);
   remaining_infos = g_alloca (sizeof (GtkCssSelectorRuleSetInfo *) * n_infos);
 
-  gtk_array_init (&exact_matches_array, (void**)exact_matches_stack, 8);
+  gtk_css_selector_matches_init (&exact_matches);
   for (i = 0; i < n_infos; i++)
     {
       GtkCssSelectorRuleSetInfo *info = infos[i];
@@ -2171,7 +2169,7 @@ subdivide_infos (GByteArray                 *array,
 	  if (info->current_selector == NULL)
 	    {
 	      /* Matches current node */
-              gtk_array_add (&exact_matches_array, info->match);
+              gtk_css_selector_matches_append (&exact_matches, info->match);
 	      if (info->selector_match != NULL)
 		*info->selector_match = GUINT_TO_POINTER (tree_offset);
 	    }
@@ -2188,17 +2186,16 @@ subdivide_infos (GByteArray                 *array,
 	}
     }
 
-  if (exact_matches_array.len > 0)
+  if (!gtk_css_selector_matches_is_empty (&exact_matches))
     {
-      gtk_array_add (&exact_matches_array, NULL); /* Null terminate */
+      gtk_css_selector_matches_append (&exact_matches, NULL); /* Null terminate */
       res = array->len;
-      g_byte_array_append (array, (guint8 *)gtk_array_get_data (&exact_matches_array),
-                           exact_matches_array.len * sizeof (gpointer));
-
-      gtk_array_free (&exact_matches_array, NULL);
+      g_byte_array_append (array, (guint8 *) gtk_css_selector_matches_get_data (&exact_matches),
+                           gtk_css_selector_matches_get_size (&exact_matches) * sizeof (gpointer));
     }
   else
     res = GTK_CSS_SELECTOR_TREE_EMPTY_OFFSET;
+  gtk_css_selector_matches_clear (&exact_matches);
   get_tree (array, tree_offset)->matches_offset = res;
 
   res = subdivide_infos (array, matched_infos, n_matched, tree_offset);

gtk/gtkcssselectorprivate.h

@@ -21,7 +21,12 @@
 #include "gtk/gtkcountingbloomfilterprivate.h"
 #include "gtk/gtkcsstypesprivate.h"
 #include "gtk/gtkcssparserprivate.h"
-#include "gtk/gtkarrayimplprivate.h"
+
+#define GTK_VECTOR_ELEMENT_TYPE gpointer
+#define GTK_VECTOR_TYPE_NAME GtkCssSelectorMatches
+#define GTK_VECTOR_NAME gtk_css_selector_matches
+#define GTK_VECTOR_PREALLOC 32
+#include "gtk/gtkvectorimpl.c"
 
 G_BEGIN_DECLS
 
@@ -45,8 +50,8 @@ int               _gtk_css_selector_compare         (const GtkCssSelector   *a,
 void         _gtk_css_selector_tree_free             (GtkCssSelectorTree       *tree);
 void         _gtk_css_selector_tree_match_all        (const GtkCssSelectorTree *tree,
                                                       const GtkCountingBloomFilter *filter,
-                                                      GtkCssNode                   *node,
-                                                      GtkArray                     *out_tree_rules);
+                                                      GtkCssNode               *node,
+                                                      GtkCssSelectorMatches    *out_tree_rules);
 GtkCssChange gtk_css_selector_tree_get_change_all    (const GtkCssSelectorTree *tree,
                                                       const GtkCountingBloomFilter *filter,
 						      GtkCssNode               *node);

gtk/gtkfilterlistmodel.c

@@ -21,7 +21,7 @@
 
 #include "gtkfilterlistmodel.h"
 
-#include "gtkrbtreeprivate.h"
+#include "gtkbitset.h"
 #include "gtkintl.h"
 #include "gtkprivate.h"
 
@@ -35,29 +35,21 @@
  * listmodel.
  * It hides some elements from the other model according to
  * criteria given by a #GtkFilter.
+ *
+ * The model can be set up to do incremental searching, so that
+ * filtering long lists doesn't block the UI. See
+ * gtk_filter_list_model_set_incremental() for details.
  */
 
 enum {
   PROP_0,
   PROP_FILTER,
+  PROP_INCREMENTAL,
   PROP_MODEL,
+  PROP_PENDING,
   NUM_PROPERTIES
 };
 
-typedef struct _FilterNode FilterNode;
-typedef struct _FilterAugment FilterAugment;
-
-struct _FilterNode
-{
-  guint visible : 1;
-};
-
-struct _FilterAugment
-{
-  guint n_items;
-  guint n_visible;
-};
-
 struct _GtkFilterListModel
 {
   GObject parent_instance;
@@ -65,8 +57,11 @@ struct _GtkFilterListModel
   GListModel *model;
   GtkFilter *filter;
   GtkFilterMatch strictness;
+  gboolean incremental;
 
-  GtkRbTree *items; /* NULL if strictness != GTK_FILTER_MATCH_SOME */
+  GtkBitset *matches; /* NULL if strictness != GTK_FILTER_MATCH_SOME */
+  GtkBitset *pending; /* not yet filtered items or NULL if all filtered */
+  guint pending_cb; /* idle callback handle */
 };
 
 struct _GtkFilterListModelClass
@@ -76,119 +71,6 @@ struct _GtkFilterListModelClass
 
 static GParamSpec *properties[NUM_PROPERTIES] = { NULL, };
 
-static void
-gtk_filter_list_model_augment (GtkRbTree *filter,
-                               gpointer   _aug,
-                               gpointer   _node,
-                               gpointer   left,
-                               gpointer   right)
-{
-  FilterNode *node = _node;
-  FilterAugment *aug = _aug;
-
-  aug->n_items = 1;
-  aug->n_visible = node->visible ? 1 : 0;
-
-  if (left)
-    {
-      FilterAugment *left_aug = gtk_rb_tree_get_augment (filter, left);
-      aug->n_items += left_aug->n_items;
-      aug->n_visible += left_aug->n_visible;
-    }
-  if (right)
-    {
-      FilterAugment *right_aug = gtk_rb_tree_get_augment (filter, right);
-      aug->n_items += right_aug->n_items;
-      aug->n_visible += right_aug->n_visible;
-    }
-}
-
-static FilterNode *
-gtk_filter_list_model_get_nth_filtered (GtkRbTree *tree,
-                                        guint      position,
-                                        guint     *out_unfiltered)
-{
-  FilterNode *node, *tmp;
-  guint unfiltered;
-
-  node = gtk_rb_tree_get_root (tree);
-  unfiltered = 0;
-
-  while (node)
-    {
-      tmp = gtk_rb_tree_node_get_left (node);
-      if (tmp)
-        {
-          FilterAugment *aug = gtk_rb_tree_get_augment (tree, tmp);
-          if (position < aug->n_visible)
-            {
-              node = tmp;
-              continue;
-            }
-          position -= aug->n_visible;
-          unfiltered += aug->n_items;
-        }
-
-      if (node->visible)
-        {
-          if (position == 0)
-            break;
-          position--;
-        }
-
-      unfiltered++;
-
-      node = gtk_rb_tree_node_get_right (node);
-    }
-
-  if (out_unfiltered)
-    *out_unfiltered = unfiltered;
-
-  return node;
-}
-
-static FilterNode *
-gtk_filter_list_model_get_nth (GtkRbTree *tree,
-                               guint      position,
-                               guint     *out_filtered)
-{
-  FilterNode *node, *tmp;
-  guint filtered;
-
-  node = gtk_rb_tree_get_root (tree);
-  filtered = 0;
-
-  while (node)
-    {
-      tmp = gtk_rb_tree_node_get_left (node);
-      if (tmp)
-        {
-          FilterAugment *aug = gtk_rb_tree_get_augment (tree, tmp);
-          if (position < aug->n_items)
-            {
-              node = tmp;
-              continue;
-            }
-          position -= aug->n_items;
-          filtered += aug->n_visible;
-        }
-
-      if (position == 0)
-        break;
-
-      position--;
-      if (node->visible)
-        filtered++;
-
-      node = gtk_rb_tree_node_get_right (node);
-    }
-
-  if (out_filtered)
-    *out_filtered = filtered;
-
-  return node;
-}
-
 static GType
 gtk_filter_list_model_get_item_type (GListModel *list)
 {
@@ -199,8 +81,6 @@ static guint
 gtk_filter_list_model_get_n_items (GListModel *list)
 {
   GtkFilterListModel *self = GTK_FILTER_LIST_MODEL (list);
-  FilterAugment *aug;
-  FilterNode *node;
 
   switch (self->strictness)
     {
@@ -211,18 +91,12 @@ gtk_filter_list_model_get_n_items (GListModel *list)
       return g_list_model_get_n_items (self->model);
 
     case GTK_FILTER_MATCH_SOME:
-      break;
+      return gtk_bitset_get_size (self->matches);
 
     default:
       g_assert_not_reached ();
+      return 0;
     }
-
-  node = gtk_rb_tree_get_root (self->items);
-  if (node == NULL)
-    return 0;
-
-  aug = gtk_rb_tree_get_augment (self->items, node);
-  return aug->n_visible;
 }
 
 static gpointer
@@ -242,7 +116,9 @@ gtk_filter_list_model_get_item (GListModel *list,
       break;
 
     case GTK_FILTER_MATCH_SOME:
-      gtk_filter_list_model_get_nth_filtered (self->items, position, &unfiltered);
+      unfiltered = gtk_bitset_get_nth (self->matches, position);
+      if (unfiltered == 0 && position >= gtk_bitset_get_size (self->matches))
+        return NULL;
       break;
 
     default:
@@ -264,8 +140,8 @@ G_DEFINE_TYPE_WITH_CODE (GtkFilterListModel, gtk_filter_list_model, G_TYPE_OBJEC
                          G_IMPLEMENT_INTERFACE (G_TYPE_LIST_MODEL, gtk_filter_list_model_model_init))
 
 static gboolean
-gtk_filter_list_model_run_filter (GtkFilterListModel *self,
-                                  guint               position)
+gtk_filter_list_model_run_filter_on_item (GtkFilterListModel *self,
+                                          guint               position)
 {
   gpointer item;
   gboolean visible;
@@ -280,26 +156,120 @@ gtk_filter_list_model_run_filter (GtkFilterListModel *self,
   return visible;
 }
 
-static guint
-gtk_filter_list_model_add_items (GtkFilterListModel *self,
-                                 FilterNode         *after,
-                                 guint               position,
-                                 guint               n_items)
+static void
+gtk_filter_list_model_run_filter (GtkFilterListModel *self,
+                                  guint               n_steps)
 {
-  FilterNode *node;
-  guint i, n_visible;
+  GtkBitsetIter iter;
+  guint i, pos;
+  gboolean more;
 
-  n_visible = 0;
+  g_return_if_fail (GTK_IS_FILTER_LIST_MODEL (self));
   
-  for (i = 0; i < n_items; i++)
+  if (self->pending == NULL)
+    return;
+
+  for (i = 0, more = gtk_bitset_iter_init_first (&iter, self->pending, &pos);
+       i < n_steps && more;
+       i++, more = gtk_bitset_iter_next (&iter, &pos))
     {
-      node = gtk_rb_tree_insert_before (self->items, after);
-      node->visible = gtk_filter_list_model_run_filter (self, position + i);
-      if (node->visible)
-        n_visible++;
+      if (gtk_filter_list_model_run_filter_on_item (self, pos))
+        gtk_bitset_add (self->matches, pos);
     }
 
-  return n_visible;
+  if (more)
+    gtk_bitset_remove_range_closed (self->pending, 0, pos);
+  else
+    g_clear_pointer (&self->pending, gtk_bitset_unref);
+  g_object_notify_by_pspec (G_OBJECT (self), properties[PROP_PENDING]);
+
+  return;
+}
+
+static void
+gtk_filter_list_model_stop_filtering (GtkFilterListModel *self)
+{
+  gboolean notify_pending = self->pending != NULL;
+
+  g_clear_pointer (&self->pending, gtk_bitset_unref);
+  g_clear_handle_id (&self->pending_cb, g_source_remove);
+
+  if (notify_pending)
+    g_object_notify_by_pspec (G_OBJECT (self), properties[PROP_PENDING]);
+}
+
+static void
+gtk_filter_list_model_emit_items_changed_for_changes (GtkFilterListModel *self,
+                                                      GtkBitset          *old)
+{
+  GtkBitset *changes;
+
+  changes = gtk_bitset_copy (self->matches);
+  gtk_bitset_difference (changes, old);
+  if (!gtk_bitset_is_empty (changes))
+    {
+      guint min, max;
+
+      min = gtk_bitset_get_minimum (changes);
+      max = gtk_bitset_get_maximum (changes);
+      g_list_model_items_changed (G_LIST_MODEL (self),
+                                  min > 0 ? gtk_bitset_get_size_in_range (self->matches, 0, min - 1) : 0,
+                                  gtk_bitset_get_size_in_range (old, min, max),
+                                  gtk_bitset_get_size_in_range (self->matches, min, max));
+    }
+  gtk_bitset_unref (changes);
+  gtk_bitset_unref (old);
+}
+
+static gboolean
+gtk_filter_list_model_run_filter_cb (gpointer data)
+{
+  GtkFilterListModel *self = data;
+  GtkBitset *old;
+
+  old = gtk_bitset_copy (self->matches);
+  gtk_filter_list_model_run_filter (self, 512);
+
+  if (self->pending == NULL)
+    gtk_filter_list_model_stop_filtering (self);
+
+  gtk_filter_list_model_emit_items_changed_for_changes (self, old);
+
+  return G_SOURCE_CONTINUE;
+}
+
+/* NB: bitset is (transfer full) */
+static void
+gtk_filter_list_model_start_filtering (GtkFilterListModel *self,
+                                       GtkBitset          *items)
+{
+  if (self->pending)
+    {
+      gtk_bitset_union (self->pending, items);
+      gtk_bitset_unref (items);
+      g_object_notify_by_pspec (G_OBJECT (self), properties[PROP_PENDING]);
+      return;
+    }
+
+  if (gtk_bitset_is_empty (items))
+    {
+      gtk_bitset_unref (items);
+      return;
+    }
+
+  self->pending = items;
+
+  if (!self->incremental)
+    {
+      gtk_filter_list_model_run_filter (self, G_MAXUINT);
+      g_assert (self->pending == NULL);
+      return;
+    }
+
+  g_object_notify_by_pspec (G_OBJECT (self), properties[PROP_PENDING]);
+  g_assert (self->pending_cb == 0);
+  self->pending_cb = g_idle_add (gtk_filter_list_model_run_filter_cb, self);
+  g_source_set_name_by_id (self->pending_cb, "[gtk] gtk_filter_list_model_run_filter_cb");
 }
 
 static void
@@ -309,8 +279,7 @@ gtk_filter_list_model_items_changed_cb (GListModel         *model,
                                         guint               added,
                                         GtkFilterListModel *self)
 {
-  FilterNode *node;
-  guint i, filter_position, filter_removed, filter_added;
+  guint filter_removed, filter_added;
 
   switch (self->strictness)
     {
@@ -328,22 +297,27 @@ gtk_filter_list_model_items_changed_cb (GListModel         *model,
       g_assert_not_reached ();
     }
 
-  node = gtk_filter_list_model_get_nth (self->items, position, &filter_position);
+  if (removed > 0)
+    filter_removed = gtk_bitset_get_size_in_range (self->matches, position, position + removed - 1);
+  else
+    filter_removed = 0;
 
-  filter_removed = 0;
-  for (i = 0; i < removed; i++)
+  gtk_bitset_slice (self->matches, position, removed, added);
+  if (self->pending)
+    gtk_bitset_slice (self->pending, position, removed, added);
+
+  if (added > 0)
     {
-      FilterNode *next = gtk_rb_tree_node_get_next (node);
-      if (node->visible)
-        filter_removed++;
-      gtk_rb_tree_remove (self->items, node);
-      node = next;
+      gtk_filter_list_model_start_filtering (self, gtk_bitset_new_range (position, added));
+      filter_added = gtk_bitset_get_size_in_range (self->matches, position, position + added - 1);
     }
-
-  filter_added = gtk_filter_list_model_add_items (self, node, position, added);
+  else
+    filter_added = 0;
 
   if (filter_removed > 0 || filter_added > 0)
-    g_list_model_items_changed (G_LIST_MODEL (self), filter_position, filter_removed, filter_added);
+    g_list_model_items_changed (G_LIST_MODEL (self),
+                                position > 0 ? gtk_bitset_get_size_in_range (self->matches, 0, position - 1) : 0,
+                                filter_removed, filter_added);
 }
 
 static void
@@ -360,6 +334,10 @@ gtk_filter_list_model_set_property (GObject      *object,
       gtk_filter_list_model_set_filter (self, g_value_get_object (value));
       break;
 
+    case PROP_INCREMENTAL:
+      gtk_filter_list_model_set_incremental (self, g_value_get_boolean (value));
+      break;
+
     case PROP_MODEL:
       gtk_filter_list_model_set_model (self, g_value_get_object (value));
       break;
@@ -384,10 +362,18 @@ gtk_filter_list_model_get_property (GObject     *object,
       g_value_set_object (value, self->filter);
       break;
 
+    case PROP_INCREMENTAL:
+      g_value_set_boolean (value, self->incremental);
+      break;
+
     case PROP_MODEL:
       g_value_set_object (value, self->model);
       break;
 
+    case PROP_PENDING:
+      g_value_set_uint (value, gtk_filter_list_model_get_pending (self));
+      break;
+
     default:
       G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
       break;
@@ -400,109 +386,16 @@ gtk_filter_list_model_clear_model (GtkFilterListModel *self)
   if (self->model == NULL)
     return;
 
+  gtk_filter_list_model_stop_filtering (self);
   g_signal_handlers_disconnect_by_func (self->model, gtk_filter_list_model_items_changed_cb, self);
   g_clear_object (&self->model);
-  if (self->items)
-    gtk_rb_tree_remove_all (self->items);
-}
-
-/*<private>
- * gtk_filter_list_model_find_filtered:
- * @self: a #GtkFilterListModel
- * @start: (out) (caller-allocates): number of unfiltered items
- *     at start of list
- * @end: (out) (caller-allocates): number of unfiltered items
- *     at end of list
- * @n_items: (out) (caller-allocates): number of unfiltered items in
- *     list
- *
- * Checks if elements in self->items are filtered out and returns
- * the range that they occupy.  
- * This function is intended to be used for GListModel::items-changed
- * emissions, so it is called in an intermediate state for @self.
- *
- * Returns: %TRUE if elements are filtered out, %FALSE if none are
- **/
-static gboolean
-gtk_filter_list_model_find_filtered (GtkFilterListModel *self,
-                                     guint              *start,
-                                     guint              *end,
-                                     guint              *n_items)
-{
-  FilterNode *root, *node, *tmp;
-  FilterAugment *aug;
-
-  if (self->items == NULL || self->model == NULL)
-    return FALSE;
-
-  root = gtk_rb_tree_get_root (self->items);
-  if (root == NULL)
-    return FALSE; /* empty parent model */
-
-  aug = gtk_rb_tree_get_augment (self->items, root);
-  if (aug->n_items == aug->n_visible)
-    return FALSE; /* all items visible */
-
-  /* find first filtered */
-  *start = 0;
-  *end = 0;
-  *n_items = aug->n_visible;
-
-  node = root;
-  while (node)
-    {
-      tmp = gtk_rb_tree_node_get_left (node);
-      if (tmp)
-        {
-          aug = gtk_rb_tree_get_augment (self->items, tmp);
-          if (aug->n_visible < aug->n_items)
-            {
-              node = tmp;
-              continue;
-            }
-          *start += aug->n_items;
-        }
-
-      if (!node->visible)
-        break;
-
-      (*start)++;
-
-      node = gtk_rb_tree_node_get_right (node);
-    }
-
-  /* find last filtered by doing everything the opposite way */
-  node = root;
-  while (node)
-    {
-      tmp = gtk_rb_tree_node_get_right (node);
-      if (tmp)
-        {
-          aug = gtk_rb_tree_get_augment (self->items, tmp);
-          if (aug->n_visible < aug->n_items)
-            {
-              node = tmp;
-              continue;
-            }
-          *end += aug->n_items;
-        }
-
-      if (!node->visible)
-        break;
-
-      (*end)++;
-
-      node = gtk_rb_tree_node_get_left (node);
-    }
-
-  return TRUE;
+  if (self->matches)
+    gtk_bitset_remove_all (self->matches);
 }
 
 static void
-gtk_filter_list_model_refilter (GtkFilterListModel *self);
-
-static void
-gtk_filter_list_model_update_strictness_and_refilter (GtkFilterListModel *self)
+gtk_filter_list_model_refilter (GtkFilterListModel *self,
+                                GtkFilterChange     change)
 {
   GtkFilterMatch new_strictness;
 
@@ -520,8 +413,9 @@ gtk_filter_list_model_update_strictness_and_refilter (GtkFilterListModel *self)
     case GTK_FILTER_MATCH_NONE:
       {
         guint n_before = g_list_model_get_n_items (G_LIST_MODEL (self));
-        g_clear_pointer (&self->items, gtk_rb_tree_unref);
+        g_clear_pointer (&self->matches, gtk_bitset_unref);
         self->strictness = new_strictness;
+        gtk_filter_list_model_stop_filtering (self);
         if (n_before > 0)
           g_list_model_items_changed (G_LIST_MODEL (self), 0, n_before, 0);
       }
@@ -541,16 +435,35 @@ gtk_filter_list_model_update_strictness_and_refilter (GtkFilterListModel *self)
         case GTK_FILTER_MATCH_SOME:
           {
             guint start, end, n_before, n_after;
+
+            gtk_filter_list_model_stop_filtering (self);
             self->strictness = new_strictness;
-            if (gtk_filter_list_model_find_filtered (self, &start, &end, &n_before))
+            n_after = g_list_model_get_n_items (G_LIST_MODEL (self));
+            start = gtk_bitset_get_minimum (self->matches);
+            end = gtk_bitset_get_maximum (self->matches);
+
+            n_before = gtk_bitset_get_size (self->matches);
+            if (n_before == n_after)
               {
-                n_after = g_list_model_get_n_items (G_LIST_MODEL (self));
-                g_clear_pointer (&self->items, gtk_rb_tree_unref);
-                g_list_model_items_changed (G_LIST_MODEL (self), start, n_before - end - start, n_after - end - start);
+                g_clear_pointer (&self->matches, gtk_bitset_unref);
               }
             else
               {
-                g_clear_pointer (&self->items, gtk_rb_tree_unref);
+                GtkBitset *inverse;
+
+                inverse = gtk_bitset_new_range (0, n_after);
+                gtk_bitset_subtract (inverse, self->matches);
+                /* otherwise all items would be visible */
+                g_assert (!gtk_bitset_is_empty (inverse));
+
+                /* find first filtered */
+                start = gtk_bitset_get_minimum (inverse);
+                end = n_after - gtk_bitset_get_maximum (inverse) - 1;
+
+                gtk_bitset_unref (inverse);
+
+                g_clear_pointer (&self->matches, gtk_bitset_unref);
+                g_list_model_items_changed (G_LIST_MODEL (self), start, n_before - end - start, n_after - end - start);
               }
           }
           break;
@@ -562,40 +475,44 @@ gtk_filter_list_model_update_strictness_and_refilter (GtkFilterListModel *self)
       break;
 
     case GTK_FILTER_MATCH_SOME:
-      switch (self->strictness)
-        {
-        case GTK_FILTER_MATCH_NONE:
+      {
+        GtkBitset *old, *pending;
+      
+        if (self->matches == NULL)
           {
-            guint n_after;
-            self->strictness = new_strictness;
-            self->items = gtk_rb_tree_new (FilterNode,
-                                           FilterAugment,
-                                           gtk_filter_list_model_augment,
-                                           NULL, NULL);
-            n_after = gtk_filter_list_model_add_items (self, NULL, 0, g_list_model_get_n_items (self->model));
-            if (n_after > 0)
-              g_list_model_items_changed (G_LIST_MODEL (self), 0, 0, n_after);
+            if (self->strictness == GTK_FILTER_MATCH_ALL)
+              old = gtk_bitset_new_range (0, g_list_model_get_n_items (self->model));
+            else
+              old = gtk_bitset_new_empty ();
           }
-          break;
-        case GTK_FILTER_MATCH_ALL:
+        else
           {
-            guint start, end, n_before, n_after;
-            self->strictness = new_strictness;
-            self->items = gtk_rb_tree_new (FilterNode,
-                                           FilterAugment,
-                                           gtk_filter_list_model_augment,
-                                           NULL, NULL);
-            n_before = g_list_model_get_n_items (self->model);
-            gtk_filter_list_model_add_items (self, NULL, 0, n_before);
-            if (gtk_filter_list_model_find_filtered (self, &start, &end, &n_after))
-              g_list_model_items_changed (G_LIST_MODEL (self), start, n_before - end - start, n_after - end - start);
+            old = self->matches;
           }
-          break;
-        default:
-        case GTK_FILTER_MATCH_SOME:
-          gtk_filter_list_model_refilter (self);
-          break;
-        }
+        self->strictness = new_strictness;
+        switch (change)
+          {
+          default:
+            g_assert_not_reached ();
+            G_GNUC_FALLTHROUGH;
+          case GTK_FILTER_CHANGE_DIFFERENT:
+            self->matches = gtk_bitset_new_empty ();
+            pending = gtk_bitset_new_range (0, g_list_model_get_n_items (self->model));
+            break;
+          case GTK_FILTER_CHANGE_LESS_STRICT:
+            self->matches = gtk_bitset_copy (old);
+            pending = gtk_bitset_new_range (0, g_list_model_get_n_items (self->model));
+            gtk_bitset_subtract (pending, self->matches);
+            break;
+          case GTK_FILTER_CHANGE_MORE_STRICT:
+            self->matches = gtk_bitset_new_empty ();
+            pending = gtk_bitset_copy (old);
+            break;
+          }
+        gtk_filter_list_model_start_filtering (self, pending);
+
+        gtk_filter_list_model_emit_items_changed_for_changes (self, old);
+      }
     }
 }
 
@@ -604,7 +521,7 @@ gtk_filter_list_model_filter_changed_cb (GtkFilter          *filter,
                                          GtkFilterChange     change,
                                          GtkFilterListModel *self)
 {
-  gtk_filter_list_model_update_strictness_and_refilter (self);
+  gtk_filter_list_model_refilter (self, change);
 }
 
 static void
@@ -624,7 +541,7 @@ gtk_filter_list_model_dispose (GObject *object)
 
   gtk_filter_list_model_clear_model (self);
   gtk_filter_list_model_clear_filter (self);
-  g_clear_pointer (&self->items, gtk_rb_tree_unref);
+  g_clear_pointer (&self->matches, gtk_bitset_unref);
 
   G_OBJECT_CLASS (gtk_filter_list_model_parent_class)->dispose (object);
 }
@@ -650,6 +567,18 @@ gtk_filter_list_model_class_init (GtkFilterListModelClass *class)
                            GTK_TYPE_FILTER,
                            GTK_PARAM_READWRITE | G_PARAM_EXPLICIT_NOTIFY);
 
+  /**
+   * GtkFilterListModel:incremental:
+   *
+   * If the model should filter items incrementally
+   */
+  properties[PROP_INCREMENTAL] =
+      g_param_spec_boolean ("incremental",
+                            P_("Incremental"),
+                            P_("Filer items incrementally"),
+                            FALSE,
+                            GTK_PARAM_READWRITE | G_PARAM_EXPLICIT_NOTIFY);
+
   /**
    * GtkFilterListModel:model:
    *
@@ -662,6 +591,18 @@ gtk_filter_list_model_class_init (GtkFilterListModelClass *class)
                            G_TYPE_LIST_MODEL,
                            GTK_PARAM_READWRITE | G_PARAM_EXPLICIT_NOTIFY);
 
+  /**
+   * GtkFilterListModel:pending:
+   *
+   * Number of items not yet filtered
+   */
+  properties[PROP_PENDING] =
+      g_param_spec_uint ("pending",
+                         P_("Pending"),
+                         P_("Number of items not yet filtered"),
+                         0, G_MAXUINT, 0,
+                         GTK_PARAM_READABLE | G_PARAM_EXPLICIT_NOTIFY);
+
   g_object_class_install_properties (gobject_class, NUM_PROPERTIES, properties);
 }
 
@@ -725,7 +666,7 @@ gtk_filter_list_model_set_filter (GtkFilterListModel *self,
     }
   else
     {
-      gtk_filter_list_model_update_strictness_and_refilter (self);
+      gtk_filter_list_model_refilter (self, GTK_FILTER_CHANGE_LESS_STRICT);
     }
 
   g_object_notify_by_pspec (G_OBJECT (self), properties[PROP_FILTER]);
@@ -784,13 +725,18 @@ gtk_filter_list_model_set_model (GtkFilterListModel *self,
       if (removed == 0)
         {
           self->strictness = GTK_FILTER_MATCH_NONE;
-          gtk_filter_list_model_update_strictness_and_refilter (self);
+          gtk_filter_list_model_refilter (self, GTK_FILTER_CHANGE_LESS_STRICT);
           added = 0;
         }
-      else if (self->items)
-        added = gtk_filter_list_model_add_items (self, NULL, 0, g_list_model_get_n_items (model));
+      else if (self->matches)
+        {
+          gtk_filter_list_model_start_filtering (self, gtk_bitset_new_range (0, g_list_model_get_n_items (model)));
+          added = gtk_bitset_get_size (self->matches);
+        }
       else
-        added = g_list_model_get_n_items (model);
+        {
+          added = g_list_model_get_n_items (model);
+        }
     }
   else
     {
@@ -820,54 +766,89 @@ gtk_filter_list_model_get_model (GtkFilterListModel *self)
   return self->model;
 }
 
-static void
-gtk_filter_list_model_refilter (GtkFilterListModel *self)
+/**
+ * gtk_filter_list_model_set_incremental:
+ * @self: a #GtkFilterListModel
+ * @incremental: %TRUE to enable incremental filtering
+ *
+ * When incremental filtering is enabled, the filterlistmodel will not run
+ * filters immediately, but will instead queue an idle handler that
+ * incrementally filters the items and adds them to the list. This of course
+ * means that items are not instantly added to the list, but only appear
+ * incrementally.
+ *
+ * When your filter blocks the UI while filtering, you might consider
+ * turning this on. Depending on your model and filters, this may become
+ * interesting around 10,000 to 100,000 items.
+ *
+ * By default, incremental filtering is disabled.
+ **/
+void
+gtk_filter_list_model_set_incremental (GtkFilterListModel *self,
+                                       gboolean            incremental)
 {
-  FilterNode *node;
-  guint i, first_change, last_change;
-  guint n_is_visible, n_was_visible;
-  gboolean visible;
-
   g_return_if_fail (GTK_IS_FILTER_LIST_MODEL (self));
-  
-  if (self->items == NULL || self->model == NULL)
+
+  if (self->incremental == incremental)
     return;
 
-  first_change = G_MAXUINT;
-  last_change = 0;
-  n_is_visible = 0;
-  n_was_visible = 0;
-  for (i = 0, node = gtk_rb_tree_get_first (self->items);
-       node != NULL;
-       i++, node = gtk_rb_tree_node_get_next (node))
-    {
-      visible = gtk_filter_list_model_run_filter (self, i);
-      if (visible == node->visible)
-        {
-          if (visible)
-            {
-              n_is_visible++;
-              n_was_visible++;
-            }
-          continue;
-        }
+  self->incremental = incremental;
 
-      node->visible = visible;
-      gtk_rb_tree_node_mark_dirty (node);
-      first_change = MIN (n_is_visible, first_change);
-      if (visible)
-        n_is_visible++;
-      else
-        n_was_visible++;
-      last_change = MAX (n_is_visible, last_change);
+  if (!incremental)
+    {
+      GtkBitset *old;
+      gtk_filter_list_model_run_filter (self, G_MAXUINT);
+
+      old = gtk_bitset_copy (self->matches);
+      gtk_filter_list_model_run_filter (self, 512);
+
+      gtk_filter_list_model_stop_filtering (self);
+
+      gtk_filter_list_model_emit_items_changed_for_changes (self, old);
     }
 
-  if (first_change <= last_change)
-    {
-      g_list_model_items_changed (G_LIST_MODEL (self),
-                                  first_change,
-                                  last_change - first_change + n_was_visible - n_is_visible,
-                                  last_change - first_change);
-    }
+  g_object_notify_by_pspec (G_OBJECT (self), properties[PROP_INCREMENTAL]);
 }
 
+/**
+ * gtk_filter_list_model_get_incremental:
+ * @self: a #GtkFilterListModel
+ *
+ * Returns whether incremental filtering was enabled via
+ * gtk_filter_list_model_set_incremental().
+ *
+ * Returns: %TRUE if incremental filtering is enabled
+ **/
+gboolean
+gtk_filter_list_model_get_incremental (GtkFilterListModel *self)
+{
+  g_return_val_if_fail (GTK_IS_FILTER_LIST_MODEL (self), FALSE);
+
+  return self->incremental;
+}
+
+/**
+ * gtk_filter_list_model_get_pending:
+ * @self: a #GtkFilterListModel
+ *
+ * Returns the number of items that have not been filtered yet.
+ *
+ * When incremental filtering is not enabled, this always returns 0.
+ *
+ * You can use this value to check if @self is busy filtering by
+ * comparing the return value to 0 or you can compute the percentage
+ * of the filter remaining by dividing the return value by
+ * g_list_model_get_n_items(gtk_filter_list_model_get_model (self)).
+ *
+ * Returns: The number of items not yet filtered
+ **/
+guint
+gtk_filter_list_model_get_pending (GtkFilterListModel *self)
+{
+  g_return_val_if_fail (GTK_IS_FILTER_LIST_MODEL (self), FALSE);
+
+  if (self->pending == NULL)
+    return 0;
+
+  return gtk_bitset_get_size (self->pending);
+}

gtk/gtkfilterlistmodel.h

@@ -50,6 +50,14 @@ void                    gtk_filter_list_model_set_model         (GtkFilterListMo
                                                                  GListModel             *model);
 GDK_AVAILABLE_IN_ALL
 GListModel *            gtk_filter_list_model_get_model         (GtkFilterListModel     *self);
+GDK_AVAILABLE_IN_ALL
+void                    gtk_filter_list_model_set_incremental   (GtkFilterListModel     *self,
+                                                                 gboolean                incremental);
+GDK_AVAILABLE_IN_ALL
+gboolean                gtk_filter_list_model_get_incremental   (GtkFilterListModel     *self);
+GDK_AVAILABLE_IN_ALL
+guint                   gtk_filter_list_model_get_pending       (GtkFilterListModel     *self);
+
 
 G_END_DECLS
 

gtk/gtkicontheme.c

@@ -55,6 +55,14 @@
 #include "gdk/gdktextureprivate.h"
 #include "gdk/gdkprofilerprivate.h"
 
+#define GTK_VECTOR_ELEMENT_TYPE char *
+#define GTK_VECTOR_NULL_TERMINATED 1
+#define GTK_VECTOR_FREE_FUNC g_free
+#define GTK_VECTOR_TYPE_NAME GtkStrvBuilder
+#define GTK_VECTOR_NAME gtk_strv_builder
+#define GTK_VECTOR_PREALLOC 16
+#include "gtkvectorimpl.c"
+
 /**
  * SECTION:gtkicontheme
  * @Short_description: Looking up icons by name
@@ -2276,13 +2284,13 @@ real_choose_icon (GtkIconTheme      *self,
 }
 
 static void
-icon_name_list_add_icon (GPtrArray   *icons,
-                         const gchar *dir_suffix,
-                         gchar       *icon_name)
+icon_name_list_add_icon (GtkStrvBuilder *icons,
+                         const gchar    *dir_suffix,
+                         gchar          *icon_name)
 {
   if (dir_suffix)
-    g_ptr_array_add (icons, g_strconcat (icon_name, dir_suffix, NULL));
-  g_ptr_array_add (icons, icon_name);
+    gtk_strv_builder_append (icons, g_strconcat (icon_name, dir_suffix, NULL));
+  gtk_strv_builder_append (icons, icon_name);
 }
 
 static GtkIconPaintable *
@@ -2296,7 +2304,7 @@ choose_icon (GtkIconTheme      *self,
 {
   gboolean has_regular = FALSE, has_symbolic = FALSE;
   GtkIconPaintable *icon;
-  GPtrArray *new_names;
+  GtkStrvBuilder new_names;
   const gchar *dir_suffix;
   guint i;
 
@@ -2327,73 +2335,70 @@ choose_icon (GtkIconTheme      *self,
 
   if ((flags & GTK_ICON_LOOKUP_FORCE_REGULAR) && has_symbolic)
     {
-      new_names = g_ptr_array_new_with_free_func (g_free);
+      gtk_strv_builder_init (&new_names);
       for (i = 0; icon_names[i]; i++)
         {
           if (icon_name_is_symbolic (icon_names[i], -1))
-            icon_name_list_add_icon (new_names, dir_suffix, g_strndup (icon_names[i], strlen (icon_names[i]) - strlen ("-symbolic")));
+            icon_name_list_add_icon (&new_names, dir_suffix, g_strndup (icon_names[i], strlen (icon_names[i]) - strlen ("-symbolic")));
           else
-            icon_name_list_add_icon (new_names, dir_suffix, g_strdup (icon_names[i]));
+            icon_name_list_add_icon (&new_names, dir_suffix, g_strdup (icon_names[i]));
         }
       for (i = 0; icon_names[i]; i++)
         {
           if (icon_name_is_symbolic (icon_names[i], -1))
-            icon_name_list_add_icon (new_names, dir_suffix, g_strdup (icon_names[i]));
+            icon_name_list_add_icon (&new_names, dir_suffix, g_strdup (icon_names[i]));
         }
-      g_ptr_array_add (new_names, NULL);
 
       icon = real_choose_icon (self,
-                               (const gchar **) new_names->pdata,
+                               (const char **) gtk_strv_builder_get_data (&new_names),
                                size,
                                scale,
                                flags & ~(GTK_ICON_LOOKUP_FORCE_REGULAR | GTK_ICON_LOOKUP_FORCE_SYMBOLIC),
                                non_blocking);
 
-      g_ptr_array_free (new_names, TRUE);
+      gtk_strv_builder_clear (&new_names);
     }
   else if ((flags & GTK_ICON_LOOKUP_FORCE_SYMBOLIC) && has_regular)
     {
-      new_names = g_ptr_array_new_with_free_func (g_free);
+      gtk_strv_builder_init (&new_names);
       for (i = 0; icon_names[i]; i++)
         {
           if (!icon_name_is_symbolic (icon_names[i], -1))
-            icon_name_list_add_icon (new_names, dir_suffix, g_strconcat (icon_names[i], "-symbolic", NULL));
+            icon_name_list_add_icon (&new_names, dir_suffix, g_strconcat (icon_names[i], "-symbolic", NULL));
           else
-            icon_name_list_add_icon (new_names, dir_suffix, g_strdup (icon_names[i]));
+            icon_name_list_add_icon (&new_names, dir_suffix, g_strdup (icon_names[i]));
         }
       for (i = 0; icon_names[i]; i++)
         {
           if (!icon_name_is_symbolic (icon_names[i], -1))
-            icon_name_list_add_icon (new_names, dir_suffix, g_strdup (icon_names[i]));
+            icon_name_list_add_icon (&new_names, dir_suffix, g_strdup (icon_names[i]));
         }
-      g_ptr_array_add (new_names, NULL);
 
       icon = real_choose_icon (self,
-                               (const gchar **) new_names->pdata,
+                               (const char **) gtk_strv_builder_get_data (&new_names),
                                size,
                                scale,
                                flags & ~(GTK_ICON_LOOKUP_FORCE_REGULAR | GTK_ICON_LOOKUP_FORCE_SYMBOLIC),
                                non_blocking);
 
-      g_ptr_array_free (new_names, TRUE);
+      gtk_strv_builder_clear (&new_names);
     }
   else if (dir_suffix)
     {
-      new_names = g_ptr_array_new_with_free_func (g_free);
+      gtk_strv_builder_init (&new_names);
       for (i = 0; icon_names[i]; i++)
         {
-          icon_name_list_add_icon (new_names, dir_suffix, g_strdup (icon_names[i]));
+          icon_name_list_add_icon (&new_names, dir_suffix, g_strdup (icon_names[i]));
         }
-      g_ptr_array_add (new_names, NULL);
 
       icon = real_choose_icon (self,
-                               (const gchar **) new_names->pdata,
+                               (const char **) gtk_strv_builder_get_data (&new_names),
                                size,
                                scale,
                                flags & ~(GTK_ICON_LOOKUP_FORCE_REGULAR | GTK_ICON_LOOKUP_FORCE_SYMBOLIC),
                                non_blocking);
 
-      g_ptr_array_free (new_names, TRUE);
+      gtk_strv_builder_clear (&new_names);
     }
   else
     {

gtk/gtkmain.c

@@ -95,7 +95,6 @@
 #include "gdk/gdk-private.h"
 #include "gsk/gskprivate.h"
 #include "gsk/gskrendernodeprivate.h"
-#include "gtkarrayimplprivate.h"
 #include "gtknative.h"
 
 #include <locale.h>
@@ -138,6 +137,13 @@
 #include "a11y/gtkaccessibility.h"
 #include "inspector/window.h"
 
+#define GTK_VECTOR_ELEMENT_TYPE GtkWidget *
+#define GTK_VECTOR_TYPE_NAME GtkWidgetStack
+#define GTK_VECTOR_NAME gtk_widget_stack
+#define GTK_VECTOR_FREE_FUNC g_object_unref
+#define GTK_VECTOR_PREALLOC 16
+#include "gtkvectorimpl.c"
+
 static GtkWindowGroup *gtk_main_get_window_group (GtkWidget   *widget);
 
 static gint pre_initialized = FALSE;
@@ -1321,8 +1327,7 @@ gtk_synthesize_crossing_events (GtkRoot         *toplevel,
   double x, y;
   GtkWidget *prev;
   gboolean seen_ancestor;
-  GtkArray target_array;
-  GtkWidget *stack_targets[16];
+  GtkWidgetStack target_array;
   int i;
 
   if (old_target == new_target)
@@ -1376,19 +1381,19 @@ gtk_synthesize_crossing_events (GtkRoot         *toplevel,
       widget = _gtk_widget_get_parent (widget);
     }
 
-  gtk_array_init (&target_array, (void**)stack_targets, 16);
+  gtk_widget_stack_init (&target_array);
   for (widget = new_target; widget; widget = _gtk_widget_get_parent (widget))
-    gtk_array_add (&target_array, widget);
+    gtk_widget_stack_append (&target_array, g_object_ref (widget));
 
   crossing.direction = GTK_CROSSING_IN;
 
   seen_ancestor = FALSE;
-  for (i = (int)target_array.len - 1; i >= 0; i--)
+  for (i = gtk_widget_stack_get_size (&target_array) - 1; i >= 0; i--)
     {
-      widget = gtk_array_index (&target_array, i);
+      widget = gtk_widget_stack_get (&target_array, i);
 
-      if (i < (int)target_array.len - 1)
-        crossing.new_descendent = gtk_array_index (&target_array, i + 1);
+      if (i < gtk_widget_stack_get_size (&target_array) - 1)
+        crossing.new_descendent = gtk_widget_stack_get (&target_array, i + 1);
       else
         crossing.new_descendent = NULL;
 
@@ -1417,7 +1422,7 @@ gtk_synthesize_crossing_events (GtkRoot         *toplevel,
         gtk_widget_set_state_flags (widget, GTK_STATE_FLAG_PRELIGHT, FALSE);
     }
 
-  gtk_array_free (&target_array, NULL);
+  gtk_widget_stack_clear (&target_array);
 }
 
 static GtkWidget *
@@ -1994,13 +1999,12 @@ gtk_propagate_event_internal (GtkWidget *widget,
 {
   gint handled_event = FALSE;
   GtkWidget *target = widget;
-  GtkArray widget_array;
-  GtkWidget *stack_widgets[16];
+  GtkWidgetStack widget_array;
   int i;
 
   /* First, propagate event down */
-  gtk_array_init (&widget_array, (void**)stack_widgets, 16);
-  gtk_array_add (&widget_array, g_object_ref (widget));
+  gtk_widget_stack_init (&widget_array);
+  gtk_widget_stack_append (&widget_array, g_object_ref (widget));
 
   for (;;)
     {
@@ -2008,16 +2012,16 @@ gtk_propagate_event_internal (GtkWidget *widget,
       if (!widget)
         break;
 
-      gtk_array_add (&widget_array, g_object_ref (widget));
+      gtk_widget_stack_append (&widget_array, g_object_ref (widget));
 
       if (widget == topmost)
         break;
     }
 
-  i = widget_array.len - 1;
+  i = gtk_widget_stack_get_size (&widget_array) - 1;
   for (;;)
     {
-      widget = gtk_array_index (&widget_array, i);
+      widget = gtk_widget_stack_get (&widget_array, i);
 
       if (!_gtk_widget_is_sensitive (widget))
         {
@@ -2050,9 +2054,9 @@ gtk_propagate_event_internal (GtkWidget *widget,
        * parents can see the button and motion
        * events of the children.
        */
-      for (i = 0; i < widget_array.len; i++)
+      for (i = 0; i < gtk_widget_stack_get_size (&widget_array); i++)
         {
-          widget = gtk_array_index (&widget_array, i);
+          widget = gtk_widget_stack_get (&widget_array, i);
 
           /* Scroll events are special cased here because it
            * feels wrong when scrolling a GtkViewport, say,
@@ -2071,7 +2075,7 @@ gtk_propagate_event_internal (GtkWidget *widget,
         }
     }
 
-  gtk_array_free (&widget_array, g_object_unref);
+  gtk_widget_stack_clear (&widget_array);
   return handled_event;
 }
 

gtk/gtksnapshot.c

@@ -34,6 +34,11 @@
 
 #include "gtk/gskpango.h"
 
+#define GTK_VECTOR_NAME gtk_snapshot_nodes
+#define GTK_VECTOR_TYPE_NAME GtkSnapshotNodes
+#define GTK_VECTOR_ELEMENT_TYPE GskRenderNode *
+#define GTK_VECTOR_FREE_FUNC gsk_render_node_unref
+#include "gtkvectorimpl.c"
 
 /**
  * SECTION:gtksnapshot
@@ -54,6 +59,85 @@
  * use gtk_snapshot_new().
  */
 
+typedef struct _GtkSnapshotState GtkSnapshotState;
+
+typedef GskRenderNode * (* GtkSnapshotCollectFunc) (GtkSnapshot      *snapshot,
+                                                    GtkSnapshotState *state,
+                                                    GskRenderNode   **nodes,
+                                                    guint             n_nodes);
+
+struct _GtkSnapshotState {
+  guint                  start_node_index;
+  guint                  n_nodes;
+
+  GskTransform *         transform;
+
+  GtkSnapshotCollectFunc collect_func;
+  union {
+    struct {
+      double             opacity;
+    } opacity;
+    struct {
+      double             radius;
+    } blur;
+    struct {
+      graphene_matrix_t matrix;
+      graphene_vec4_t offset;
+    } color_matrix;
+    struct {
+      graphene_rect_t bounds;
+      graphene_rect_t child_bounds;
+    } repeat;
+    struct {
+      graphene_rect_t bounds;
+    } clip;
+    struct {
+      GskRoundedRect bounds;
+    } rounded_clip;
+    struct {
+      gsize n_shadows;
+      GskShadow *shadows;
+      GskShadow a_shadow; /* Used if n_shadows == 1 */
+    } shadow;
+    struct {
+      GskBlendMode blend_mode;
+      GskRenderNode *bottom_node;
+    } blend;
+    struct {
+      double progress;
+      GskRenderNode *start_node;
+    } cross_fade;
+    struct {
+      char *message;
+    } debug;
+  } data;
+};
+
+static void gtk_snapshot_state_clear (GtkSnapshotState *state);
+
+#define GTK_VECTOR_NAME gtk_snapshot_states
+#define GTK_VECTOR_TYPE_NAME GtkSnapshotStates
+#define GTK_VECTOR_ELEMENT_TYPE GtkSnapshotState
+#define GTK_VECTOR_FREE_FUNC gtk_snapshot_state_clear
+#define GTK_VECTOR_BY_VALUE 1
+#include "gtkvectorimpl.c"
+
+/* This is a nasty little hack. We typedef GtkSnapshot to the fake object GdkSnapshot
+ * so that we don't need to typecast between them.
+ * After all, the GdkSnapshot only exist so poor language bindings don't trip. Hardcore
+ * C code can just blatantly ignore such layering violations with a typedef.
+ */
+struct _GdkSnapshot {
+  GObject                parent_instance; /* it's really GdkSnapshot, but don't tell anyone! */
+
+  GtkSnapshotStates      state_stack;
+  GtkSnapshotNodes       nodes;
+};
+
+struct _GtkSnapshotClass {
+  GObjectClass           parent_class; /* it's really GdkSnapshotClass, but don't tell anyone! */
+};
+
 G_DEFINE_TYPE (GtkSnapshot, gtk_snapshot, GDK_TYPE_SNAPSHOT)
 
 static void
@@ -61,11 +145,11 @@ gtk_snapshot_dispose (GObject *object)
 {
   GtkSnapshot *snapshot = GTK_SNAPSHOT (object);
 
-  if (snapshot->state_stack)
+  if (!gtk_snapshot_states_is_empty (&snapshot->state_stack))
     gsk_render_node_unref (gtk_snapshot_to_node (snapshot));
 
-  g_assert (snapshot->state_stack == NULL);
-  g_assert (snapshot->nodes == NULL);
+  g_assert (gtk_snapshot_states_is_empty (&snapshot->state_stack));
+  g_assert (gtk_snapshot_nodes_is_empty (&snapshot->nodes));
 
   G_OBJECT_CLASS (gtk_snapshot_parent_class)->dispose (object);
 }
@@ -112,15 +196,15 @@ gtk_snapshot_push_state (GtkSnapshot            *snapshot,
                          GskTransform           *transform,
                          GtkSnapshotCollectFunc  collect_func)
 {
-  const gsize n_states = snapshot->state_stack->len;
+  const gsize n_states = gtk_snapshot_states_get_size (&snapshot->state_stack);
   GtkSnapshotState *state;
 
-  g_array_set_size (snapshot->state_stack, n_states + 1);
-  state = &g_array_index (snapshot->state_stack, GtkSnapshotState, n_states);
+  gtk_snapshot_states_set_size (&snapshot->state_stack, n_states + 1);
+  state = gtk_snapshot_states_get (&snapshot->state_stack, n_states);
 
   state->transform = gsk_transform_ref (transform);
   state->collect_func = collect_func;
-  state->start_node_index = snapshot->nodes->len;
+  state->start_node_index = gtk_snapshot_nodes_get_size (&snapshot->nodes);
   state->n_nodes = 0;
 
   return state;
@@ -129,17 +213,21 @@ gtk_snapshot_push_state (GtkSnapshot            *snapshot,
 static GtkSnapshotState *
 gtk_snapshot_get_current_state (const GtkSnapshot *snapshot)
 {
-  g_assert (snapshot->state_stack->len > 0);
+  gsize size = gtk_snapshot_states_get_size (&snapshot->state_stack);
 
-  return &g_array_index (snapshot->state_stack, GtkSnapshotState, snapshot->state_stack->len - 1);
+  g_assert (size > 0);
+
+  return gtk_snapshot_states_get (&snapshot->state_stack, size - 1);
 }
 
 static GtkSnapshotState *
 gtk_snapshot_get_previous_state (const GtkSnapshot *snapshot)
 {
-  g_assert (snapshot->state_stack->len > 1);
+  gsize size = gtk_snapshot_states_get_size (&snapshot->state_stack);
 
-  return &g_array_index (snapshot->state_stack, GtkSnapshotState, snapshot->state_stack->len - 2);
+  g_assert (size > 1);
+
+  return gtk_snapshot_states_get (&snapshot->state_stack, size - 2);
 }
 
 static void
@@ -162,9 +250,8 @@ gtk_snapshot_new (void)
 
   snapshot = g_object_new (GTK_TYPE_SNAPSHOT, NULL);
 
-  snapshot->state_stack = g_array_new (FALSE, TRUE, sizeof (GtkSnapshotState));
-  g_array_set_clear_func (snapshot->state_stack, (GDestroyNotify)gtk_snapshot_state_clear);
-  snapshot->nodes = g_ptr_array_new_with_free_func ((GDestroyNotify)gsk_render_node_unref);
+  gtk_snapshot_states_init (&snapshot->state_stack);
+  gtk_snapshot_nodes_init (&snapshot->nodes);
 
   gtk_snapshot_push_state (snapshot,
                            NULL,
@@ -1029,30 +1116,28 @@ gtk_snapshot_pop_one (GtkSnapshot *snapshot)
   guint state_index;
   GskRenderNode *node;
 
-  if (snapshot->state_stack->len == 0)
+  if (gtk_snapshot_states_is_empty (&snapshot->state_stack))
     {
       g_warning ("Too many gtk_snapshot_pop() calls.");
       return NULL;
     }
 
   state = gtk_snapshot_get_current_state (snapshot);
-  state_index = snapshot->state_stack->len - 1;
+  state_index = gtk_snapshot_states_get_size (&snapshot->state_stack) - 1;
 
   if (state->collect_func)
     {
       node = state->collect_func (snapshot,
                                   state,
-                                  (GskRenderNode **) snapshot->nodes->pdata + state->start_node_index,
+                                  (GskRenderNode **) gtk_snapshot_nodes_index (&snapshot->nodes, state->start_node_index),
                                   state->n_nodes);
 
       /* The collect func may not modify the state stack... */
-      g_assert (state_index == snapshot->state_stack->len - 1);
+      g_assert (state_index == gtk_snapshot_states_get_size (&snapshot->state_stack) - 1);
 
       /* Remove all the state's nodes from the list of nodes */
-      g_assert (state->start_node_index + state->n_nodes == snapshot->nodes->len);
-      g_ptr_array_remove_range (snapshot->nodes,
-                                snapshot->nodes->len - state->n_nodes,
-                                state->n_nodes);
+      g_assert (state->start_node_index + state->n_nodes == gtk_snapshot_nodes_get_size (&snapshot->nodes));
+      gtk_snapshot_nodes_splice (&snapshot->nodes, state->start_node_index, state->n_nodes, NULL, 0);
     }
   else
     {
@@ -1063,10 +1148,10 @@ gtk_snapshot_pop_one (GtkSnapshot *snapshot)
       /* move the nodes to the parent */
       previous_state = gtk_snapshot_get_previous_state (snapshot);
       previous_state->n_nodes += state->n_nodes;
-      g_assert (previous_state->start_node_index + previous_state->n_nodes == snapshot->nodes->len);
+      g_assert (previous_state->start_node_index + previous_state->n_nodes == gtk_snapshot_nodes_get_size (&snapshot->nodes));
     }
 
-  g_array_remove_index (snapshot->state_stack, state_index);
+  gtk_snapshot_states_splice (&snapshot->state_stack, state_index, 1, NULL, 0);
 
   return node;
 }
@@ -1081,7 +1166,7 @@ gtk_snapshot_append_node_internal (GtkSnapshot   *snapshot,
 
   if (current_state)
     {
-      g_ptr_array_add (snapshot->nodes, node);
+      gtk_snapshot_nodes_append (&snapshot->nodes, node);
       current_state->n_nodes ++;
     }
   else
@@ -1162,16 +1247,14 @@ gtk_snapshot_to_node (GtkSnapshot *snapshot)
   result = gtk_snapshot_pop_internal (snapshot);
 
   /* We should have exactly our initial state */
-  if (snapshot->state_stack->len > 0)
+  if (!gtk_snapshot_states_is_empty (&snapshot->state_stack))
     {
-      g_warning ("Too many gtk_snapshot_push() calls. %u states remaining.", snapshot->state_stack->len);
+      g_warning ("Too many gtk_snapshot_push() calls. %zu states remaining.",
+                 gtk_snapshot_states_get_size (&snapshot->state_stack));
     }
 
-  g_array_free (snapshot->state_stack, TRUE);
-  g_ptr_array_free (snapshot->nodes, TRUE);
-
-  snapshot->state_stack = NULL;
-  snapshot->nodes = NULL;
+  gtk_snapshot_states_clear (&snapshot->state_stack);
+  gtk_snapshot_nodes_clear (&snapshot->nodes);
 
   return result;
 }

gtk/gtksnapshotprivate.h

@@ -24,76 +24,6 @@
 
 G_BEGIN_DECLS
 
-typedef struct _GtkSnapshotState GtkSnapshotState;
-
-typedef GskRenderNode * (* GtkSnapshotCollectFunc) (GtkSnapshot      *snapshot,
-                                                    GtkSnapshotState *state,
-                                                    GskRenderNode   **nodes,
-                                                    guint             n_nodes);
-
-struct _GtkSnapshotState {
-  guint                  start_node_index;
-  guint                  n_nodes;
-
-  GskTransform *         transform;
-
-  GtkSnapshotCollectFunc collect_func;
-  union {
-    struct {
-      double             opacity;
-    } opacity;
-    struct {
-      double             radius;
-    } blur;
-    struct {
-      graphene_matrix_t matrix;
-      graphene_vec4_t offset;
-    } color_matrix;
-    struct {
-      graphene_rect_t bounds;
-      graphene_rect_t child_bounds;
-    } repeat;
-    struct {
-      graphene_rect_t bounds;
-    } clip;
-    struct {
-      GskRoundedRect bounds;
-    } rounded_clip;
-    struct {
-      gsize n_shadows;
-      GskShadow *shadows;
-      GskShadow a_shadow; /* Used if n_shadows == 1 */
-    } shadow;
-    struct {
-      GskBlendMode blend_mode;
-      GskRenderNode *bottom_node;
-    } blend;
-    struct {
-      double progress;
-      GskRenderNode *start_node;
-    } cross_fade;
-    struct {
-      char *message;
-    } debug;
-  } data;
-};
-
-/* This is a nasty little hack. We typedef GtkSnapshot to the fake object GdkSnapshot
- * so that we don't need to typecast between them.
- * After all, the GdkSnapshot only exist so poor language bindings don't trip. Hardcore
- * C code can just blatantly ignore such layering violations with a typedef.
- */
-struct _GdkSnapshot {
-  GObject                parent_instance; /* it's really GdkSnapshot, but don't tell anyone! */
-
-  GArray                *state_stack;
-  GPtrArray             *nodes;
-};
-
-struct _GtkSnapshotClass {
-  GObjectClass           parent_class; /* it's really GdkSnapshotClass, but don't tell anyone! */
-};
-
 void                    gtk_snapshot_append_text                (GtkSnapshot            *snapshot,
                                                                  PangoFont              *font,
                                                                  PangoGlyphString       *glyphs,

gtk/gtkstringlist.c

@@ -57,6 +57,12 @@
 
  */
 
+#define GTK_VECTOR_ELEMENT_TYPE GtkStringObject *
+#define GTK_VECTOR_NAME objects
+#define GTK_VECTOR_TYPE_NAME Objects
+#define GTK_VECTOR_FREE_FUNC g_object_unref
+#include "gtkvectorimpl.c"
+
 struct _GtkStringObject
 {
   GObject parent_instance;
@@ -190,7 +196,7 @@ struct _GtkStringList
 {
   GObject parent_instance;
 
-  GSequence *items;
+  Objects items;
 };
 
 struct _GtkStringListClass
@@ -209,7 +215,7 @@ gtk_string_list_get_n_items (GListModel *list)
 {
   GtkStringList *self = GTK_STRING_LIST (list);
 
-  return g_sequence_get_length (self->items);
+  return objects_get_size (&self->items);
 }
 
 static gpointer
@@ -217,14 +223,11 @@ gtk_string_list_get_item (GListModel *list,
                           guint       position)
 {
   GtkStringList *self = GTK_STRING_LIST (list);
-  GSequenceIter *iter;
 
-  iter = g_sequence_get_iter_at_pos (self->items, position);
-
-  if (g_sequence_iter_is_end (iter))
+  if (position >= objects_get_size (&self->items))
     return NULL;
-  else
-    return g_object_ref (g_sequence_get (iter));
+
+  return g_object_ref (objects_get (&self->items, position));
 }
 
 static void
@@ -331,7 +334,7 @@ item_end_element (GtkBuildableParseContext  *context,
           g_string_assign (data->string, translated);
         }
 
-      g_sequence_append (data->list->items, gtk_string_object_new (data->string->str));
+      gtk_string_list_append (data->list, data->string->str);
     }
 
   data->translatable = FALSE;
@@ -411,7 +414,7 @@ gtk_string_list_dispose (GObject *object)
 {
   GtkStringList *self = GTK_STRING_LIST (object);
 
-  g_clear_pointer (&self->items, g_sequence_free);
+  objects_clear (&self->items);
 
   G_OBJECT_CLASS (gtk_string_list_parent_class)->dispose (object);
 }
@@ -427,7 +430,7 @@ gtk_string_list_class_init (GtkStringListClass *class)
 static void
 gtk_string_list_init (GtkStringList *self)
 {
-  self->items = g_sequence_new (g_object_unref);
+  objects_init (&self->items);
 }
 
 /**
@@ -476,32 +479,19 @@ gtk_string_list_splice (GtkStringList      *self,
                         guint               n_removals,
                         const char * const *additions)
 {
-  GSequenceIter *it;
-  guint add, n_items;
+  guint add;
 
   g_return_if_fail (GTK_IS_STRING_LIST (self));
   g_return_if_fail (position + n_removals >= position); /* overflow */
+  g_return_if_fail (position + n_removals <= objects_get_size (&self->items));
 
-  n_items = g_sequence_get_length (self->items);
-  g_return_if_fail (position + n_removals <= n_items);
-
-  it = g_sequence_get_iter_at_pos (self->items, position);
-
-  if (n_removals)
-    {
-      GSequenceIter *end;
-
-      end = g_sequence_iter_move (it, n_removals);
-      g_sequence_remove_range (it, end);
-
-      it = end;
-    }
+  objects_splice (&self->items, position, n_removals, NULL, 0);
 
   if (additions)
     {
       for (add = 0; additions[add]; add++)
         {
-          g_sequence_insert_before (it, gtk_string_object_new (additions[add]));
+          objects_append (&self->items, gtk_string_object_new (additions[add]));
         }
     }
   else
@@ -525,14 +515,11 @@ void
 gtk_string_list_append (GtkStringList *self,
                         const char    *string)
 {
-  guint n_items;
-
   g_return_if_fail (GTK_IS_STRING_LIST (self));
 
-  n_items = g_sequence_get_length (self->items);
-  g_sequence_append (self->items, gtk_string_object_new (string));
+  objects_append (&self->items, gtk_string_object_new (string));
 
-  g_list_model_items_changed (G_LIST_MODEL (self), n_items, 0, 1);
+  g_list_model_items_changed (G_LIST_MODEL (self), objects_get_size (&self->items) - 1, 0, 1);
 }
 
 /**
@@ -554,14 +541,11 @@ void
 gtk_string_list_take (GtkStringList *self,
                       char          *string)
 {
-  guint n_items;
-
   g_return_if_fail (GTK_IS_STRING_LIST (self));
 
-  n_items = g_sequence_get_length (self->items);
-  g_sequence_append (self->items, gtk_string_object_new_take (string));
+  objects_append (&self->items, gtk_string_object_new_take (string));
 
-  g_list_model_items_changed (G_LIST_MODEL (self), n_items, 0, 1);
+  g_list_model_items_changed (G_LIST_MODEL (self), objects_get_size (&self->items) - 1, 0, 1);
 }
 
 /**
@@ -576,16 +560,9 @@ void
 gtk_string_list_remove (GtkStringList *self,
                         guint          position)
 {
-  GSequenceIter *iter;
-
   g_return_if_fail (GTK_IS_STRING_LIST (self));
 
-  iter = g_sequence_get_iter_at_pos (self->items, position);
-  g_return_if_fail (!g_sequence_iter_is_end (iter));
-
-  g_sequence_remove (iter);
-
-  g_list_model_items_changed (G_LIST_MODEL (self), position, 1, 0);
+  gtk_string_list_splice (self, position, 1, NULL);
 }
 
 /**
@@ -605,20 +582,10 @@ const char *
 gtk_string_list_get_string (GtkStringList *self,
                             guint          position)
 {
-  GSequenceIter *iter;
-
   g_return_val_if_fail (GTK_IS_STRING_LIST (self), NULL);
 
-  iter = g_sequence_get_iter_at_pos (self->items, position);
+  if (position >= objects_get_size (&self->items))
+    return NULL;
 
-  if (g_sequence_iter_is_end (iter))
-    {
-      return NULL;
-    }
-  else
-    {
-      GtkStringObject *obj = g_sequence_get (iter);
-
-      return obj->string;
-    }
+  return objects_get (&self->items, position)->string;
 }

gtk/gtkvectorimpl.c

@@ -0,0 +1,283 @@
+/*
+ * 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
+
+#ifdef GTK_VECTOR_NULL_TERMINATED
+#define GTK_VECTOR_REAL_SIZE(_size) ((_size) + 1)
+#else
+#define GTK_VECTOR_REAL_SIZE(_size) (_size)
+#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_REAL_SIZE(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;
+#ifdef GTK_VECTOR_NULL_TERMINATED
+  *self->start = *(_T_[1]) {};
+#endif
+#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++)
+#ifdef GTK_VECTOR_BY_VALUE
+    GTK_VECTOR_FREE_FUNC (e);
+#else
+    GTK_VECTOR_FREE_FUNC (*e);
+#endif
+#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) (const GtkVector *self)
+{
+  return self->start;
+}
+
+G_GNUC_UNUSED static inline _T_ *
+gtk_vector(index) (const GtkVector *self,
+                   gsize            pos)
+{
+  return self->start + pos;
+}
+
+G_GNUC_UNUSED static inline gsize
+gtk_vector(get_capacity) (const GtkVector *self)
+{
+  return self->end_allocation - self->start;
+}
+
+G_GNUC_UNUSED static inline gsize
+gtk_vector(get_size) (const GtkVector *self)
+{
+  return self->end - self->start;
+}
+
+G_GNUC_UNUSED static inline gboolean
+gtk_vector(is_empty) (const 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 (GTK_VECTOR_REAL_SIZE (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_) * GTK_VECTOR_REAL_SIZE (size));
+    }
+  else
+#endif
+#ifdef GTK_VECTOR_NULL_TERMINATED
+  if (self->start == NULL)
+    {
+      self->start = g_new (_T_, new_size);
+      *self->start = *(_T_[1]) {};
+    }
+  else
+#endif
+    self->start = g_renew (_T_, self->start, new_size);
+
+  self->end = self->start + size;
+  self->end_allocation = self->start + new_size;
+#ifdef GTK_VECTOR_NULL_TERMINATED
+  self->end_allocation--;
+#endif
+}
+
+G_GNUC_UNUSED static void
+gtk_vector(splice) (GtkVector *self,
+                    gsize      pos,
+                    gsize      removed,
+                    _T_       *additions,
+                    gsize      added)
+{
+  gsize size;
+  gsize remaining;
+
+  size = gtk_vector(get_size) (self);
+  g_assert (pos + removed <= size);
+  remaining = size - pos - removed;
+
+  gtk_vector(free_elements) (gtk_vector(index) (self, pos),
+                             gtk_vector(index) (self, pos + removed));
+
+  gtk_vector(reserve) (self, size - removed + added);
+
+  if (GTK_VECTOR_REAL_SIZE (remaining) && removed != added)
+    memmove (gtk_vector(index) (self, pos + added),
+             gtk_vector(index) (self, pos + removed),
+             GTK_VECTOR_REAL_SIZE (remaining) * sizeof (_T_));
+
+  if (added)
+    {
+      if (additions)
+        memcpy (gtk_vector(index) (self, pos),
+                additions,
+                added * sizeof (_T_));
+      else
+        memset (gtk_vector(index) (self, pos), 0, added * sizeof (_T_));
+    }
+
+  /* might overflow, but does the right thing */
+  self->end += added - removed;
+}
+
+G_GNUC_UNUSED static void
+gtk_vector(set_size) (GtkVector *self,
+                      gsize      new_size)
+{
+  gsize old_size = gtk_vector(get_size) (self);
+  if (new_size > old_size)
+    gtk_vector(splice) (self, old_size, 0, NULL, new_size - old_size);
+  else
+    gtk_vector(splice) (self, old_size, old_size - new_size, NULL, 0);
+}
+
+G_GNUC_UNUSED static void
+gtk_vector(append) (GtkVector *self,
+#ifdef GTK_VECTOR_BY_VALUE
+                    _T_       *value)
+#else
+                    _T_        value)
+#endif
+{
+  gtk_vector(splice) (self, 
+                      gtk_vector(get_size) (self),
+                      0,
+#ifdef GTK_VECTOR_BY_VALUE
+                      value,
+#else
+                      &value,
+#endif
+                      1);
+}
+
+#ifdef GTK_VECTOR_BY_VALUE
+G_GNUC_UNUSED static _T_ *
+gtk_vector(get) (const GtkVector *self,
+                 gsize            pos)
+{
+  return gtk_vector(index) (self, pos);
+}
+#else
+G_GNUC_UNUSED static _T_ 
+gtk_vector(get) (const GtkVector *self,
+                 gsize            pos)
+{
+  return *gtk_vector(index) (self, pos);
+}
+#endif
+
+
+#ifndef GTK_VECTOR_NO_UNDEF
+
+#undef _T_
+#undef GtkVector
+#undef gtk_vector_paste_more
+#undef gtk_vector_paste
+#undef gtk_vector
+#undef GTK_VECTOR_REAL_SIZE
+
+#undef GTK_VECTOR_BY_VALUE
+#undef GTK_VECTOR_ELEMENT_TYPE
+#undef GTK_VECTOR_FREE_FUNC
+#undef GTK_VECTOR_NAME
+#undef GTK_VECTOR_NULL_TERMINATED
+#undef GTK_VECTOR_PREALLOC
+#undef GTK_VECTOR_TYPE_NAME
+
+#endif

gtk/meson.build

@@ -160,6 +160,7 @@ gtk_public_sources = files([
   'gtkappchooserwidget.c',
   'gtkapplication.c',
   'gtkapplicationwindow.c',
+  'gtkarraystore.c',
   'gtkaspectframe.c',
   'gtkassistant.c',
   'gtkbinlayout.c',
@@ -447,6 +448,7 @@ gtk_public_headers = files([
   'gtkappchooserwidget.h',
   'gtkapplication.h',
   'gtkapplicationwindow.h',
+  'gtkarraystore.h',
   'gtkaspectframe.h',
   'gtkassistant.h',
   'gtkbinlayout.h',

testsuite/gtk/filterlistmodel-exhaustive.c

@@ -0,0 +1,479 @@
+/* GtkRBTree tests.
+ *
+ * Copyright (C) 2011, Red Hat, Inc.
+ * Authors: Benjamin Otte <otte@gnome.org>
+ *
+ * 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 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/>.
+ */
+
+#include <locale.h>
+
+#include <gtk/gtk.h>
+
+#define ensure_updated() G_STMT_START{ \
+  while (g_main_context_pending (NULL)) \
+    g_main_context_iteration (NULL, TRUE); \
+}G_STMT_END
+
+#define assert_model_equal(model1, model2) G_STMT_START{ \
+  guint _i, _n; \
+  g_assert_cmpint (g_list_model_get_n_items (model1), ==, g_list_model_get_n_items (model2)); \
+  _n = g_list_model_get_n_items (model1); \
+  for (_i = 0; _i < _n; _i++) \
+    { \
+      gpointer o1 = g_list_model_get_item (model1, _i); \
+      gpointer o2 = g_list_model_get_item (model2, _i); \
+      if (o1 != o2) \
+        { \
+          char *_s = g_strdup_printf ("Objects differ at index %u out of %u", _i, _n); \
+         g_assertion_message (G_LOG_DOMAIN, __FILE__, __LINE__, G_STRFUNC, _s); \
+          g_free (_s); \
+        } \
+    } \
+}G_STMT_END
+
+G_GNUC_UNUSED static char *
+model_to_string (GListModel *model)
+{
+  GString *string;
+  guint i, n;
+
+  n = g_list_model_get_n_items (model);
+  string = g_string_new (NULL);
+
+  /* Check that all unchanged items are indeed unchanged */
+  for (i = 0; i < n; i++)
+    {
+      gpointer item = g_list_model_get_item (model, i);
+
+      if (i > 0)
+        g_string_append (string, ", ");
+      g_string_append (string, gtk_string_object_get_string (item));
+      g_object_unref (item);
+    }
+
+  return g_string_free (string, FALSE);
+}
+
+static void
+assert_items_changed_correctly (GListModel *model,
+                                guint       position,
+                                guint       removed,
+                                guint       added,
+                                GListModel *compare)
+{
+  guint i, n_items;
+
+  //g_print ("%s => %u -%u +%u => %s\n", model_to_string (compare), position, removed, added, model_to_string (model));
+
+  g_assert_cmpint (g_list_model_get_n_items (model), ==, g_list_model_get_n_items (compare) - removed + added);
+  n_items = g_list_model_get_n_items (model);
+
+  /* Check that all unchanged items are indeed unchanged */
+  for (i = 0; i < position; i++)
+    {
+      gpointer o1 = g_list_model_get_item (model, i);
+      gpointer o2 = g_list_model_get_item (compare, i);
+      g_assert_cmphex (GPOINTER_TO_SIZE (o1), ==, GPOINTER_TO_SIZE (o2));
+      g_object_unref (o1);
+      g_object_unref (o2);
+    }
+  for (i = position + added; i < n_items; i++)
+    {
+      gpointer o1 = g_list_model_get_item (model, i);
+      gpointer o2 = g_list_model_get_item (compare, i - added + removed);
+      g_assert_cmphex (GPOINTER_TO_SIZE (o1), ==, GPOINTER_TO_SIZE (o2));
+      g_object_unref (o1);
+      g_object_unref (o2);
+    }
+
+  /* Check that the first and last added item are different from
+   * first and last removed item.
+   * Otherwise we could have kept them as-is
+   */
+  if (removed > 0 && added > 0)
+    {
+      gpointer o1 = g_list_model_get_item (model, position);
+      gpointer o2 = g_list_model_get_item (compare, position);
+      g_assert_cmphex (GPOINTER_TO_SIZE (o1), !=, GPOINTER_TO_SIZE (o2));
+      g_object_unref (o1);
+      g_object_unref (o2);
+
+      o1 = g_list_model_get_item (model, position + added - 1);
+      o2 = g_list_model_get_item (compare, position + removed - 1);
+      g_assert_cmphex (GPOINTER_TO_SIZE (o1), !=, GPOINTER_TO_SIZE (o2));
+      g_object_unref (o1);
+      g_object_unref (o2);
+    }
+
+  /* Finally, perform the same change as the signal indicates */
+  g_list_store_splice (G_LIST_STORE (compare), position, removed, NULL, 0);
+  for (i = position; i < position + added; i++)
+    {
+      gpointer item = g_list_model_get_item (G_LIST_MODEL (model), i);
+      g_list_store_insert (G_LIST_STORE (compare), i, item);
+      g_object_unref (item);
+    }
+}
+
+static GtkFilterListModel *
+filter_list_model_new (GListModel *source,
+                       GtkFilter  *filter)
+{
+  GtkFilterListModel *model;
+  GListStore *check;
+  guint i;
+
+  model = gtk_filter_list_model_new (source, filter);
+  check = g_list_store_new (G_TYPE_OBJECT);
+  for (i = 0; i < g_list_model_get_n_items (G_LIST_MODEL (model)); i++)
+    {
+      gpointer item = g_list_model_get_item (G_LIST_MODEL (model), i);
+      g_list_store_append (check, item);
+      g_object_unref (item);
+    }
+  g_signal_connect_data (model,
+                         "items-changed",
+                         G_CALLBACK (assert_items_changed_correctly), 
+                         check,
+                         (GClosureNotify) g_object_unref,
+                         0);
+
+  return model;
+}
+
+#define N_MODELS 8
+
+static GtkFilterListModel *
+create_filter_list_model (gconstpointer  model_id,
+                          GListModel    *source,
+                          GtkFilter     *filter)
+{
+  GtkFilterListModel *model;
+  guint id = GPOINTER_TO_UINT (model_id);
+
+  model = filter_list_model_new (id & 1 ? NULL : source, id & 2 ? NULL : filter);
+
+  switch (id >> 2)
+  {
+    case 0:
+      break;
+
+    case 1:
+      gtk_filter_list_model_set_incremental (model, TRUE);
+      break;
+
+    default:
+      g_assert_not_reached ();
+      break;
+  }
+
+  if (id & 1)
+    gtk_filter_list_model_set_model (model, source);
+  if (id & 2)
+    gtk_filter_list_model_set_filter (model, filter);
+
+  return model;
+}
+
+static GListModel *
+create_source_model (guint min_size, guint max_size)
+{
+  GtkStringList *list;
+  guint i, size;
+
+  size = g_random_int_range (min_size, max_size + 1);
+  list = gtk_string_list_new (NULL);
+
+  for (i = 0; i < size; i++)
+    gtk_string_list_append (list, g_random_boolean () ? "A" : "B");
+
+  return G_LIST_MODEL (list);
+}
+
+#define N_FILTERS 5
+
+static GtkFilter *
+create_filter (gsize id)
+{
+  GtkFilter *filter;
+  GtkExpression *expr;
+
+  switch (id)
+  {
+    case 0:
+      /* GTK_FILTER_MATCH_ALL */
+      return gtk_string_filter_new ();
+
+    case 1:
+      /* GTK_FILTER_MATCH_NONE */
+      filter = gtk_string_filter_new ();
+      gtk_string_filter_set_search (GTK_STRING_FILTER (filter), "does not matter, because no expression");
+      return filter;
+
+    case 2:
+    case 3:
+    case 4:
+      /* match all As, Bs and nothing */
+      filter = gtk_string_filter_new ();
+      expr = gtk_property_expression_new (GTK_TYPE_STRING_OBJECT, NULL, "string");
+      gtk_string_filter_set_expression (GTK_STRING_FILTER (filter), expr);
+      gtk_expression_unref (expr);
+      if (id == 2)
+        gtk_string_filter_set_search (GTK_STRING_FILTER (filter), "A");
+      else if (id == 3)
+        gtk_string_filter_set_search (GTK_STRING_FILTER (filter), "B");
+      else
+        gtk_string_filter_set_search (GTK_STRING_FILTER (filter), "does-not-match");
+      return filter;
+
+    default:
+      g_assert_not_reached ();
+      return NULL;
+  }
+}
+
+static GtkFilter *
+create_random_filter (gboolean allow_null)
+{
+  guint n;
+
+  if (allow_null)
+    n = g_random_int_range (0, N_FILTERS + 1);
+  else
+    n = g_random_int_range (0, N_FILTERS);
+  
+  if (n >= N_FILTERS)
+    return NULL;
+
+  return create_filter (n);
+}
+
+static void
+test_no_filter (gconstpointer model_id)
+{
+  GtkFilterListModel *model;
+  GListModel *source;
+  GtkFilter *filter;
+
+  source = create_source_model (10, 10);
+  model = create_filter_list_model (model_id, source, NULL);
+  ensure_updated ();
+  assert_model_equal (G_LIST_MODEL (model), source);
+
+  filter = create_random_filter (FALSE);
+  gtk_filter_list_model_set_filter (model, filter);
+  g_object_unref (filter);
+  gtk_filter_list_model_set_filter (model, NULL);
+  ensure_updated ();
+  assert_model_equal (G_LIST_MODEL (model), source);
+
+  g_object_unref (model);
+  g_object_unref (source);
+}
+
+/* Compare this:
+ *   source => filter1 => filter2
+ * with:
+ *   source => multifilter(filter1, filter2)
+ * and randomly change the source and filters and see if the
+ * two continue agreeing.
+ */
+static void
+test_two_filters (gconstpointer model_id)
+{
+  GtkFilterListModel *compare;
+  GtkFilterListModel *model1, *model2;
+  GListModel *source;
+  GtkFilter *every, *filter;
+  guint i, j, k;
+
+  source = create_source_model (10, 10);
+  model1 = create_filter_list_model (model_id, source, NULL);
+  model2 = create_filter_list_model (model_id, G_LIST_MODEL (model1), NULL);
+  every = gtk_every_filter_new ();
+  compare = create_filter_list_model (model_id, source, every);
+  g_object_unref (every);
+  g_object_unref (source);
+
+  for (i = 0; i < N_FILTERS; i++)
+    {
+      filter = create_filter (i);
+      gtk_filter_list_model_set_filter (model1, filter);
+      gtk_multi_filter_append (GTK_MULTI_FILTER (every), filter);
+
+      for (j = 0; j < N_FILTERS; j++)
+        {
+          filter = create_filter (i);
+          gtk_filter_list_model_set_filter (model2, filter);
+          gtk_multi_filter_append (GTK_MULTI_FILTER (every), filter);
+
+          ensure_updated ();
+          assert_model_equal (G_LIST_MODEL (model2), G_LIST_MODEL (compare));
+
+          for (k = 0; k < 10; k++)
+            {
+              source = create_source_model (0, 20);
+              gtk_filter_list_model_set_model (compare, source);
+              gtk_filter_list_model_set_model (model1, source);
+              g_object_unref (source);
+
+              ensure_updated ();
+              assert_model_equal (G_LIST_MODEL (model2), G_LIST_MODEL (compare));
+            }
+
+          gtk_multi_filter_remove (GTK_MULTI_FILTER (every), 1);
+        }
+
+      gtk_multi_filter_remove (GTK_MULTI_FILTER (every), 0);
+    }
+
+  g_object_unref (compare);
+  g_object_unref (model2);
+  g_object_unref (model1);
+}
+
+/* Compare this:
+ *   (source => filter) * => flatten
+ * with:
+ *   source * => flatten => filter
+ * and randomly add/remove sources and change the filters and
+ * see if the two agree.
+ *
+ * We use a multifilter for the top chain so that changing the filter
+ * is easy.
+ */
+static void
+test_model_changes (gconstpointer model_id)
+{
+  GListStore *store1, *store2;
+  GtkFlattenListModel *flatten1, *flatten2;
+  GtkFilterListModel *model2;
+  GtkFilter *multi, *filter;
+  gsize i;
+
+  filter = create_random_filter (TRUE);
+  multi = gtk_every_filter_new ();
+  if (filter)
+    gtk_multi_filter_append (GTK_MULTI_FILTER (multi), filter);
+
+  store1 = g_list_store_new (G_TYPE_OBJECT);
+  store2 = g_list_store_new (G_TYPE_OBJECT);
+  flatten1 = gtk_flatten_list_model_new (G_LIST_MODEL (store1));
+  flatten2 = gtk_flatten_list_model_new (G_LIST_MODEL (store2));
+  model2 = create_filter_list_model (model_id, G_LIST_MODEL (flatten2), filter);
+
+  for (i = 0; i < 500; i++)
+    {
+      gboolean add = FALSE, remove = FALSE;
+      guint position;
+
+      switch (g_random_int_range (0, 4))
+      {
+        case 0:
+          /* change the filter */
+          filter = create_random_filter (TRUE);
+          gtk_multi_filter_remove (GTK_MULTI_FILTER (multi), 0); /* no-op if no filter */
+          if (filter)
+            gtk_multi_filter_append (GTK_MULTI_FILTER (multi), filter);
+          gtk_filter_list_model_set_filter (model2, filter);
+          break;
+
+        case 1:
+          /* remove a model */
+          remove = TRUE;
+          break;
+
+        case 2:
+          /* add a model */
+          add = TRUE;
+          break;
+
+        case 3:
+          /* replace a model */
+          remove = TRUE;
+          add = TRUE;
+          break;
+
+        default:
+          g_assert_not_reached ();
+          break;
+      }
+
+      position = g_random_int_range (0, g_list_model_get_n_items (G_LIST_MODEL (store1)) + 1);
+      if (g_list_model_get_n_items (G_LIST_MODEL (store1)) == position)
+        remove = FALSE;
+
+      if (add)
+        {
+          /* We want at least one element, otherwise the filters will see no changes */
+          GListModel *source = create_source_model (1, 20);
+          GtkFilterListModel *model1 = create_filter_list_model (model_id, source, multi);
+          g_list_store_splice (store1,
+                               position,
+                               remove ? 1 : 0,
+                               (gpointer *) &model1, 1);
+          g_list_store_splice (store2,
+                               position,
+                               remove ? 1 : 0,
+                               (gpointer *) &source, 1);
+          g_object_unref (source);
+        }
+      else if (remove)
+        {
+          g_list_store_remove (store1, position);
+          g_list_store_remove (store2, position);
+        }
+
+      if (g_random_boolean ())
+        {
+          ensure_updated ();
+          assert_model_equal (G_LIST_MODEL (flatten1), G_LIST_MODEL (model2));
+        }
+    }
+
+  g_object_unref (model2);
+  g_object_unref (flatten2);
+  g_object_unref (flatten1);
+  g_object_unref (store2);
+  g_object_unref (store1);
+  g_object_unref (multi);
+}
+
+static void
+add_test_for_all_models (const char    *name,
+                         GTestDataFunc  test_func)
+{
+  guint i;
+
+  for (i = 0; i < N_MODELS; i++)
+    {
+      char *path = g_strdup_printf ("/filterlistmodel/model%u/%s", i, name);
+      g_test_add_data_func (path, GUINT_TO_POINTER (i), test_func);
+      g_free (path);
+    }
+}
+
+int
+main (int argc, char *argv[])
+{
+  g_test_init (&argc, &argv, NULL);
+  setlocale (LC_ALL, "C");
+
+  add_test_for_all_models ("no-filter", test_no_filter);
+  add_test_for_all_models ("two-filters", test_two_filters);
+  add_test_for_all_models ("model-changes", test_model_changes);
+
+  return g_test_run ();
+}

testsuite/gtk/gtkarraystore.c

@@ -0,0 +1,283 @@
+/*
+ * 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 "config.h"
+
+#include "gtkarraystore.h"
+
+/**
+ * SECTION:gtkarraystore
+ * @title: GtkArrayStore2
+ * @short_description: A simple array implementation of #GListModel
+ *
+ * #GtkArrayStore2 is a simple implementation of #GListModel that stores all
+ * items in memory.
+ *
+ * It provides appending, deletions, and lookups in O(1) time and insertions
+ * in O(N) time. it is implemented using an array.
+ */
+
+/**
+ * GtkArrayStore2:
+ *
+ * #GtkArrayStore2 is an opaque data structure and can only be accessed
+ * using the following functions.
+ **/
+
+struct _GtkArrayStore2
+{
+  GObject parent_instance;
+
+  GType item_type;
+  GPtrArray *items;
+};
+
+enum
+{
+  PROP_0,
+  PROP_ITEM_TYPE,
+  N_PROPERTIES
+};
+
+static void gtk_array_store2_iface_init (GListModelInterface *iface);
+
+G_DEFINE_TYPE_WITH_CODE (GtkArrayStore2, gtk_array_store2, G_TYPE_OBJECT,
+                         G_IMPLEMENT_INTERFACE (G_TYPE_LIST_MODEL, gtk_array_store2_iface_init));
+
+static void
+gtk_array_store2_dispose (GObject *object)
+{
+  GtkArrayStore2 *self = GTK_ARRAY_STORE2 (object);
+
+  g_ptr_array_free (self->items, TRUE);
+
+  G_OBJECT_CLASS (gtk_array_store2_parent_class)->dispose (object);
+}
+
+static void
+gtk_array_store2_get_property (GObject    *object,
+                              guint       property_id,
+                              GValue     *value,
+                              GParamSpec *pspec)
+{
+  GtkArrayStore2 *self = GTK_ARRAY_STORE2 (object);
+
+  switch (property_id)
+    {
+    case PROP_ITEM_TYPE:
+      g_value_set_gtype (value, self->item_type);
+      break;
+
+    default:
+      G_OBJECT_WARN_INVALID_PROPERTY_ID (object, property_id, pspec);
+    }
+}
+
+static void
+gtk_array_store2_set_property (GObject      *object,
+                              guint         property_id,
+                              const GValue *value,
+                              GParamSpec   *pspec)
+{
+  GtkArrayStore2 *self = GTK_ARRAY_STORE2 (object);
+
+  switch (property_id)
+    {
+    case PROP_ITEM_TYPE: /* construct-only */
+      g_assert (g_type_is_a (g_value_get_gtype (value), G_TYPE_OBJECT));
+      self->item_type = g_value_get_gtype (value);
+      break;
+
+    default:
+      G_OBJECT_WARN_INVALID_PROPERTY_ID (object, property_id, pspec);
+    }
+}
+
+static void
+gtk_array_store2_class_init (GtkArrayStore2Class *klass)
+{
+  GObjectClass *object_class = G_OBJECT_CLASS (klass);
+
+  object_class->dispose = gtk_array_store2_dispose;
+  object_class->get_property = gtk_array_store2_get_property;
+  object_class->set_property = gtk_array_store2_set_property;
+
+  /**
+   * GtkArrayStore2:item-type:
+   *
+   * The type of items contained in this list self. Items must be
+   * subclasses of #GObject.
+   **/
+  g_object_class_install_property (object_class, PROP_ITEM_TYPE,
+    g_param_spec_gtype ("item-type", "", "", G_TYPE_OBJECT,
+                        G_PARAM_CONSTRUCT_ONLY | G_PARAM_READWRITE | G_PARAM_STATIC_STRINGS));
+}
+
+static GType
+gtk_array_store2_get_item_type (GListModel *list)
+{
+  GtkArrayStore2 *self = GTK_ARRAY_STORE2 (list);
+
+  return self->item_type;
+}
+
+static guint
+gtk_array_store2_get_n_items (GListModel *list)
+{
+  GtkArrayStore2 *self = GTK_ARRAY_STORE2 (list);
+
+  return self->items->len;
+}
+
+static gpointer
+gtk_array_store2_get_item (GListModel *list,
+                          guint       position)
+{
+  GtkArrayStore2 *self = GTK_ARRAY_STORE2 (list);
+
+  if (position >= self->items->len)
+    return NULL;
+
+  return g_object_ref (g_ptr_array_index (self->items, position));
+}
+
+static void
+gtk_array_store2_iface_init (GListModelInterface *iface)
+{
+  iface->get_item_type = gtk_array_store2_get_item_type;
+  iface->get_n_items = gtk_array_store2_get_n_items;
+  iface->get_item = gtk_array_store2_get_item;
+}
+
+static void
+gtk_array_store2_init (GtkArrayStore2 *self)
+{
+  self->items = g_ptr_array_new_with_free_func (g_object_unref);
+}
+
+/**
+ * gtk_array_store2_new:
+ * @item_type: the #GType of items in the list
+ *
+ * Creates a new #GtkArrayStore2 with items of type @item_type. @item_type
+ * must be a subclass of #GObject.
+ *
+ * Returns: a new #GtkArrayStore2
+ */
+GtkArrayStore2 *
+gtk_array_store2_new (GType item_type)
+{
+  g_return_val_if_fail (g_type_is_a (item_type, G_TYPE_OBJECT), NULL);
+
+  return g_object_new (GTK_TYPE_ARRAY_STORE2,
+                       "item-type", item_type,
+                       NULL);
+}
+
+/**
+ * gtk_array_store2_append:
+ * @self: a #GtkArrayStore2
+ * @item: (type GObject): the new item
+ *
+ * Appends @item to @self. @item must be of type #GtkArrayStore2:item-type.
+ *
+ * This function takes a ref on @item.
+ *
+ * Use gtk_array_store2_splice() to append multiple items at the same time
+ * efficiently.
+ */
+void
+gtk_array_store2_append (GtkArrayStore2 *self,
+                        gpointer       item)
+{
+  guint position;
+
+  g_return_if_fail (GTK_IS_ARRAY_STORE2 (self));
+  g_return_if_fail (g_type_is_a (G_OBJECT_TYPE (item), self->item_type));
+
+  position = self->items->len;
+  g_ptr_array_add (self->items, g_object_ref (item));
+  g_list_model_items_changed (G_LIST_MODEL (self), position, 0, 1);
+}
+
+/**
+ * gtk_array_store2_remove_all:
+ * @self: a #GtkArrayStore2
+ *
+ * Removes all items from @self.
+ *
+ * Since: 2.44
+ */
+void
+gtk_array_store2_remove_all (GtkArrayStore2 *self)
+{
+  guint n_items;
+
+  g_return_if_fail (GTK_IS_ARRAY_STORE2 (self));
+
+  n_items = self->items->len;
+  g_ptr_array_remove_range (self->items, 0, n_items);
+
+  g_list_model_items_changed (G_LIST_MODEL (self), 0, n_items, 0);
+}
+
+/**
+ * gtk_array_store2_splice:
+ * @self: a #GtkArrayStore2
+ * @position: the position at which to make the change
+ * @n_removals: the number of items to remove
+ * @additions: (array length=n_additions) (element-type GObject): the items to add
+ * @n_additions: the number of items to add
+ *
+ * Changes @self by removing @n_removals items and adding @n_additions
+ * items to it. @additions must contain @n_additions items of type
+ * #GtkArrayStore2:item-type.  %NULL is not permitted.
+ *
+ * This function is more efficient than gtk_array_store2_insert() and
+ * gtk_array_store2_remove(), because it only emits
+ * #GListModel::items-changed once for the change.
+ *
+ * This function takes a ref on each item in @additions.
+ *
+ * The parameters @position and @n_removals must be correct (ie:
+ * @position + @n_removals must be less than or equal to the length of
+ * the list at the time this function is called).
+ *
+ * Since: 2.44
+ */
+void
+gtk_array_store2_splice (GtkArrayStore2 *self,
+                        guint       position,
+                        guint       n_removals,
+                        gpointer   *additions,
+                        guint       n_additions)
+{
+  guint i;
+
+  g_return_if_fail (GTK_IS_ARRAY_STORE2 (self));
+  g_return_if_fail (position + n_removals >= position); /* overflow */
+  g_return_if_fail (position + n_removals <= self->items->len);
+
+  g_ptr_array_remove_range (self->items, position, n_removals);
+
+  for (i = 0; i < n_additions; i++)
+    g_ptr_array_add (self->items, g_object_ref (additions[i]));
+
+  g_list_model_items_changed (G_LIST_MODEL (self), position, n_removals, n_additions);
+}

testsuite/gtk/gtkarraystore.h

@@ -0,0 +1,50 @@
+/*
+ * 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>
+ */
+
+#ifndef __GTK_ARRAY_STORE2_H__
+#define __GTK_ARRAY_STORE2_H__
+
+#include <gdk/gdk.h>
+
+G_BEGIN_DECLS
+
+#define GTK_TYPE_ARRAY_STORE2 (gtk_array_store2_get_type ())
+GDK_AVAILABLE_IN_ALL
+G_DECLARE_FINAL_TYPE(GtkArrayStore2, gtk_array_store2, GTK, ARRAY_STORE2, GObject)
+
+GDK_AVAILABLE_IN_ALL
+GtkArrayStore2 *         gtk_array_store2_new                             (GType           item_type);
+
+GDK_AVAILABLE_IN_ALL
+void                    gtk_array_store2_append                          (GtkArrayStore2  *store,
+                                                                         gpointer        item);
+
+GDK_AVAILABLE_IN_ALL
+void                    gtk_array_store2_remove_all                      (GtkArrayStore2  *store);
+
+GDK_AVAILABLE_IN_ALL
+void                    gtk_array_store2_splice                          (GtkArrayStore2  *store,
+                                                                         guint           position,
+                                                                         guint           n_removals,
+                                                                         gpointer       *additions,
+                                                                         guint           n_additions);
+
+G_END_DECLS
+
+#endif /* __GTK_ARRAY_STORE2_H__ */

testsuite/gtk/gtkstringlist.c

@@ -0,0 +1,222 @@
+/*
+ * Copyright © 2020 Red Hat, Inc.
+ *
+ * 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: Matthias Clasen <mclasen@redhat.com>
+ */
+
+#include "config.h"
+
+#include <gtk.h>
+#include "gtkstringlist.h"
+
+struct _GtkStringList2
+{
+  GObject parent_instance;
+
+  GSequence *items;
+};
+
+struct _GtkStringList2Class
+{
+  GObjectClass parent_class;
+};
+
+static GType
+gtk_string_list2_get_item_type (GListModel *list)
+{
+  return G_TYPE_OBJECT;
+}
+
+static guint
+gtk_string_list2_get_n_items (GListModel *list)
+{
+  GtkStringList2 *self = GTK_STRING_LIST2 (list);
+
+  return g_sequence_get_length (self->items);
+}
+
+static gpointer
+gtk_string_list2_get_item (GListModel *list,
+                          guint       position)
+{
+  GtkStringList2 *self = GTK_STRING_LIST2 (list);
+  GSequenceIter *iter;
+
+  iter = g_sequence_get_iter_at_pos (self->items, position);
+
+  if (g_sequence_iter_is_end (iter))
+     return NULL;
+  else
+    return g_object_ref (g_sequence_get (iter));
+}
+
+static void
+gtk_string_list2_model_init (GListModelInterface *iface)
+{
+  iface->get_item_type = gtk_string_list2_get_item_type;
+  iface->get_n_items = gtk_string_list2_get_n_items;
+  iface->get_item = gtk_string_list2_get_item;
+}
+
+G_DEFINE_TYPE_WITH_CODE (GtkStringList2, gtk_string_list2, G_TYPE_OBJECT,
+                         G_IMPLEMENT_INTERFACE (G_TYPE_LIST_MODEL,
+                                                gtk_string_list2_model_init))
+
+static void
+gtk_string_list2_dispose (GObject *object)
+{
+  GtkStringList2 *self = GTK_STRING_LIST2 (object);
+
+  g_clear_pointer (&self->items, g_sequence_free);
+
+  G_OBJECT_CLASS (gtk_string_list2_parent_class)->dispose (object);
+}
+
+static void
+gtk_string_list2_class_init (GtkStringList2Class *class)
+{
+  GObjectClass *gobject_class = G_OBJECT_CLASS (class);
+
+  gobject_class->dispose = gtk_string_list2_dispose;
+}
+
+static void
+gtk_string_list2_init (GtkStringList2 *self)
+{
+  self->items = g_sequence_new (g_object_unref);
+}
+
+GtkStringList2 *
+gtk_string_list2_new (const char * const *strings)
+{
+  GtkStringList2 *self;
+
+  self = g_object_new (GTK_TYPE_STRING_LIST2, NULL);
+
+  gtk_string_list2_splice (self, 0, 0, strings);
+
+  return self;
+}
+
+typedef struct {
+  GObject obj;
+  char *str;
+} StrObj;
+
+static GtkStringObject *
+string_object_new (const char *string)
+{
+  GtkStringObject *s;
+
+  s = g_object_new (GTK_TYPE_STRING_OBJECT, NULL);
+  ((StrObj*)s)->str = g_strdup (string);
+
+  return s;
+}
+
+void
+gtk_string_list2_splice (GtkStringList2      *self,
+                        guint               position,
+                        guint               n_removals,
+                        const char * const *additions)
+{
+  guint n_items;
+  guint add;
+  GSequenceIter *it;
+
+  g_return_if_fail (GTK_IS_STRING_LIST2 (self));
+  g_return_if_fail (position + n_removals >= position); /* overflow */
+
+  n_items = g_sequence_get_length (self->items);
+  g_return_if_fail (position + n_removals <= n_items);
+
+  it = g_sequence_get_iter_at_pos (self->items, position);
+
+  if (n_removals)
+    {
+      GSequenceIter *end;
+
+      end = g_sequence_iter_move (it, n_removals);
+      g_sequence_remove_range (it, end);
+
+      it = end;
+    }
+
+  if (additions)
+    {
+      for (add = 0; additions[add]; add++)
+        {
+          g_sequence_insert_before (it, string_object_new (additions[add]));
+        }
+    }
+  else
+    add = 0;
+
+  if (n_removals || add)
+    g_list_model_items_changed (G_LIST_MODEL (self), position, n_removals, add);
+}
+
+void
+gtk_string_list2_append (GtkStringList2 *self,
+                        const char    *string)
+{
+  guint n_items;
+
+  g_return_if_fail (GTK_IS_STRING_LIST2 (self));
+
+  n_items = g_sequence_get_length (self->items);
+  g_sequence_append (self->items, string_object_new (string));
+
+  g_list_model_items_changed (G_LIST_MODEL (self), n_items, 0, 1);
+}
+
+void
+gtk_string_list2_remove (GtkStringList2 *self,
+                        guint          position)
+{
+  GSequenceIter *iter;
+
+  g_return_if_fail (GTK_IS_STRING_LIST2 (self));
+
+  iter = g_sequence_get_iter_at_pos (self->items, position);
+  g_return_if_fail (!g_sequence_iter_is_end (iter));
+
+  g_sequence_remove (iter);
+
+  g_list_model_items_changed (G_LIST_MODEL (self), position, 1, 0);
+}
+
+const char *
+gtk_string_list2_get_string (GtkStringList2 *self,
+                            guint          position)
+{
+  GSequenceIter *iter;
+
+   g_return_val_if_fail (GTK_IS_STRING_LIST (self), NULL);
+
+  iter = g_sequence_get_iter_at_pos (self->items, position);
+
+  if (g_sequence_iter_is_end (iter))
+    {
+      return NULL;
+    }
+   else
+    {
+      GtkStringObject *obj = g_sequence_get (iter);
+
+      return gtk_string_object_get_string (obj);
+    }
+}

testsuite/gtk/gtkstringlist.h

@@ -0,0 +1,62 @@
+/*
+ * Copyright © 2020 Red Hat, Inc.
+ *
+ * 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: Matthias Clasen <mclasen@redhat.com>
+ */
+
+#ifndef __GTK_STRING_LIST2_H__
+#define __GTK_STRING_LIST2_H__
+
+#include <gio/gio.h>
+/* for GDK_AVAILABLE_IN_ALL */
+#include <gdk/gdk.h>
+
+
+G_BEGIN_DECLS
+
+#define GTK_TYPE_STRING_LIST2 (gtk_string_list2_get_type ())
+
+GDK_AVAILABLE_IN_ALL
+G_DECLARE_FINAL_TYPE (GtkStringList2, gtk_string_list2, GTK, STRING_LIST2, GObject)
+
+GDK_AVAILABLE_IN_ALL
+GtkStringList2 * gtk_string_list2_new             (const char * const    *strings);
+
+GDK_AVAILABLE_IN_ALL
+void            gtk_string_list2_append          (GtkStringList2         *self,
+                                                 const char            *string);
+
+GDK_AVAILABLE_IN_ALL
+void            gtk_string_list2_take            (GtkStringList2         *self,
+                                                 char                  *string);
+
+GDK_AVAILABLE_IN_ALL
+void            gtk_string_list2_remove          (GtkStringList2         *self,
+                                                 guint                  position);
+
+GDK_AVAILABLE_IN_ALL
+void            gtk_string_list2_splice          (GtkStringList2         *self,
+                                                 guint                  position,
+                                                 guint                  n_removals,
+                                                 const char * const    *additions);
+
+GDK_AVAILABLE_IN_ALL
+const char *    gtk_string_list2_get_string      (GtkStringList2         *self,
+                                                 guint                  position);
+
+G_END_DECLS
+
+#endif /* __GTK_STRING_LIST2_H__ */

testsuite/gtk/listmodel-performance.c

@@ -0,0 +1,422 @@
+#include <gtk/gtk.h>
+
+#include "gtkarraystore.h"
+#include "gtkstringlist.h"
+
+typedef struct {
+  const char *name;
+  GListModel * (* create_model) (guint n_items);
+  void         (* append)       (GListModel *model, const char *s);
+  void         (* insert)       (GListModel *model, guint pos, const char *s);
+} Model;
+
+static GListModel *
+make_list_store (guint n_items)
+{
+  GListStore *store;
+  guint i;
+
+  store = g_list_store_new (GTK_TYPE_STRING_OBJECT);
+
+  for (i = 0; i < n_items; i++)
+    {
+      char *string;
+      gpointer obj;
+
+      string = g_strdup_printf ("item %d", i);
+      obj = gtk_string_object_new (string);
+      g_list_store_append (store, obj);
+      g_object_unref (obj);
+      g_free (string);
+    }
+
+  return G_LIST_MODEL (store);
+}
+
+static void
+append_list_store (GListModel *model, const char *s)
+{
+  gpointer obj = gtk_string_object_new (s);
+  g_list_store_append (G_LIST_STORE (model), obj);
+  g_object_unref (obj);
+}
+
+static void
+insert_list_store (GListModel *model, guint pos, const char *s)
+{
+  gpointer obj = gtk_string_object_new (s);
+  g_list_store_insert (G_LIST_STORE (model), pos, obj);
+  g_object_unref (obj);
+}
+
+static GListModel *
+make_array_store (guint n_items)
+{
+  GtkArrayStore *store;
+  guint i;
+
+  store = gtk_array_store_new ();
+
+  for (i = 0; i < n_items; i++)
+    {
+      char *string;
+      gpointer obj;
+
+      string = g_strdup_printf ("item %d", i);
+      obj = gtk_string_object_new (string);
+      gtk_array_store_append (store, obj);
+      g_object_unref (obj);
+      g_free (string);
+    }
+
+  return G_LIST_MODEL (store);
+}
+
+static void
+append_array_store (GListModel *model, const char *s)
+{
+  gpointer obj = gtk_string_object_new (s);
+  gtk_array_store_append (GTK_ARRAY_STORE (model), obj);
+  g_object_unref (obj);
+}
+
+static void
+insert_array_store (GListModel *model, guint pos, const char *s)
+{
+  gpointer obj = gtk_string_object_new (s);
+  gtk_array_store_splice (GTK_ARRAY_STORE (model), pos, 0, (gpointer *)&obj, 1);
+  g_object_unref (obj);
+}
+
+static GListModel *
+make_array_store2 (guint n_items)
+{
+  GtkArrayStore2 *store;
+  guint i;
+
+  store = gtk_array_store2_new (GTK_TYPE_STRING_OBJECT);
+
+  for (i = 0; i < n_items; i++)
+    {
+      char *string;
+      gpointer obj;
+
+      string = g_strdup_printf ("item %d", i);
+      obj = gtk_string_object_new (string);
+      gtk_array_store2_append (store, obj);
+      g_object_unref (obj);
+      g_free (string);
+    }
+
+  return G_LIST_MODEL (store);
+}
+
+static void
+append_array_store2 (GListModel *model, const char *s)
+{
+  gpointer obj = gtk_string_object_new (s);
+  gtk_array_store2_append (GTK_ARRAY_STORE2 (model), obj);
+  g_object_unref (obj);
+}
+
+static void
+insert_array_store2 (GListModel *model, guint pos, const char *s)
+{
+  gpointer obj = gtk_string_object_new (s);
+  gtk_array_store2_splice (GTK_ARRAY_STORE2 (model), pos, 0, (gpointer *)&obj, 1);
+  g_object_unref (obj);
+}
+
+static GListModel *
+make_sequence_string_list (guint n_items)
+{
+  GtkStringList2 *store;
+  guint i;
+
+  store = gtk_string_list2_new (NULL);
+
+  for (i = 0; i < n_items; i++)
+    {
+      char *string;
+
+      string = g_strdup_printf ("item %d", i);
+      gtk_string_list2_append (store, string);
+      g_free (string);
+    }
+
+  return G_LIST_MODEL (store);
+}
+
+static void
+append_sequence_string_list (GListModel *model, const char *s)
+{
+  gtk_string_list2_append (GTK_STRING_LIST2 (model), s);
+}
+
+static void
+insert_sequence_string_list (GListModel *model, guint pos, const char *s)
+{
+  gtk_string_list2_splice (GTK_STRING_LIST2 (model), pos, 0, (const char *[2]) { s, NULL });
+}
+
+static GListModel *
+make_string_list (guint n_items)
+{
+  GtkStringList *store;
+  guint i;
+
+  store = gtk_string_list_new (NULL);
+
+  for (i = 0; i < n_items; i++)
+    {
+      char *string;
+
+      string = g_strdup_printf ("item %d", i);
+      gtk_string_list_append (store, string);
+      g_free (string);
+    }
+
+  return G_LIST_MODEL (store);
+}
+
+static void
+append_string_list (GListModel *model, const char *s)
+{
+  gtk_string_list_append (GTK_STRING_LIST (model), s);
+}
+
+static void
+insert_string_list (GListModel *model, guint pos, const char *s)
+{
+  gtk_string_list_splice (GTK_STRING_LIST (model), pos, 0, (const char *[2]) { s, NULL });
+}
+
+static void
+do_random_access (const Model *klass,
+                  guint        size)
+{
+  GListModel *model;
+  guint i;
+  guint position;
+  GtkStringObject *obj;
+  gint64 start, end;
+  guint iterations = 10000000;
+
+  model = klass->create_model (size);
+
+  start = g_get_monotonic_time ();
+
+  for (i = 0; i < iterations; i++)
+    {
+      position = g_random_int_range (0, size);
+      obj = g_list_model_get_item (model, position);
+      if (g_getenv ("PRINT_ACCESS"))
+        g_printerr ("%s", gtk_string_object_get_string (obj));
+      g_object_unref (obj);
+    }
+
+  end = g_get_monotonic_time ();
+
+  g_printerr ("\"random access\",\"%s\", %u, %g\n",
+              klass->name,
+              size,
+              ((double)(end - start)) / iterations);
+
+  g_object_unref (model);
+}
+
+static void
+do_linear_access (const Model *klass,
+                  guint        size)
+{
+  GListModel *model;
+  guint i;
+  GtkStringObject *obj;
+  gint64 start, end;
+  guint iterations = 1000000;
+
+  model = klass->create_model (size);
+
+  start = g_get_monotonic_time ();
+
+  for (i = 0; i < iterations; i++)
+    {
+      obj = g_list_model_get_item (model, i % size);
+      if (g_getenv ("PRINT_ACCESS"))
+        g_printerr ("%s", gtk_string_object_get_string (obj));
+      g_object_unref (obj);
+    }
+
+  end = g_get_monotonic_time ();
+
+  g_printerr ("\"linear access\", \"%s\", %u, %g\n",
+              klass->name,
+              size,
+              ((double)(end - start)) / iterations);
+
+  g_object_unref (model);
+}
+
+static void
+do_append (const Model *klass,
+           guint        size)
+{
+  GListModel *model;
+  guint i, j;
+  gint64 start, end;
+  int iterations = 5;
+  gint64 total;
+
+  total = 0;
+
+  for (i = 0; i < iterations; i++)
+    {
+      model = klass->create_model (size);
+
+      start = g_get_monotonic_time ();
+
+      for (j = 0; j < size; j++)
+        {
+          char *string = g_strdup_printf ("item %d", j);
+
+          klass->append (model, string);
+        }
+
+      end = g_get_monotonic_time ();
+      total += end - start;
+
+      g_object_unref (model);
+    }
+
+  g_printerr ("\"append\", \"%s\", %u, %g\n", klass->name, size, ((double)total) / iterations);
+}
+
+static void
+do_insert (const Model *klass,
+           guint        size)
+{
+  GListModel *model;
+  guint i, j;
+  gint64 start, end;
+  int iterations = 5;
+  gint64 total;
+  guint position;
+
+  total = 0;
+
+  for (i = 0; i < iterations; i++)
+    {
+      model = klass->create_model (size);
+
+      start = g_get_monotonic_time ();
+
+      for (j = 1; j < size; j++)
+        {
+          char *string = g_strdup_printf ("item %d", j);
+          position = g_random_int_range (0, j);
+
+          klass->insert (model, position, string);
+
+          g_free (string);
+        }
+
+      end = g_get_monotonic_time ();
+      total += end - start;
+
+      g_object_unref (model);
+    }
+
+  g_printerr ("\"insert\", \"%s\", %u, %g\n", klass->name, size, ((double)total) / iterations);
+}
+
+const Model all_models[] = {
+  {
+    "liststore",
+    make_list_store,
+    append_list_store,
+    insert_list_store
+  },
+  {
+    "arraystore",
+    make_array_store,
+    append_array_store,
+    insert_array_store
+  },
+  {
+    "ptrarraystore",
+    make_array_store2,
+    append_array_store2,
+    insert_array_store2
+  },
+  {
+    "sequence-stringlist",
+    make_sequence_string_list,
+    append_sequence_string_list,
+    insert_sequence_string_list
+  },
+  {
+    "stringlist",
+    make_string_list,
+    append_string_list,
+    insert_string_list
+  }
+};
+
+typedef struct {
+  void (* test_func) (const Model *model, guint size);
+  const Model *model;
+  guint size;
+} TestData;
+
+static void
+free_test_data (gpointer data)
+{
+  g_free (data);
+}
+
+static void
+run_test (gconstpointer data)
+{
+  const TestData *test = data;
+
+  test->test_func (test->model, test->size);
+}
+
+static void
+add_test (const char *name,
+          void (* test_func) (const Model *model, guint size))
+{
+  int max_size = 10 * 1000 * 1000;
+  int size;
+  int i;
+
+  for (i = 0; i < G_N_ELEMENTS (all_models); i++)
+    {
+      for (size = 1; size <= max_size; size *= 100)
+        {
+          TestData *test = g_new0 (TestData, 1);
+          char *path;
+
+          test->test_func = test_func;
+          test->model = &all_models[i];
+          test->size = size;
+          path = g_strdup_printf ("/model/%s/%s/size-%d", name, all_models[i].name, size);
+          g_test_add_data_func_full (path, test, run_test, free_test_data);
+          g_free (path);
+        }
+    }
+}
+
+int
+main (int argc, char *argv[])
+{
+  gtk_test_init (&argc, &argv);
+
+  g_printerr ("\"test\",\"model\",\"model size\",\"time\"\n");
+  add_test ("random-access", do_random_access);
+  add_test ("linear-access", do_linear_access);
+  add_test ("append", do_append);
+  add_test ("insert", do_insert);
+
+  return g_test_run ();
+}

testsuite/gtk/meson.build

@@ -30,6 +30,7 @@ tests = [
   ['expression'],
   ['filter'],
   ['filterlistmodel'],
+  ['filterlistmodel-exhaustive'],
   ['flattenlistmodel'],
   ['floating'],
   ['flowbox'],
@@ -74,8 +75,11 @@ tests = [
   ['typename'],
   ['displayclose'],
   ['revealer-size'],
+  ['vector'],
+  ['vector-performance'],
   ['widgetorder'],
   ['widget-refcount'],
+  ['listmodel-performance', ['listmodel-performance.c','gtkstringlist.c','gtkarraystore.c']]
 ]
 
 # Tests that are expected to fail

testsuite/gtk/vector-performance.c

@@ -0,0 +1,443 @@
+#include <gtk/gtk.h>
+
+#define GTK_VECTOR_ELEMENT_TYPE gpointer
+#define GTK_VECTOR_NAME pointer_vector
+#define GTK_VECTOR_TYPE_NAME PointerVector
+#include "../../gtk/gtkvectorimpl.c"
+
+#define GTK_VECTOR_ELEMENT_TYPE gpointer
+#define GTK_VECTOR_NAME prealloc_vector
+#define GTK_VECTOR_TYPE_NAME PreallocVector
+#define GTK_VECTOR_PREALLOC 1024
+#include "../../gtk/gtkvectorimpl.c"
+
+static inline guint
+quick_random (guint prev)
+{
+  prev ^= prev << 13;
+  prev ^= prev >> 17;
+  prev ^= prev << 5;
+  return prev;
+}
+
+typedef struct {
+  const char *name;
+  gsize stack_space;
+  gpointer     (* create)       (gpointer space, gsize size);
+  void         (* free)         (gpointer array);
+  void         (* reserve)      (gpointer array, gsize size);
+  gpointer     (* get)          (gpointer array, gsize pos);
+  void         (* append)       (gpointer array, gpointer data);
+  void         (* insert)       (gpointer array, gsize pos, gpointer data);
+} Array;
+
+static gpointer
+create_ptrarray (gpointer space,
+                 gsize    size)
+{
+  return g_ptr_array_sized_new (size);
+}
+
+static void
+free_ptrarray (gpointer array)
+{
+  g_ptr_array_free (array, TRUE);
+}
+
+static void
+reserve_ptrarray (gpointer array,
+                  gsize    size)
+{
+  gsize length = ((GPtrArray *) array)->len;
+
+  if (length >= size)
+    return;
+
+  g_ptr_array_set_size (array, size);
+  g_ptr_array_set_size (array, length);
+}
+
+static gpointer
+get_ptrarray (gpointer array,
+              gsize    pos)
+{
+  return g_ptr_array_index ((GPtrArray *) array, pos);
+}
+
+static void
+append_ptrarray (gpointer array,
+                 gpointer data)
+{
+  g_ptr_array_add (array, data);
+}
+
+static void
+insert_ptrarray (gpointer array,
+                 gsize pos,
+                 gpointer data)
+{
+  g_ptr_array_insert (array, pos, data);
+}
+
+static gpointer
+create_vector (gpointer space,
+               gsize    size)
+{
+  pointer_vector_init (space);
+
+  if (size)
+    pointer_vector_reserve ((PointerVector *) space, size);
+
+  return space;
+}
+
+static void
+free_vector (gpointer array)
+{
+  pointer_vector_clear (array);
+}
+
+static void
+reserve_vector (gpointer array,
+                gsize    size)
+{
+  pointer_vector_reserve (array, size);
+}
+
+static gpointer
+get_vector (gpointer array,
+            gsize    pos)
+{
+  return pointer_vector_get (array, pos);
+}
+
+static void
+append_vector (gpointer array,
+               gpointer data)
+{
+  pointer_vector_append (array, data);
+}
+
+static void
+insert_vector (gpointer array,
+               gsize pos,
+               gpointer data)
+{
+  pointer_vector_splice (array, pos, 0, &data, 1);
+}
+
+static gpointer
+create_prealloc (gpointer space,
+                 gsize    size)
+{
+  prealloc_vector_init (space);
+
+  if (size)
+    prealloc_vector_reserve ((PreallocVector *) space, size);
+
+  return space;
+}
+
+static void
+free_prealloc (gpointer array)
+{
+  prealloc_vector_clear (array);
+}
+
+static void
+reserve_prealloc (gpointer array,
+                  gsize    size)
+{
+  prealloc_vector_reserve (array, size);
+}
+
+static gpointer
+get_prealloc (gpointer array,
+              gsize    pos)
+{
+  return prealloc_vector_get (array, pos);
+}
+
+static void
+append_prealloc (gpointer array,
+                 gpointer data)
+{
+  prealloc_vector_append (array, data);
+}
+
+static void
+insert_prealloc (gpointer array,
+                 gsize pos,
+                 gpointer data)
+{
+  prealloc_vector_splice (array, pos, 0, &data, 1);
+}
+
+static void
+do_random_access (const Array *klass,
+                  guint        random,
+                  gsize        size,
+                  gsize        max_size)
+{
+  gpointer stack;
+  gpointer array;
+  guint i;
+  guint position;
+  gint64 start, end;
+  guint iterations = 10000000;
+
+  size = pow (100 * 100 * 100 * 100, (double) size / max_size);
+
+  if (klass->stack_space)
+    stack = g_alloca (klass->stack_space);
+  else
+    stack = NULL;
+  array = klass->create (stack, size);
+  for (i = 0; i < size; i++)
+    klass->append (array, GSIZE_TO_POINTER (i));
+
+  start = g_get_monotonic_time ();
+
+  for (i = 0; i < iterations; i++)
+    {
+      position = random % size;
+      random = quick_random (random);
+      g_assert_cmpint (position, ==, GPOINTER_TO_SIZE (klass->get (array, position)));
+    }
+
+  end = g_get_monotonic_time ();
+
+  g_print ("\"random access\",\"%s\", %zu, %g\n",
+           klass->name,
+           size,
+           ((double)(end - start)) / iterations);
+
+  klass->free (array);
+}
+
+static void
+do_linear_access (const Array *klass,
+                  guint        random,
+                  gsize        size,
+                  gsize        max_size)
+{
+  gpointer stack;
+  gpointer array;
+  guint i;
+  gint64 start, end;
+  guint iterations = 1000000;
+
+  size = pow (100 * 100 * 100 * 100, (double) size / max_size);
+
+  if (klass->stack_space)
+    stack = g_alloca (klass->stack_space);
+  else
+    stack = NULL;
+  array = klass->create (stack, size);
+  for (i = 0; i < size; i++)
+    klass->append (array, GSIZE_TO_POINTER (i));
+
+  start = g_get_monotonic_time ();
+
+  for (i = 0; i < iterations; i++)
+    {
+      g_assert_cmpint (i % size, ==, GPOINTER_TO_SIZE (klass->get (array, i % size)));
+    }
+
+  end = g_get_monotonic_time ();
+
+  g_print ("\"linear access\", \"%s\", %zu, %g\n",
+           klass->name,
+           size,
+           ((double)(end - start)) / iterations);
+
+  klass->free (array);
+}
+
+static void
+do_append (const Array *klass,
+           guint        random,
+           gsize        size,
+           gsize        max_size)
+{
+  gpointer stack;
+  gpointer array;
+  guint i;
+  gint64 start, end;
+  int iterations = 10000;
+
+  size = pow (100 * 1000 * 1000, (double) size / max_size);
+
+  if (klass->stack_space)
+    stack = g_alloca (klass->stack_space);
+  else
+    stack = NULL;
+  array = klass->create (stack, size);
+  for (i = 0; i < size; i++)
+    klass->append (array, GSIZE_TO_POINTER (i));
+
+  start = g_get_monotonic_time ();
+
+  for (i = size; i < size + iterations; i++)
+    {
+      klass->append (array, GSIZE_TO_POINTER (i));
+    }
+
+  end = g_get_monotonic_time ();
+
+  klass->free (array);
+
+  g_print ("\"append\", \"%s\", %zu, %g\n",
+           klass->name,
+           size,
+           ((double) (end - start)) / iterations);
+}
+
+static void
+do_insert (const Array *klass,
+           guint        random,
+           gsize        size,
+           gsize        max_size)
+{
+  gpointer stack;
+  gpointer array;
+  guint i;
+  gint64 start, end;
+  int iterations = 10000;
+
+  size = pow (25 * 25 * 25 * 25, (double) size / max_size);
+
+  if (klass->stack_space)
+    stack = g_alloca (klass->stack_space);
+  else
+    stack = NULL;
+  array = klass->create (stack, size);
+  for (i = 0; i < size; i++)
+    klass->append (array, GSIZE_TO_POINTER (i));
+
+  start = g_get_monotonic_time ();
+
+  for (i = size; i < size + iterations; i++)
+    {
+      gsize position = random % size;
+      random = quick_random (random);
+
+      klass->insert (array, position, GSIZE_TO_POINTER (i));
+    }
+
+  end = g_get_monotonic_time ();
+
+  klass->free (array);
+
+  g_print ("\"insert\", \"%s\", %zu, %g\n",
+           klass->name,
+           size,
+           ((double) (end - start)) / iterations);
+}
+
+static void
+do_create (const Array *klass,
+           guint        random,
+           gsize        size,
+           gsize        max_size)
+{
+  gpointer stack;
+  gpointer array;
+  gsize i, j;
+  gint64 start, end;
+  gsize iterations = 100000;
+
+  size = pow (4 * 4 * 4 * 4, (double) size / max_size);
+
+  if (klass->stack_space)
+    stack = g_alloca (klass->stack_space);
+  else
+    stack = NULL;
+
+  start = g_get_monotonic_time ();
+
+  for (i = 0; i < iterations; i++)
+    {
+      gsize position = random % size;
+      random = quick_random (random);
+
+      array = klass->create (stack, size);
+      for (j = 0; j < size; j++)
+        klass->append (array, GSIZE_TO_POINTER (i));
+
+      klass->insert (array, position, GSIZE_TO_POINTER (i));
+      klass->free (array);
+    }
+
+  end = g_get_monotonic_time ();
+
+  g_print ("\"create\", \"%s\", %zu, %g\n",
+           klass->name,
+           size,
+           ((double) (end - start)) / iterations);
+}
+
+const Array all_arrays[] = {
+  {
+    "ptrarray",
+    0,
+    create_ptrarray,
+    free_ptrarray,
+    reserve_ptrarray,
+    get_ptrarray,
+    append_ptrarray,
+    insert_ptrarray
+  },
+  {
+    "vector",
+    sizeof (PointerVector),
+    create_vector,
+    free_vector,
+    reserve_vector,
+    get_vector,
+    append_vector,
+    insert_vector
+  },
+  {
+    "preallocated-vector",
+    sizeof (PreallocVector),
+    create_prealloc,
+    free_prealloc,
+    reserve_prealloc,
+    get_prealloc,
+    append_prealloc,
+    insert_prealloc
+  }
+};
+
+static void
+run_test (void (* test_func) (const Array *klass, guint random, gsize size, gsize max_size))
+{
+  int max_size = 4;
+  int size;
+  int i;
+  guint random = g_random_int ();
+
+  for (i = 0; i < G_N_ELEMENTS (all_arrays); i++)
+    {
+      for (size = 1; size <= max_size; size++)
+        {
+          test_func (&all_arrays[i], random, size, max_size);
+        }
+    }
+}
+
+int
+main (int argc, char *argv[])
+{
+  gtk_test_init (&argc, &argv);
+
+  g_print ("\"test\",\"model\",\"model size\",\"time\"\n");
+  run_test (do_random_access);
+  run_test (do_linear_access);
+  run_test (do_append);
+  run_test (do_insert);
+  run_test (do_create);
+
+  return g_test_run ();
+}

testsuite/gtk/vector.c

@@ -0,0 +1,105 @@
+/*
+ * 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"
+
+#define GTK_VECTOR_ELEMENT_TYPE int
+#define GTK_VECTOR_NAME null_int_vector
+#define GTK_VECTOR_TYPE_NAME NullIntVector
+#define GTK_VECTOR_NULL_TERMINATED 1
+#include "vectorimpl.c"
+
+#define GTK_VECTOR_ELEMENT_TYPE int
+#define GTK_VECTOR_NAME null_pre_int_vector
+#define GTK_VECTOR_TYPE_NAME NullPreIntVector
+#define GTK_VECTOR_PREALLOC 100
+#define GTK_VECTOR_NULL_TERMINATED 1
+#include "vectorimpl.c"
+
+#define GTK_VECTOR_ELEMENT_TYPE int
+#define GTK_VECTOR_NAME null_free_int_vector
+#define GTK_VECTOR_TYPE_NAME NullFreeIntVector
+#define GTK_VECTOR_FREE_FUNC int_free_func
+#define GTK_VECTOR_NULL_TERMINATED 1
+#include "vectorimpl.c"
+
+#define GTK_VECTOR_ELEMENT_TYPE int
+#define GTK_VECTOR_NAME null_pre_free_int_vector
+#define GTK_VECTOR_TYPE_NAME NullPreFreeIntVector
+#define GTK_VECTOR_PREALLOC 100
+#define GTK_VECTOR_FREE_FUNC int_free_func
+#define GTK_VECTOR_NULL_TERMINATED 1
+#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/null/simple", null_int_vector_test_simple);
+  g_test_add_func ("/intvector/null/prealloc/simple", null_pre_int_vector_test_simple);
+  g_test_add_func ("/intvector/null/freefunc/simple", null_free_int_vector_test_simple);
+  g_test_add_func ("/intvector/null/prealloc/freefunc/simple", null_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);
+  g_test_add_func ("/intvector/null/splice", null_int_vector_test_splice);
+  g_test_add_func ("/intvector/null/prealloc/splice", null_pre_int_vector_test_splice);
+  g_test_add_func ("/intvector/null/freefunc/splice", null_free_int_vector_test_splice);
+  g_test_add_func ("/intvector/null/prealloc/freefunc/splice", null_pre_free_int_vector_test_splice);
+
+  return g_test_run ();
+}

testsuite/gtk/vectorimpl.c

@@ -0,0 +1,117 @@
+/*
+ * 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);
+#ifdef GTK_VECTOR_NULL_TERMINATED
+      g_assert_cmpint (*gtk_vector(index) (&v, gtk_vector(get_size) (&v)), ==, 0);
+#endif
+    }
+  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));
+#ifdef GTK_VECTOR_NULL_TERMINATED
+      if (gtk_vector(get_size) (&v))
+        g_assert_cmpint (*gtk_vector(index) (&v, gtk_vector(get_size) (&v)), ==, 0);
+#endif
+      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_REAL_SIZE
+
+#undef GTK_VECTOR_ELEMENT_TYPE
+#undef GTK_VECTOR_NAME
+#undef GTK_VECTOR_TYPE_NAME
+#undef GTK_VECTOR_PREALLOC
+#undef GTK_VECTOR_NULL_TERMINATED
+