8d80659e504ffb34bb0c6a633184fece35751b18Timo Sirainen/* Array is a buffer accessible using fixed size elements. As long as the
887e05e03f83735acd5479be563193b3c2584d91Phil Carmody compiler provides a typeof() operator, the array provides type safety. If
8d80659e504ffb34bb0c6a633184fece35751b18Timo Sirainen a wrong type is tried to be added to the array, or if the array's contents
8d80659e504ffb34bb0c6a633184fece35751b18Timo Sirainen are tried to be used using a wrong type, the compiler will give a warning.
30972f343b285b6214ea053e1939b92cfe79040cTimo Sirainen Example usage:
4ee00532a265bdfb38539d811fcd12d51210ac35Timo Sirainen ARRAY(struct bar) bars;
91dca97b367c54a139c268b56a0c67f564bd9197Timo Sirainen i_array_init(&foo->bars, 10);
bd3714d623d67f7dc8bd70ba39b467762ae409e8Timo Sirainen struct bar *bar = array_idx(&foo->bars, 5);
bd3714d623d67f7dc8bd70ba39b467762ae409e8Timo Sirainen struct baz *baz = array_idx(&foo->bars, 5); // compiler warning
8d80659e504ffb34bb0c6a633184fece35751b18Timo Sirainen If you want to pass an array as a parameter to a function, you'll need to
8d80659e504ffb34bb0c6a633184fece35751b18Timo Sirainen create a type for the array using ARRAY_DEFINE_TYPE() and use the type in
fe08c73b0bf87bfa3bfb2d3df5dc9845113e0cf3Phil Carmody the parameter using ARRAY_TYPE(). Any arrays that you want to be passing
fe08c73b0bf87bfa3bfb2d3df5dc9845113e0cf3Phil Carmody around, such as structure members as in the above example, must also be
fe08c73b0bf87bfa3bfb2d3df5dc9845113e0cf3Phil Carmody defined using ARRAY_TYPE() too, rather than ARRAY().
8d80659e504ffb34bb0c6a633184fece35751b18Timo Sirainen ARRAY_DEFINE_TYPE(foo, struct foo);
fe08c73b0bf87bfa3bfb2d3df5dc9845113e0cf3Phil Carmody void do_foo(ARRAY_TYPE(foo) *foos) {
fe08c73b0bf87bfa3bfb2d3df5dc9845113e0cf3Phil Carmody struct foo *foo = array_idx(foos, 0);
fe08c73b0bf87bfa3bfb2d3df5dc9845113e0cf3Phil Carmody struct foo_manager {
fe08c73b0bf87bfa3bfb2d3df5dc9845113e0cf3Phil Carmody ARRAY_TYPE(foo) foos; // pedantically, ARRAY(struct foo) is a different type
fe08c73b0bf87bfa3bfb2d3df5dc9845113e0cf3Phil Carmody do_foo(&my_foo_manager->foos); // No compiler warning about mismatched types
91dca97b367c54a139c268b56a0c67f564bd9197Timo Sirainen#define p_array_init(array, pool, init_count) \
11a29a16c8b41ad7c057420e53963a4595adc33dTimo Sirainen array_create(array, pool, sizeof(**(array)->v), init_count)
91dca97b367c54a139c268b56a0c67f564bd9197Timo Sirainen p_array_init(array, pool_datastack_create(), init_count)
0f111ddfcb893d75a79bb60942c77d97e15f6b99Phil Carmody **(array1)->v_modifiable, **(array2)->v_modifiable)
1df7543b209cabc208515c6bfc3b123f6ea184c2Timo Sirainen/* usage: struct foo *foo; array_foreach(foo_arr, foo) { .. } */
1df7543b209cabc208515c6bfc3b123f6ea184c2Timo Sirainen#if (defined(__STDC__) && __STDC_VERSION__ >= 199901L)
1df7543b209cabc208515c6bfc3b123f6ea184c2Timo Sirainen (const char *)(elem = *(array)->v) + (array)->arr.buffer->used; \
1df7543b209cabc208515c6bfc3b123f6ea184c2Timo Sirainen# define array_foreach_modifiable(array, elem) \
1df7543b209cabc208515c6bfc3b123f6ea184c2Timo Sirainen (const char *)(elem = ARRAY_TYPE_CAST_MODIFIABLE(array) \
1df7543b209cabc208515c6bfc3b123f6ea184c2Timo Sirainen buffer_get_modifiable_data((array)->arr.buffer, NULL)) + \
2d729323913a672708dc600242e1cc3085985dccPhil Carmody/* Bikeshed: which is better
2d729323913a672708dc600242e1cc3085985dccPhil Carmody array_foreach_elem(array, myvar) { ... use myvar ... } // not clear myvar is modified
2d729323913a672708dc600242e1cc3085985dccPhil Carmody array_foreach_elem(array, &myvar) { ... use myvar ... } // clearer, as more pass-by-referencey
2d729323913a672708dc600242e1cc3085985dccPhil Carmody Latter is impossible if we want to use the variable name as the base for the other variable names
2d729323913a672708dc600242e1cc3085985dccPhil Carmody for (unsigned int _foreach_offset = ARRAY_TYPE_CHECK(array, &elem) + \
2d729323913a672708dc600242e1cc3085985dccPhil Carmody (_foreach_offset < (array)->arr.buffer->used) && \
2d729323913a672708dc600242e1cc3085985dccPhil Carmody (memcpy(&elem, CONST_PTR_OFFSET(*(array)->v, _foreach_offset), sizeof(elem)), TRUE) \
1df7543b209cabc208515c6bfc3b123f6ea184c2Timo Sirainen elem != CONST_PTR_OFFSET(*(array)->v, (array)->arr.buffer->used); \
1df7543b209cabc208515c6bfc3b123f6ea184c2Timo Sirainen# define array_foreach_modifiable(array, elem) \
1df7543b209cabc208515c6bfc3b123f6ea184c2Timo Sirainen for (elem = ARRAY_TYPE_CAST_MODIFIABLE(array) \
548bf569f620a42a34dcddd95260d7da587b230eTimo Sirainen buffer_get_modifiable_data((array)->arr.buffer, NULL); \
1df7543b209cabc208515c6bfc3b123f6ea184c2Timo Sirainen elem != CONST_PTR_OFFSET(*(array)->v, (array)->arr.buffer->used); \
30972f343b285b6214ea053e1939b92cfe79040cTimo Sirainenstatic inline void
684844265f01abd1da5864647a6dd69cc1bbbc71Timo Sirainenarray_create_from_buffer_i(struct array *array, buffer_t *buffer,
8d80659e504ffb34bb0c6a633184fece35751b18Timo Sirainen#define array_create_from_buffer(array, buffer, element_size) \
684844265f01abd1da5864647a6dd69cc1bbbc71Timo Sirainen array_create_from_buffer_i(&(array)->arr, buffer, element_size)
30972f343b285b6214ea053e1939b92cfe79040cTimo Sirainenstatic inline void
684844265f01abd1da5864647a6dd69cc1bbbc71Timo Sirainenarray_create_i(struct array *array, pool_t pool,
30972f343b285b6214ea053e1939b92cfe79040cTimo Sirainen buffer = buffer_create_dynamic(pool, init_count * element_size);
684844265f01abd1da5864647a6dd69cc1bbbc71Timo Sirainen array_create_from_buffer_i(array, buffer, element_size);
8d80659e504ffb34bb0c6a633184fece35751b18Timo Sirainen#define array_create(array, pool, element_size, init_count) \
684844265f01abd1da5864647a6dd69cc1bbbc71Timo Sirainen array_create_i(&(array)->arr, pool, element_size, init_count)
30972f343b285b6214ea053e1939b92cfe79040cTimo Sirainenstatic inline void
6ef7e31619edfaa17ed044b45861d106a86191efTimo Sirainenstatic inline bool
30972f343b285b6214ea053e1939b92cfe79040cTimo Sirainenstatic inline void
0f819b4ecd3a144514f576516177029ffe0bd6d5Timo Sirainenstatic inline unsigned int ATTR_PURE
0f819b4ecd3a144514f576516177029ffe0bd6d5Timo Sirainen return array->buffer->used / array->element_size;
19557f192d37cd54a1a090a8a26d9d47265e4413Aki Tuomi/* No need for the real count if all we're doing is comparing against 0 */
30972f343b285b6214ea053e1939b92cfe79040cTimo Sirainenstatic inline void
684844265f01abd1da5864647a6dd69cc1bbbc71Timo Sirainenarray_append_i(struct array *array, const void *data, unsigned int count)
30972f343b285b6214ea053e1939b92cfe79040cTimo Sirainen buffer_append(array->buffer, data, count * array->element_size);
684844265f01abd1da5864647a6dd69cc1bbbc71Timo Sirainen array_append_i(&(array)->arr + ARRAY_TYPE_CHECK(array, data), \
30972f343b285b6214ea053e1939b92cfe79040cTimo Sirainenstatic inline void
684844265f01abd1da5864647a6dd69cc1bbbc71Timo Sirainenarray_append_array_i(struct array *dest_array, const struct array *src_array)
30972f343b285b6214ea053e1939b92cfe79040cTimo Sirainen i_assert(dest_array->element_size == src_array->element_size);
30972f343b285b6214ea053e1939b92cfe79040cTimo Sirainen buffer_append_buf(dest_array->buffer, src_array->buffer, 0, (size_t)-1);
8d80659e504ffb34bb0c6a633184fece35751b18Timo Sirainen#define array_append_array(dest_array, src_array) \
70c380a7b077e7c9fab056d977f0415bf8d063e0Phil Carmody array_append_array_i(&(dest_array)->arr + ARRAY_TYPES_CHECK(dest_array, src_array), \
30972f343b285b6214ea053e1939b92cfe79040cTimo Sirainenstatic inline void
684844265f01abd1da5864647a6dd69cc1bbbc71Timo Sirainenarray_insert_i(struct array *array, unsigned int idx,
30972f343b285b6214ea053e1939b92cfe79040cTimo Sirainen buffer_insert(array->buffer, idx * array->element_size,
b046ca519fc1092495691df7256de32a18dc7a17Timo Sirainen#define array_insert(array, idx, data, count) \
684844265f01abd1da5864647a6dd69cc1bbbc71Timo Sirainen array_insert_i(&(array)->arr + ARRAY_TYPE_CHECK(array, data), \
30972f343b285b6214ea053e1939b92cfe79040cTimo Sirainenstatic inline void
684844265f01abd1da5864647a6dd69cc1bbbc71Timo Sirainenarray_delete_i(struct array *array, unsigned int idx, unsigned int count)
30972f343b285b6214ea053e1939b92cfe79040cTimo Sirainen buffer_delete(array->buffer, idx * array->element_size,
30972f343b285b6214ea053e1939b92cfe79040cTimo Sirainenstatic inline const void *
684844265f01abd1da5864647a6dd69cc1bbbc71Timo Sirainenarray_get_i(const struct array *array, unsigned int *count_r)
684844265f01abd1da5864647a6dd69cc1bbbc71Timo Sirainen ARRAY_TYPE_CAST_CONST(array)array_get_i(&(array)->arr, count)
173b12537fdc65f71235073193223e811a00d130Phil Carmody/* Re: i_assert() vs. pure: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=51971#c1 */
68a4946b12583b88fa802e52ebee45cd96056772Timo Sirainenstatic inline const void * ATTR_PURE
684844265f01abd1da5864647a6dd69cc1bbbc71Timo Sirainenarray_idx_i(const struct array *array, unsigned int idx)
30972f343b285b6214ea053e1939b92cfe79040cTimo Sirainen i_assert(idx * array->element_size < array->buffer->used);
30972f343b285b6214ea053e1939b92cfe79040cTimo Sirainen return CONST_PTR_OFFSET(array->buffer->data, idx * array->element_size);
684844265f01abd1da5864647a6dd69cc1bbbc71Timo Sirainen ARRAY_TYPE_CAST_CONST(array)array_idx_i(&(array)->arr, idx)
30972f343b285b6214ea053e1939b92cfe79040cTimo Sirainenstatic inline void *
684844265f01abd1da5864647a6dd69cc1bbbc71Timo Sirainenarray_get_modifiable_i(struct array *array, unsigned int *count_r)
8d80659e504ffb34bb0c6a633184fece35751b18Timo Sirainen return buffer_get_modifiable_data(array->buffer, NULL);
1d4e5de8414ed93d1c810b30a91ad83d6d954861Sergey Kitovarray_idx_modifiable_i(const struct array *array, unsigned int idx) ATTR_PURE;
1d4e5de8414ed93d1c810b30a91ad83d6d954861Sergey Kitovvoid *array_idx_get_space_i(struct array *array, unsigned int idx);
aa181b6e3751d4e76da6f135729032660b14406cTimo Sirainenvoid array_idx_set_i(struct array *array, unsigned int idx, const void *data);
684844265f01abd1da5864647a6dd69cc1bbbc71Timo Sirainen array_idx_set_i(&(array)->arr + ARRAY_TYPE_CHECK(array, data), \
aa181b6e3751d4e76da6f135729032660b14406cTimo Sirainenvoid array_idx_clear_i(struct array *array, unsigned int idx);
30972f343b285b6214ea053e1939b92cfe79040cTimo Sirainenstatic inline void *
30972f343b285b6214ea053e1939b92cfe79040cTimo Sirainen data = buffer_append_space_unsafe(array->buffer, array->element_size);
684844265f01abd1da5864647a6dd69cc1bbbc71Timo Sirainen ARRAY_TYPE_CAST_MODIFIABLE(array)array_append_space_i(&(array)->arr)
aa181b6e3751d4e76da6f135729032660b14406cTimo Sirainenvoid *array_insert_space_i(struct array *array, unsigned int idx);
f59e2b09deeb94317342016949592577ef150c1bTimo Sirainenstatic inline void
f59e2b09deeb94317342016949592577ef150c1bTimo Sirainenarray_copy(struct array *dest, unsigned int dest_idx,
f59e2b09deeb94317342016949592577ef150c1bTimo Sirainen const struct array *src, unsigned int src_idx, unsigned int count)
f59e2b09deeb94317342016949592577ef150c1bTimo Sirainen i_assert(dest->element_size == src->element_size);
f59e2b09deeb94317342016949592577ef150c1bTimo Sirainen buffer_copy(dest->buffer, dest_idx * dest->element_size,
9a6250aecfe56f0970761806c16794c04330f46aPhil Carmody/* Exchange ownership of two arrays, which should have been allocated
9a6250aecfe56f0970761806c16794c04330f46aPhil Carmody from the same pool/context. Useful for updating an array with a
19557f192d37cd54a1a090a8a26d9d47265e4413Aki Tuomi replacement. Can also do it with uninitialized arrays (which will
fdc468280e23ddd3a91a0539e7a48ba9c8a60d27Phil Carmody have .element_size == 0). */
9a6250aecfe56f0970761806c16794c04330f46aPhil Carmodystatic inline void
9a6250aecfe56f0970761806c16794c04330f46aPhil Carmodyarray_swap_i(struct array *array1, struct array *array2)
9a6250aecfe56f0970761806c16794c04330f46aPhil Carmody array_swap_i(&(array1)->arr + ARRAY_TYPES_CHECK(array1, array2), \
0f111ddfcb893d75a79bb60942c77d97e15f6b99Phil Carmody/* Test equality via a comparator */
0f111ddfcb893d75a79bb60942c77d97e15f6b99Phil Carmodybool array_equal_fn_i(const struct array *array1,
0f111ddfcb893d75a79bb60942c77d97e15f6b99Phil Carmody int (*cmp)(const void*, const void *)) ATTR_PURE;
0f111ddfcb893d75a79bb60942c77d97e15f6b99Phil Carmody CALLBACK_TYPECHECK(cmp, int (*)(typeof(*(array1)->v), \
0f111ddfcb893d75a79bb60942c77d97e15f6b99Phil Carmody (int (*)(const void *, const void *))cmp)
0f111ddfcb893d75a79bb60942c77d97e15f6b99Phil Carmodybool array_equal_fn_ctx_i(const struct array *array1,
0f111ddfcb893d75a79bb60942c77d97e15f6b99Phil Carmody int (*cmp)(const void*, const void *, const void *),
0f111ddfcb893d75a79bb60942c77d97e15f6b99Phil Carmody/* Same, but with a context pointer.
0f111ddfcb893d75a79bb60942c77d97e15f6b99Phil Carmody context can't be void* as ``const typeof(context)'' won't compile,
0f111ddfcb893d75a79bb60942c77d97e15f6b99Phil Carmody so ``const typeof(*context)*'' is required instead, and that requires a
0f111ddfcb893d75a79bb60942c77d97e15f6b99Phil Carmody complete type. */
0f111ddfcb893d75a79bb60942c77d97e15f6b99Phil Carmody#define array_equal_fn_ctx(array1, array2, cmp, ctx) \
0f111ddfcb893d75a79bb60942c77d97e15f6b99Phil Carmody CALLBACK_TYPECHECK(cmp, int (*)(typeof(*(array1)->v), \
0f111ddfcb893d75a79bb60942c77d97e15f6b99Phil Carmody (int (*)(const void *, const void *, const void *))cmp, \
304cda7b78964aeacda7cd5388c7eb2a0be3e31aTimo Sirainenvoid array_sort_i(struct array *array, int (*cmp)(const void *, const void *));
27a44fcfd8d19bffe0f267f20a2b5d3fe7600fddTimo Sirainen CALLBACK_TYPECHECK(cmp, int (*)(typeof(*(array)->v), \
27a44fcfd8d19bffe0f267f20a2b5d3fe7600fddTimo Sirainen (int (*)(const void *, const void *))cmp)
40252a7eb6030f51dc6436e5b844c8a65890a736Timo Sirainenvoid *array_bsearch_i(struct array *array, const void *key,
40252a7eb6030f51dc6436e5b844c8a65890a736Timo Sirainen int (*cmp)(const void *, const void *));
27a44fcfd8d19bffe0f267f20a2b5d3fe7600fddTimo Sirainen ARRAY_TYPE_CAST_MODIFIABLE(array)array_bsearch_i(&(array)->arr + \
27a44fcfd8d19bffe0f267f20a2b5d3fe7600fddTimo Sirainen CALLBACK_TYPECHECK(cmp, int (*)(typeof(const typeof(*key) *), \
27a44fcfd8d19bffe0f267f20a2b5d3fe7600fddTimo Sirainen (const void *)key, (int (*)(const void *, const void *))cmp)
c029156a6eed53d440b496406e3df08b569568ecPhil Carmody/* Returns pointer to first element for which cmp(key,elem)==0, or NULL */
c029156a6eed53d440b496406e3df08b569568ecPhil Carmodyconst void *array_lsearch_i(const struct array *array, const void *key,
c029156a6eed53d440b496406e3df08b569568ecPhil Carmody int (*cmp)(const void *, const void *));
c029156a6eed53d440b496406e3df08b569568ecPhil Carmodystatic inline void *array_lsearch_modifiable_i(struct array *array, const void *key,
c029156a6eed53d440b496406e3df08b569568ecPhil Carmody int (*cmp)(const void *, const void *))
c029156a6eed53d440b496406e3df08b569568ecPhil Carmody return (void *)array_lsearch_i(array, key, cmp);
c029156a6eed53d440b496406e3df08b569568ecPhil Carmody#define ARRAY_LSEARCH_CALL(modifiable, array, key, cmp) \
c029156a6eed53d440b496406e3df08b569568ecPhil Carmody CALLBACK_TYPECHECK(cmp, int (*)(typeof(const typeof(*key) *), \
c029156a6eed53d440b496406e3df08b569568ecPhil Carmody (const void *)key, \
c029156a6eed53d440b496406e3df08b569568ecPhil Carmody (int (*)(const void *, const void *))cmp)
c029156a6eed53d440b496406e3df08b569568ecPhil Carmody ARRAY_TYPE_CAST_CONST(array)ARRAY_LSEARCH_CALL(_, array, key, cmp)
c029156a6eed53d440b496406e3df08b569568ecPhil Carmody#define array_lsearch_modifiable(array, key, cmp) \