Paul Eggert wrote:
> Perhaps it'd work without the "#define __libc_dynarray_resize
> gl_dynarray_resize" etc. lines, because the two sets of
> __libc_*dynarray* functions would be in different C namespaces? But it
> might be confusing to debug.
No, there would be conflicts with glibc. In C, the namespace scope is
the compilation unit. Since each of the files malloc/dynarray_*.c is a
separate compilation unit, we would be colliding with the __libc_*
symbols defined by glibc (both with dynamic and with static linking).
Since dynarray looks useful, I wrote a small unit test, to see how the
module can be used on its own. I noticed three things:
I) A compilation error because "intprops.h" is included by not present.
II) It's not immediately clear which files to include. I define
#define DYNARRAY_STRUCT int_sequence
#define DYNARRAY_ELEMENT int
#define DYNARRAY_PREFIX intseq_
and then:
* With just <dynarray.h>:
In file included from ../../gltests/../gllib/dynarray.h:29:0,
from ../../gltests/test-dynarray.c:25:
../../gltests/../gllib/malloc/dynarray.h:171:1: warning: return type defaults
to 'int' [-Wimplicit-int]
libc_hidden_proto (__libc_dynarray_emplace_enlarge)
^
../../gltests/../gllib/malloc/dynarray.h: In function 'libc_hidden_proto':
../../gltests/../gllib/malloc/dynarray.h:172:1: error: expected declaration
specifiers before 'libc_hidden_proto'
libc_hidden_proto (__libc_dynarray_resize)
^
* With <libc-config.h> and <dynarray.h>:
../../gltests/test-dynarray.c: In function 'main':
../../gltests/test-dynarray.c:41:23: error: storage size of 's' isn't known
struct int_sequence s;
^
* With just <malloc/dynarray-skeleton.c>:
In file included from ../../gltests/../gllib/malloc/dynarray-skeleton.c:88:0,
from ../../gltests/test-dynarray.c:26:
../../gltests/../gllib/malloc/dynarray.h:171:1: warning: return type defaults
to 'int' [-Wimplicit-int]
libc_hidden_proto (__libc_dynarray_emplace_enlarge)
^
../../gltests/../gllib/malloc/dynarray.h: In function 'libc_hidden_proto':
../../gltests/../gllib/malloc/dynarray.h:172:1: error: expected declaration
specifiers before 'libc_hidden_proto'
libc_hidden_proto (__libc_dynarray_resize)
^
* With <libc-config.h> and <malloc/dynarray-skeleton.c>:
test-dynarray.o: In function `intseq_add__':
/media/develdata/devel/GNULIB/testdir4/build-64/gltests/../../gltests/../gllib/malloc/dynarray-skeleton.c:281:
undefined reference to `__libc_dynarray_emplace_enlarge'
test-dynarray.o: In function `intseq_at':
/media/develdata/devel/GNULIB/testdir4/build-64/gltests/../../gltests/../gllib/malloc/dynarray-skeleton.c:253:
undefined reference to `__libc_dynarray_at_failure'
collect2: error: ld returned 1 exit status
* So the result is that all of these files need to be included:
#include <libc-config.h>
#include <dynarray.h>
#include <malloc/dynarray-skeleton.c>
But that is not a proper interface for a module. To use a module, one should
need to include one file, not three.
III) The API documentation needs to be gathered from three places:
malloc/dynarray.h has tutorial documentation that is not consumable without
having read the reference documentation. The reference documentation is
in malloc/dynarray-skeleton.c, at the top of the file and then mixed with
the implementation. *shudder*
The following two patches bring this in order, and add a unit test.
2021-03-06 Bruno Haible <[email protected]>
dynarray: Add tests.
* tests/test-dynarray.c: New file.
* modules/dynarray-tests: New file.
dynarray: Make the module usable on its own.
* lib/dynarray.h: Document the exported API. Comments taken from
lib/malloc/dynarray-skeleton.c and lib/malloc/dynarray.h.
Distinguish an internal include from an include for instantiation.
In the latter case, include <libc-config.h> and
<malloc/dynarray-skeleton.c>.
* modules/dynarray (Depends-on): Add intprops.
(Include): Reduce to just "dynarray.h".
>From 7ce163b7e92e127bb0d883df35ac9b642391ff8d Mon Sep 17 00:00:00 2001
From: Bruno Haible <[email protected]>
Date: Sun, 7 Mar 2021 00:40:27 +0100
Subject: [PATCH 1/2] dynarray: Make the module usable on its own.
* lib/dynarray.h: Document the exported API. Comments taken from
lib/malloc/dynarray-skeleton.c and lib/malloc/dynarray.h.
Distinguish an internal include from an include for instantiation.
In the latter case, include <libc-config.h> and
<malloc/dynarray-skeleton.c>.
* modules/dynarray (Depends-on): Add intprops.
(Include): Reduce to just "dynarray.h".
---
ChangeLog | 11 +++
lib/dynarray.h | 255 ++++++++++++++++++++++++++++++++++++++++++++++++++++++-
modules/dynarray | 4 +-
3 files changed, 266 insertions(+), 4 deletions(-)
diff --git a/ChangeLog b/ChangeLog
index e05cda2..8a86d1c 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,16 @@
2021-03-06 Bruno Haible <[email protected]>
+ dynarray: Make the module usable on its own.
+ * lib/dynarray.h: Document the exported API. Comments taken from
+ lib/malloc/dynarray-skeleton.c and lib/malloc/dynarray.h.
+ Distinguish an internal include from an include for instantiation.
+ In the latter case, include <libc-config.h> and
+ <malloc/dynarray-skeleton.c>.
+ * modules/dynarray (Depends-on): Add intprops.
+ (Include): Reduce to just "dynarray.h".
+
+2021-03-06 Bruno Haible <[email protected]>
+
scratch_buffer: Add comment.
* lib/scratch_buffer.h: Add comment.
diff --git a/lib/dynarray.h b/lib/dynarray.h
index 37053d0..9a8d395 100644
--- a/lib/dynarray.h
+++ b/lib/dynarray.h
@@ -14,16 +14,267 @@
You should have received a copy of the GNU General Public License
along with this program. If not, see <https://www.gnu.org/licenses/>. */
-/* Written by Paul Eggert, 2021. */
+/* Written by Paul Eggert and Bruno Haible, 2021. */
#ifndef _GL_DYNARRAY_H
#define _GL_DYNARRAY_H
+/* Before including this file, you need to define:
+
+ DYNARRAY_STRUCT
+ The struct tag of dynamic array to be defined.
+
+ DYNARRAY_ELEMENT
+ The type name of the element type. Elements are copied
+ as if by memcpy, and can change address as the dynamic
+ array grows.
+
+ DYNARRAY_PREFIX
+ The prefix of the functions which are defined.
+
+ The following parameters are optional:
+
+ DYNARRAY_ELEMENT_FREE
+ DYNARRAY_ELEMENT_FREE (E) is evaluated to deallocate the
+ contents of elements. E is of type DYNARRAY_ELEMENT *.
+
+ DYNARRAY_ELEMENT_INIT
+ DYNARRAY_ELEMENT_INIT (E) is evaluated to initialize a new
+ element. E is of type DYNARRAY_ELEMENT *.
+ If DYNARRAY_ELEMENT_FREE but not DYNARRAY_ELEMENT_INIT is
+ defined, new elements are automatically zero-initialized.
+ Otherwise, new elements have undefined contents.
+
+ DYNARRAY_INITIAL_SIZE
+ The size of the statically allocated array (default:
+ at least 2, more elements if they fit into 128 bytes).
+ Must be a preprocessor constant. If DYNARRAY_INITIAL_SIZE is 0,
+ there is no statically allocated array at, and all non-empty
+ arrays are heap-allocated.
+
+ DYNARRAY_FINAL_TYPE
+ The name of the type which holds the final array. If not
+ defined, is PREFIX##finalize not provided. DYNARRAY_FINAL_TYPE
+ must be a struct type, with members of type DYNARRAY_ELEMENT and
+ size_t at the start (in this order).
+
+ These macros are undefined after this header file has been
+ included.
+
+ The following types are provided (their members are private to the
+ dynarray implementation):
+
+ struct DYNARRAY_STRUCT
+
+ The following functions are provided:
+ */
+
+/* Initialize a dynamic array object. This must be called before any
+ use of the object. */
+#if 0
+static void
+ DYNARRAY_PREFIX##init (struct DYNARRAY_STRUCT *list);
+#endif
+
+/* Deallocate the dynamic array and its elements. */
+#if 0
+static void
+ DYNARRAY_PREFIX##free (struct DYNARRAY_STRUCT *list);
+#endif
+
+/* Return true if the dynamic array is in an error state. */
+#if 0
+static bool
+ DYNARRAY_PREFIX##has_failed (const struct DYNARRAY_STRUCT *list);
+#endif
+
+/* Mark the dynamic array as failed. All elements are deallocated as
+ a side effect. */
+#if 0
+static void
+ DYNARRAY_PREFIX##mark_failed (struct DYNARRAY_STRUCT *list);
+#endif
+
+/* Return the number of elements which have been added to the dynamic
+ array. */
+#if 0
+static size_t
+ DYNARRAY_PREFIX##size (const struct DYNARRAY_STRUCT *list);
+#endif
+
+/* Return a pointer to the first array element, if any. For a
+ zero-length array, the pointer can be NULL even though the dynamic
+ array has not entered the failure state. */
+#if 0
+static DYNARRAY_ELEMENT *
+ DYNARRAY_PREFIX##begin (const struct DYNARRAY_STRUCT *list);
+#endif
+
+/* Return a pointer one element past the last array element. For a
+ zero-length array, the pointer can be NULL even though the dynamic
+ array has not entered the failure state. */
+#if 0
+static DYNARRAY_ELEMENT *
+ DYNARRAY_PREFIX##end (const struct DYNARRAY_STRUCT *list);
+#endif
+
+/* Return a pointer to the array element at INDEX. Terminate the
+ process if INDEX is out of bounds. */
+#if 0
+static DYNARRAY_ELEMENT *
+ DYNARRAY_PREFIX##at (struct DYNARRAY_STRUCT *list, size_t index);
+#endif
+
+/* Add ITEM at the end of the array, enlarging it by one element.
+ Mark *LIST as failed if the dynamic array allocation size cannot be
+ increased. */
+#if 0
+static void
+ DYNARRAY_PREFIX##add (struct DYNARRAY_STRUCT *list,
+ DYNARRAY_ELEMENT item);
+#endif
+
+/* Allocate a place for a new element in *LIST and return a pointer to
+ it. The pointer can be NULL if the dynamic array cannot be
+ enlarged due to a memory allocation failure. */
+#if 0
+static DYNARRAY_ELEMENT *
+ DYNARRAY_PREFIX##emplace (struct DYNARRAY_STRUCT *list);
+#endif
+
+/* Change the size of *LIST to SIZE. If SIZE is larger than the
+ existing size, new elements are added (which can be initialized).
+ Otherwise, the list is truncated, and elements are freed. Return
+ false on memory allocation failure (and mark *LIST as failed). */
+#if 0
+static bool
+ DYNARRAY_PREFIX##resize (struct DYNARRAY_STRUCT *list, size_t size);
+#endif
+
+/* Remove the last element of LIST if it is present. */
+#if 0
+static void
+ DYNARRAY_PREFIX##remove_last (struct DYNARRAY_STRUCT *list);
+#endif
+
+/* Remove all elements from the list. The elements are freed, but the
+ list itself is not. */
+#if 0
+static void
+ DYNARRAY_PREFIX##clear (struct DYNARRAY_STRUCT *list);
+#endif
+
+#if defined DYNARRAY_FINAL_TYPE
+/* Transfer the dynamic array to a permanent location at *RESULT.
+ Returns true on success on false on allocation failure. In either
+ case, *LIST is re-initialized and can be reused. A NULL pointer is
+ stored in *RESULT if LIST refers to an empty list. On success, the
+ pointer in *RESULT is heap-allocated and must be deallocated using
+ free. */
+#if 0
+static bool
+ DYNARRAY_PREFIX##finalize (struct DYNARRAY_STRUCT *list,
+ DYNARRAY_FINAL_TYPE *result);
+#endif
+#else /* !defined DYNARRAY_FINAL_TYPE */
+/* Transfer the dynamic array to a heap-allocated array and return a
+ pointer to it. The pointer is NULL if memory allocation fails, or
+ if the array is empty, so this function should be used only for
+ arrays which are known not be empty (usually because they always
+ have a sentinel at the end). If LENGTHP is not NULL, the array
+ length is written to *LENGTHP. *LIST is re-initialized and can be
+ reused. */
+#if 0
+static DYNARRAY_ELEMENT *
+ DYNARRAY_PREFIX##finalize (struct DYNARRAY_STRUCT *list,
+ size_t *lengthp);
+#endif
+#endif
+
+/* A minimal example which provides a growing list of integers can be
+ defined like this:
+
+ struct int_array
+ {
+ // Pointer to result array followed by its length,
+ // as required by DYNARRAY_FINAL_TYPE.
+ int *array;
+ size_t length;
+ };
+
+ #define DYNARRAY_STRUCT dynarray_int
+ #define DYNARRAY_ELEMENT int
+ #define DYNARRAY_PREFIX dynarray_int_
+ #define DYNARRAY_FINAL_TYPE struct int_array
+ #include <malloc/dynarray-skeleton.c>
+
+ To create a three-element array with elements 1, 2, 3, use this
+ code:
+
+ struct dynarray_int dyn;
+ dynarray_int_init (&dyn);
+ for (int i = 1; i <= 3; ++i)
+ {
+ int *place = dynarray_int_emplace (&dyn);
+ assert (place != NULL);
+ *place = i;
+ }
+ struct int_array result;
+ bool ok = dynarray_int_finalize (&dyn, &result);
+ assert (ok);
+ assert (result.length == 3);
+ assert (result.array[0] == 1);
+ assert (result.array[1] == 2);
+ assert (result.array[2] == 3);
+ free (result.array);
+
+ If the elements contain resources which must be freed, define
+ DYNARRAY_ELEMENT_FREE appropriately, like this:
+
+ struct str_array
+ {
+ char **array;
+ size_t length;
+ };
+
+ #define DYNARRAY_STRUCT dynarray_str
+ #define DYNARRAY_ELEMENT char *
+ #define DYNARRAY_ELEMENT_FREE(ptr) free (*ptr)
+ #define DYNARRAY_PREFIX dynarray_str_
+ #define DYNARRAY_FINAL_TYPE struct str_array
+ #include <malloc/dynarray-skeleton.c>
+ */
+
+
+/* The implementation is imported from glibc. */
+
+/* Avoid possible conflicts with symbols exported by the GNU libc. */
#define __libc_dynarray_at_failure gl_dynarray_at_failure
#define __libc_dynarray_emplace_enlarge gl_dynarray_emplace_enlarge
#define __libc_dynarray_finalize gl_dynarray_finalize
#define __libc_dynarray_resize_clear gl_dynarray_resize_clear
#define __libc_dynarray_resize gl_dynarray_resize
-#include <malloc/dynarray.h>
+
+#if defined DYNARRAY_STRUCT || defined DYNARRAY_ELEMENT || defined DYNARRAY_PREFIX
+
+# include <libc-config.h>
+
+/* Define auxiliary structs and declare auxiliary functions, common to all
+ instantiations of dynarray. */
+# include <malloc/dynarray.h>
+
+/* Define the instantiation, specified through
+ DYNARRAY_STRUCT
+ DYNARRAY_ELEMENT
+ DYNARRAY_PREFIX
+ etc. */
+# include <malloc/dynarray-skeleton.c>
+
+#else
+
+/* This file is being included from one of the malloc/dynarray_*.c files. */
+# include <malloc/dynarray.h>
+
+#endif
#endif /* _GL_DYNARRAY_H */
diff --git a/modules/dynarray b/modules/dynarray
index 36a08ad..dcdcba4 100644
--- a/modules/dynarray
+++ b/modules/dynarray
@@ -16,6 +16,7 @@ c99
libc-config
stdbool
stddef
+intprops
configure.ac:
@@ -27,8 +28,7 @@ lib_SOURCES += malloc/dynarray_at_failure.c \
malloc/dynarray_resize_clear.c
Include:
-<dynarray.h>
-<malloc/dynarray-skeleton.c>
+"dynarray.h"
License:
LGPLv2+
--
2.7.4
>From 84b97a7332d6eae7b446645aea04f43eec473e8d Mon Sep 17 00:00:00 2001
From: Bruno Haible <[email protected]>
Date: Sun, 7 Mar 2021 00:41:44 +0100
Subject: [PATCH 2/2] dynarray: Add tests.
* tests/test-dynarray.c: New file.
* modules/dynarray-tests: New file.
---
ChangeLog | 4 ++++
modules/dynarray-tests | 11 +++++++++++
tests/test-dynarray.c | 53 ++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 68 insertions(+)
create mode 100644 modules/dynarray-tests
create mode 100644 tests/test-dynarray.c
diff --git a/ChangeLog b/ChangeLog
index 8a86d1c..5a100d7 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,9 @@
2021-03-06 Bruno Haible <[email protected]>
+ dynarray: Add tests.
+ * tests/test-dynarray.c: New file.
+ * modules/dynarray-tests: New file.
+
dynarray: Make the module usable on its own.
* lib/dynarray.h: Document the exported API. Comments taken from
lib/malloc/dynarray-skeleton.c and lib/malloc/dynarray.h.
diff --git a/modules/dynarray-tests b/modules/dynarray-tests
new file mode 100644
index 0000000..2791b9c
--- /dev/null
+++ b/modules/dynarray-tests
@@ -0,0 +1,11 @@
+Files:
+tests/test-dynarray.c
+tests/macros.h
+
+Depends-on:
+
+configure.ac:
+
+Makefile.am:
+TESTS += test-dynarray
+check_PROGRAMS += test-dynarray
diff --git a/tests/test-dynarray.c b/tests/test-dynarray.c
new file mode 100644
index 0000000..4308148
--- /dev/null
+++ b/tests/test-dynarray.c
@@ -0,0 +1,53 @@
+/* Test of type-safe arrays that grow dynamically.
+ Copyright (C) 2021 Free Software Foundation, Inc.
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2, or (at your option)
+ any later version.
+
+ This program 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 General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, see <https://www.gnu.org/licenses/>. */
+
+/* Written by Bruno Haible <[email protected]>, 2021. */
+
+#include <config.h>
+
+#define DYNARRAY_STRUCT int_sequence
+#define DYNARRAY_ELEMENT int
+#define DYNARRAY_PREFIX intseq_
+#include "dynarray.h"
+
+#include "macros.h"
+
+#define N 100000
+
+static int
+value_at (int i)
+{
+ return (i % 13) + ((i * i) % 251);
+}
+
+int
+main ()
+{
+ struct int_sequence s;
+ int i;
+
+ intseq_init (&s);
+ for (i = 0; i < N; i++)
+ intseq_add (&s, value_at (i));
+ for (i = N - 1; i >= N / 2; i--)
+ {
+ ASSERT (* intseq_at (&s, i) == value_at (i));
+ intseq_remove_last (&s);
+ }
+ intseq_free (&s);
+
+ return 0;
+}
--
2.7.4
