summaryrefslogtreecommitdiffstats
path: root/lib/dynarray.h
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--lib/dynarray.h284
1 files changed, 284 insertions, 0 deletions
diff --git a/lib/dynarray.h b/lib/dynarray.h
new file mode 100644
index 0000000..ca6439d
--- /dev/null
+++ b/lib/dynarray.h
@@ -0,0 +1,284 @@
+/* Type-safe arrays which grow dynamically.
+ Copyright 2021-2022 Free Software Foundation, Inc.
+
+ This file 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.
+
+ This file 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 this program. If not, see <https://www.gnu.org/licenses/>. */
+
+/* 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
+
+#if defined DYNARRAY_STRUCT || defined DYNARRAY_ELEMENT || defined DYNARRAY_PREFIX
+
+# ifndef _GL_LIKELY
+/* Rely on __builtin_expect, as provided by the module 'builtin-expect'. */
+# define _GL_LIKELY(cond) __builtin_expect ((cond), 1)
+# define _GL_UNLIKELY(cond) __builtin_expect ((cond), 0)
+# endif
+
+/* Define auxiliary structs and declare auxiliary functions, common to all
+ instantiations of dynarray. */
+# include <malloc/dynarray.gl.h>
+
+/* Define the instantiation, specified through
+ DYNARRAY_STRUCT
+ DYNARRAY_ELEMENT
+ DYNARRAY_PREFIX
+ etc. */
+# include <malloc/dynarray-skeleton.gl.h>
+
+#else
+
+/* This file is being included from one of the malloc/dynarray_*.c files. */
+# include <malloc/dynarray.h>
+
+#endif
+
+#endif /* _GL_DYNARRAY_H */