Ruby  3.1.4p223 (2023-03-30 revision HEAD)
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;
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 */