| 1 | /* Type-safe arrays which grow dynamically. Shared definitions.
|
|---|
| 2 | Copyright (C) 2017-2021 Free Software Foundation, Inc.
|
|---|
| 3 | This file is part of the GNU C Library.
|
|---|
| 4 |
|
|---|
| 5 | The GNU C Library is free software; you can redistribute it and/or
|
|---|
| 6 | modify it under the terms of the GNU Lesser General Public
|
|---|
| 7 | License as published by the Free Software Foundation; either
|
|---|
| 8 | version 2.1 of the License, or (at your option) any later version.
|
|---|
| 9 |
|
|---|
| 10 | The GNU C Library is distributed in the hope that it will be useful,
|
|---|
| 11 | but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|---|
| 12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
|---|
| 13 | Lesser General Public License for more details.
|
|---|
| 14 |
|
|---|
| 15 | You should have received a copy of the GNU Lesser General Public
|
|---|
| 16 | License along with the GNU C Library; if not, see
|
|---|
| 17 | <https://www.gnu.org/licenses/>. */
|
|---|
| 18 |
|
|---|
| 19 | /* To use the dynarray facility, you need to include
|
|---|
| 20 | <malloc/dynarray-skeleton.c> and define the parameter macros
|
|---|
| 21 | documented in that file.
|
|---|
| 22 |
|
|---|
| 23 | A minimal example which provides a growing list of integers can be
|
|---|
| 24 | defined like this:
|
|---|
| 25 |
|
|---|
| 26 | struct int_array
|
|---|
| 27 | {
|
|---|
| 28 | // Pointer to result array followed by its length,
|
|---|
| 29 | // as required by DYNARRAY_FINAL_TYPE.
|
|---|
| 30 | int *array;
|
|---|
| 31 | size_t length;
|
|---|
| 32 | };
|
|---|
| 33 |
|
|---|
| 34 | #define DYNARRAY_STRUCT dynarray_int
|
|---|
| 35 | #define DYNARRAY_ELEMENT int
|
|---|
| 36 | #define DYNARRAY_PREFIX dynarray_int_
|
|---|
| 37 | #define DYNARRAY_FINAL_TYPE struct int_array
|
|---|
| 38 | #include <malloc/dynarray-skeleton.c>
|
|---|
| 39 |
|
|---|
| 40 | To create a three-element array with elements 1, 2, 3, use this
|
|---|
| 41 | code:
|
|---|
| 42 |
|
|---|
| 43 | struct dynarray_int dyn;
|
|---|
| 44 | dynarray_int_init (&dyn);
|
|---|
| 45 | for (int i = 1; i <= 3; ++i)
|
|---|
| 46 | {
|
|---|
| 47 | int *place = dynarray_int_emplace (&dyn);
|
|---|
| 48 | assert (place != NULL);
|
|---|
| 49 | *place = i;
|
|---|
| 50 | }
|
|---|
| 51 | struct int_array result;
|
|---|
| 52 | bool ok = dynarray_int_finalize (&dyn, &result);
|
|---|
| 53 | assert (ok);
|
|---|
| 54 | assert (result.length == 3);
|
|---|
| 55 | assert (result.array[0] == 1);
|
|---|
| 56 | assert (result.array[1] == 2);
|
|---|
| 57 | assert (result.array[2] == 3);
|
|---|
| 58 | free (result.array);
|
|---|
| 59 |
|
|---|
| 60 | If the elements contain resources which must be freed, define
|
|---|
| 61 | DYNARRAY_ELEMENT_FREE appropriately, like this:
|
|---|
| 62 |
|
|---|
| 63 | struct str_array
|
|---|
| 64 | {
|
|---|
| 65 | char **array;
|
|---|
| 66 | size_t length;
|
|---|
| 67 | };
|
|---|
| 68 |
|
|---|
| 69 | #define DYNARRAY_STRUCT dynarray_str
|
|---|
| 70 | #define DYNARRAY_ELEMENT char *
|
|---|
| 71 | #define DYNARRAY_ELEMENT_FREE(ptr) free (*ptr)
|
|---|
| 72 | #define DYNARRAY_PREFIX dynarray_str_
|
|---|
| 73 | #define DYNARRAY_FINAL_TYPE struct str_array
|
|---|
| 74 | #include <malloc/dynarray-skeleton.c>
|
|---|
| 75 |
|
|---|
| 76 | Compared to scratch buffers, dynamic arrays have the following
|
|---|
| 77 | features:
|
|---|
| 78 |
|
|---|
| 79 | - They have an element type, and are not just an untyped buffer of
|
|---|
| 80 | bytes.
|
|---|
| 81 |
|
|---|
| 82 | - When growing, previously stored elements are preserved. (It is
|
|---|
| 83 | expected that scratch_buffer_grow_preserve and
|
|---|
| 84 | scratch_buffer_set_array_size eventually go away because all
|
|---|
| 85 | current users are moved to dynamic arrays.)
|
|---|
| 86 |
|
|---|
| 87 | - Scratch buffers have a more aggressive growth policy because
|
|---|
| 88 | growing them typically means a retry of an operation (across an
|
|---|
| 89 | NSS service module boundary), which is expensive.
|
|---|
| 90 |
|
|---|
| 91 | - For the same reason, scratch buffers have a much larger initial
|
|---|
| 92 | stack allocation. */
|
|---|
| 93 |
|
|---|
| 94 | #ifndef _DYNARRAY_H
|
|---|
| 95 | #define _DYNARRAY_H
|
|---|
| 96 |
|
|---|
| 97 | #include <stdbool.h>
|
|---|
| 98 | #include <stddef.h>
|
|---|
| 99 | #include <string.h>
|
|---|
| 100 |
|
|---|
| 101 | struct dynarray_header
|
|---|
| 102 | {
|
|---|
| 103 | size_t used;
|
|---|
| 104 | size_t allocated;
|
|---|
| 105 | void *array;
|
|---|
| 106 | };
|
|---|
| 107 |
|
|---|
| 108 | /* Marker used in the allocated member to indicate that an error was
|
|---|
| 109 | encountered. */
|
|---|
| 110 | static inline size_t
|
|---|
| 111 | __dynarray_error_marker (void)
|
|---|
| 112 | {
|
|---|
| 113 | return -1;
|
|---|
| 114 | }
|
|---|
| 115 |
|
|---|
| 116 | /* Internal function. See the has_failed function in
|
|---|
| 117 | dynarray-skeleton.c. */
|
|---|
| 118 | static inline bool
|
|---|
| 119 | __dynarray_error (struct dynarray_header *list)
|
|---|
| 120 | {
|
|---|
| 121 | return list->allocated == __dynarray_error_marker ();
|
|---|
| 122 | }
|
|---|
| 123 |
|
|---|
| 124 | /* Internal function. Enlarge the dynamically allocated area of the
|
|---|
| 125 | array to make room for one more element. SCRATCH is a pointer to
|
|---|
| 126 | the scratch area (which is not heap-allocated and must not be
|
|---|
| 127 | freed). ELEMENT_SIZE is the size, in bytes, of one element.
|
|---|
| 128 | Return false on failure, true on success. */
|
|---|
| 129 | bool __libc_dynarray_emplace_enlarge (struct dynarray_header *,
|
|---|
| 130 | void *scratch, size_t element_size);
|
|---|
| 131 |
|
|---|
| 132 | /* Internal function. Enlarge the dynamically allocated area of the
|
|---|
| 133 | array to make room for at least SIZE elements (which must be larger
|
|---|
| 134 | than the existing used part of the dynamic array). SCRATCH is a
|
|---|
| 135 | pointer to the scratch area (which is not heap-allocated and must
|
|---|
| 136 | not be freed). ELEMENT_SIZE is the size, in bytes, of one element.
|
|---|
| 137 | Return false on failure, true on success. */
|
|---|
| 138 | bool __libc_dynarray_resize (struct dynarray_header *, size_t size,
|
|---|
| 139 | void *scratch, size_t element_size);
|
|---|
| 140 |
|
|---|
| 141 | /* Internal function. Like __libc_dynarray_resize, but clear the new
|
|---|
| 142 | part of the dynamic array. */
|
|---|
| 143 | bool __libc_dynarray_resize_clear (struct dynarray_header *, size_t size,
|
|---|
| 144 | void *scratch, size_t element_size);
|
|---|
| 145 |
|
|---|
| 146 | /* Internal type. */
|
|---|
| 147 | struct dynarray_finalize_result
|
|---|
| 148 | {
|
|---|
| 149 | void *array;
|
|---|
| 150 | size_t length;
|
|---|
| 151 | };
|
|---|
| 152 |
|
|---|
| 153 | /* Internal function. Copy the dynamically-allocated area to an
|
|---|
| 154 | explicitly-sized heap allocation. SCRATCH is a pointer to the
|
|---|
| 155 | embedded scratch space. ELEMENT_SIZE is the size, in bytes, of the
|
|---|
| 156 | element type. On success, true is returned, and pointer and length
|
|---|
| 157 | are written to *RESULT. On failure, false is returned. The caller
|
|---|
| 158 | has to take care of some of the memory management; this function is
|
|---|
| 159 | expected to be called from dynarray-skeleton.c. */
|
|---|
| 160 | bool __libc_dynarray_finalize (struct dynarray_header *list, void *scratch,
|
|---|
| 161 | size_t element_size,
|
|---|
| 162 | struct dynarray_finalize_result *result);
|
|---|
| 163 |
|
|---|
| 164 |
|
|---|
| 165 | /* Internal function. Terminate the process after an index error.
|
|---|
| 166 | SIZE is the number of elements of the dynamic array. INDEX is the
|
|---|
| 167 | lookup index which triggered the failure. */
|
|---|
| 168 | _Noreturn void __libc_dynarray_at_failure (size_t size, size_t index);
|
|---|
| 169 |
|
|---|
| 170 | #ifndef _ISOMAC
|
|---|
| 171 | libc_hidden_proto (__libc_dynarray_emplace_enlarge)
|
|---|
| 172 | libc_hidden_proto (__libc_dynarray_resize)
|
|---|
| 173 | libc_hidden_proto (__libc_dynarray_resize_clear)
|
|---|
| 174 | libc_hidden_proto (__libc_dynarray_finalize)
|
|---|
| 175 | libc_hidden_proto (__libc_dynarray_at_failure)
|
|---|
| 176 | #endif
|
|---|
| 177 |
|
|---|
| 178 | #endif /* _DYNARRAY_H */
|
|---|