[glib/th/g-ptr-array-set-null-terminated: 1151/1151] array: add support for %NULL termination in GPtrArray

[Thomas Haller <thaller src gnome org>]

commit 25b56dc3c18b7dadff46dcaae63e22add7d28616
Author: Thomas Haller <thaller redhat com>
Date:   Wed May 6 19:35:37 2020 +0200

    array: add support for %NULL termination in GPtrArray
    
    GArray supports a "zero_terminated" flag, but GPtrArray doesn't.
    This is odd, because especially for a pointer array it makes sense
    to have a %NULL sentinel. This would be for example useful to track
    or construct a strv array with a GPtrArray.
    
    As workaround for this missing feature you could use a GArray instead
    (ugly) or to explicitly add the %NULL element. However the latter increases
    the "len" of the array, which can be problematic if you want to still use
    the GPtrArray for other purposes.
    
    Add API for marking a GPtrArray as %NULL terminated. In that case, the
    API will ensure that there is always a valid %NULL sentinel after the
    array. Note that the API does not enforce that a %NULL terminated API
    actually has any data allocated. That means, even with a %NULL terminated
    array, pdata can still be %NULL (only if len is zero).
    
    Add g_ptr_array_new_null_terminated() constructor. The null-terminated flag
    cannot be cleared. Once the GPtrArray is flagged to be %NULL terminated, it
    sticks. The purpose is that once a user checks whether a GPtrArray instance
    is safe to be treated as a %NULL terminated array, the decision does
    not need to be re-evaluated.
    
    Also add a g_ptr_array_is_null_terminated(). That is useful because it
    allows you to check whether a GPtrArray created by somebody else is safe
    to use as a %NULL terminated array. Since there is no API to make an
    array not %NULL terminated anymore, this is not error prone.
    
    The new flag is tracked as a guint8 in GRealPtrArray. On common 64 bit
    architectures this does not increase the size of the struct as it fits
    in an existing hole. Note that this is not a bitfield because it's
    probably more efficient to access the entire guint8. However, there is
    still a 3 bytes hole (on common 32 and 64 architectures), so if we need
    to add more flags in the future, we still have space for 24 bits,
    despite the new flag not being a bitfield.
    
    The biggest downside of the patch is the runtime overhead that most
    operations now need to check whether %NULL termination is requested.
    
    https://gitlab.gnome.org/GNOME/glib/-/issues/353

 docs/reference/glib/glib-sections.txt |   2 +
 glib/garray.c                         | 175 ++++++++++++++++++++++++++++------
 glib/garray.h                         |   7 ++
 glib/tests/array-test.c               |  64 +++++++++++--
 4 files changed, 213 insertions(+), 35 deletions(-)
---
diff --git a/docs/reference/glib/glib-sections.txt b/docs/reference/glib/glib-sections.txt
index eed764893..3a7e3428a 100644
--- a/docs/reference/glib/glib-sections.txt
+++ b/docs/reference/glib/glib-sections.txt
@@ -2928,7 +2928,9 @@ g_ptr_array_sized_new
 g_ptr_array_new_with_free_func
 g_ptr_array_copy
 g_ptr_array_new_full
+g_ptr_array_new_null_terminated
 g_ptr_array_set_free_func
+g_ptr_array_is_null_terminated
 g_ptr_array_ref
 g_ptr_array_unref
 g_ptr_array_add
diff --git a/glib/garray.c b/glib/garray.c
index de720210c..8f4259288 100644
--- a/glib/garray.c
+++ b/glib/garray.c
@@ -1058,6 +1058,7 @@ struct _GRealPtrArray
   guint           len;
   guint           alloc;
   gatomicrefcount ref_count;
+  guint8          null_terminated; /* always either 0 or 1, so it can be added to array lengths */
   GDestroyNotify  element_free_func;
 };
 
@@ -1077,9 +1078,17 @@ struct _GRealPtrArray
 static void g_ptr_array_maybe_expand (GRealPtrArray *array,
                                       guint          len);
 
+static void
+ptr_array_null_terminate (GRealPtrArray *rarray)
+{
+  if (G_UNLIKELY (rarray->null_terminated))
+    rarray->pdata[rarray->len] = NULL;
+}
+
 static GPtrArray *
 ptr_array_new (guint reserved_size,
-               GDestroyNotify element_free_func)
+               GDestroyNotify element_free_func,
+               gboolean null_terminated)
 {
   GRealPtrArray *array;
 
@@ -1088,12 +1097,25 @@ ptr_array_new (guint reserved_size,
   array->pdata = NULL;
   array->len = 0;
   array->alloc = 0;
+  array->null_terminated = (!!null_terminated);
   array->element_free_func = element_free_func;
 
   g_atomic_ref_count_init (&array->ref_count);
 
   if (reserved_size != 0)
-    g_ptr_array_maybe_expand (array, reserved_size);
+    {
+      if (G_LIKELY (reserved_size < G_MAXUINT) &&
+          null_terminated)
+        reserved_size++;
+      g_ptr_array_maybe_expand (array, reserved_size);
+      if (null_terminated)
+        {
+          /* don't use ptr_array_null_terminate(). It helps the compiler
+           * to see when @null_terminated is false and thereby inline
+           * ptr_array_new() and possibly remove the code entirely. */
+          array->pdata[0] = NULL;
+        }
+    }
 
   return (GPtrArray *) array;
 }
@@ -1108,7 +1130,7 @@ ptr_array_new (guint reserved_size,
 GPtrArray*
 g_ptr_array_new (void)
 {
-  return ptr_array_new (0, NULL);
+  return ptr_array_new (0, NULL, FALSE);
 }
 
 /**
@@ -1202,7 +1224,8 @@ g_ptr_array_steal (GPtrArray *array,
  * pointing to) are copied to the new #GPtrArray.
  *
  * The copy of @array will have the same #GDestroyNotify for its elements as
- * @array.
+ * @array. The copy will also be %NULL terminated if (and only if) the source
+ * array is.
  *
  * Returns: (transfer full): a deep copy of the initial #GPtrArray.
  *
@@ -1213,27 +1236,39 @@ g_ptr_array_copy (GPtrArray *array,
                   GCopyFunc  func,
                   gpointer   user_data)
 {
+  GRealPtrArray *rarray = (GRealPtrArray *) array;
   GPtrArray *new_array;
 
   g_return_val_if_fail (array != NULL, NULL);
 
-  new_array = ptr_array_new (array->len,
-                             ((GRealPtrArray *) array)->element_free_func);
+  new_array = ptr_array_new (0,
+                             rarray->element_free_func,
+                             rarray->null_terminated);
 
-  if (func != NULL)
+  if (rarray->alloc > 0)
     {
-      guint i;
+      g_ptr_array_maybe_expand ((GRealPtrArray *) new_array, array->len + rarray->null_terminated);
 
-      for (i = 0; i < array->len; i++)
-        new_array->pdata[i] = func (array->pdata[i], user_data);
-    }
-  else if (array->len > 0)
-    {
-      memcpy (new_array->pdata, array->pdata,
-              array->len * sizeof (*array->pdata));
-    }
+      if (array->len > 0)
+        {
+          if (func != NULL)
+            {
+              guint i;
 
-  new_array->len = array->len;
+              for (i = 0; i < array->len; i++)
+                new_array->pdata[i] = func (array->pdata[i], user_data);
+            }
+          else
+            {
+              memcpy (new_array->pdata, array->pdata,
+                      array->len * sizeof (*array->pdata));
+            }
+
+          new_array->len = array->len;
+        }
+
+      ptr_array_null_terminate (rarray);
+    }
 
   return new_array;
 }
@@ -1252,7 +1287,7 @@ g_ptr_array_copy (GPtrArray *array,
 GPtrArray*
 g_ptr_array_sized_new (guint reserved_size)
 {
-  return ptr_array_new (reserved_size, NULL);
+  return ptr_array_new (reserved_size, NULL, FALSE);
 }
 
 /**
@@ -1303,7 +1338,7 @@ g_array_copy (GArray *array)
 GPtrArray*
 g_ptr_array_new_with_free_func (GDestroyNotify element_free_func)
 {
-  return ptr_array_new (0, element_free_func);
+  return ptr_array_new (0, element_free_func, FALSE);
 }
 
 /**
@@ -1328,7 +1363,42 @@ GPtrArray*
 g_ptr_array_new_full (guint          reserved_size,
                       GDestroyNotify element_free_func)
 {
-  return ptr_array_new (reserved_size, element_free_func);
+  return ptr_array_new (reserved_size, element_free_func, FALSE);
+}
+
+/**
+ * g_ptr_array_new_null_terminated:
+ * @reserved_size: number of pointers preallocated.
+ *     If @null_terminated is %TRUE, the actually allocated
+ *     buffer size is @reserved_size plus 1, unless @reserved_size
+ *     is zero, in which case no initial buffers gets allocated.
+ * @element_free_func: (nullable): A function to free elements with
+ *     destroy @array or %NULL
+ * @null_terminated: whether to make the array as %NULL terminated.
+ *
+ * Like g_ptr_array_new_full() but also allows to set the array to
+ * be %NULL terminated.
+ *
+ * #GPtrArray created by other constructors are not %NULL terminated.
+ *
+ * Note that if the @array's length is zero and currently no
+ * data array is allocated, then pdata will still be %NULL.
+ * %GPtrArray will only %NULL terminate pdata, if an actual
+ * array is allocated. It does not guarantee that an array
+ * is always allocated. In other words, if the length is zero,
+ * then pdata may either point to a %NULL terminated array of length
+ * zero or be %NULL.
+ *
+ * Returns: A new #GPtrArray
+ *
+ * Since: 2.68
+ */
+GPtrArray*
+g_ptr_array_new_null_terminated (guint          reserved_size,
+                                 GDestroyNotify element_free_func,
+                                 gboolean       null_terminated)
+{
+  return ptr_array_new (reserved_size, element_free_func, null_terminated);
 }
 
 /**
@@ -1354,6 +1424,22 @@ g_ptr_array_set_free_func (GPtrArray      *array,
   rarray->element_free_func = element_free_func;
 }
 
+/**
+ * g_ptr_array_is_null_terminated:
+ * @array: the #GPtrArray
+ *
+ * Returns: %TRUE if the array is made to be %NULL terminated.
+ *
+ * Since: 2.68
+ */
+gboolean
+g_ptr_array_is_null_terminated (GPtrArray *array)
+{
+  g_return_val_if_fail (array, FALSE);
+
+  return ((GRealPtrArray *) array)->null_terminated;
+}
+
 /**
  * g_ptr_array_ref:
  * @array: a #GPtrArray
@@ -1417,6 +1503,10 @@ g_ptr_array_unref (GPtrArray *array)
  * be freed separately if @free_seg is %TRUE and no #GDestroyNotify
  * function has been set for @array.
  *
+ * Note that if the array is %NULL terminated and @free_seg is %FALSE
+ * and the pdata is %NULL (and the length is zero), the this function
+ * will return %NULL too and not allocate an empty %NULL terminated buffer.
+ *
  * This function is not thread-safe. If using a #GPtrArray from multiple
  * threads, use only the atomic g_ptr_array_ref() and g_ptr_array_unref()
  * functions.
@@ -1499,6 +1589,7 @@ g_ptr_array_maybe_expand (GRealPtrArray *array,
   if ((array->len + len) > array->alloc)
     {
       guint old_alloc = array->alloc;
+
       array->alloc = g_nearest_pow (array->len + len);
       array->alloc = MAX (array->alloc, MIN_ARRAY_SIZE);
       array->pdata = g_realloc (array->pdata, sizeof (gpointer) * array->alloc);
@@ -1534,7 +1625,13 @@ g_ptr_array_set_size  (GPtrArray *array,
   if (length_unsigned > rarray->len)
     {
       guint i;
-      g_ptr_array_maybe_expand (rarray, (length_unsigned - rarray->len));
+
+      if (G_UNLIKELY (rarray->null_terminated) &&
+          length_unsigned - rarray->len > G_MAXUINT - 1)
+         g_error ("array would overflow");
+
+      g_ptr_array_maybe_expand (rarray, (length_unsigned - rarray->len) + rarray->null_terminated);
+
       /* This is not 
        *     memset (array->pdata + array->len, 0,
        *            sizeof (gpointer) * (length_unsigned - array->len));
@@ -1543,11 +1640,13 @@ g_ptr_array_set_size  (GPtrArray *array,
        */
       for (i = rarray->len; i < length_unsigned; i++)
         rarray->pdata[i] = NULL;
+
+      rarray->len = length_unsigned;
+
+      ptr_array_null_terminate (rarray);
     }
   else if (length_unsigned < rarray->len)
     g_ptr_array_remove_range (array, length_unsigned, rarray->len - length_unsigned);
-
-  rarray->len = length_unsigned;
 }
 
 static gpointer
@@ -1577,7 +1676,8 @@ ptr_array_remove_index (GPtrArray *array,
 
   rarray->len -= 1;
 
-  if (G_UNLIKELY (g_mem_gc_friendly))
+  if (G_UNLIKELY (g_mem_gc_friendly) ||
+      rarray->null_terminated)
     rarray->pdata[rarray->len] = NULL;
 
   return result;
@@ -1693,6 +1793,10 @@ g_ptr_array_remove_range (GPtrArray *array,
   g_return_val_if_fail (rarray != NULL, NULL);
   g_return_val_if_fail (rarray->len == 0 || (rarray->len != 0 && rarray->pdata != NULL), NULL);
   g_return_val_if_fail (index_ <= rarray->len, NULL);
+
+  if (length == 0)
+    return array;
+
   g_return_val_if_fail (index_ + length <= rarray->len, NULL);
 
   if (rarray->element_free_func != NULL)
@@ -1714,6 +1818,8 @@ g_ptr_array_remove_range (GPtrArray *array,
       for (i = 0; i < length; i++)
         rarray->pdata[rarray->len + i] = NULL;
     }
+  else
+    ptr_array_null_terminate (rarray);
 
   return array;
 }
@@ -1810,9 +1916,11 @@ g_ptr_array_add (GPtrArray *array,
   g_return_if_fail (rarray);
   g_return_if_fail (rarray->len == 0 || (rarray->len != 0 && rarray->pdata != NULL));
 
-  g_ptr_array_maybe_expand (rarray, 1);
+  g_ptr_array_maybe_expand (rarray, 1u + rarray->null_terminated);
 
   rarray->pdata[rarray->len++] = data;
+
+  ptr_array_null_terminate (rarray);
 }
 
 /**
@@ -1848,7 +1956,14 @@ g_ptr_array_extend (GPtrArray  *array_to_extend,
   g_return_if_fail (array_to_extend != NULL);
   g_return_if_fail (array != NULL);
 
-  g_ptr_array_maybe_expand (rarray_to_extend, array->len);
+  if (array->len == 0u)
+    return;
+
+  if (G_UNLIKELY (array->len == G_MAXUINT) &&
+      rarray_to_extend->null_terminated)
+    g_error ("adding %u to array would overflow", array->len);
+
+  g_ptr_array_maybe_expand (rarray_to_extend, array->len + rarray_to_extend->null_terminated);
 
   if (func != NULL)
     {
@@ -1858,13 +1973,15 @@ g_ptr_array_extend (GPtrArray  *array_to_extend,
         rarray_to_extend->pdata[i + rarray_to_extend->len] =
           func (array->pdata[i], user_data);
     }
-  else if (array->len > 0)
+  else
     {
       memcpy (rarray_to_extend->pdata + rarray_to_extend->len, array->pdata,
               array->len * sizeof (*array->pdata));
     }
 
   rarray_to_extend->len += array->len;
+
+  ptr_array_null_terminate (rarray_to_extend);
 }
 
 /**
@@ -1922,7 +2039,7 @@ g_ptr_array_insert (GPtrArray *array,
   g_return_if_fail (index_ >= -1);
   g_return_if_fail (index_ <= (gint)rarray->len);
 
-  g_ptr_array_maybe_expand (rarray, 1);
+  g_ptr_array_maybe_expand (rarray, 1u + rarray->null_terminated);
 
   if (index_ < 0)
     index_ = rarray->len;
@@ -1934,6 +2051,8 @@ g_ptr_array_insert (GPtrArray *array,
 
   rarray->len++;
   rarray->pdata[index_] = data;
+
+  ptr_array_null_terminate (rarray);
 }
 
 /* Please keep this doc-comment in sync with pointer_array_sort_example()
diff --git a/glib/garray.h b/glib/garray.h
index 67131b5b3..b8a63a79d 100644
--- a/glib/garray.h
+++ b/glib/garray.h
@@ -152,6 +152,10 @@ GPtrArray* g_ptr_array_sized_new          (guint             reserved_size);
 GLIB_AVAILABLE_IN_ALL
 GPtrArray* g_ptr_array_new_full           (guint             reserved_size,
                                           GDestroyNotify    element_free_func);
+GLIB_AVAILABLE_IN_2_68
+GPtrArray* g_ptr_array_new_null_terminated (guint          reserved_size,
+                                            GDestroyNotify element_free_func,
+                                            gboolean       null_terminated);
 GLIB_AVAILABLE_IN_ALL
 gpointer*  g_ptr_array_free               (GPtrArray        *array,
                                           gboolean          free_seg);
@@ -223,6 +227,9 @@ gboolean   g_ptr_array_find_with_equal_func (GPtrArray     *haystack,
                                              GEqualFunc     equal_func,
                                              guint         *index_);
 
+GLIB_AVAILABLE_IN_2_68
+gboolean g_ptr_array_is_null_terminated (GPtrArray *array);
+
 
 /* Byte arrays, an array of guint8.  Implemented as a GArray,
  * but type-safe.
diff --git a/glib/tests/array-test.c b/glib/tests/array-test.c
index adedfc19f..5214cf0b9 100644
--- a/glib/tests/array-test.c
+++ b/glib/tests/array-test.c
@@ -845,6 +845,23 @@ test_array_copy_sized (void)
   g_array_unref (array1);
 }
 
+#define _assert_ptr_array_null_terminated(array, null_terminated) \
+  G_STMT_START \
+    { \
+      GPtrArray *const _array = (array); \
+      const gboolean _null_terminated = (null_terminated); \
+      \
+      g_assert_cmpint(_null_terminated, ==, g_ptr_array_is_null_terminated(_array)); \
+      if (_array->pdata) \
+        { \
+          if (_null_terminated) \
+            g_assert (!_array->pdata[_array->len]); \
+        } \
+      else \
+        g_assert_cmpint (_array->len, ==, 0); \
+    } \
+  G_STMT_END
+
 /* Check g_ptr_array_steal() function */
 static void
 pointer_array_steal (void)
@@ -936,16 +953,26 @@ pointer_array_insert (void)
 }
 
 static void
-pointer_array_ref_count (void)
+pointer_array_ref_count (gconstpointer test_data)
 {
+  const gboolean NULL_TERMINATED = GPOINTER_TO_INT(test_data);
   GPtrArray *gparray;
   GPtrArray *gparray2;
   gint i;
   gint sum = 0;
 
-  gparray = g_ptr_array_new ();
+  if (NULL_TERMINATED || (g_test_rand_int () % 2))
+    gparray = g_ptr_array_new_null_terminated (0, NULL, NULL_TERMINATED);
+  else
+    gparray = g_ptr_array_new ();
+
+  _assert_ptr_array_null_terminated(gparray, NULL_TERMINATED);
+
   for (i = 0; i < 10000; i++)
-    g_ptr_array_add (gparray, GINT_TO_POINTER (i));
+    {
+      g_ptr_array_add (gparray, GINT_TO_POINTER (i));
+      _assert_ptr_array_null_terminated(gparray, NULL_TERMINATED);
+    }
 
   /* check we can ref, unref and still access the array */
   gparray2 = g_ptr_array_ref (gparray);
@@ -954,6 +981,8 @@ pointer_array_ref_count (void)
   for (i = 0; i < 10000; i++)
     g_assert (g_ptr_array_index (gparray, i) == GINT_TO_POINTER (i));
 
+  _assert_ptr_array_null_terminated(gparray, NULL_TERMINATED);
+
   g_ptr_array_foreach (gparray, sum_up, &sum);
   g_assert (sum == 49995000);
 
@@ -962,6 +991,8 @@ pointer_array_ref_count (void)
   g_ptr_array_free (gparray, TRUE);
 
   g_assert_cmpint (gparray2->len, ==, 0);
+  _assert_ptr_array_null_terminated(gparray, NULL_TERMINATED);
+
   g_ptr_array_unref (gparray2);
 }
 
@@ -1600,19 +1631,32 @@ steal_destroy_notify (gpointer data)
 /* Test that g_ptr_array_steal_index() and g_ptr_array_steal_index_fast() can
  * remove elements from a pointer array without the #GDestroyNotify being called. */
 static void
-pointer_array_steal_index (void)
+pointer_array_steal_index (gconstpointer test_data)
 {
+  const gboolean NULL_TERMINATED = GPOINTER_TO_INT(test_data);
   guint i1 = 0, i2 = 0, i3 = 0, i4 = 0;
   gpointer out1, out2;
-  GPtrArray *array = g_ptr_array_new_with_free_func (steal_destroy_notify);
+  GPtrArray *array;
+
+  if (NULL_TERMINATED || (g_test_rand_int () % 2))
+    array = g_ptr_array_new_null_terminated (0, steal_destroy_notify, NULL_TERMINATED);
+  else
+    array = g_ptr_array_new_with_free_func (steal_destroy_notify);
+
+  _assert_ptr_array_null_terminated(array, NULL_TERMINATED);
 
   g_ptr_array_add (array, &i1);
   g_ptr_array_add (array, &i2);
+
+  _assert_ptr_array_null_terminated(array, NULL_TERMINATED);
+
   g_ptr_array_add (array, &i3);
   g_ptr_array_add (array, &i4);
 
   g_assert_cmpuint (array->len, ==, 4);
 
+  _assert_ptr_array_null_terminated(array, NULL_TERMINATED);
+
   /* Remove a single element. */
   out1 = g_ptr_array_steal_index (array, 0);
   g_assert_true (out1 == &i1);
@@ -1624,6 +1668,8 @@ pointer_array_steal_index (void)
   g_assert_true (g_ptr_array_index (array, 1) == &i3);
   g_assert_true (g_ptr_array_index (array, 2) == &i4);
 
+  _assert_ptr_array_null_terminated(array, NULL_TERMINATED);
+
   /* Remove another element, quickly. */
   out2 = g_ptr_array_steal_index_fast (array, 0);
   g_assert_true (out2 == &i2);
@@ -1634,6 +1680,8 @@ pointer_array_steal_index (void)
   g_assert_true (g_ptr_array_index (array, 0) == &i4);
   g_assert_true (g_ptr_array_index (array, 1) == &i3);
 
+  _assert_ptr_array_null_terminated(array, NULL_TERMINATED);
+
   /* Check that destroying the pointer array doesn’t affect the stolen elements. */
   g_ptr_array_unref (array);
 
@@ -2020,7 +2068,8 @@ main (int argc, char *argv[])
   /* pointer arrays */
   g_test_add_func ("/pointerarray/add", pointer_array_add);
   g_test_add_func ("/pointerarray/insert", pointer_array_insert);
-  g_test_add_func ("/pointerarray/ref-count", pointer_array_ref_count);
+  g_test_add_data_func ("/pointerarray/ref-count/0", GINT_TO_POINTER (0), pointer_array_ref_count);
+  g_test_add_data_func ("/pointerarray/ref-count/1", GINT_TO_POINTER (1), pointer_array_ref_count);
   g_test_add_func ("/pointerarray/free-func", pointer_array_free_func);
   g_test_add_func ("/pointerarray/array_copy", pointer_array_copy);
   g_test_add_func ("/pointerarray/array_extend", pointer_array_extend);
@@ -2032,7 +2081,8 @@ main (int argc, char *argv[])
   g_test_add_func ("/pointerarray/find/empty", pointer_array_find_empty);
   g_test_add_func ("/pointerarray/find/non-empty", pointer_array_find_non_empty);
   g_test_add_func ("/pointerarray/steal", pointer_array_steal);
-  g_test_add_func ("/pointerarray/steal_index", pointer_array_steal_index);
+  g_test_add_data_func ("/pointerarray/steal_index/0", GINT_TO_POINTER (0), pointer_array_steal_index);
+  g_test_add_data_func ("/pointerarray/steal_index/1", GINT_TO_POINTER (1), pointer_array_steal_index);
 
   /* byte arrays */
   g_test_add_func ("/bytearray/steal", byte_array_steal);