1 #ifndef ARRAY_H
2 #define ARRAY_H
3
4 /* Array is a buffer accessible using fixed size elements. As long as the
5 compiler provides a typeof() operator, the array provides type safety. If
6 a wrong type is tried to be added to the array, or if the array's contents
7 are tried to be used using a wrong type, the compiler will give a warning.
8
9 Example usage:
10
11 struct foo {
12 ARRAY(struct bar) bars;
13 ...
14 };
15
16 i_array_init(&foo->bars, 10);
17
18 struct bar *bar = array_idx(&foo->bars, 5);
19 struct baz *baz = array_idx(&foo->bars, 5); // compiler warning
20
21 If you want to pass an array as a parameter to a function, you'll need to
22 create a type for the array using ARRAY_DEFINE_TYPE() and use the type in
23 the parameter using ARRAY_TYPE(). Any arrays that you want to be passing
24 around, such as structure members as in the above example, must also be
25 defined using ARRAY_TYPE() too, rather than ARRAY().
26
27 Example:
28
29 ARRAY_DEFINE_TYPE(foo, struct foo);
30 void do_foo(ARRAY_TYPE(foo) *foos) {
31 struct foo *foo = array_idx(foos, 0);
32 }
33 struct foo_manager {
34 ARRAY_TYPE(foo) foos; // pedantically, ARRAY(struct foo) is a different type
35 };
36 // ...
37 do_foo(&my_foo_manager->foos); // No compiler warning about mismatched types
38
39 */
40 #include "array-decl.h"
41 #include "buffer.h"
42
43 #define p_array_init(array, pool, init_count) \
44 array_create(array, pool, sizeof(**(array)->v), init_count)
45 #define i_array_init(array, init_count) \
46 p_array_init(array, default_pool, init_count)
47 #define t_array_init(array, init_count) \
48 p_array_init(array, pool_datastack_create(), init_count)
49
50 #ifdef HAVE_TYPEOF
51 # define ARRAY_TYPE_CAST_CONST(array) \
52 (typeof(*(array)->v))
53 # define ARRAY_TYPE_CAST_MODIFIABLE(array) \
54 (typeof(*(array)->v_modifiable))
55 # define ARRAY_TYPE_CHECK(array, data) \
56 COMPILE_ERROR_IF_TYPES_NOT_COMPATIBLE( \
57 **(array)->v_modifiable, *(data))
58 # define ARRAY_TYPES_CHECK(array1, array2) \
59 COMPILE_ERROR_IF_TYPES_NOT_COMPATIBLE( \
60 **(array1)->v_modifiable, **(array2)->v_modifiable)
61
62 #else
63 # define ARRAY_TYPE_CAST_CONST(array)
64 # define ARRAY_TYPE_CAST_MODIFIABLE(array)
65 # define ARRAY_TYPE_CHECK(array, data) 0
66 # define ARRAY_TYPES_CHECK(array1, array2) 0
67 #endif
68
69 /* Usage:
70 ARRAY(struct foo) foo_arr;
71 struct foo *foo;
72
73 array_foreach(&foo_arr, foo) {
74 ..
75 }
76
77 Note that deleting an element while iterating will cause the iteration to
78 skip over the next element. So deleting a single element and breaking out
79 of the loop is fine, but continuing the loop is likely a bug. Use
80 array_foreach_reverse() instead when deleting multiple elements.
81 */
82 #define array_foreach(array, elem) \
83 for (const void *elem ## __foreach_end = \
84 (const char *)(elem = *(array)->v) + (array)->arr.buffer->used; \
85 elem != elem ## __foreach_end; (elem)++)
86 #define array_foreach_modifiable(array, elem) \
87 for (const void *elem ## _end = \
88 (const char *)(elem = ARRAY_TYPE_CAST_MODIFIABLE(array) \
89 buffer_get_modifiable_data((array)->arr.buffer, NULL)) + \
90 (array)->arr.buffer->used; \
91 elem != elem ## _end; (elem)++)
92
93 /* Iterate the array in reverse order. */
94 #define array_foreach_reverse(array, elem) \
95 for (elem = CONST_PTR_OFFSET(*(array)->v, (array)->arr.buffer->used); \
96 (const char *)(elem--) > (const char *)*(array)->v; )
97 #define array_foreach_reverse_modifiable(array, elem) \
98 for (elem = ARRAY_TYPE_CAST_MODIFIABLE(array) \
99 ((char *)buffer_get_modifiable_data((array)->arr.buffer, NULL) + \
100 (array)->arr.buffer->used); \
101 (const char *)(elem--) > (const char *)*(array)->v; )
102
103 /* Usage:
104 ARRAY(struct foo *) foo_ptrs_arr;
105 struct foo *foo;
106
107 array_foreach_elem(&foo_ptrs_arr, foo) {
108 ..
109 } */
110 #define array_foreach_elem(array, elem) \
111 for (const void *_foreach_end = \
112 CONST_PTR_OFFSET(*(array)->v, (array)->arr.buffer->used), \
113 *_foreach_ptr = CONST_PTR_OFFSET(*(array)->v, ARRAY_TYPE_CHECK(array, &elem) + \
114 COMPILE_ERROR_IF_TRUE(sizeof(elem) > sizeof(void *))) \
115 ; \
116 (_foreach_ptr != _foreach_end && \
117 (memcpy(&elem, _foreach_ptr, sizeof(elem)), TRUE)) \
118 ; \
119 _foreach_ptr = CONST_PTR_OFFSET(_foreach_ptr, sizeof(elem)))
120
121
122 #define array_ptr_to_idx(array, elem) \
123 ((elem) - (array)->v[0])
124 /* Return index of iterated element inside array_foreach() or
125 array_foreach_modifiable() loop. Note that this doesn't work inside
126 array_foreach_elem() loop. */
127 #define array_foreach_idx(array, elem) \
128 array_ptr_to_idx(array, elem)
129
130 static inline void
array_create_from_buffer_i(struct array * array,buffer_t * buffer,size_t element_size)131 array_create_from_buffer_i(struct array *array, buffer_t *buffer,
132 size_t element_size)
133 {
134 array->buffer = buffer;
135 array->element_size = element_size;
136 }
137 #define array_create_from_buffer(array, buffer, element_size) \
138 array_create_from_buffer_i(&(array)->arr, buffer, element_size)
139
140 static inline void
array_create_i(struct array * array,pool_t pool,size_t element_size,unsigned int init_count)141 array_create_i(struct array *array, pool_t pool,
142 size_t element_size, unsigned int init_count)
143 {
144 buffer_t *buffer;
145
146 buffer = buffer_create_dynamic_max(pool, init_count * element_size,
147 SIZE_MAX / element_size < UINT_MAX ? SIZE_MAX :
148 UINT_MAX * element_size);
149 array_create_from_buffer_i(array, buffer, element_size);
150 }
151 #define array_create(array, pool, element_size, init_count) \
152 array_create_i(&(array)->arr, pool, element_size, init_count)
153
154 static inline void
array_free_i(struct array * array)155 array_free_i(struct array *array)
156 {
157 buffer_free(&array->buffer);
158 }
159 #define array_free(array) \
160 array_free_i(&(array)->arr)
161
162 static inline void * ATTR_WARN_UNUSED_RESULT
array_free_without_data_i(struct array * array)163 array_free_without_data_i(struct array *array)
164 {
165 return buffer_free_without_data(&array->buffer);
166 }
167 #define array_free_without_data(array) \
168 ARRAY_TYPE_CAST_MODIFIABLE(array)array_free_without_data_i(&(array)->arr)
169
170 static inline bool
array_is_created_i(const struct array * array)171 array_is_created_i(const struct array *array)
172 {
173 return array->buffer != NULL;
174 }
175 #define array_is_created(array) \
176 array_is_created_i(&(array)->arr)
177
178 static inline pool_t ATTR_PURE
array_get_pool_i(struct array * array)179 array_get_pool_i(struct array *array)
180 {
181 return buffer_get_pool(array->buffer);
182 }
183 #define array_get_pool(array) \
184 array_get_pool_i(&(array)->arr)
185
186 static inline void
array_clear_i(struct array * array)187 array_clear_i(struct array *array)
188 {
189 buffer_set_used_size(array->buffer, 0);
190 }
191 #define array_clear(array) \
192 array_clear_i(&(array)->arr)
193
194 static inline unsigned int ATTR_PURE
array_count_i(const struct array * array)195 array_count_i(const struct array *array)
196 {
197 return array->buffer->used / array->element_size;
198 }
199 #define array_count(array) \
200 array_count_i(&(array)->arr)
201 /* No need for the real count if all we're doing is comparing against 0 */
202 #define array_is_empty(array) \
203 ((array)->arr.buffer->used == 0)
204 #define array_not_empty(array) \
205 ((array)->arr.buffer->used > 0)
206
207 static inline void
array_append_i(struct array * array,const void * data,unsigned int count)208 array_append_i(struct array *array, const void *data, unsigned int count)
209 {
210 buffer_append(array->buffer, data, count * array->element_size);
211 }
212
213 #define array_append(array, data, count) \
214 TYPE_CHECKS(void, ARRAY_TYPE_CHECK(array, data), \
215 array_append_i(&(array)->arr, data, count))
216
217 static inline void
array_append_array_i(struct array * dest_array,const struct array * src_array)218 array_append_array_i(struct array *dest_array, const struct array *src_array)
219 {
220 i_assert(dest_array->element_size == src_array->element_size);
221 buffer_append_buf(dest_array->buffer, src_array->buffer, 0, SIZE_MAX);
222 }
223 #define array_append_array(dest_array, src_array) \
224 TYPE_CHECKS(void, ARRAY_TYPES_CHECK(dest_array, src_array), \
225 array_append_array_i(&(dest_array)->arr, &(src_array)->arr))
226
227 static inline void
array_insert_i(struct array * array,unsigned int idx,const void * data,unsigned int count)228 array_insert_i(struct array *array, unsigned int idx,
229 const void *data, unsigned int count)
230 {
231 buffer_insert(array->buffer, idx * array->element_size,
232 data, count * array->element_size);
233 }
234
235 #define array_insert(array, idx, data, count) \
236 TYPE_CHECKS(void, ARRAY_TYPE_CHECK(array, data), \
237 array_insert_i(&(array)->arr, idx, data, count))
238
239 static inline void
array_delete_i(struct array * array,unsigned int idx,unsigned int count)240 array_delete_i(struct array *array, unsigned int idx, unsigned int count)
241 {
242 buffer_delete(array->buffer, idx * array->element_size,
243 count * array->element_size);
244 }
245 #define array_delete(array, idx, count) \
246 array_delete_i(&(array)->arr, idx, count)
247
248 static inline const void *
array_get_i(const struct array * array,unsigned int * count_r)249 array_get_i(const struct array *array, unsigned int *count_r)
250 {
251 *count_r = array_count_i(array);
252 return array->buffer->data;
253 }
254 #define array_get(array, count) \
255 ARRAY_TYPE_CAST_CONST(array)array_get_i(&(array)->arr, count)
256
257 /* Re: i_assert() vs. pure: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=51971#c1 */
258 static inline const void * ATTR_PURE
array_idx_i(const struct array * array,unsigned int idx)259 array_idx_i(const struct array *array, unsigned int idx)
260 {
261 i_assert(idx < array->buffer->used / array->element_size);
262 return CONST_PTR_OFFSET(array->buffer->data, idx * array->element_size);
263 }
264
265 #define array_front(array) array_idx(array, 0)
266 #define array_front_modifiable(array) array_idx_modifiable(array, 0)
267 #define array_back(array) array_idx(array, array_count(array)-1)
268 #define array_back_modifiable(array) array_idx_modifiable(array, array_count(array)-1)
269 #define array_pop_back(array) array_delete(array, array_count(array)-1, 1);
270 #define array_push_back(array, item) array_append(array, (item), 1)
271 #define array_pop_front(array) array_delete(array, 0, 1)
272 #define array_push_front(array, item) array_insert(array, 0, (item), 1)
273
274 #define array_idx(array, idx) \
275 ARRAY_TYPE_CAST_CONST(array)array_idx_i(&(array)->arr, idx)
276 /* Using *array_idx() will fail if the compiler doesn't support typeof().
277 The same can be done with array_idx_elem() for arrays that have pointers. */
278 #ifdef HAVE_TYPEOF
279 # define array_idx_elem(array, idx) \
280 (TRUE ? *array_idx(array, idx) : \
281 COMPILE_ERROR_IF_TRUE(sizeof(**(array)->v) != sizeof(void *)))
282 #else
283 # define array_idx_elem(array, idx) \
284 (*(void **)array_idx_i(&(array)->arr, idx))
285 #endif
286
287 static inline void *
array_get_modifiable_i(struct array * array,unsigned int * count_r)288 array_get_modifiable_i(struct array *array, unsigned int *count_r)
289 {
290 *count_r = array_count_i(array);
291 return buffer_get_modifiable_data(array->buffer, NULL);
292 }
293 #define array_get_modifiable(array, count) \
294 ARRAY_TYPE_CAST_MODIFIABLE(array) \
295 array_get_modifiable_i(&(array)->arr, count)
296
297 void *
298 array_idx_modifiable_i(const struct array *array, unsigned int idx) ATTR_PURE;
299 #define array_idx_modifiable(array, idx) \
300 ARRAY_TYPE_CAST_MODIFIABLE(array) \
301 array_idx_modifiable_i(&(array)->arr, idx)
302
303 void *array_idx_get_space_i(struct array *array, unsigned int idx);
304 #define array_idx_get_space(array, idx) \
305 ARRAY_TYPE_CAST_MODIFIABLE(array) \
306 array_idx_get_space_i(&(array)->arr, idx)
307
308 void array_idx_set_i(struct array *array, unsigned int idx, const void *data);
309 #define array_idx_set(array, idx, data) \
310 TYPE_CHECKS(void, ARRAY_TYPE_CHECK(array, data), \
311 array_idx_set_i(&(array)->arr, idx, data))
312
313 void array_idx_clear_i(struct array *array, unsigned int idx);
314 #define array_idx_clear(array, idx) \
315 array_idx_clear_i(&(array)->arr, idx)
316
317 static inline void *
array_append_space_i(struct array * array)318 array_append_space_i(struct array *array)
319 {
320 void *data;
321
322 data = buffer_append_space_unsafe(array->buffer, array->element_size);
323 memset(data, 0, array->element_size);
324 return data;
325 }
326 #define array_append_space(array) \
327 ARRAY_TYPE_CAST_MODIFIABLE(array)array_append_space_i(&(array)->arr)
328 #define array_append_zero(array) \
329 (void)array_append_space_i(&(array)->arr)
330
331 void *array_insert_space_i(struct array *array, unsigned int idx);
332 #define array_insert_space(array, idx) \
333 ARRAY_TYPE_CAST_MODIFIABLE(array) \
334 array_insert_space_i(&(array)->arr, idx)
335
336 static inline void
array_copy(struct array * dest,unsigned int dest_idx,const struct array * src,unsigned int src_idx,unsigned int count)337 array_copy(struct array *dest, unsigned int dest_idx,
338 const struct array *src, unsigned int src_idx, unsigned int count)
339 {
340 i_assert(dest->element_size == src->element_size);
341
342 buffer_copy(dest->buffer, dest_idx * dest->element_size,
343 src->buffer, src_idx * src->element_size,
344 count * dest->element_size);
345 }
346
347 bool array_cmp_i(const struct array *array1,
348 const struct array *array2) ATTR_PURE;
349 #define array_cmp(array1, array2) \
350 array_cmp_i(&(array1)->arr, &(array2)->arr)
351
352 /* Test equality via a comparator */
353 bool array_equal_fn_i(const struct array *array1,
354 const struct array *array2,
355 int (*cmp)(const void*, const void *)) ATTR_PURE;
356 #define array_equal_fn(array1, array2, cmp) \
357 TYPE_CHECKS(bool, \
358 ARRAY_TYPES_CHECK(array1, array2) || \
359 CALLBACK_TYPECHECK(cmp, int (*)(typeof(*(array1)->v), \
360 typeof(*(array2)->v))), \
361 array_equal_fn_i(&(array1)->arr, &(array2)->arr, \
362 (int (*)(const void *, const void *))cmp))
363 bool array_equal_fn_ctx_i(const struct array *array1,
364 const struct array *array2,
365 int (*cmp)(const void*, const void *, const void *),
366 const void *context) ATTR_PURE;
367 /* Same, but with a context pointer.
368 context can't be void* as ``const typeof(context)'' won't compile,
369 so ``const typeof(*context)*'' is required instead, and that requires a
370 complete type. */
371 #define array_equal_fn_ctx(array1, array2, cmp, ctx) \
372 TYPE_CHECKS(bool, \
373 ARRAY_TYPES_CHECK(array1, array2) || \
374 CALLBACK_TYPECHECK(cmp, int (*)(typeof(*(array1)->v), \
375 typeof(*(array2)->v), \
376 const typeof(*ctx)*)), \
377 array_equal_fn_ctx_i(&(array1)->arr, &(array2)->arr, \
378 (int (*)(const void *, const void *, const void *))cmp, ctx))
379
380 void array_reverse_i(struct array *array);
381 #define array_reverse(array) \
382 array_reverse_i(&(array)->arr)
383
384 void array_sort_i(struct array *array, int (*cmp)(const void *, const void *));
385 #define array_sort(array, cmp) \
386 TYPE_CHECKS(void, \
387 CALLBACK_TYPECHECK(cmp, int (*)(typeof(*(array)->v), \
388 typeof(*(array)->v))), \
389 array_sort_i(&(array)->arr, (int (*)(const void *, const void *))cmp))
390
391 void *array_bsearch_i(struct array *array, const void *key,
392 int (*cmp)(const void *, const void *));
393 #define array_bsearch(array, key, cmp) \
394 TYPE_CHECKS(void *, \
395 CALLBACK_TYPECHECK(cmp, int (*)(typeof(const typeof(*key) *), \
396 typeof(*(array)->v))), \
397 ARRAY_TYPE_CAST_MODIFIABLE(array)array_bsearch_i(&(array)->arr, \
398 (const void *)key, (int (*)(const void *, const void *))cmp))
399
400 /* Returns pointer to first element for which cmp(key,elem)==0, or NULL */
401 const void *array_lsearch_i(const struct array *array, const void *key,
402 int (*cmp)(const void *, const void *));
array_lsearch_modifiable_i(struct array * array,const void * key,int (* cmp)(const void *,const void *))403 static inline void *array_lsearch_modifiable_i(struct array *array, const void *key,
404 int (*cmp)(const void *, const void *))
405 {
406 return (void *)array_lsearch_i(array, key, cmp);
407 }
408 #define ARRAY_LSEARCH_CALL(modifiable, array, key, cmp) \
409 TYPE_CHECKS(void *, \
410 CALLBACK_TYPECHECK(cmp, int (*)(typeof(const typeof(*key) *), \
411 typeof(*(array)->v))), \
412 array_lsearch##modifiable##i( \
413 &(array)->arr, (const void *)key, \
414 (int (*)(const void *, const void *))cmp))
415 #define array_lsearch(array, key, cmp) \
416 ARRAY_TYPE_CAST_CONST(array)ARRAY_LSEARCH_CALL(_, array, key, cmp)
417 #define array_lsearch_modifiable(array, key, cmp) \
418 ARRAY_TYPE_CAST_MODIFIABLE(array)ARRAY_LSEARCH_CALL(_modifiable_, array, key, cmp)
419
420 #endif
421