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 //      if (!rb_darray_append(&char_array, 'e')) abort();
  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, int32_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, int32_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, int32_t idx);
  37 //
  38 #define rb_darray_ref(ary, idx) (&((ary)->data[(idx)]))
  39
  40 // Copy a new element into the array. Return 1 on success and 0 on failure.
  41 // ptr_to_ary is evaluated multiple times.
  42 //
  43 // bool rb_darray_append(rb_darray(T) *ptr_to_ary, T element);
  44 //
  45 #define rb_darray_append(ptr_to_ary, element) (   \
  46     rb_darray_ensure_space((ptr_to_ary), sizeof(**(ptr_to_ary)), sizeof((*(ptr_to_ary))->data[0])) ? ( \
  47         rb_darray_set(*(ptr_to_ary),              \
  48                       (*(ptr_to_ary))->meta.size, \
  49                       (element)),                 \
  50         ++((*(ptr_to_ary))->meta.size),           \
  51         1                                         \
  52     ) : 0)
  53
  54 // Last element of the array
  55 //
  56 #define rb_darray_back(ary) ((ary)->data[(ary)->meta.size - 1])
  57
  58 // Remove the last element of the array.
  59 //
  60 #define rb_darray_pop_back(ary) ((ary)->meta.size--)
  61
  62 // Remove element at idx and replace it by the last element
  63 #define rb_darray_remove_unordered(ary, idx) do {   \
  64     rb_darray_set(ary, idx, rb_darray_back(ary));   \
  65     rb_darray_pop_back(ary);                        \
  66 } while (0);
  67
  68 // Iterate over items of the array in a for loop
  69 //
  70 #define rb_darray_foreach(ary, idx_name, elem_ptr_var) \
  71     for (int idx_name = 0; idx_name < rb_darray_size(ary) && ((elem_ptr_var) = rb_darray_ref(ary, idx_name)); ++idx_name)
  72
  73 // Iterate over valid indicies in the array in a for loop
  74 //
  75 #define rb_darray_for(ary, idx_name) \
  76     for (int idx_name = 0; idx_name < rb_darray_size(ary); ++idx_name)
  77
  78 // Make a dynamic array of a certain size. All bytes backing the elements are set to zero.
  79 // Return 1 on success and 0 on failure.
  80 //
  81 // Note that NULL is a valid empty dynamic array.
  82 //
  83 // bool rb_darray_make(rb_darray(T) *ptr_to_ary, int32_t size);
  84 //
  85 #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]))
  86
  87 // Set the size of the array to zero without freeing the backing memory.
  88 // Allows reusing the same array.
  89 //
  90 #define rb_darray_clear(ary) (ary->meta.size = 0)
  91
  92 typedef struct rb_darray_meta {
  93     int32_t size;
  94     int32_t capa;
  95 } rb_darray_meta_t;
  96
  97 // Get the size of the dynamic array.
  98 //
  99 static inline int32_t
 100 rb_darray_size(const void *ary)
 101 {
 102     const rb_darray_meta_t *meta = ary;
 103     return meta ? meta->size : 0;
 104 }
 105
 106 // Get the capacity of the dynamic array.
 107 //
 108 static inline int32_t
 109 rb_darray_capa(const void *ary)
 110 {
 111     const rb_darray_meta_t *meta = ary;
 112     return meta ? meta->capa : 0;
 113 }
 114
 115 // Free the dynamic array.
 116 //
 117 static inline void
 118 rb_darray_free(void *ary)
 119 {
 120     free(ary);
 121 }
 122
 123 // Internal function. Calculate buffer size on malloc heap.
 124 static inline size_t
 125 rb_darray_buffer_size(int32_t capacity, size_t header_size, size_t element_size)
 126 {
 127     if (capacity == 0) return 0;
 128     return header_size + (size_t)capacity * element_size;
 129 }
 130
 131 // Internal function
 132 // Ensure there is space for one more element. Return 1 on success and 0 on failure.
 133 // Note: header_size can be bigger than sizeof(rb_darray_meta_t) when T is __int128_t, for example.
 134 static inline int
 135 rb_darray_ensure_space(void *ptr_to_ary, size_t header_size, size_t element_size)
 136 {
 137     rb_darray_meta_t **ptr_to_ptr_to_meta = ptr_to_ary;
 138     rb_darray_meta_t *meta = *ptr_to_ptr_to_meta;
 139     int32_t current_capa = rb_darray_capa(meta);
 140     if (rb_darray_size(meta) < current_capa) return 1;
 141
 142     int32_t new_capa;
 143     // Calculate new capacity
 144     if (current_capa == 0) {
 145         new_capa = 1;
 146     }
 147     else {
 148         int64_t doubled = 2 * (int64_t)current_capa;
 149         new_capa = (int32_t)doubled;
 150         if (new_capa != doubled) return 0;
 151     }
 152
 153     // Calculate new buffer size
 154     size_t current_buffer_size = rb_darray_buffer_size(current_capa, header_size, element_size);
 155     size_t new_buffer_size = rb_darray_buffer_size(new_capa, header_size, element_size);
 156     if (new_buffer_size <= current_buffer_size) return 0;
 157
 158     rb_darray_meta_t *doubled_ary = realloc(meta, new_buffer_size);
 159     if (!doubled_ary) return 0;
 160
 161     if (meta == NULL) {
 162         // First allocation. Initialize size. On subsequence allocations
 163         // realloc takes care of carrying over the size.
 164         doubled_ary->size = 0;
 165     }
 166
 167     doubled_ary->capa = new_capa;
 168
 169     // We don't have access to the type of the dynamic array in function context.
 170     // Write out result with memcpy to avoid strict aliasing issue.
 171     memcpy(ptr_to_ary, &doubled_ary, sizeof(doubled_ary));
 172     return 1;
 173 }
 174
 175 static inline int
 176 rb_darray_make_impl(void *ptr_to_ary, int32_t array_size, size_t header_size, size_t element_size)
 177 {
 178     rb_darray_meta_t **ptr_to_ptr_to_meta = ptr_to_ary;
 179     if (array_size < 0) return 0;
 180     if (array_size == 0) {
 181         *ptr_to_ptr_to_meta = NULL;
 182         return 1;
 183     }
 184
 185     size_t buffer_size = rb_darray_buffer_size(array_size, header_size, element_size);
 186     rb_darray_meta_t *meta = calloc(buffer_size, 1);
 187     if (!meta) return 0;
 188
 189     meta->size = array_size;
 190     meta->capa = array_size;
 191
 192     // We don't have access to the type of the dynamic array in function context.
 193     // Write out result with memcpy to avoid strict aliasing issue.
 194     memcpy(ptr_to_ary, &meta, sizeof(meta));
 195     return 1;
 196 }
 197
 198 #endif /* RUBY_DARRAY_H */