darray.h

   1 #ifndef RUBY_DARRAY_H
   2 #define RUBY_DARRAY_H
   3
   4 #include <stdint.h>
   5 #include <stddef.h>
   6 #include <stdlib.h>
   7
   8 // Type for a dynamic array. Use to declare a dynamic array.
   9 // It is a pointer so it fits in st_table nicely. Designed
  10 // to be fairly type-safe.
  11 //
  12 // NULL is a valid empty dynamic array.
  13 //
  14 // Example:
  15 //      rb_darray(char) char_array = NULL;
  16 //      rb_darray_append(&char_array, 'e');
  17 //      printf("pushed %c\n", *rb_darray_ref(char_array, 0));
  18 //      rb_darray_free(char_array);
  19 //
  20 #define rb_darray(T) struct { rb_darray_meta_t meta; T data[]; } *
  21
  22 // Copy an element out of the array. Warning: not bounds checked.
  23 //
  24 // T rb_darray_get(rb_darray(T) ary, size_t idx);
  25 //
  26 #define rb_darray_get(ary, idx) ((ary)->data[(idx)])
  27
  28 // Assign to an element. Warning: not bounds checked.
  29 //
  30 // void rb_darray_set(rb_darray(T) ary, size_t idx, T element);
  31 //
  32 #define rb_darray_set(ary, idx, element) ((ary)->data[(idx)] = (element))
  33
  34 // Get a pointer to an element. Warning: not bounds checked.
  35 //
  36 // T *rb_darray_ref(rb_darray(T) ary, size_t idx);
  37 //
  38 #define rb_darray_ref(ary, idx) (&((ary)->data[(idx)]))
  39
  40 /* Copy a new element into the array. ptr_to_ary is evaluated multiple times.
  41  *
  42  * void rb_darray_append(rb_darray(T) *ptr_to_ary, T element);
  43  */
  44 #define rb_darray_append(ptr_to_ary, element) \
  45     rb_darray_append_impl(ptr_to_ary, element, rb_darray_realloc_mul_add)
  46
  47 #define rb_darray_append_without_gc(ptr_to_ary, element) \
  48     rb_darray_append_impl(ptr_to_ary, element, rb_darray_realloc_mul_add_without_gc)
  49
  50 #define rb_darray_append_impl(ptr_to_ary, element, realloc_func) do {  \
  51     rb_darray_ensure_space((ptr_to_ary), \
  52                            sizeof(**(ptr_to_ary)), \
  53                            sizeof((*(ptr_to_ary))->data[0]), \
  54                            realloc_func); \
  55     rb_darray_set(*(ptr_to_ary), \
  56                   (*(ptr_to_ary))->meta.size, \
  57                   (element)); \
  58     (*(ptr_to_ary))->meta.size++; \
  59 } while (0)
  60
  61 #define rb_darray_insert_without_gc(ptr_to_ary, idx, element) do { \
  62     rb_darray_ensure_space((ptr_to_ary), \
  63                            sizeof(**(ptr_to_ary)), \
  64                            sizeof((*(ptr_to_ary))->data[0]), \
  65                            rb_darray_realloc_mul_add_without_gc); \
  66     MEMMOVE( \
  67         rb_darray_ref(*(ptr_to_ary), idx + 1), \
  68         rb_darray_ref(*(ptr_to_ary), idx), \
  69         (*(ptr_to_ary))->data[0], \
  70         rb_darray_size(*(ptr_to_ary)) - idx); \
  71     rb_darray_set(*(ptr_to_ary), idx, element); \
  72     (*(ptr_to_ary))->meta.size++; \
  73 } while (0)
  74
  75 // Iterate over items of the array in a for loop
  76 //
  77 #define rb_darray_foreach(ary, idx_name, elem_ptr_var) \
  78     for (size_t idx_name = 0; idx_name < rb_darray_size(ary) && ((elem_ptr_var) = rb_darray_ref(ary, idx_name)); ++idx_name)
  79
  80 // Iterate over valid indices in the array in a for loop
  81 //
  82 #define rb_darray_for(ary, idx_name) \
  83     for (size_t idx_name = 0; idx_name < rb_darray_size(ary); ++idx_name)
  84
  85 /* Make a dynamic array of a certain size. All bytes backing the elements are set to zero.
  86  * Return 1 on success and 0 on failure.
  87  *
  88  * Note that NULL is a valid empty dynamic array.
  89  *
  90  * void rb_darray_make(rb_darray(T) *ptr_to_ary, size_t size);
  91  */
  92 #define rb_darray_make(ptr_to_ary, size) \
  93     rb_darray_make_impl((ptr_to_ary), size, sizeof(**(ptr_to_ary)), \
  94                          sizeof((*(ptr_to_ary))->data[0]), rb_darray_calloc_mul_add)
  95
  96 #define rb_darray_make_without_gc(ptr_to_ary, size) \
  97     rb_darray_make_impl((ptr_to_ary), size, sizeof(**(ptr_to_ary)), \
  98                         sizeof((*(ptr_to_ary))->data[0]), rb_darray_calloc_mul_add_without_gc)
  99
 100 /* Resize the darray to a new capacity. The new capacity must be greater than
 101  * or equal to the size of the darray.
 102  *
 103  * void rb_darray_resize_capa(rb_darray(T) *ptr_to_ary, size_t capa);
 104  */
 105 #define rb_darray_resize_capa_without_gc(ptr_to_ary, capa) \
 106     rb_darray_resize_capa_impl((ptr_to_ary), capa, sizeof(**(ptr_to_ary)), \
 107                                sizeof((*(ptr_to_ary))->data[0]), rb_darray_realloc_mul_add_without_gc)
 108
 109 #define rb_darray_data_ptr(ary) ((ary)->data)
 110
 111 typedef struct rb_darray_meta {
 112     size_t size;
 113     size_t capa;
 114 } rb_darray_meta_t;
 115
 116 /* Set the size of the array to zero without freeing the backing memory.
 117  * Allows reusing the same array. */
 118 static inline void
 119 rb_darray_clear(void *ary)
 120 {
 121     rb_darray_meta_t *meta = ary;
 122     if (meta) {
 123         meta->size = 0;
 124     }
 125 }
 126
 127 // Get the size of the dynamic array.
 128 //
 129 static inline size_t
 130 rb_darray_size(const void *ary)
 131 {
 132     const rb_darray_meta_t *meta = ary;
 133     return meta ? meta->size : 0;
 134 }
 135
 136
 137 static inline void
 138 rb_darray_pop(void *ary, size_t count)
 139 {
 140     rb_darray_meta_t *meta = ary;
 141     meta->size -= count;
 142 }
 143
 144 // Get the capacity of the dynamic array.
 145 //
 146 static inline size_t
 147 rb_darray_capa(const void *ary)
 148 {
 149     const rb_darray_meta_t *meta = ary;
 150     return meta ? meta->capa : 0;
 151 }
 152
 153 /* Free the dynamic array. */
 154 static inline void
 155 rb_darray_free(void *ary)
 156 {
 157     xfree(ary);
 158 }
 159
 160 static inline void
 161 rb_darray_free_without_gc(void *ary)
 162 {
 163     free(ary);
 164 }
 165
 166 /* Internal function. Like rb_xcalloc_mul_add. */
 167 static inline void *
 168 rb_darray_calloc_mul_add(size_t x, size_t y, size_t z)
 169 {
 170     size_t size = rbimpl_size_add_or_raise(rbimpl_size_mul_or_raise(x, y), z);
 171
 172     void *ptr = xcalloc(1, size);
 173     RUBY_ASSERT(ptr != NULL);
 174
 175     return ptr;
 176 }
 177
 178 /* Internal function. Like rb_xcalloc_mul_add but does not trigger GC. */
 179 static inline void *
 180 rb_darray_calloc_mul_add_without_gc(size_t x, size_t y, size_t z)
 181 {
 182     size_t size = rbimpl_size_add_or_raise(rbimpl_size_mul_or_raise(x, y), z);
 183
 184     void *ptr = calloc(1, size);
 185     if (ptr == NULL) rb_bug("rb_darray_calloc_mul_add_without_gc: failed");
 186
 187     return ptr;
 188 }
 189
 190 /* Internal function. Like rb_xrealloc_mul_add. */
 191 static inline void *
 192 rb_darray_realloc_mul_add(void *orig_ptr, size_t x, size_t y, size_t z)
 193 {
 194     size_t size = rbimpl_size_add_or_raise(rbimpl_size_mul_or_raise(x, y), z);
 195
 196     void *ptr = xrealloc(orig_ptr, size);
 197     RUBY_ASSERT(ptr != NULL);
 198
 199     return ptr;
 200 }
 201
 202 /* Internal function. Like rb_xrealloc_mul_add but does not trigger GC. */
 203 static inline void *
 204 rb_darray_realloc_mul_add_without_gc(void *orig_ptr, size_t x, size_t y, size_t z)
 205 {
 206     size_t size = rbimpl_size_add_or_raise(rbimpl_size_mul_or_raise(x, y), z);
 207
 208     void *ptr = realloc(orig_ptr, size);
 209     if (ptr == NULL) rb_bug("rb_darray_realloc_mul_add_without_gc: failed");
 210
 211     return ptr;
 212 }
 213
 214 /* Internal function. Resizes the capacity of a darray. The new capacity must
 215  * be greater than or equal to the size of the darray. */
 216 static inline void
 217 rb_darray_resize_capa_impl(void *ptr_to_ary, size_t new_capa, size_t header_size, size_t element_size,
 218                            void *(*realloc_mul_add_impl)(void *, size_t, size_t, size_t))
 219 {
 220     rb_darray_meta_t **ptr_to_ptr_to_meta = ptr_to_ary;
 221     rb_darray_meta_t *meta = *ptr_to_ptr_to_meta;
 222
 223     rb_darray_meta_t *new_ary = realloc_mul_add_impl(meta, new_capa, element_size, header_size);
 224
 225     if (meta == NULL) {
 226         /* First allocation. Initialize size. On subsequence allocations
 227          * realloc takes care of carrying over the size. */
 228         new_ary->size = 0;
 229     }
 230
 231     RUBY_ASSERT(new_ary->size <= new_capa);
 232
 233     new_ary->capa = new_capa;
 234
 235     // We don't have access to the type of the dynamic array in function context.
 236     // Write out result with memcpy to avoid strict aliasing issue.
 237     memcpy(ptr_to_ary, &new_ary, sizeof(new_ary));
 238 }
 239
 240 // Internal function
 241 // Ensure there is space for one more element.
 242 // Note: header_size can be bigger than sizeof(rb_darray_meta_t) when T is __int128_t, for example.
 243 static inline void
 244 rb_darray_ensure_space(void *ptr_to_ary, size_t header_size, size_t element_size,
 245                        void *(*realloc_mul_add_impl)(void *, size_t, size_t, size_t))
 246 {
 247     rb_darray_meta_t **ptr_to_ptr_to_meta = ptr_to_ary;
 248     rb_darray_meta_t *meta = *ptr_to_ptr_to_meta;
 249     size_t current_capa = rb_darray_capa(meta);
 250     if (rb_darray_size(meta) < current_capa) return;
 251
 252     // Double the capacity
 253     size_t new_capa = current_capa == 0 ? 1 : current_capa * 2;
 254
 255     rb_darray_resize_capa_impl(ptr_to_ary, new_capa, header_size, element_size, realloc_mul_add_impl);
 256 }
 257
 258 static inline void
 259 rb_darray_make_impl(void *ptr_to_ary, size_t array_size, size_t header_size, size_t element_size,
 260                     void *(*calloc_mul_add_impl)(size_t, size_t, size_t))
 261 {
 262     rb_darray_meta_t **ptr_to_ptr_to_meta = ptr_to_ary;
 263     if (array_size == 0) {
 264         *ptr_to_ptr_to_meta = NULL;
 265         return;
 266     }
 267
 268     rb_darray_meta_t *meta = calloc_mul_add_impl(array_size, element_size, header_size);
 269
 270     meta->size = array_size;
 271     meta->capa = array_size;
 272
 273     // We don't have access to the type of the dynamic array in function context.
 274     // Write out result with memcpy to avoid strict aliasing issue.
 275     memcpy(ptr_to_ary, &meta, sizeof(meta));
 276 }
 277
 278 #endif /* RUBY_DARRAY_H */