darray.h (0a1cb0a822b6665b972539da41209569b5d9de6e)

#ifndef RUBY_DARRAY_H
#define RUBY_DARRAY_H
 
#include <stdint.h>
#include <stddef.h>
#include <stdlib.h>
#include "ruby/ruby.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) \
    rb_darray_append_impl(ptr_to_ary, element, rb_darray_realloc_mul_add)
 
#define rb_darray_append_without_gc(ptr_to_ary, element) \
    rb_darray_append_impl(ptr_to_ary, element, rb_darray_realloc_mul_add_without_gc)
 
#define rb_darray_append_impl(ptr_to_ary, element, realloc_func) do {  \
    rb_darray_ensure_space((ptr_to_ary), \
                           sizeof(**(ptr_to_ary)), \
                           sizeof((*(ptr_to_ary))->data[0]), \
                           realloc_func); \
    rb_darray_set(*(ptr_to_ary), \
                  (*(ptr_to_ary))->meta.size, \
                  (element)); \
    (*(ptr_to_ary))->meta.size++; \
} while (0)
 
#define rb_darray_insert_without_gc(ptr_to_ary, idx, element) do { \
    rb_darray_ensure_space((ptr_to_ary), \
                           sizeof(**(ptr_to_ary)), \
                           sizeof((*(ptr_to_ary))->data[0]), \
                           rb_darray_realloc_mul_add_without_gc); \
    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]), rb_darray_calloc_mul_add)
 
#define rb_darray_make_without_gc(ptr_to_ary, size) \
    rb_darray_make_impl((ptr_to_ary), size, sizeof(**(ptr_to_ary)), \
                        sizeof((*(ptr_to_ary))->data[0]), rb_darray_calloc_mul_add_without_gc)
 
/* 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_without_gc(ptr_to_ary, capa) \
    rb_darray_resize_capa_impl((ptr_to_ary), capa, sizeof(**(ptr_to_ary)), \
                               sizeof((*(ptr_to_ary))->data[0]), rb_darray_realloc_mul_add_without_gc)
 
#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;
}
 
/* Estimate of the amount of memory used by this darray.
 * Useful for TypedData objects. */
#define rb_darray_memsize(ary) (sizeof(*(ary)) + (rb_darray_size(ary) * sizeof((ary)->data[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);
}
 
static inline void
rb_darray_free_sized0(void *ary, size_t element_size)
{
    const rb_darray_meta_t *meta = ary;
    if (meta) {
        ruby_xfree_sized(ary, sizeof(*meta) + (element_size * meta->capa));
    }
}
#define rb_darray_free_sized(ary, T) rb_darray_free_sized0((ary), sizeof(T))
 
static inline void
rb_darray_free_without_gc(void *ary)
{
    free(ary);
}
 
/* Internal function. Like rb_xcalloc_mul_add. */
static inline void *
rb_darray_calloc_mul_add(size_t x, size_t y, size_t z)
{
    size_t size = rbimpl_size_add_or_raise(rbimpl_size_mul_or_raise(x, y), z);
 
    void *ptr = xcalloc(1, size);
    RUBY_ASSERT(ptr != NULL);
 
    return ptr;
}
 
/* Internal function. Like rb_xcalloc_mul_add but does not trigger GC. */
static inline void *
rb_darray_calloc_mul_add_without_gc(size_t x, size_t y, size_t z)
{
    size_t size = rbimpl_size_add_or_raise(rbimpl_size_mul_or_raise(x, y), z);
 
    void *ptr = calloc(1, size);
    if (ptr == NULL) rb_bug("rb_darray_calloc_mul_add_without_gc: failed");
 
    return ptr;
}
 
void *ruby_xrealloc_sized(void *ptr, size_t new_size, size_t old_size);
 
/* Internal function. Like rb_xrealloc_mul_add. */
static inline void *
rb_darray_realloc_mul_add(void *orig_ptr, size_t capa, size_t element_size, size_t header_size)
{
    size_t size = rbimpl_size_add_or_raise(rbimpl_size_mul_or_raise(capa, element_size), header_size);
    size_t old_size = (rb_darray_capa(orig_ptr) * element_size) + header_size; // We know it won't overflow
 
    void *ptr = ruby_xrealloc_sized(orig_ptr, size, old_size);
    RUBY_ASSERT(ptr != NULL);
 
    return ptr;
}
 
/* Internal function. Like rb_xrealloc_mul_add but does not trigger GC. */
static inline void *
rb_darray_realloc_mul_add_without_gc(void *orig_ptr, size_t x, size_t y, size_t z)
{
    size_t size = rbimpl_size_add_or_raise(rbimpl_size_mul_or_raise(x, y), z);
 
    void *ptr = realloc(orig_ptr, size);
    if (ptr == NULL) rb_bug("rb_darray_realloc_mul_add_without_gc: failed");
 
    return ptr;
}
 
/* 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,
                           void *(*realloc_mul_add_impl)(void *, size_t, size_t, size_t))
{
    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 = realloc_mul_add_impl(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,
                       void *(*realloc_mul_add_impl)(void *, size_t, size_t, size_t))
{
    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, realloc_mul_add_impl);
}
 
static inline void
rb_darray_make_impl(void *ptr_to_ary, size_t array_size, size_t header_size, size_t element_size,
                    void *(*calloc_mul_add_impl)(size_t, size_t, size_t))
{
    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 = calloc_mul_add_impl(array_size, element_size, header_size);
 
    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 */