|
Packit |
6c4009 |
/* Type-safe arrays which grow dynamically.
|
|
Packit |
6c4009 |
Copyright (C) 2017-2018 Free Software Foundation, Inc.
|
|
Packit |
6c4009 |
This file is part of the GNU C Library.
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
The GNU C Library is free software; you can redistribute it and/or
|
|
Packit |
6c4009 |
modify it under the terms of the GNU Lesser General Public
|
|
Packit |
6c4009 |
License as published by the Free Software Foundation; either
|
|
Packit |
6c4009 |
version 2.1 of the License, or (at your option) any later version.
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
The GNU C Library is distributed in the hope that it will be useful,
|
|
Packit |
6c4009 |
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
Packit |
6c4009 |
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
|
Packit |
6c4009 |
Lesser General Public License for more details.
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
You should have received a copy of the GNU Lesser General Public
|
|
Packit |
6c4009 |
License along with the GNU C Library; if not, see
|
|
Packit |
6c4009 |
<http://www.gnu.org/licenses/>. */
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Pre-processor macros which act as parameters:
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
DYNARRAY_STRUCT
|
|
Packit |
6c4009 |
The struct tag of dynamic array to be defined.
|
|
Packit |
6c4009 |
DYNARRAY_ELEMENT
|
|
Packit |
6c4009 |
The type name of the element type. Elements are copied
|
|
Packit |
6c4009 |
as if by memcpy, and can change address as the dynamic
|
|
Packit |
6c4009 |
array grows.
|
|
Packit |
6c4009 |
DYNARRAY_PREFIX
|
|
Packit |
6c4009 |
The prefix of the functions which are defined.
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
The following parameters are optional:
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
DYNARRAY_ELEMENT_FREE
|
|
Packit |
6c4009 |
DYNARRAY_ELEMENT_FREE (E) is evaluated to deallocate the
|
|
Packit |
6c4009 |
contents of elements. E is of type DYNARRAY_ELEMENT *.
|
|
Packit |
6c4009 |
DYNARRAY_ELEMENT_INIT
|
|
Packit |
6c4009 |
DYNARRAY_ELEMENT_INIT (E) is evaluated to initialize a new
|
|
Packit |
6c4009 |
element. E is of type DYNARRAY_ELEMENT *.
|
|
Packit |
6c4009 |
If DYNARRAY_ELEMENT_FREE but not DYNARRAY_ELEMENT_INIT is
|
|
Packit |
6c4009 |
defined, new elements are automatically zero-initialized.
|
|
Packit |
6c4009 |
Otherwise, new elements have undefined contents.
|
|
Packit |
6c4009 |
DYNARRAY_INITIAL_SIZE
|
|
Packit |
6c4009 |
The size of the statically allocated array (default:
|
|
Packit |
6c4009 |
at least 2, more elements if they fit into 128 bytes).
|
|
Packit |
6c4009 |
Must be a preprocessor constant. If DYNARRAY_INITIAL_SIZE is 0,
|
|
Packit |
6c4009 |
there is no statically allocated array at, and all non-empty
|
|
Packit |
6c4009 |
arrays are heap-allocated.
|
|
Packit |
6c4009 |
DYNARRAY_FINAL_TYPE
|
|
Packit |
6c4009 |
The name of the type which holds the final array. If not
|
|
Packit |
6c4009 |
defined, is PREFIX##finalize not provided. DYNARRAY_FINAL_TYPE
|
|
Packit |
6c4009 |
must be a struct type, with members of type DYNARRAY_ELEMENT and
|
|
Packit |
6c4009 |
size_t at the start (in this order).
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
These macros are undefined after this header file has been
|
|
Packit |
6c4009 |
included.
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
The following types are provided (their members are private to the
|
|
Packit |
6c4009 |
dynarray implementation):
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
struct DYNARRAY_STRUCT
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
The following functions are provided:
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
void DYNARRAY_PREFIX##init (struct DYNARRAY_STRUCT *);
|
|
Packit |
6c4009 |
void DYNARRAY_PREFIX##free (struct DYNARRAY_STRUCT *);
|
|
Packit |
6c4009 |
bool DYNARRAY_PREFIX##has_failed (const struct DYNARRAY_STRUCT *);
|
|
Packit |
6c4009 |
void DYNARRAY_PREFIX##mark_failed (struct DYNARRAY_STRUCT *);
|
|
Packit |
6c4009 |
size_t DYNARRAY_PREFIX##size (const struct DYNARRAY_STRUCT *);
|
|
Packit |
6c4009 |
DYNARRAY_ELEMENT *DYNARRAY_PREFIX##begin (const struct DYNARRAY_STRUCT *);
|
|
Packit |
6c4009 |
DYNARRAY_ELEMENT *DYNARRAY_PREFIX##end (const struct DYNARRAY_STRUCT *);
|
|
Packit |
6c4009 |
DYNARRAY_ELEMENT *DYNARRAY_PREFIX##at (struct DYNARRAY_STRUCT *, size_t);
|
|
Packit |
6c4009 |
void DYNARRAY_PREFIX##add (struct DYNARRAY_STRUCT *, DYNARRAY_ELEMENT);
|
|
Packit |
6c4009 |
DYNARRAY_ELEMENT *DYNARRAY_PREFIX##emplace (struct DYNARRAY_STRUCT *);
|
|
Packit |
6c4009 |
bool DYNARRAY_PREFIX##resize (struct DYNARRAY_STRUCT *, size_t);
|
|
Packit |
6c4009 |
void DYNARRAY_PREFIX##remove_last (struct DYNARRAY_STRUCT *);
|
|
Packit |
6c4009 |
void DYNARRAY_PREFIX##clear (struct DYNARRAY_STRUCT *);
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
The following functions are provided are provided if the
|
|
Packit |
6c4009 |
prerequisites are met:
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
bool DYNARRAY_PREFIX##finalize (struct DYNARRAY_STRUCT *,
|
|
Packit |
6c4009 |
DYNARRAY_FINAL_TYPE *);
|
|
Packit |
6c4009 |
(if DYNARRAY_FINAL_TYPE is defined)
|
|
Packit |
6c4009 |
DYNARRAY_ELEMENT *DYNARRAY_PREFIX##finalize (struct DYNARRAY_STRUCT *,
|
|
Packit |
6c4009 |
size_t *);
|
|
Packit |
6c4009 |
(if DYNARRAY_FINAL_TYPE is not defined)
|
|
Packit |
6c4009 |
*/
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#include <malloc/dynarray.h>
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#include <errno.h>
|
|
Packit |
6c4009 |
#include <stdlib.h>
|
|
Packit |
6c4009 |
#include <string.h>
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#ifndef DYNARRAY_STRUCT
|
|
Packit |
6c4009 |
# error "DYNARRAY_STRUCT must be defined"
|
|
Packit |
6c4009 |
#endif
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#ifndef DYNARRAY_ELEMENT
|
|
Packit |
6c4009 |
# error "DYNARRAY_ELEMENT must be defined"
|
|
Packit |
6c4009 |
#endif
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#ifndef DYNARRAY_PREFIX
|
|
Packit |
6c4009 |
# error "DYNARRAY_PREFIX must be defined"
|
|
Packit |
6c4009 |
#endif
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#ifdef DYNARRAY_INITIAL_SIZE
|
|
Packit |
6c4009 |
# if DYNARRAY_INITIAL_SIZE < 0
|
|
Packit |
6c4009 |
# error "DYNARRAY_INITIAL_SIZE must be non-negative"
|
|
Packit |
6c4009 |
# endif
|
|
Packit |
6c4009 |
# if DYNARRAY_INITIAL_SIZE > 0
|
|
Packit |
6c4009 |
# define DYNARRAY_HAVE_SCRATCH 1
|
|
Packit |
6c4009 |
# else
|
|
Packit |
6c4009 |
# define DYNARRAY_HAVE_SCRATCH 0
|
|
Packit |
6c4009 |
# endif
|
|
Packit |
6c4009 |
#else
|
|
Packit |
6c4009 |
/* Provide a reasonable default which limits the size of
|
|
Packit |
6c4009 |
DYNARRAY_STRUCT. */
|
|
Packit |
6c4009 |
# define DYNARRAY_INITIAL_SIZE \
|
|
Packit |
6c4009 |
(sizeof (DYNARRAY_ELEMENT) > 64 ? 2 : 128 / sizeof (DYNARRAY_ELEMENT))
|
|
Packit |
6c4009 |
# define DYNARRAY_HAVE_SCRATCH 1
|
|
Packit |
6c4009 |
#endif
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Public type definitions. */
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* All fields of this struct are private to the implementation. */
|
|
Packit |
6c4009 |
struct DYNARRAY_STRUCT
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
union
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
struct dynarray_header dynarray_abstract;
|
|
Packit |
6c4009 |
struct
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
/* These fields must match struct dynarray_header. */
|
|
Packit |
6c4009 |
size_t used;
|
|
Packit |
6c4009 |
size_t allocated;
|
|
Packit |
6c4009 |
DYNARRAY_ELEMENT *array;
|
|
Packit |
6c4009 |
} dynarray_header;
|
|
Packit |
6c4009 |
};
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#if DYNARRAY_HAVE_SCRATCH
|
|
Packit |
6c4009 |
/* Initial inline allocation. */
|
|
Packit |
6c4009 |
DYNARRAY_ELEMENT scratch[DYNARRAY_INITIAL_SIZE];
|
|
Packit |
6c4009 |
#endif
|
|
Packit |
6c4009 |
};
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Internal use only: Helper macros. */
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Ensure macro-expansion of DYNARRAY_PREFIX. */
|
|
Packit |
6c4009 |
#define DYNARRAY_CONCAT0(prefix, name) prefix##name
|
|
Packit |
6c4009 |
#define DYNARRAY_CONCAT1(prefix, name) DYNARRAY_CONCAT0(prefix, name)
|
|
Packit |
6c4009 |
#define DYNARRAY_NAME(name) DYNARRAY_CONCAT1(DYNARRAY_PREFIX, name)
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Address of the scratch buffer if any. */
|
|
Packit |
6c4009 |
#if DYNARRAY_HAVE_SCRATCH
|
|
Packit |
6c4009 |
# define DYNARRAY_SCRATCH(list) (list)->scratch
|
|
Packit |
6c4009 |
#else
|
|
Packit |
6c4009 |
# define DYNARRAY_SCRATCH(list) NULL
|
|
Packit |
6c4009 |
#endif
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Internal use only: Helper functions. */
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Internal function. Call DYNARRAY_ELEMENT_FREE with the array
|
|
Packit |
6c4009 |
elements. Name mangling needed due to the DYNARRAY_ELEMENT_FREE
|
|
Packit |
6c4009 |
macro expansion. */
|
|
Packit |
6c4009 |
static inline void
|
|
Packit |
6c4009 |
DYNARRAY_NAME (free__elements__) (DYNARRAY_ELEMENT *__dynarray_array,
|
|
Packit |
6c4009 |
size_t __dynarray_used)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
#ifdef DYNARRAY_ELEMENT_FREE
|
|
Packit |
6c4009 |
for (size_t __dynarray_i = 0; __dynarray_i < __dynarray_used; ++__dynarray_i)
|
|
Packit |
6c4009 |
DYNARRAY_ELEMENT_FREE (&__dynarray_array[__dynarray_i]);
|
|
Packit |
6c4009 |
#endif /* DYNARRAY_ELEMENT_FREE */
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Internal function. Free the non-scratch array allocation. */
|
|
Packit |
6c4009 |
static inline void
|
|
Packit |
6c4009 |
DYNARRAY_NAME (free__array__) (struct DYNARRAY_STRUCT *list)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
#if DYNARRAY_HAVE_SCRATCH
|
|
Packit |
6c4009 |
if (list->dynarray_header.array != list->scratch)
|
|
Packit |
6c4009 |
free (list->dynarray_header.array);
|
|
Packit |
6c4009 |
#else
|
|
Packit |
6c4009 |
free (list->dynarray_header.array);
|
|
Packit |
6c4009 |
#endif
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Public functions. */
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Initialize a dynamic array object. This must be called before any
|
|
Packit |
6c4009 |
use of the object. */
|
|
Packit |
6c4009 |
__attribute__ ((nonnull (1)))
|
|
Packit |
6c4009 |
static void
|
|
Packit |
6c4009 |
DYNARRAY_NAME (init) (struct DYNARRAY_STRUCT *list)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
list->dynarray_header.used = 0;
|
|
Packit |
6c4009 |
list->dynarray_header.allocated = DYNARRAY_INITIAL_SIZE;
|
|
Packit |
6c4009 |
list->dynarray_header.array = DYNARRAY_SCRATCH (list);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Deallocate the dynamic array and its elements. */
|
|
Packit |
6c4009 |
__attribute__ ((unused, nonnull (1)))
|
|
Packit |
6c4009 |
static void
|
|
Packit |
6c4009 |
DYNARRAY_NAME (free) (struct DYNARRAY_STRUCT *list)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
DYNARRAY_NAME (free__elements__)
|
|
Packit |
6c4009 |
(list->dynarray_header.array, list->dynarray_header.used);
|
|
Packit |
6c4009 |
DYNARRAY_NAME (free__array__) (list);
|
|
Packit |
6c4009 |
DYNARRAY_NAME (init) (list);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Return true if the dynamic array is in an error state. */
|
|
Packit |
6c4009 |
__attribute__ ((nonnull (1)))
|
|
Packit |
6c4009 |
static inline bool
|
|
Packit |
6c4009 |
DYNARRAY_NAME (has_failed) (const struct DYNARRAY_STRUCT *list)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
return list->dynarray_header.allocated == __dynarray_error_marker ();
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Mark the dynamic array as failed. All elements are deallocated as
|
|
Packit |
6c4009 |
a side effect. */
|
|
Packit |
6c4009 |
__attribute__ ((nonnull (1)))
|
|
Packit |
6c4009 |
static void
|
|
Packit |
6c4009 |
DYNARRAY_NAME (mark_failed) (struct DYNARRAY_STRUCT *list)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
DYNARRAY_NAME (free__elements__)
|
|
Packit |
6c4009 |
(list->dynarray_header.array, list->dynarray_header.used);
|
|
Packit |
6c4009 |
DYNARRAY_NAME (free__array__) (list);
|
|
Packit |
6c4009 |
list->dynarray_header.array = DYNARRAY_SCRATCH (list);
|
|
Packit |
6c4009 |
list->dynarray_header.used = 0;
|
|
Packit |
6c4009 |
list->dynarray_header.allocated = __dynarray_error_marker ();
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Return the number of elements which have been added to the dynamic
|
|
Packit |
6c4009 |
array. */
|
|
Packit |
6c4009 |
__attribute__ ((nonnull (1)))
|
|
Packit |
6c4009 |
static inline size_t
|
|
Packit |
6c4009 |
DYNARRAY_NAME (size) (const struct DYNARRAY_STRUCT *list)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
return list->dynarray_header.used;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Return a pointer to the array element at INDEX. Terminate the
|
|
Packit |
6c4009 |
process if INDEX is out of bounds. */
|
|
Packit |
6c4009 |
__attribute__ ((nonnull (1)))
|
|
Packit |
6c4009 |
static inline DYNARRAY_ELEMENT *
|
|
Packit |
6c4009 |
DYNARRAY_NAME (at) (struct DYNARRAY_STRUCT *list, size_t index)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
if (__glibc_unlikely (index >= DYNARRAY_NAME (size) (list)))
|
|
Packit |
6c4009 |
__libc_dynarray_at_failure (DYNARRAY_NAME (size) (list), index);
|
|
Packit |
6c4009 |
return list->dynarray_header.array + index;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Return a pointer to the first array element, if any. For a
|
|
Packit |
6c4009 |
zero-length array, the pointer can be NULL even though the dynamic
|
|
Packit |
6c4009 |
array has not entered the failure state. */
|
|
Packit |
6c4009 |
__attribute__ ((nonnull (1)))
|
|
Packit |
6c4009 |
static inline DYNARRAY_ELEMENT *
|
|
Packit |
6c4009 |
DYNARRAY_NAME (begin) (struct DYNARRAY_STRUCT *list)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
return list->dynarray_header.array;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Return a pointer one element past the last array element. For a
|
|
Packit |
6c4009 |
zero-length array, the pointer can be NULL even though the dynamic
|
|
Packit |
6c4009 |
array has not entered the failure state. */
|
|
Packit |
6c4009 |
__attribute__ ((nonnull (1)))
|
|
Packit |
6c4009 |
static inline DYNARRAY_ELEMENT *
|
|
Packit |
6c4009 |
DYNARRAY_NAME (end) (struct DYNARRAY_STRUCT *list)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
return list->dynarray_header.array + list->dynarray_header.used;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Internal function. Slow path for the add function below. */
|
|
Packit |
6c4009 |
static void
|
|
Packit |
6c4009 |
DYNARRAY_NAME (add__) (struct DYNARRAY_STRUCT *list, DYNARRAY_ELEMENT item)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
if (__glibc_unlikely
|
|
Packit |
6c4009 |
(!__libc_dynarray_emplace_enlarge (&list->dynarray_abstract,
|
|
Packit |
6c4009 |
DYNARRAY_SCRATCH (list),
|
|
Packit |
6c4009 |
sizeof (DYNARRAY_ELEMENT))))
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
DYNARRAY_NAME (mark_failed) (list);
|
|
Packit |
6c4009 |
return;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Copy the new element and increase the array length. */
|
|
Packit |
6c4009 |
list->dynarray_header.array[list->dynarray_header.used++] = item;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Add ITEM at the end of the array, enlarging it by one element.
|
|
Packit |
6c4009 |
Mark *LIST as failed if the dynamic array allocation size cannot be
|
|
Packit |
6c4009 |
increased. */
|
|
Packit |
6c4009 |
__attribute__ ((unused, nonnull (1)))
|
|
Packit |
6c4009 |
static inline void
|
|
Packit |
6c4009 |
DYNARRAY_NAME (add) (struct DYNARRAY_STRUCT *list, DYNARRAY_ELEMENT item)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
/* Do nothing in case of previous error. */
|
|
Packit |
6c4009 |
if (DYNARRAY_NAME (has_failed) (list))
|
|
Packit |
6c4009 |
return;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Enlarge the array if necessary. */
|
|
Packit |
6c4009 |
if (__glibc_unlikely (list->dynarray_header.used
|
|
Packit |
6c4009 |
== list->dynarray_header.allocated))
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
DYNARRAY_NAME (add__) (list, item);
|
|
Packit |
6c4009 |
return;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Copy the new element and increase the array length. */
|
|
Packit |
6c4009 |
list->dynarray_header.array[list->dynarray_header.used++] = item;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Internal function. Building block for the emplace functions below.
|
|
Packit |
6c4009 |
Assumes space for one more element in *LIST. */
|
|
Packit |
6c4009 |
static inline DYNARRAY_ELEMENT *
|
|
Packit |
6c4009 |
DYNARRAY_NAME (emplace__tail__) (struct DYNARRAY_STRUCT *list)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
DYNARRAY_ELEMENT *result
|
|
Packit |
6c4009 |
= &list->dynarray_header.array[list->dynarray_header.used];
|
|
Packit |
6c4009 |
++list->dynarray_header.used;
|
|
Packit |
6c4009 |
#if defined (DYNARRAY_ELEMENT_INIT)
|
|
Packit |
6c4009 |
DYNARRAY_ELEMENT_INIT (result);
|
|
Packit |
6c4009 |
#elif defined (DYNARRAY_ELEMENT_FREE)
|
|
Packit |
6c4009 |
memset (result, 0, sizeof (*result));
|
|
Packit |
6c4009 |
#endif
|
|
Packit |
6c4009 |
return result;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Internal function. Slow path for the emplace function below. */
|
|
Packit |
6c4009 |
static DYNARRAY_ELEMENT *
|
|
Packit |
6c4009 |
DYNARRAY_NAME (emplace__) (struct DYNARRAY_STRUCT *list)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
if (__glibc_unlikely
|
|
Packit |
6c4009 |
(!__libc_dynarray_emplace_enlarge (&list->dynarray_abstract,
|
|
Packit |
6c4009 |
DYNARRAY_SCRATCH (list),
|
|
Packit |
6c4009 |
sizeof (DYNARRAY_ELEMENT))))
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
DYNARRAY_NAME (mark_failed) (list);
|
|
Packit |
6c4009 |
return NULL;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
return DYNARRAY_NAME (emplace__tail__) (list);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Allocate a place for a new element in *LIST and return a pointer to
|
|
Packit |
6c4009 |
it. The pointer can be NULL if the dynamic array cannot be
|
|
Packit |
6c4009 |
enlarged due to a memory allocation failure. */
|
|
Packit |
6c4009 |
__attribute__ ((unused, warn_unused_result, nonnull (1)))
|
|
Packit |
6c4009 |
static
|
|
Packit |
6c4009 |
/* Avoid inlining with the larger initialization code. */
|
|
Packit |
6c4009 |
#if !(defined (DYNARRAY_ELEMENT_INIT) || defined (DYNARRAY_ELEMENT_FREE))
|
|
Packit |
6c4009 |
inline
|
|
Packit |
6c4009 |
#endif
|
|
Packit |
6c4009 |
DYNARRAY_ELEMENT *
|
|
Packit |
6c4009 |
DYNARRAY_NAME (emplace) (struct DYNARRAY_STRUCT *list)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
/* Do nothing in case of previous error. */
|
|
Packit |
6c4009 |
if (DYNARRAY_NAME (has_failed) (list))
|
|
Packit |
6c4009 |
return NULL;
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Enlarge the array if necessary. */
|
|
Packit |
6c4009 |
if (__glibc_unlikely (list->dynarray_header.used
|
|
Packit |
6c4009 |
== list->dynarray_header.allocated))
|
|
Packit |
6c4009 |
return (DYNARRAY_NAME (emplace__) (list));
|
|
Packit |
6c4009 |
return DYNARRAY_NAME (emplace__tail__) (list);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Change the size of *LIST to SIZE. If SIZE is larger than the
|
|
Packit |
6c4009 |
existing size, new elements are added (which can be initialized).
|
|
Packit |
6c4009 |
Otherwise, the list is truncated, and elements are freed. Return
|
|
Packit |
6c4009 |
false on memory allocation failure (and mark *LIST as failed). */
|
|
Packit |
6c4009 |
__attribute__ ((unused, nonnull (1)))
|
|
Packit |
6c4009 |
static bool
|
|
Packit |
6c4009 |
DYNARRAY_NAME (resize) (struct DYNARRAY_STRUCT *list, size_t size)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
if (size > list->dynarray_header.used)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
bool ok;
|
|
Packit |
6c4009 |
#if defined (DYNARRAY_ELEMENT_INIT)
|
|
Packit |
6c4009 |
/* The new elements have to be initialized. */
|
|
Packit |
6c4009 |
size_t old_size = list->dynarray_header.used;
|
|
Packit |
6c4009 |
ok = __libc_dynarray_resize (&list->dynarray_abstract,
|
|
Packit |
6c4009 |
size, DYNARRAY_SCRATCH (list),
|
|
Packit |
6c4009 |
sizeof (DYNARRAY_ELEMENT));
|
|
Packit |
6c4009 |
if (ok)
|
|
Packit |
6c4009 |
for (size_t i = old_size; i < size; ++i)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
DYNARRAY_ELEMENT_INIT (&list->dynarray_header.array[i]);
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
#elif defined (DYNARRAY_ELEMENT_FREE)
|
|
Packit |
6c4009 |
/* Zero initialization is needed so that the elements can be
|
|
Packit |
6c4009 |
safely freed. */
|
|
Packit |
6c4009 |
ok = __libc_dynarray_resize_clear
|
|
Packit |
6c4009 |
(&list->dynarray_abstract, size,
|
|
Packit |
6c4009 |
DYNARRAY_SCRATCH (list), sizeof (DYNARRAY_ELEMENT));
|
|
Packit |
6c4009 |
#else
|
|
Packit |
6c4009 |
ok = __libc_dynarray_resize (&list->dynarray_abstract,
|
|
Packit |
6c4009 |
size, DYNARRAY_SCRATCH (list),
|
|
Packit |
6c4009 |
sizeof (DYNARRAY_ELEMENT));
|
|
Packit |
6c4009 |
#endif
|
|
Packit |
6c4009 |
if (__glibc_unlikely (!ok))
|
|
Packit |
6c4009 |
DYNARRAY_NAME (mark_failed) (list);
|
|
Packit |
6c4009 |
return ok;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
else
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
/* The list has shrunk in size. Free the removed elements. */
|
|
Packit |
6c4009 |
DYNARRAY_NAME (free__elements__)
|
|
Packit |
6c4009 |
(list->dynarray_header.array + size,
|
|
Packit |
6c4009 |
list->dynarray_header.used - size);
|
|
Packit |
6c4009 |
list->dynarray_header.used = size;
|
|
Packit |
6c4009 |
return true;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Remove the last element of LIST if it is present. */
|
|
Packit |
6c4009 |
__attribute__ ((unused, nonnull (1)))
|
|
Packit |
6c4009 |
static void
|
|
Packit |
6c4009 |
DYNARRAY_NAME (remove_last) (struct DYNARRAY_STRUCT *list)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
/* used > 0 implies that the array is the non-failed state. */
|
|
Packit |
6c4009 |
if (list->dynarray_header.used > 0)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
size_t new_length = list->dynarray_header.used - 1;
|
|
Packit |
6c4009 |
#ifdef DYNARRAY_ELEMENT_FREE
|
|
Packit |
6c4009 |
DYNARRAY_ELEMENT_FREE (&list->dynarray_header.array[new_length]);
|
|
Packit |
6c4009 |
#endif
|
|
Packit |
6c4009 |
list->dynarray_header.used = new_length;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Remove all elements from the list. The elements are freed, but the
|
|
Packit |
6c4009 |
list itself is not. */
|
|
Packit |
6c4009 |
__attribute__ ((unused, nonnull (1)))
|
|
Packit |
6c4009 |
static void
|
|
Packit |
6c4009 |
DYNARRAY_NAME (clear) (struct DYNARRAY_STRUCT *list)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
/* free__elements__ does nothing if the list is in the failed
|
|
Packit |
6c4009 |
state. */
|
|
Packit |
6c4009 |
DYNARRAY_NAME (free__elements__)
|
|
Packit |
6c4009 |
(list->dynarray_header.array, list->dynarray_header.used);
|
|
Packit |
6c4009 |
list->dynarray_header.used = 0;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#ifdef DYNARRAY_FINAL_TYPE
|
|
Packit |
6c4009 |
/* Transfer the dynamic array to a permanent location at *RESULT.
|
|
Packit |
6c4009 |
Returns true on success on false on allocation failure. In either
|
|
Packit |
6c4009 |
case, *LIST is re-initialized and can be reused. A NULL pointer is
|
|
Packit |
6c4009 |
stored in *RESULT if LIST refers to an empty list. On success, the
|
|
Packit |
6c4009 |
pointer in *RESULT is heap-allocated and must be deallocated using
|
|
Packit |
6c4009 |
free. */
|
|
Packit |
6c4009 |
__attribute__ ((unused, warn_unused_result, nonnull (1, 2)))
|
|
Packit |
6c4009 |
static bool
|
|
Packit |
6c4009 |
DYNARRAY_NAME (finalize) (struct DYNARRAY_STRUCT *list,
|
|
Packit |
6c4009 |
DYNARRAY_FINAL_TYPE *result)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
struct dynarray_finalize_result res;
|
|
Packit |
6c4009 |
if (__libc_dynarray_finalize (&list->dynarray_abstract,
|
|
Packit |
6c4009 |
DYNARRAY_SCRATCH (list),
|
|
Packit |
6c4009 |
sizeof (DYNARRAY_ELEMENT), &res))
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
/* On success, the result owns all the data. */
|
|
Packit |
6c4009 |
DYNARRAY_NAME (init) (list);
|
|
Packit |
6c4009 |
*result = (DYNARRAY_FINAL_TYPE) { res.array, res.length };
|
|
Packit |
6c4009 |
return true;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
else
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
/* On error, we need to free all data. */
|
|
Packit |
6c4009 |
DYNARRAY_NAME (free) (list);
|
|
Packit |
6c4009 |
errno = ENOMEM;
|
|
Packit |
6c4009 |
return false;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
#else /* !DYNARRAY_FINAL_TYPE */
|
|
Packit |
6c4009 |
/* Transfer the dynamic array to a heap-allocated array and return a
|
|
Packit |
6c4009 |
pointer to it. The pointer is NULL if memory allocation fails, or
|
|
Packit |
6c4009 |
if the array is empty, so this function should be used only for
|
|
Packit |
6c4009 |
arrays which are known not be empty (usually because they always
|
|
Packit |
6c4009 |
have a sentinel at the end). If LENGTHP is not NULL, the array
|
|
Packit |
6c4009 |
length is written to *LENGTHP. *LIST is re-initialized and can be
|
|
Packit |
6c4009 |
reused. */
|
|
Packit |
6c4009 |
__attribute__ ((unused, warn_unused_result, nonnull (1)))
|
|
Packit |
6c4009 |
static DYNARRAY_ELEMENT *
|
|
Packit |
6c4009 |
DYNARRAY_NAME (finalize) (struct DYNARRAY_STRUCT *list, size_t *lengthp)
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
struct dynarray_finalize_result res;
|
|
Packit |
6c4009 |
if (__libc_dynarray_finalize (&list->dynarray_abstract,
|
|
Packit |
6c4009 |
DYNARRAY_SCRATCH (list),
|
|
Packit |
6c4009 |
sizeof (DYNARRAY_ELEMENT), &res))
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
/* On success, the result owns all the data. */
|
|
Packit |
6c4009 |
DYNARRAY_NAME (init) (list);
|
|
Packit |
6c4009 |
if (lengthp != NULL)
|
|
Packit |
6c4009 |
*lengthp = res.length;
|
|
Packit |
6c4009 |
return res.array;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
else
|
|
Packit |
6c4009 |
{
|
|
Packit |
6c4009 |
/* On error, we need to free all data. */
|
|
Packit |
6c4009 |
DYNARRAY_NAME (free) (list);
|
|
Packit |
6c4009 |
errno = ENOMEM;
|
|
Packit |
6c4009 |
return NULL;
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
}
|
|
Packit |
6c4009 |
#endif /* !DYNARRAY_FINAL_TYPE */
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
/* Undo macro definitions. */
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#undef DYNARRAY_CONCAT0
|
|
Packit |
6c4009 |
#undef DYNARRAY_CONCAT1
|
|
Packit |
6c4009 |
#undef DYNARRAY_NAME
|
|
Packit |
6c4009 |
#undef DYNARRAY_SCRATCH
|
|
Packit |
6c4009 |
#undef DYNARRAY_HAVE_SCRATCH
|
|
Packit |
6c4009 |
|
|
Packit |
6c4009 |
#undef DYNARRAY_STRUCT
|
|
Packit |
6c4009 |
#undef DYNARRAY_ELEMENT
|
|
Packit |
6c4009 |
#undef DYNARRAY_PREFIX
|
|
Packit |
6c4009 |
#undef DYNARRAY_ELEMENT_FREE
|
|
Packit |
6c4009 |
#undef DYNARRAY_ELEMENT_INIT
|
|
Packit |
6c4009 |
#undef DYNARRAY_INITIAL_SIZE
|
|
Packit |
6c4009 |
#undef DYNARRAY_FINAL_TYPE
|