diff options
Diffstat (limited to 'darray.h')
| -rw-r--r-- | darray.h | 207 |
1 files changed, 0 insertions, 207 deletions
diff --git a/darray.h b/darray.h deleted file mode 100644 index 8c4a9d40af..0000000000 --- a/darray.h +++ /dev/null @@ -1,207 +0,0 @@ -#ifndef RUBY_DARRAY_H -#define RUBY_DARRAY_H - -#include <stdint.h> -#include <stddef.h> -#include <stdlib.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. -// -// NULL is a valid empty dynamic array. -// -// Example: -// rb_darray(char) char_array = NULL; -// rb_darray_append(&char_array, 'e'); -// printf("pushed %c\n", *rb_darray_ref(char_array, 0)); -// rb_darray_free(char_array); -// -#define rb_darray(T) struct { rb_darray_meta_t meta; T data[]; } * - -// Copy an element out of the array. Warning: not bounds checked. -// -// T rb_darray_get(rb_darray(T) ary, size_t idx); -// -#define rb_darray_get(ary, idx) ((ary)->data[(idx)]) - -// Assign to an element. Warning: not bounds checked. -// -// void rb_darray_set(rb_darray(T) ary, size_t idx, T element); -// -#define rb_darray_set(ary, idx, element) ((ary)->data[(idx)] = (element)) - -// Get a pointer to an element. Warning: not bounds checked. -// -// T *rb_darray_ref(rb_darray(T) ary, size_t idx); -// -#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)), \ - sizeof((*(ptr_to_ary))->data[0])); \ - rb_darray_set(*(ptr_to_ary), \ - (*(ptr_to_ary))->meta.size, \ - (element)); \ - (*(ptr_to_ary))->meta.size++; \ -} while (0) - -#define rb_darray_insert(ptr_to_ary, idx, element) do { \ - rb_darray_ensure_space((ptr_to_ary), \ - sizeof(**(ptr_to_ary)), \ - sizeof((*(ptr_to_ary))->data[0])); \ - MEMMOVE( \ - rb_darray_ref(*(ptr_to_ary), idx + 1), \ - rb_darray_ref(*(ptr_to_ary), idx), \ - (*(ptr_to_ary))->data[0], \ - rb_darray_size(*(ptr_to_ary)) - idx); \ - rb_darray_set(*(ptr_to_ary), idx, element); \ - (*(ptr_to_ary))->meta.size++; \ -} while (0) - -// Iterate over items of the array in a for loop -// -#define rb_darray_foreach(ary, idx_name, elem_ptr_var) \ - for (size_t idx_name = 0; idx_name < rb_darray_size(ary) && ((elem_ptr_var) = rb_darray_ref(ary, idx_name)); ++idx_name) - -// Iterate over valid indices in the array in a for loop -// -#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. - * 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])) - -/* 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])) - -#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 -rb_darray_size(const void *ary) -{ - const rb_darray_meta_t *meta = ary; - return meta ? meta->size : 0; -} - - -static inline void -rb_darray_pop(void *ary, size_t count) -{ - rb_darray_meta_t *meta = ary; - meta->size -= count; -} - -// Get the capacity of the dynamic array. -// -static inline size_t -rb_darray_capa(const void *ary) -{ - const rb_darray_meta_t *meta = ary; - return meta ? meta->capa : 0; -} - -/* Free the dynamic array. */ -static inline void -rb_darray_free(void *ary) -{ - 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 -// Ensure there is space for one more element. -// Note: header_size can be bigger than sizeof(rb_darray_meta_t) when T is __int128_t, for example. -static inline void -rb_darray_ensure_space(void *ptr_to_ary, 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; - size_t current_capa = rb_darray_capa(meta); - if (rb_darray_size(meta) < current_capa) return; - - // Double the capacity - size_t new_capa = current_capa == 0 ? 1 : current_capa * 2; - - rb_darray_resize_capa_impl(ptr_to_ary, new_capa, header_size, element_size); -} - -static inline void -rb_darray_make_impl(void *ptr_to_ary, size_t array_size, size_t header_size, size_t element_size) -{ - rb_darray_meta_t **ptr_to_ptr_to_meta = ptr_to_ary; - if (array_size == 0) { - *ptr_to_ptr_to_meta = NULL; - return; - } - - rb_darray_meta_t *meta = xcalloc(array_size * element_size + header_size, 1); - - meta->size = array_size; - meta->capa = array_size; - - // 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, &meta, sizeof(meta)); -} - -#endif /* RUBY_DARRAY_H */ |