diff options
author | Florian Weimer <fweimer@redhat.com> | 2017-06-02 11:59:28 +0200 |
---|---|---|
committer | Florian Weimer <fweimer@redhat.com> | 2017-06-02 11:59:28 +0200 |
commit | 91b6eb1140eda6bab324821ee3785e5d0ca155b8 (patch) | |
tree | c8b630c412611a9b9f5e600e8824661f403bfa7f /malloc/tst-dynarray.c | |
parent | 09103e40252454e906a0b8543a142fc96b4c17c1 (diff) | |
download | glibc-91b6eb1140eda6bab324821ee3785e5d0ca155b8.tar.gz glibc-91b6eb1140eda6bab324821ee3785e5d0ca155b8.tar.xz glibc-91b6eb1140eda6bab324821ee3785e5d0ca155b8.zip |
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.
Diffstat (limited to 'malloc/tst-dynarray.c')
-rw-r--r-- | malloc/tst-dynarray.c | 517 |
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> |