/* Test for dynamic arrays.

   Copyright (C) 2017-2018 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"

#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>