Add internal facility for dynamic array handling

This is intended as a type-safe alternative to obstacks and
hand-written realloc constructs.  The implementation avoids
writing function pointers to the heap.

1 files changed, 517 insertions, 0 deletions

diff --git a/malloc/tst-dynarray.c b/malloc/tst-dynarray.c
new file mode 100644
index 0000000000..7aee85aa39
--- /dev/null
+++ b/malloc/tst-dynarray.c
@@ -0,0 +1,517 @@
+/* Test for dynamic arrays.
+   Copyright (C) 2017 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C 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.
+
+   The GNU C 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 the GNU C Library; if not, see
+   <http://www.gnu.org/licenses/>.  */
+
+#include "tst-dynarray-shared.h"
+
+#define DYNARRAY_STRUCT dynarray_long
+#define DYNARRAY_ELEMENT long
+#define DYNARRAY_PREFIX dynarray_long_
+#define DYNARRAY_ELEMENT_INIT(e) (*(e) = 17)
+#include <malloc/dynarray-skeleton.c>
+
+struct long_array
+{
+  long *array;
+  size_t length;
+};
+
+#define DYNARRAY_STRUCT dynarray_long_noscratch
+#define DYNARRAY_ELEMENT long
+#define DYNARRAY_PREFIX dynarray_long_noscratch_
+#define DYNARRAY_ELEMENT_INIT(e) (*(e) = 23)
+#define DYNARRAY_FINAL_TYPE struct long_array
+#define DYNARRAY_INITIAL_SIZE 0
+#include <malloc/dynarray-skeleton.c>
+
+#define DYNARRAY_STRUCT zstr
+#define DYNARRAY_ELEMENT char
+#define DYNARRAY_PREFIX zstr_
+#define DYNARRAY_INITIAL_SIZE 128
+#include <malloc/dynarray-skeleton.c>
+
+#include <malloc.h>
+#include <mcheck.h>
+#include <stdint.h>
+#include <support/check.h>
+#include <support/support.h>
+
+enum { max_count = 20 };
+
+/* Test dynamic arrays with int elements (no automatic deallocation
+   for elements).  */
+static void
+test_int (void)
+{
+  /* Empty array.  */
+  {
+    struct dynarray_int dyn;
+    dynarray_int_init (&dyn);
+    CHECK_EMPTY (int, &dyn);
+  }
+
+  /* Empty array with finalization.  */
+  {
+    struct dynarray_int dyn;
+    dynarray_int_init (&dyn);
+    CHECK_INIT_STATE (int, &dyn);
+    struct int_array result = { (int *) (uintptr_t) -1, -1 };
+    TEST_VERIFY_EXIT (dynarray_int_finalize (&dyn, &result));
+    CHECK_INIT_STATE (int, &dyn);
+    TEST_VERIFY_EXIT (result.array == NULL);
+    TEST_VERIFY_EXIT (result.length == 0);
+  }
+
+  /* Non-empty array tests.
+
+     do_add: Switch between emplace (false) and add (true).
+     do_finalize: Perform finalize call at the end.
+     do_clear: Perform clear call at the end.
+     do_remove_last: Perform remove_last call after adding elements.
+     count: Number of elements added to the array.  */
+  for (int do_add = 0; do_add < 2; ++do_add)
+    for (int do_finalize = 0; do_finalize < 2; ++do_finalize)
+      for (int do_clear = 0; do_clear < 2; ++do_clear)
+        for (int do_remove_last = 0; do_remove_last < 2; ++do_remove_last)
+          for (unsigned int count = 0; count < max_count; ++count)
+            {
+              if (do_remove_last && count == 0)
+                continue;
+              unsigned int base = count * count;
+              struct dynarray_int dyn;
+              dynarray_int_init (&dyn);
+              for (unsigned int i = 0; i < count; ++i)
+                {
+                  if (do_add)
+                    dynarray_int_add (&dyn, base + i);
+                  else
+                    {
+                      int *place = dynarray_int_emplace (&dyn);
+                      TEST_VERIFY_EXIT (place != NULL);
+                      *place = base + i;
+                    }
+                  TEST_VERIFY_EXIT (!dynarray_int_has_failed (&dyn));
+                  TEST_VERIFY_EXIT (dynarray_int_size (&dyn) == i + 1);
+                  TEST_VERIFY_EXIT (dynarray_int_size (&dyn)
+                                    <= dyn.dynarray_header.allocated);
+                }
+              TEST_VERIFY_EXIT (dynarray_int_size (&dyn) == count);
+              TEST_VERIFY_EXIT (count <= dyn.dynarray_header.allocated);
+              unsigned final_count;
+              bool heap_array = dyn.dynarray_header.array != dyn.scratch;
+              if (do_remove_last)
+                {
+                  dynarray_int_remove_last (&dyn);
+                  if (count == 0)
+                    final_count = 0;
+                  else
+                    final_count = count - 1;
+                }
+              else
+                final_count = count;
+              if (do_clear)
+                {
+                  dynarray_int_clear (&dyn);
+                  final_count = 0;
+                }
+              TEST_VERIFY_EXIT (!dynarray_int_has_failed (&dyn));
+              TEST_VERIFY_EXIT ((dyn.dynarray_header.array != dyn.scratch)
+                                == heap_array);
+              TEST_VERIFY_EXIT (dynarray_int_size (&dyn) == final_count);
+              TEST_VERIFY_EXIT (dyn.dynarray_header.allocated >= final_count);
+              if (!do_clear)
+                for (unsigned int i = 0; i < final_count; ++i)
+                  TEST_VERIFY_EXIT (*dynarray_int_at (&dyn, i) == base + i);
+              if (do_finalize)
+                {
+                  struct int_array result = { (int *) (uintptr_t) -1, -1 };
+                  TEST_VERIFY_EXIT (dynarray_int_finalize (&dyn, &result));
+                  CHECK_INIT_STATE (int, &dyn);
+                  TEST_VERIFY_EXIT (result.length == final_count);
+                  if (final_count == 0)
+                    TEST_VERIFY_EXIT (result.array == NULL);
+                  else
+                    {
+                      TEST_VERIFY_EXIT (result.array != NULL);
+                      TEST_VERIFY_EXIT (result.array != (int *) (uintptr_t) -1);
+                      TEST_VERIFY_EXIT
+                        (malloc_usable_size (result.array)
+                         >= final_count * sizeof (result.array[0]));
+                      for (unsigned int i = 0; i < final_count; ++i)
+                        TEST_VERIFY_EXIT (result.array[i] == base + i);
+                      free (result.array);
+                    }
+                }
+              else /* !do_finalize */
+                {
+                  dynarray_int_free (&dyn);
+                  CHECK_INIT_STATE (int, &dyn);
+                }
+            }
+}
+
+/* Test dynamic arrays with char * elements (with automatic
+   deallocation of the pointed-to strings).  */
+static void
+test_str (void)
+{
+  /* Empty array.  */
+  {
+    struct dynarray_str dyn;
+    dynarray_str_init (&dyn);
+    CHECK_EMPTY (str, &dyn);
+  }
+
+  /* Empty array with finalization.  */
+  {
+    struct dynarray_str dyn;
+    dynarray_str_init (&dyn);
+    TEST_VERIFY_EXIT (!dynarray_str_has_failed (&dyn));
+    struct str_array result = { (char **) (uintptr_t) -1, -1 };
+    TEST_VERIFY_EXIT (dynarray_str_finalize (&dyn, &result));
+    CHECK_INIT_STATE (str, &dyn);
+    TEST_VERIFY_EXIT (result.array == NULL);
+    TEST_VERIFY_EXIT (result.length == 0);
+  }
+
+  /* Non-empty array tests.
+
+     do_add: Switch between emplace (false) and add (true).
+     do_finalize: Perform finalize call at the end.
+     do_clear: Perform clear call at the end.
+     do_remove_last: Perform remove_last call after adding elements.
+     count: Number of elements added to the array.  */
+  for (int do_add = 0; do_add < 2; ++do_add)
+    for (int do_finalize = 0; do_finalize < 2; ++do_finalize)
+      for (int do_clear = 0; do_clear < 2; ++do_clear)
+        for (int do_remove_last = 0; do_remove_last < 2; ++do_remove_last)
+          for (unsigned int count = 0; count < max_count; ++count)
+            {
+              if (do_remove_last && count == 0)
+                continue;
+              unsigned int base = count * count;
+              struct dynarray_str dyn;
+              dynarray_str_init (&dyn);
+              for (unsigned int i = 0; i < count; ++i)
+                {
+                  char *item = xasprintf ("%d", base + i);
+                  if (do_add)
+                    dynarray_str_add (&dyn, item);
+                  else
+                    {
+                      char **place = dynarray_str_emplace (&dyn);
+                      TEST_VERIFY_EXIT (place != NULL);
+                      TEST_VERIFY_EXIT (*place == NULL);
+                      *place = item;
+                    }
+                  TEST_VERIFY_EXIT (!dynarray_str_has_failed (&dyn));
+                  TEST_VERIFY_EXIT (dynarray_str_size (&dyn) == i + 1);
+                  TEST_VERIFY_EXIT (dynarray_str_size (&dyn)
+                                    <= dyn.dynarray_header.allocated);
+                }
+              TEST_VERIFY_EXIT (dynarray_str_size (&dyn) == count);
+              TEST_VERIFY_EXIT (count <= dyn.dynarray_header.allocated);
+              unsigned final_count;
+              bool heap_array = dyn.dynarray_header.array != dyn.scratch;
+              if (do_remove_last)
+                {
+                  dynarray_str_remove_last (&dyn);
+                  if (count == 0)
+                    final_count = 0;
+                  else
+                    final_count = count - 1;
+                }
+              else
+                final_count = count;
+              if (do_clear)
+                {
+                  dynarray_str_clear (&dyn);
+                  final_count = 0;
+                }
+              TEST_VERIFY_EXIT (!dynarray_str_has_failed (&dyn));
+              TEST_VERIFY_EXIT ((dyn.dynarray_header.array != dyn.scratch)
+                                == heap_array);
+              TEST_VERIFY_EXIT (dynarray_str_size (&dyn) == final_count);
+              TEST_VERIFY_EXIT (dyn.dynarray_header.allocated >= final_count);
+              if (!do_clear)
+                for (unsigned int i = 0; i < count - do_remove_last; ++i)
+                  {
+                    char *expected = xasprintf ("%d", base + i);
+                    const char *actual = *dynarray_str_at (&dyn, i);
+                    TEST_VERIFY_EXIT (strcmp (actual, expected) == 0);
+                    free (expected);
+                  }
+              if (do_finalize)
+                {
+                  struct str_array result = { (char **) (uintptr_t) -1, -1 };
+                  TEST_VERIFY_EXIT (dynarray_str_finalize (&dyn, &result));
+                  CHECK_INIT_STATE (str, &dyn);
+                  TEST_VERIFY_EXIT (result.length == final_count);
+                  if (final_count == 0)
+                    TEST_VERIFY_EXIT (result.array == NULL);
+                  else
+                    {
+                      TEST_VERIFY_EXIT (result.array != NULL);
+                      TEST_VERIFY_EXIT (result.array
+                                        != (char **) (uintptr_t) -1);
+                      TEST_VERIFY_EXIT (result.length
+                                        == count - do_remove_last);
+                      TEST_VERIFY_EXIT
+                        (malloc_usable_size (result.array)
+                         >= final_count * sizeof (result.array[0]));
+                      for (unsigned int i = 0; i < count - do_remove_last; ++i)
+                        {
+                          char *expected = xasprintf ("%d", base + i);
+                          char *actual = result.array[i];
+                          TEST_VERIFY_EXIT (strcmp (actual, expected) == 0);
+                          free (expected);
+                          free (actual);
+                        }
+                      free (result.array);
+                    }
+                }
+              else /* !do_finalize */
+                {
+                  dynarray_str_free (&dyn);
+                  CHECK_INIT_STATE (str, &dyn);
+                }
+            }
+
+  /* Test resizing.  */
+  {
+    enum { count = 2131 };
+    struct dynarray_str dyn;
+    dynarray_str_init (&dyn);
+
+    /* From length 0 to length 1.  */
+    TEST_VERIFY (dynarray_str_resize (&dyn, 1));
+    TEST_VERIFY (dynarray_str_size (&dyn) == 1);
+    TEST_VERIFY (*dynarray_str_at (&dyn, 0) == NULL);
+    *dynarray_str_at (&dyn, 0) = xstrdup ("allocated");
+    dynarray_str_free (&dyn);
+
+    /* From length 0 to length 1 and 2.  */
+    TEST_VERIFY (dynarray_str_resize (&dyn, 1));
+    TEST_VERIFY (dynarray_str_size (&dyn) == 1);
+    TEST_VERIFY (*dynarray_str_at (&dyn, 0) == NULL);
+    *dynarray_str_at (&dyn, 0) = xstrdup ("allocated0");
+    TEST_VERIFY (dynarray_str_resize (&dyn, 2));
+    TEST_VERIFY (dynarray_str_size (&dyn) == 2);
+    TEST_VERIFY (strcmp (*dynarray_str_at (&dyn, 0), "allocated0") == 0);
+    TEST_VERIFY (*dynarray_str_at (&dyn, 1) == NULL);
+    *dynarray_str_at (&dyn, 1) = xstrdup ("allocated1");
+    TEST_VERIFY (dynarray_str_resize (&dyn, count));
+    TEST_VERIFY (dynarray_str_size (&dyn) == count);
+    TEST_VERIFY (strcmp (*dynarray_str_at (&dyn, 0), "allocated0") == 0);
+    TEST_VERIFY (strcmp (*dynarray_str_at (&dyn, 1), "allocated1") == 0);
+    for (int i = 2; i < count; ++i)
+      TEST_VERIFY (*dynarray_str_at (&dyn, i) == NULL);
+    *dynarray_str_at (&dyn, count - 1) = xstrdup ("allocated2");
+    TEST_VERIFY (dynarray_str_resize (&dyn, 3));
+    TEST_VERIFY (strcmp (*dynarray_str_at (&dyn, 0), "allocated0") == 0);
+    TEST_VERIFY (strcmp (*dynarray_str_at (&dyn, 1), "allocated1") == 0);
+    TEST_VERIFY (*dynarray_str_at (&dyn, 2) == NULL);
+    dynarray_str_free (&dyn);
+  }
+}
+
+/* Verify that DYNARRAY_ELEMENT_INIT has an effect.  */
+static void
+test_long_init (void)
+{
+  enum { count = 2131 };
+  {
+    struct dynarray_long dyn;
+    dynarray_long_init (&dyn);
+    for (int i = 0; i < count; ++i)
+      {
+        long *place = dynarray_long_emplace (&dyn);
+        TEST_VERIFY_EXIT (place != NULL);
+        TEST_VERIFY (*place == 17);
+      }
+    TEST_VERIFY (dynarray_long_size (&dyn) == count);
+    for (int i = 0; i < count; ++i)
+      TEST_VERIFY (*dynarray_long_at (&dyn, i) == 17);
+    dynarray_long_free (&dyn);
+
+    TEST_VERIFY (dynarray_long_resize (&dyn, 1));
+    TEST_VERIFY (dynarray_long_size (&dyn) == 1);
+    TEST_VERIFY (*dynarray_long_at (&dyn, 0) == 17);
+    *dynarray_long_at (&dyn, 0) = 18;
+    dynarray_long_free (&dyn);
+    TEST_VERIFY (dynarray_long_resize (&dyn, 1));
+    TEST_VERIFY (dynarray_long_size (&dyn) == 1);
+    TEST_VERIFY (*dynarray_long_at (&dyn, 0) == 17);
+    TEST_VERIFY (dynarray_long_resize (&dyn, 2));
+    TEST_VERIFY (dynarray_long_size (&dyn) == 2);
+    TEST_VERIFY (*dynarray_long_at (&dyn, 0) == 17);
+    TEST_VERIFY (*dynarray_long_at (&dyn, 1) == 17);
+    *dynarray_long_at (&dyn, 0) = 18;
+    TEST_VERIFY (dynarray_long_resize (&dyn, count));
+    TEST_VERIFY (dynarray_long_size (&dyn) == count);
+    TEST_VERIFY (*dynarray_long_at (&dyn, 0) == 18);
+    for (int i = 1; i < count; ++i)
+      TEST_VERIFY (*dynarray_long_at (&dyn, i) == 17);
+    dynarray_long_free (&dyn);
+  }
+
+  /* Similar, but without an on-stack scratch region
+     (DYNARRAY_INITIAL_SIZE is 0).  */
+  {
+    struct dynarray_long_noscratch dyn;
+    dynarray_long_noscratch_init (&dyn);
+    struct long_array result;
+    TEST_VERIFY_EXIT (dynarray_long_noscratch_finalize (&dyn, &result));
+    TEST_VERIFY (result.array == NULL);
+    TEST_VERIFY (result.length == 0);
+
+    /* Test with one element.  */
+    {
+      long *place = dynarray_long_noscratch_emplace (&dyn);
+      TEST_VERIFY_EXIT (place != NULL);
+      TEST_VERIFY (*place == 23);
+    }
+    TEST_VERIFY (dynarray_long_noscratch_size (&dyn) == 1);
+    TEST_VERIFY (*dynarray_long_noscratch_at (&dyn, 0) == 23);
+    TEST_VERIFY_EXIT (dynarray_long_noscratch_finalize (&dyn, &result));
+    TEST_VERIFY_EXIT (result.array != NULL);
+    TEST_VERIFY (result.length == 1);
+    TEST_VERIFY (result.array[0] == 23);
+    free (result.array);
+
+    for (int i = 0; i < count; ++i)
+      {
+        long *place = dynarray_long_noscratch_emplace (&dyn);
+        TEST_VERIFY_EXIT (place != NULL);
+        TEST_VERIFY (*place == 23);
+        if (i == 0)
+          *place = 29;
+      }
+    TEST_VERIFY (dynarray_long_noscratch_size (&dyn) == count);
+    TEST_VERIFY (*dynarray_long_noscratch_at (&dyn, 0) == 29);
+    for (int i = 1; i < count; ++i)
+      TEST_VERIFY (*dynarray_long_noscratch_at (&dyn, i) == 23);
+    TEST_VERIFY_EXIT (dynarray_long_noscratch_finalize (&dyn, &result));
+    TEST_VERIFY_EXIT (result.array != NULL);
+    TEST_VERIFY (result.length == count);
+    TEST_VERIFY (result.array[0] == 29);
+    for (int i = 1; i < count; ++i)
+      TEST_VERIFY (result.array[i] == 23);
+    free (result.array);
+
+    TEST_VERIFY (dynarray_long_noscratch_resize (&dyn, 1));
+    TEST_VERIFY (dynarray_long_noscratch_size (&dyn) == 1);
+    TEST_VERIFY (*dynarray_long_noscratch_at (&dyn, 0) == 23);
+    *dynarray_long_noscratch_at (&dyn, 0) = 24;
+    dynarray_long_noscratch_free (&dyn);
+    TEST_VERIFY (dynarray_long_noscratch_resize (&dyn, 1));
+    TEST_VERIFY (dynarray_long_noscratch_size (&dyn) == 1);
+    TEST_VERIFY (*dynarray_long_noscratch_at (&dyn, 0) == 23);
+    TEST_VERIFY (dynarray_long_noscratch_resize (&dyn, 2));
+    TEST_VERIFY (dynarray_long_noscratch_size (&dyn) == 2);
+    TEST_VERIFY (*dynarray_long_noscratch_at (&dyn, 0) == 23);
+    TEST_VERIFY (*dynarray_long_noscratch_at (&dyn, 1) == 23);
+    *dynarray_long_noscratch_at (&dyn, 0) = 24;
+    TEST_VERIFY (dynarray_long_noscratch_resize (&dyn, count));
+    TEST_VERIFY (dynarray_long_noscratch_size (&dyn) == count);
+    TEST_VERIFY (*dynarray_long_noscratch_at (&dyn, 0) == 24);
+    for (int i = 1; i < count; ++i)
+      TEST_VERIFY (*dynarray_long_noscratch_at (&dyn, i) == 23);
+    dynarray_long_noscratch_free (&dyn);
+  }
+}
+
+/* Test NUL-terminated string construction with the add function and
+   the simple finalize function.  */
+static void
+test_zstr (void)
+{
+  /* Totally empty string (no NUL termination).  */
+  {
+    struct zstr s;
+    zstr_init (&s);
+    char *result = zstr_finalize (&s, NULL);
+    TEST_VERIFY (result == NULL);
+    TEST_VERIFY (zstr_size (&s) == 0);
+    size_t length = 1;
+    result = zstr_finalize (&s, &length);
+    TEST_VERIFY (result == NULL);
+    TEST_VERIFY (length == 0);
+    TEST_VERIFY (zstr_size (&s) == 0);
+  }
+
+  /* Empty string.  */
+  {
+    struct zstr s;
+    zstr_init (&s);
+    zstr_add (&s, '\0');
+    char *result = zstr_finalize (&s, NULL);
+    TEST_VERIFY_EXIT (result != NULL);
+    TEST_VERIFY (*result == '\0');
+    TEST_VERIFY (zstr_size (&s) == 0);
+    free (result);
+
+    zstr_add (&s, '\0');
+    size_t length = 1;
+    result = zstr_finalize (&s, &length);
+    TEST_VERIFY_EXIT (result != NULL);
+    TEST_VERIFY (*result == '\0');
+    TEST_VERIFY (length == 1);
+    TEST_VERIFY (zstr_size (&s) == 0);
+    free (result);
+  }
+
+  /* A few characters.  */
+  {
+    struct zstr s;
+    zstr_init (&s);
+    zstr_add (&s, 'A');
+    zstr_add (&s, 'b');
+    zstr_add (&s, 'c');
+    zstr_add (&s, '\0');
+    char *result = zstr_finalize (&s, NULL);
+    TEST_VERIFY_EXIT (result != NULL);
+    TEST_VERIFY (strcmp (result, "Abc") == 0);
+    TEST_VERIFY (zstr_size (&s) == 0);
+    free (result);
+
+    zstr_add (&s, 'X');
+    zstr_add (&s, 'y');
+    zstr_add (&s, 'z');
+    zstr_add (&s, '\0');
+    size_t length = 1;
+    result = zstr_finalize (&s, &length);
+    TEST_VERIFY_EXIT (result != NULL);
+    TEST_VERIFY (strcmp (result, "Xyz") == 0);
+    TEST_VERIFY (length == 4);
+    TEST_VERIFY (zstr_size (&s) == 0);
+    free (result);
+  }
+}
+
+static int
+do_test (void)
+{
+  mtrace ();
+  test_int ();
+  test_str ();
+  test_long_init ();
+  test_zstr ();
+  return 0;
+}
+
+#include <support/test-driver.c>