diff options
Diffstat (limited to 'darray.h')
| -rw-r--r-- | darray.h | 124 |
1 files changed, 68 insertions, 56 deletions
@@ -5,6 +5,8 @@ #include <stddef.h> #include <stdlib.h> +#include "internal/bits.h" + // Type for a dynamic array. Use to declare a dynamic array. // It is a pointer so it fits in st_table nicely. Designed // to be fairly type-safe. @@ -37,12 +39,16 @@ // #define rb_darray_ref(ary, idx) (&((ary)->data[(idx)])) -// Copy a new element into the array. ptr_to_ary is evaluated multiple times. -// -// void rb_darray_append(rb_darray(T) *ptr_to_ary, T element); -// -#define rb_darray_append(ptr_to_ary, element) do { \ - rb_darray_ensure_space((ptr_to_ary), sizeof(**(ptr_to_ary)), \ +/* Copy a new element into the array. ptr_to_ary is evaluated multiple times. + * + * void rb_darray_append(rb_darray(T) *ptr_to_ary, T element); + */ +#define rb_darray_append(ptr_to_ary, element) \ + rb_darray_append_impl(ptr_to_ary, element) + +#define rb_darray_append_impl(ptr_to_ary, element) do { \ + rb_darray_ensure_space((ptr_to_ary), \ + sizeof(**(ptr_to_ary)), \ sizeof((*(ptr_to_ary))->data[0])); \ rb_darray_set(*(ptr_to_ary), \ (*(ptr_to_ary))->meta.size, \ @@ -50,21 +56,6 @@ (*(ptr_to_ary))->meta.size++; \ } while (0) - -// Last element of the array -// -#define rb_darray_back(ary) ((ary)->data[(ary)->meta.size - 1]) - -// Remove the last element of the array. -// -#define rb_darray_pop_back(ary) ((ary)->meta.size--) - -// Remove element at idx and replace it by the last element -#define rb_darray_remove_unordered(ary, idx) do { \ - rb_darray_set(ary, idx, rb_darray_back(ary)); \ - rb_darray_pop_back(ary); \ -} while (0); - // Iterate over items of the array in a for loop // #define rb_darray_foreach(ary, idx_name, elem_ptr_var) \ @@ -75,28 +66,42 @@ #define rb_darray_for(ary, idx_name) \ for (size_t idx_name = 0; idx_name < rb_darray_size(ary); ++idx_name) -// Make a dynamic array of a certain size. All bytes backing the elements are set to zero. -// -// Note that NULL is a valid empty dynamic array. -// -// void rb_darray_make(rb_darray(T) *ptr_to_ary, size_t size); -// +/* Make a dynamic array of a certain size. All bytes backing the elements are set to zero. + * Return 1 on success and 0 on failure. + * + * Note that NULL is a valid empty dynamic array. + * + * void rb_darray_make(rb_darray(T) *ptr_to_ary, size_t size); + */ #define rb_darray_make(ptr_to_ary, size) \ - rb_darray_make_impl((ptr_to_ary), size, sizeof(**(ptr_to_ary)), \ - sizeof((*(ptr_to_ary))->data[0])) + rb_darray_make_impl((ptr_to_ary), size, sizeof(**(ptr_to_ary)), sizeof((*(ptr_to_ary))->data[0])) -#define rb_darray_data_ptr(ary) ((ary)->data) +/* Resize the darray to a new capacity. The new capacity must be greater than + * or equal to the size of the darray. + * + * void rb_darray_resize_capa(rb_darray(T) *ptr_to_ary, size_t capa); + */ +#define rb_darray_resize_capa(ptr_to_ary, capa) \ + rb_darray_resize_capa_impl((ptr_to_ary), capa, sizeof(**(ptr_to_ary)), sizeof((*(ptr_to_ary))->data[0])) -// Set the size of the array to zero without freeing the backing memory. -// Allows reusing the same array. -// -#define rb_darray_clear(ary) (ary->meta.size = 0) +#define rb_darray_data_ptr(ary) ((ary)->data) typedef struct rb_darray_meta { size_t size; size_t capa; } rb_darray_meta_t; +/* Set the size of the array to zero without freeing the backing memory. + * Allows reusing the same array. */ +static inline void +rb_darray_clear(void *ary) +{ + rb_darray_meta_t *meta = ary; + if (meta) { + meta->size = 0; + } +} + // Get the size of the dynamic array. // static inline size_t @@ -115,13 +120,36 @@ rb_darray_capa(const void *ary) return meta ? meta->capa : 0; } -// Free the dynamic array. -// +/* Free the dynamic array. */ static inline void rb_darray_free(void *ary) { - rb_darray_meta_t *meta = ary; - ruby_sized_xfree(ary, meta->capa); + xfree(ary); +} + +/* Internal function. Resizes the capacity of a darray. The new capacity must + * be greater than or equal to the size of the darray. */ +static inline void +rb_darray_resize_capa_impl(void *ptr_to_ary, size_t new_capa, size_t header_size, size_t element_size) +{ + rb_darray_meta_t **ptr_to_ptr_to_meta = ptr_to_ary; + rb_darray_meta_t *meta = *ptr_to_ptr_to_meta; + + rb_darray_meta_t *new_ary = xrealloc(meta, new_capa * element_size + header_size); + + if (meta == NULL) { + /* First allocation. Initialize size. On subsequence allocations + * realloc takes care of carrying over the size. */ + new_ary->size = 0; + } + + RUBY_ASSERT(new_ary->size <= new_capa); + + new_ary->capa = new_capa; + + // We don't have access to the type of the dynamic array in function context. + // Write out result with memcpy to avoid strict aliasing issue. + memcpy(ptr_to_ary, &new_ary, sizeof(new_ary)); } // Internal function @@ -138,21 +166,7 @@ rb_darray_ensure_space(void *ptr_to_ary, size_t header_size, size_t element_size // Double the capacity size_t new_capa = current_capa == 0 ? 1 : current_capa * 2; - rb_darray_meta_t *doubled_ary = rb_xrealloc_mul_add(meta, new_capa, element_size, header_size); - // rb_xrealloc functions guarantee that NULL is not returned - assert(doubled_ary != NULL); - - if (meta == NULL) { - // First allocation. Initialize size. On subsequence allocations - // realloc takes care of carrying over the size. - doubled_ary->size = 0; - } - - doubled_ary->capa = new_capa; - - // We don't have access to the type of the dynamic array in function context. - // Write out result with memcpy to avoid strict aliasing issue. - memcpy(ptr_to_ary, &doubled_ary, sizeof(doubled_ary)); + rb_darray_resize_capa_impl(ptr_to_ary, new_capa, header_size, element_size); } static inline void @@ -164,9 +178,7 @@ rb_darray_make_impl(void *ptr_to_ary, size_t array_size, size_t header_size, siz return; } - rb_darray_meta_t *meta = rb_xcalloc_mul_add(array_size, element_size, header_size); - // rb_xcalloc functions guarantee that NULL is not returned - assert(meta != NULL); + rb_darray_meta_t *meta = xcalloc(array_size * element_size + header_size, 1); meta->size = array_size; meta->capa = array_size; |