diff options
Diffstat (limited to 'darray.h')
| -rw-r--r-- | darray.h | 99 |
1 files changed, 74 insertions, 25 deletions
@@ -4,9 +4,7 @@ #include <stdint.h> #include <stddef.h> #include <stdlib.h> - -#include "internal/bits.h" -#include "internal/gc.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 @@ -45,7 +43,7 @@ * 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_xrealloc_mul_add) + 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) @@ -61,6 +59,20 @@ (*(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) \ @@ -80,7 +92,7 @@ */ #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_xcalloc_mul_add) + 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)), \ @@ -92,7 +104,7 @@ * 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), rb_darray_next_power_of_two(capa), sizeof(**(ptr_to_ary)), \ + 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) @@ -122,6 +134,17 @@ rb_darray_size(const void *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 @@ -135,9 +158,18 @@ rb_darray_capa(const void *ary) static inline void rb_darray_free(void *ary) { - rb_darray_meta_t *meta = ary; - if (meta) ruby_sized_xfree(ary, meta->capa); + 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) @@ -145,12 +177,23 @@ rb_darray_free_without_gc(void *ary) free(ary); } -/* Internal function. Like rb_xcalloc_mul_add but does not trigger GC and does - * not check for overflow in arithmetic. */ +/* 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 = (x * y) + 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"); @@ -158,32 +201,38 @@ rb_darray_calloc_mul_add_without_gc(size_t x, size_t y, size_t z) return ptr; } -/* Internal function. Like rb_xrealloc_mul_add but does not trigger GC and does - * not check for overflow in arithmetic. */ +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_without_gc(const void *orig_ptr, size_t x, size_t y, size_t z) +rb_darray_realloc_mul_add(void *orig_ptr, size_t capa, size_t element_size, size_t header_size) { - size_t size = (x * y) + z; + 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 = realloc((void *)orig_ptr, size); - if (ptr == NULL) rb_bug("rb_darray_realloc_mul_add_without_gc: failed"); + void *ptr = ruby_xrealloc_sized(orig_ptr, size, old_size); + RUBY_ASSERT(ptr != NULL); return ptr; } -/* Internal function. Returns the next power of two that is greater than or - * equal to n. */ -static inline size_t -rb_darray_next_power_of_two(size_t n) +/* 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) { - return (size_t)(1 << (64 - nlz_int64(n))); + 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)(const void *, size_t, size_t, size_t)) + 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; @@ -196,7 +245,7 @@ rb_darray_resize_capa_impl(void *ptr_to_ary, size_t new_capa, size_t header_size new_ary->size = 0; } - assert(new_ary->size <= new_capa); + RUBY_ASSERT(new_ary->size <= new_capa); new_ary->capa = new_capa; @@ -210,7 +259,7 @@ rb_darray_resize_capa_impl(void *ptr_to_ary, size_t new_capa, size_t header_size // 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)(const void *, size_t, size_t, size_t)) + 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; |