[thirdparty/glibc.git] / malloc / tst-dynarray.c

/* Test for dynamic arrays.
   Copyright (C) 2017-2019 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
   <https://www.gnu.org/licenses/>.  */

#include "tst-dynarray-shared.h"

#include <errno.h>
#include <stdint.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);
              if (count > 0)
                {
                  TEST_VERIFY (dynarray_int_begin (&dyn)
                               == dynarray_int_at (&dyn, 0));
                  TEST_VERIFY (dynarray_int_end (&dyn)
                               == dynarray_int_at (&dyn, count - 1) + 1);
                }
              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 (final_count > 0)
                {
                  TEST_VERIFY (dynarray_int_begin (&dyn)
                               == dynarray_int_at (&dyn, 0));
                  TEST_VERIFY (dynarray_int_end (&dyn)
                               == dynarray_int_at (&dyn, final_count - 1) + 1);
                }
              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);
              if (count > 0)
                {
                  TEST_VERIFY (dynarray_str_begin (&dyn)
                               == dynarray_str_at (&dyn, 0));
                  TEST_VERIFY (dynarray_str_end (&dyn)
                               == dynarray_str_at (&dyn, count - 1) + 1);
                }
              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 (final_count > 0)
                {
                  TEST_VERIFY (dynarray_str_begin (&dyn)
                               == dynarray_str_at (&dyn, 0));
                  TEST_VERIFY (dynarray_str_end (&dyn)
                               == dynarray_str_at (&dyn, final_count - 1) + 1);
                }
              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 overflow in resize.  */
static void
test_long_overflow (void)
{
  {
    struct dynarray_long dyn;
    dynarray_long_init (&dyn);
    errno = EINVAL;
    TEST_VERIFY (!dynarray_long_resize
                 (&dyn, (SIZE_MAX / sizeof (long)) + 1));
    TEST_VERIFY (errno == ENOMEM);
    TEST_VERIFY (dynarray_long_has_failed (&dyn));
  }

  {
    struct dynarray_long_noscratch dyn;
    dynarray_long_noscratch_init (&dyn);
    errno = EINVAL;
    TEST_VERIFY (!dynarray_long_noscratch_resize
                 (&dyn, (SIZE_MAX / sizeof (long)) + 1));
    TEST_VERIFY (errno == ENOMEM);
    TEST_VERIFY (dynarray_long_noscratch_has_failed (&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_long_overflow ();
  test_zstr ();
  return 0;
}

#include <support/test-driver.c>
Commit	Line	Data
91b6eb11	1	/* Test for dynamic arrays.
04277e02	2	Copyright (C) 2017-2019 Free Software Foundation, Inc.
91b6eb11 FW	3	This file is part of the GNU C Library.
	4
	5	The GNU C Library is free software; you can redistribute it and/or
	6	modify it under the terms of the GNU Lesser General Public
	7	License as published by the Free Software Foundation; either
	8	version 2.1 of the License, or (at your option) any later version.
	9
	10	The GNU C Library is distributed in the hope that it will be useful,
	11	but WITHOUT ANY WARRANTY; without even the implied warranty of
	12	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	13	Lesser General Public License for more details.
	14
	15	You should have received a copy of the GNU Lesser General Public
	16	License along with the GNU C Library; if not, see
5a82c748	17	<https://www.gnu.org/licenses/>. */
91b6eb11 FW	18
	19	#include "tst-dynarray-shared.h"
	20
5898f454 FW	21	#include <errno.h>
	22	#include <stdint.h>
	23
91b6eb11 FW	24	#define DYNARRAY_STRUCT dynarray_long
	25	#define DYNARRAY_ELEMENT long
	26	#define DYNARRAY_PREFIX dynarray_long_
	27	#define DYNARRAY_ELEMENT_INIT(e) (*(e) = 17)
	28	#include <malloc/dynarray-skeleton.c>
	29
	30	struct long_array
	31	{
	32	long *array;
	33	size_t length;
	34	};
	35
	36	#define DYNARRAY_STRUCT dynarray_long_noscratch
	37	#define DYNARRAY_ELEMENT long
	38	#define DYNARRAY_PREFIX dynarray_long_noscratch_
	39	#define DYNARRAY_ELEMENT_INIT(e) (*(e) = 23)
	40	#define DYNARRAY_FINAL_TYPE struct long_array
	41	#define DYNARRAY_INITIAL_SIZE 0
	42	#include <malloc/dynarray-skeleton.c>
	43
	44	#define DYNARRAY_STRUCT zstr
	45	#define DYNARRAY_ELEMENT char
	46	#define DYNARRAY_PREFIX zstr_
	47	#define DYNARRAY_INITIAL_SIZE 128
	48	#include <malloc/dynarray-skeleton.c>
	49
	50	#include <malloc.h>
	51	#include <mcheck.h>
	52	#include <stdint.h>
	53	#include <support/check.h>
	54	#include <support/support.h>
	55
	56	enum { max_count = 20 };
	57
	58	/* Test dynamic arrays with int elements (no automatic deallocation
	59	for elements). */
	60	static void
	61	test_int (void)
	62	{
	63	/* Empty array. */
	64	{
	65	struct dynarray_int dyn;
	66	dynarray_int_init (&dyn);
	67	CHECK_EMPTY (int, &dyn);
	68	}
	69
	70	/* Empty array with finalization. */
	71	{
	72	struct dynarray_int dyn;
	73	dynarray_int_init (&dyn);
	74	CHECK_INIT_STATE (int, &dyn);
	75	struct int_array result = { (int *) (uintptr_t) -1, -1 };
	76	TEST_VERIFY_EXIT (dynarray_int_finalize (&dyn, &result));
	77	CHECK_INIT_STATE (int, &dyn);
	78	TEST_VERIFY_EXIT (result.array == NULL);
	79	TEST_VERIFY_EXIT (result.length == 0);
	80	}
	81
	82	/* Non-empty array tests.
	83
	84	do_add: Switch between emplace (false) and add (true).
	85	do_finalize: Perform finalize call at the end.
	86	do_clear: Perform clear call at the end.
	87	do_remove_last: Perform remove_last call after adding elements.
88	count: Number of elements added to the array. */
89	for (int do_add = 0; do_add < 2; ++do_add)
90	for (int do_finalize = 0; do_finalize < 2; ++do_finalize)
91	for (int do_clear = 0; do_clear < 2; ++do_clear)
92	for (int do_remove_last = 0; do_remove_last < 2; ++do_remove_last)
93	for (unsigned int count = 0; count < max_count; ++count)
94	{
95	if (do_remove_last && count == 0)
96	continue;
97	unsigned int base = count * count;
98	struct dynarray_int dyn;
99	dynarray_int_init (&dyn);
100	for (unsigned int i = 0; i < count; ++i)
101	{
102	if (do_add)
103	dynarray_int_add (&dyn, base + i);
104	else
105	{
106	int *place = dynarray_int_emplace (&dyn);
107	TEST_VERIFY_EXIT (place != NULL);
108	*place = base + i;
109	}
110	TEST_VERIFY_EXIT (!dynarray_int_has_failed (&dyn));
111	TEST_VERIFY_EXIT (dynarray_int_size (&dyn) == i + 1);
112	TEST_VERIFY_EXIT (dynarray_int_size (&dyn)
113	<= dyn.dynarray_header.allocated);
114	}
115	TEST_VERIFY_EXIT (dynarray_int_size (&dyn) == count);
116	TEST_VERIFY_EXIT (count <= dyn.dynarray_header.allocated);
f8bf87fa FW	117	if (count > 0)
	118	{
	119	TEST_VERIFY (dynarray_int_begin (&dyn)
	120	== dynarray_int_at (&dyn, 0));
	121	TEST_VERIFY (dynarray_int_end (&dyn)
	122	== dynarray_int_at (&dyn, count - 1) + 1);
	123	}
91b6eb11 FW	124	unsigned final_count;
	125	bool heap_array = dyn.dynarray_header.array != dyn.scratch;
	126	if (do_remove_last)
	127	{
	128	dynarray_int_remove_last (&dyn);
	129	if (count == 0)
	130	final_count = 0;
	131	else
	132	final_count = count - 1;
	133	}
	134	else
	135	final_count = count;
f8bf87fa FW	136	if (final_count > 0)
	137	{
	138	TEST_VERIFY (dynarray_int_begin (&dyn)
	139	== dynarray_int_at (&dyn, 0));
	140	TEST_VERIFY (dynarray_int_end (&dyn)
	141	== dynarray_int_at (&dyn, final_count - 1) + 1);
	142	}
91b6eb11 FW	143	if (do_clear)
	144	{
	145	dynarray_int_clear (&dyn);
	146	final_count = 0;
	147	}
	148	TEST_VERIFY_EXIT (!dynarray_int_has_failed (&dyn));
	149	TEST_VERIFY_EXIT ((dyn.dynarray_header.array != dyn.scratch)
	150	== heap_array);
	151	TEST_VERIFY_EXIT (dynarray_int_size (&dyn) == final_count);
	152	TEST_VERIFY_EXIT (dyn.dynarray_header.allocated >= final_count);
	153	if (!do_clear)
	154	for (unsigned int i = 0; i < final_count; ++i)
	155	TEST_VERIFY_EXIT (*dynarray_int_at (&dyn, i) == base + i);
	156	if (do_finalize)
	157	{
	158	struct int_array result = { (int *) (uintptr_t) -1, -1 };
	159	TEST_VERIFY_EXIT (dynarray_int_finalize (&dyn, &result));
	160	CHECK_INIT_STATE (int, &dyn);
	161	TEST_VERIFY_EXIT (result.length == final_count);
	162	if (final_count == 0)
	163	TEST_VERIFY_EXIT (result.array == NULL);
	164	else
	165	{
	166	TEST_VERIFY_EXIT (result.array != NULL);
	167	TEST_VERIFY_EXIT (result.array != (int *) (uintptr_t) -1);
	168	TEST_VERIFY_EXIT
	169	(malloc_usable_size (result.array)
	170	>= final_count * sizeof (result.array[0]));
	171	for (unsigned int i = 0; i < final_count; ++i)
	172	TEST_VERIFY_EXIT (result.array[i] == base + i);
	173	free (result.array);
	174	}
	175	}
	176	else /* !do_finalize */
	177	{
	178	dynarray_int_free (&dyn);
	179	CHECK_INIT_STATE (int, &dyn);
	180	}
	181	}
	182	}
	183
	184	/* Test dynamic arrays with char * elements (with automatic
	185	deallocation of the pointed-to strings). */
	186	static void
	187	test_str (void)
	188	{
	189	/* Empty array. */
	190	{
	191	struct dynarray_str dyn;
	192	dynarray_str_init (&dyn);
	193	CHECK_EMPTY (str, &dyn);
	194	}
	195
	196	/* Empty array with finalization. */
	197	{
	198	struct dynarray_str dyn;
	199	dynarray_str_init (&dyn);
	200	TEST_VERIFY_EXIT (!dynarray_str_has_failed (&dyn));
	201	struct str_array result = { (char **) (uintptr_t) -1, -1 };
	202	TEST_VERIFY_EXIT (dynarray_str_finalize (&dyn, &result));
	203	CHECK_INIT_STATE (str, &dyn);
	204	TEST_VERIFY_EXIT (result.array == NULL);
	205	TEST_VERIFY_EXIT (result.length == 0);
	206	}
207
208	/* Non-empty array tests.
209
210	do_add: Switch between emplace (false) and add (true).
211	do_finalize: Perform finalize call at the end.
212	do_clear: Perform clear call at the end.
213	do_remove_last: Perform remove_last call after adding elements.
214	count: Number of elements added to the array. */
215	for (int do_add = 0; do_add < 2; ++do_add)
216	for (int do_finalize = 0; do_finalize < 2; ++do_finalize)
217	for (int do_clear = 0; do_clear < 2; ++do_clear)
218	for (int do_remove_last = 0; do_remove_last < 2; ++do_remove_last)
219	for (unsigned int count = 0; count < max_count; ++count)
220	{
221	if (do_remove_last && count == 0)
222	continue;
223	unsigned int base = count * count;
224	struct dynarray_str dyn;
225	dynarray_str_init (&dyn);
226	for (unsigned int i = 0; i < count; ++i)
227	{
228	char *item = xasprintf ("%d", base + i);
229	if (do_add)
230	dynarray_str_add (&dyn, item);
231	else
232	{
233	char **place = dynarray_str_emplace (&dyn);
234	TEST_VERIFY_EXIT (place != NULL);
235	TEST_VERIFY_EXIT (*place == NULL);
236	*place = item;
237	}
238	TEST_VERIFY_EXIT (!dynarray_str_has_failed (&dyn));
239	TEST_VERIFY_EXIT (dynarray_str_size (&dyn) == i + 1);
240	TEST_VERIFY_EXIT (dynarray_str_size (&dyn)
241	<= dyn.dynarray_header.allocated);
242	}
243	TEST_VERIFY_EXIT (dynarray_str_size (&dyn) == count);
244	TEST_VERIFY_EXIT (count <= dyn.dynarray_header.allocated);
f8bf87fa FW	245	if (count > 0)
	246	{
	247	TEST_VERIFY (dynarray_str_begin (&dyn)
	248	== dynarray_str_at (&dyn, 0));
	249	TEST_VERIFY (dynarray_str_end (&dyn)
	250	== dynarray_str_at (&dyn, count - 1) + 1);
	251	}
91b6eb11 FW	252	unsigned final_count;
	253	bool heap_array = dyn.dynarray_header.array != dyn.scratch;
	254	if (do_remove_last)
	255	{
	256	dynarray_str_remove_last (&dyn);
	257	if (count == 0)
	258	final_count = 0;
	259	else
	260	final_count = count - 1;
	261	}
	262	else
	263	final_count = count;
f8bf87fa FW	264	if (final_count > 0)
	265	{
	266	TEST_VERIFY (dynarray_str_begin (&dyn)
	267	== dynarray_str_at (&dyn, 0));
	268	TEST_VERIFY (dynarray_str_end (&dyn)
	269	== dynarray_str_at (&dyn, final_count - 1) + 1);
	270	}
91b6eb11 FW	271	if (do_clear)
	272	{
	273	dynarray_str_clear (&dyn);
	274	final_count = 0;
	275	}
	276	TEST_VERIFY_EXIT (!dynarray_str_has_failed (&dyn));
	277	TEST_VERIFY_EXIT ((dyn.dynarray_header.array != dyn.scratch)
	278	== heap_array);
	279	TEST_VERIFY_EXIT (dynarray_str_size (&dyn) == final_count);
	280	TEST_VERIFY_EXIT (dyn.dynarray_header.allocated >= final_count);
	281	if (!do_clear)
	282	for (unsigned int i = 0; i < count - do_remove_last; ++i)
	283	{
	284	char *expected = xasprintf ("%d", base + i);
	285	const char actual = dynarray_str_at (&dyn, i);
	286	TEST_VERIFY_EXIT (strcmp (actual, expected) == 0);
	287	free (expected);
	288	}
	289	if (do_finalize)
	290	{
	291	struct str_array result = { (char **) (uintptr_t) -1, -1 };
	292	TEST_VERIFY_EXIT (dynarray_str_finalize (&dyn, &result));
	293	CHECK_INIT_STATE (str, &dyn);
	294	TEST_VERIFY_EXIT (result.length == final_count);
	295	if (final_count == 0)
	296	TEST_VERIFY_EXIT (result.array == NULL);
	297	else
	298	{
	299	TEST_VERIFY_EXIT (result.array != NULL);
	300	TEST_VERIFY_EXIT (result.array
	301	!= (char **) (uintptr_t) -1);
	302	TEST_VERIFY_EXIT (result.length
	303	== count - do_remove_last);
	304	TEST_VERIFY_EXIT
	305	(malloc_usable_size (result.array)
	306	>= final_count * sizeof (result.array[0]));
	307	for (unsigned int i = 0; i < count - do_remove_last; ++i)
	308	{
	309	char *expected = xasprintf ("%d", base + i);
	310	char *actual = result.array[i];
	311	TEST_VERIFY_EXIT (strcmp (actual, expected) == 0);
	312	free (expected);
	313	free (actual);
	314	}
	315	free (result.array);
	316	}
	317	}
	318	else /* !do_finalize */
	319	{
	320	dynarray_str_free (&dyn);
	321	CHECK_INIT_STATE (str, &dyn);
	322	}
	323	}
	324
	325	/* Test resizing. */
	326	{
	327	enum { count = 2131 };
	328	struct dynarray_str dyn;
	329	dynarray_str_init (&dyn);
	330
	331	/* From length 0 to length 1. */
	332	TEST_VERIFY (dynarray_str_resize (&dyn, 1));
	333	TEST_VERIFY (dynarray_str_size (&dyn) == 1);
	334	TEST_VERIFY (*dynarray_str_at (&dyn, 0) == NULL);
335	*dynarray_str_at (&dyn, 0) = xstrdup ("allocated");
336	dynarray_str_free (&dyn);
337
338	/* From length 0 to length 1 and 2. */
339	TEST_VERIFY (dynarray_str_resize (&dyn, 1));
340	TEST_VERIFY (dynarray_str_size (&dyn) == 1);
341	TEST_VERIFY (*dynarray_str_at (&dyn, 0) == NULL);
342	*dynarray_str_at (&dyn, 0) = xstrdup ("allocated0");
343	TEST_VERIFY (dynarray_str_resize (&dyn, 2));
344	TEST_VERIFY (dynarray_str_size (&dyn) == 2);
345	TEST_VERIFY (strcmp (*dynarray_str_at (&dyn, 0), "allocated0") == 0);
346	TEST_VERIFY (*dynarray_str_at (&dyn, 1) == NULL);
347	*dynarray_str_at (&dyn, 1) = xstrdup ("allocated1");
348	TEST_VERIFY (dynarray_str_resize (&dyn, count));
349	TEST_VERIFY (dynarray_str_size (&dyn) == count);
350	TEST_VERIFY (strcmp (*dynarray_str_at (&dyn, 0), "allocated0") == 0);
351	TEST_VERIFY (strcmp (*dynarray_str_at (&dyn, 1), "allocated1") == 0);
352	for (int i = 2; i < count; ++i)
353	TEST_VERIFY (*dynarray_str_at (&dyn, i) == NULL);
354	*dynarray_str_at (&dyn, count - 1) = xstrdup ("allocated2");
355	TEST_VERIFY (dynarray_str_resize (&dyn, 3));
356	TEST_VERIFY (strcmp (*dynarray_str_at (&dyn, 0), "allocated0") == 0);
357	TEST_VERIFY (strcmp (*dynarray_str_at (&dyn, 1), "allocated1") == 0);
358	TEST_VERIFY (*dynarray_str_at (&dyn, 2) == NULL);
359	dynarray_str_free (&dyn);
360	}
361	}
362
363	/* Verify that DYNARRAY_ELEMENT_INIT has an effect. */
364	static void
365	test_long_init (void)
366	{
367	enum { count = 2131 };
368	{
369	struct dynarray_long dyn;
370	dynarray_long_init (&dyn);
371	for (int i = 0; i < count; ++i)
372	{
373	long *place = dynarray_long_emplace (&dyn);
374	TEST_VERIFY_EXIT (place != NULL);
375	TEST_VERIFY (*place == 17);
376	}
377	TEST_VERIFY (dynarray_long_size (&dyn) == count);
378	for (int i = 0; i < count; ++i)
379	TEST_VERIFY (*dynarray_long_at (&dyn, i) == 17);
380	dynarray_long_free (&dyn);
381
382	TEST_VERIFY (dynarray_long_resize (&dyn, 1));
383	TEST_VERIFY (dynarray_long_size (&dyn) == 1);
384	TEST_VERIFY (*dynarray_long_at (&dyn, 0) == 17);
385	*dynarray_long_at (&dyn, 0) = 18;
386	dynarray_long_free (&dyn);
387	TEST_VERIFY (dynarray_long_resize (&dyn, 1));
388	TEST_VERIFY (dynarray_long_size (&dyn) == 1);
389	TEST_VERIFY (*dynarray_long_at (&dyn, 0) == 17);
390	TEST_VERIFY (dynarray_long_resize (&dyn, 2));
391	TEST_VERIFY (dynarray_long_size (&dyn) == 2);
392	TEST_VERIFY (*dynarray_long_at (&dyn, 0) == 17);
393	TEST_VERIFY (*dynarray_long_at (&dyn, 1) == 17);
394	*dynarray_long_at (&dyn, 0) = 18;
395	TEST_VERIFY (dynarray_long_resize (&dyn, count));
396	TEST_VERIFY (dynarray_long_size (&dyn) == count);
397	TEST_VERIFY (*dynarray_long_at (&dyn, 0) == 18);
398	for (int i = 1; i < count; ++i)
399	TEST_VERIFY (*dynarray_long_at (&dyn, i) == 17);
400	dynarray_long_free (&dyn);
401	}
402
403	/* Similar, but without an on-stack scratch region
404	(DYNARRAY_INITIAL_SIZE is 0). */
405	{
406	struct dynarray_long_noscratch dyn;
407	dynarray_long_noscratch_init (&dyn);
408	struct long_array result;
409	TEST_VERIFY_EXIT (dynarray_long_noscratch_finalize (&dyn, &result));
410	TEST_VERIFY (result.array == NULL);
411	TEST_VERIFY (result.length == 0);
412
413	/* Test with one element. */
414	{
415	long *place = dynarray_long_noscratch_emplace (&dyn);
416	TEST_VERIFY_EXIT (place != NULL);
417	TEST_VERIFY (*place == 23);
418	}
419	TEST_VERIFY (dynarray_long_noscratch_size (&dyn) == 1);
420	TEST_VERIFY (*dynarray_long_noscratch_at (&dyn, 0) == 23);
421	TEST_VERIFY_EXIT (dynarray_long_noscratch_finalize (&dyn, &result));
422	TEST_VERIFY_EXIT (result.array != NULL);
423	TEST_VERIFY (result.length == 1);
424	TEST_VERIFY (result.array[0] == 23);
425	free (result.array);
426
427	for (int i = 0; i < count; ++i)
428	{
429	long *place = dynarray_long_noscratch_emplace (&dyn);
430	TEST_VERIFY_EXIT (place != NULL);
431	TEST_VERIFY (*place == 23);
432	if (i == 0)
433	*place = 29;
434	}
435	TEST_VERIFY (dynarray_long_noscratch_size (&dyn) == count);
436	TEST_VERIFY (*dynarray_long_noscratch_at (&dyn, 0) == 29);
437	for (int i = 1; i < count; ++i)
438	TEST_VERIFY (*dynarray_long_noscratch_at (&dyn, i) == 23);
439	TEST_VERIFY_EXIT (dynarray_long_noscratch_finalize (&dyn, &result));
440	TEST_VERIFY_EXIT (result.array != NULL);
441	TEST_VERIFY (result.length == count);
442	TEST_VERIFY (result.array[0] == 29);
443	for (int i = 1; i < count; ++i)
444	TEST_VERIFY (result.array[i] == 23);
445	free (result.array);
446
447	TEST_VERIFY (dynarray_long_noscratch_resize (&dyn, 1));
448	TEST_VERIFY (dynarray_long_noscratch_size (&dyn) == 1);
449	TEST_VERIFY (*dynarray_long_noscratch_at (&dyn, 0) == 23);
450	*dynarray_long_noscratch_at (&dyn, 0) = 24;
451	dynarray_long_noscratch_free (&dyn);
452	TEST_VERIFY (dynarray_long_noscratch_resize (&dyn, 1));
453	TEST_VERIFY (dynarray_long_noscratch_size (&dyn) == 1);
454	TEST_VERIFY (*dynarray_long_noscratch_at (&dyn, 0) == 23);
455	TEST_VERIFY (dynarray_long_noscratch_resize (&dyn, 2));
456	TEST_VERIFY (dynarray_long_noscratch_size (&dyn) == 2);
457	TEST_VERIFY (*dynarray_long_noscratch_at (&dyn, 0) == 23);
458	TEST_VERIFY (*dynarray_long_noscratch_at (&dyn, 1) == 23);
459	*dynarray_long_noscratch_at (&dyn, 0) = 24;
460	TEST_VERIFY (dynarray_long_noscratch_resize (&dyn, count));
461	TEST_VERIFY (dynarray_long_noscratch_size (&dyn) == count);
462	TEST_VERIFY (*dynarray_long_noscratch_at (&dyn, 0) == 24);
463	for (int i = 1; i < count; ++i)
464	TEST_VERIFY (*dynarray_long_noscratch_at (&dyn, i) == 23);
465	dynarray_long_noscratch_free (&dyn);
466	}
467	}
468
5898f454 FW	469	/* Test overflow in resize. */
	470	static void
	471	test_long_overflow (void)
	472	{
	473	{
	474	struct dynarray_long dyn;
	475	dynarray_long_init (&dyn);
	476	errno = EINVAL;
	477	TEST_VERIFY (!dynarray_long_resize
	478	(&dyn, (SIZE_MAX / sizeof (long)) + 1));
	479	TEST_VERIFY (errno == ENOMEM);
	480	TEST_VERIFY (dynarray_long_has_failed (&dyn));
	481	}
	482
	483	{
	484	struct dynarray_long_noscratch dyn;
	485	dynarray_long_noscratch_init (&dyn);
	486	errno = EINVAL;
	487	TEST_VERIFY (!dynarray_long_noscratch_resize
	488	(&dyn, (SIZE_MAX / sizeof (long)) + 1));
	489	TEST_VERIFY (errno == ENOMEM);
	490	TEST_VERIFY (dynarray_long_noscratch_has_failed (&dyn));
	491	}
	492	}
	493
91b6eb11 FW	494	/* Test NUL-terminated string construction with the add function and
	495	the simple finalize function. */
	496	static void
	497	test_zstr (void)
	498	{
	499	/* Totally empty string (no NUL termination). */
	500	{
	501	struct zstr s;
	502	zstr_init (&s);
	503	char *result = zstr_finalize (&s, NULL);
	504	TEST_VERIFY (result == NULL);
	505	TEST_VERIFY (zstr_size (&s) == 0);
	506	size_t length = 1;
	507	result = zstr_finalize (&s, &length);
	508	TEST_VERIFY (result == NULL);
	509	TEST_VERIFY (length == 0);
	510	TEST_VERIFY (zstr_size (&s) == 0);
	511	}
	512
	513	/* Empty string. */
	514	{
	515	struct zstr s;
	516	zstr_init (&s);
	517	zstr_add (&s, '\0');
	518	char *result = zstr_finalize (&s, NULL);
	519	TEST_VERIFY_EXIT (result != NULL);
	520	TEST_VERIFY (*result == '\0');
	521	TEST_VERIFY (zstr_size (&s) == 0);
	522	free (result);
	523
	524	zstr_add (&s, '\0');
	525	size_t length = 1;
	526	result = zstr_finalize (&s, &length);
	527	TEST_VERIFY_EXIT (result != NULL);
	528	TEST_VERIFY (*result == '\0');
	529	TEST_VERIFY (length == 1);
	530	TEST_VERIFY (zstr_size (&s) == 0);
	531	free (result);
	532	}
	533
	534	/* A few characters. */
	535	{
	536	struct zstr s;
	537	zstr_init (&s);
	538	zstr_add (&s, 'A');
	539	zstr_add (&s, 'b');
	540	zstr_add (&s, 'c');
	541	zstr_add (&s, '\0');
	542	char *result = zstr_finalize (&s, NULL);
	543	TEST_VERIFY_EXIT (result != NULL);
	544	TEST_VERIFY (strcmp (result, "Abc") == 0);
	545	TEST_VERIFY (zstr_size (&s) == 0);
	546	free (result);
	547
	548	zstr_add (&s, 'X');
	549	zstr_add (&s, 'y');
	550	zstr_add (&s, 'z');
	551	zstr_add (&s, '\0');
	552	size_t length = 1;
	553	result = zstr_finalize (&s, &length);
	554	TEST_VERIFY_EXIT (result != NULL);
	555	TEST_VERIFY (strcmp (result, "Xyz") == 0);
	556	TEST_VERIFY (length == 4);
	557	TEST_VERIFY (zstr_size (&s) == 0);
558	free (result);
559	}
560	}
561
562	static int
563	do_test (void)
564	{
565	mtrace ();
566	test_int ();
567	test_str ();
568	test_long_init ();
5898f454	569	test_long_overflow ();
91b6eb11 FW	570	test_zstr ();
	571	return 0;
	572	}
	573
	574	#include <support/test-driver.c>