1 files changed, 296 insertions, 0 deletions
diff --git a/darray.h b/darray.h
new file mode 100644
index 0000000000..10fd5e4ccc
--- /dev/null
+++ b/darray.h
@@ -0,0 +1,296 @@
+#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)
+
+/* Removes the element at idx and replaces it with the last element.
+ * ptr_to_ary and idx is evaluated multiple times.
+ * Warning: not bounds checked.
+ *
+ * void rb_darray_swap_remove(rb_darray(T) *ptr_to_ary, size_t idx);
+ */
+#define rb_darray_swap_remove(ptr_to_ary, idx) do { \
+    size_t _darray_size = rb_darray_size(*(ptr_to_ary)); \
+    if ((idx) != _darray_size - 1) { \
+        (*(ptr_to_ary))->data[idx] = (*(ptr_to_ary))->data[_darray_size - 1]; \
+    } \
+    (*(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_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;
+}
+
+/* Internal function. Like rb_xrealloc_mul_add. */
+static inline void *
+rb_darray_realloc_mul_add(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 = xrealloc(orig_ptr, 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 */