/src/dovecot/src/lib/array.h

Source
#ifndef ARRAY_H
#define ARRAY_H

/* Array is a buffer accessible using fixed size elements. As long as the
   compiler provides a typeof() operator, the array provides type safety. If
   a wrong type is tried to be added to the array, or if the array's contents
   are tried to be used using a wrong type, the compiler will give a warning.

   Example usage:

   struct foo {
  ARRAY(struct bar) bars;
  ...
   };

   i_array_init(&foo->bars, 10);

   struct bar *bar = array_idx(&foo->bars, 5);
   struct baz *baz = array_idx(&foo->bars, 5); // compiler warning

   If you want to pass an array as a parameter to a function, you'll need to
   create a type for the array using ARRAY_DEFINE_TYPE() and use the type in
   the parameter using ARRAY_TYPE(). Any arrays that you want to be passing
   around, such as structure members as in the above example, must also be
   defined using ARRAY_TYPE() too, rather than ARRAY().

   Example:

   ARRAY_DEFINE_TYPE(foo, struct foo);
   void do_foo(ARRAY_TYPE(foo) *foos) {
  struct foo *foo = array_idx(foos, 0);
   }
   struct foo_manager {
  ARRAY_TYPE(foo) foos; // pedantically, ARRAY(struct foo) is a different type
   };
   // ...
  do_foo(&my_foo_manager->foos); // No compiler warning about mismatched types

*/
#include "array-decl.h"
#include "buffer.h"

#define p_array_init(array, pool, init_count) \
  array_create(array, pool, sizeof(**(array)->v), init_count) // NOLINT(bugprone-sizeof-expression)
#define i_array_init(array, init_count) \
  p_array_init(array, default_pool, init_count)
#define t_array_init(array, init_count) \
  p_array_init(array, pool_datastack_create(), init_count)

#ifdef HAVE_TYPEOF
#  define ARRAY_TYPE_CAST_CONST(array) \
  (typeof(*(array)->v))
#  define ARRAY_TYPE_CAST_MODIFIABLE(array) \
  (typeof(*(array)->v_modifiable))
#  define ARRAY_TYPE_CHECK(array, data) \
  COMPILE_ERROR_IF_TYPES_NOT_COMPATIBLE( \
    **(array)->v_modifiable, *(data))
#  define ARRAY_TYPES_CHECK(array1, array2) \
  COMPILE_ERROR_IF_TYPES_NOT_COMPATIBLE( \
    **(array1)->v_modifiable, **(array2)->v_modifiable)

#else
#  define ARRAY_TYPE_CAST_CONST(array)
#  define ARRAY_TYPE_CAST_MODIFIABLE(array)
#  define ARRAY_TYPE_CHECK(array, data) 0
#  define ARRAY_TYPES_CHECK(array1, array2) 0
#endif

/* Usage:
   ARRAY(struct foo) foo_arr;
   struct foo *foo;

   array_foreach(&foo_arr, foo) {
     ..
   }

   Note that deleting an element while iterating will cause the iteration to
   skip over the next element. So deleting a single element and breaking out
   of the loop is fine, but continuing the loop is likely a bug. Use
   array_foreach_reverse() instead when deleting multiple elements.
*/
#define array_foreach(array, elem) \
  for (const void *elem ## __foreach_end = \
    (const char *)(elem = *(array)->v) + (array)->arr.buffer->used; \
       elem != elem ## __foreach_end; (elem)++)
#define array_foreach_modifiable(array, elem) \
  for (const void *elem ## _end = \
    (const char *)(elem = ARRAY_TYPE_CAST_MODIFIABLE(array) \
      buffer_get_modifiable_data((array)->arr.buffer, NULL)) + \
      (array)->arr.buffer->used; \
       elem != elem ## _end; (elem)++)

/* Iterate the array in reverse order. */
#define array_foreach_reverse(array, elem) \
  for (elem = CONST_PTR_OFFSET(*(array)->v, (array)->arr.buffer->used); \
       (const char *)(elem--) > (const char *)*(array)->v; )
#define array_foreach_reverse_modifiable(array, elem) \
  for (elem = ARRAY_TYPE_CAST_MODIFIABLE(array) \
    ((char *)buffer_get_modifiable_data((array)->arr.buffer, NULL) + \
     (array)->arr.buffer->used); \
       (const char *)(elem--) > (const char *)*(array)->v; )

/* Usage:
   ARRAY(struct foo *) foo_ptrs_arr;
   struct foo *foo;

   array_foreach_elem(&foo_ptrs_arr, foo) {
     ..
   } */
#define array_foreach_elem(array, elem) \
  for (const void *_foreach_end = \
    /* NOLINTBEGIN(bugprone-sizeof-expression) */ \
    CONST_PTR_OFFSET(*(array)->v, (array)->arr.buffer->used), \
       *_foreach_ptr = CONST_PTR_OFFSET(*(array)->v, ARRAY_TYPE_CHECK(array, &elem) + \
    COMPILE_ERROR_IF_TRUE(sizeof(elem) > sizeof(void *))) \
         ;              \
       (_foreach_ptr != _foreach_end &&   \
       (memcpy(&elem, _foreach_ptr, sizeof(elem)), TRUE)) \
    ;             \
       _foreach_ptr = CONST_PTR_OFFSET(_foreach_ptr, sizeof(elem))) \
       /* NOLINTEND(bugprone-sizeof-expression) */ \


#define array_ptr_to_idx(array, elem) \
  ((elem) - (array)->v[0])
/* Return index of iterated element inside array_foreach() or
   array_foreach_modifiable() loop. Note that this doesn't work inside
   array_foreach_elem() loop. */
#define array_foreach_idx(array, elem) \
  array_ptr_to_idx(array, elem)

static inline void
array_create_from_buffer_i(struct array *array, buffer_t *buffer,
         size_t element_size)
{
  array->buffer = buffer;
  array->element_size = element_size;
}
#define array_create_from_buffer(array, buffer, element_size) \
  array_create_from_buffer_i(&(array)->arr, buffer, element_size)

static inline void
array_create_i(struct array *array, pool_t pool,
         size_t element_size, unsigned int init_count)
{
  buffer_t *buffer;

  buffer = buffer_create_dynamic_max(pool,
    MALLOC_MULTIPLY(init_count, element_size),
    SIZE_MAX / element_size < UINT_MAX ? SIZE_MAX :
    UINT_MAX * element_size);
  array_create_from_buffer_i(array, buffer, element_size);
}
#define array_create(array, pool, element_size, init_count) \
  array_create_i(&(array)->arr, pool, element_size, init_count)

static inline void
array_free_i(struct array *array)
{
  buffer_free(&array->buffer);
}
#define array_free(array) \
  array_free_i(&(array)->arr)

static inline void * ATTR_WARN_UNUSED_RESULT
array_free_without_data_i(struct array *array)
{
  return buffer_free_without_data(&array->buffer);
}
#define array_free_without_data(array) \
  ARRAY_TYPE_CAST_MODIFIABLE(array)array_free_without_data_i(&(array)->arr)

static inline bool
array_is_created_i(const struct array *array)
{
  return array->buffer != NULL;
}
#define array_is_created(array) \
  array_is_created_i(&(array)->arr)

static inline pool_t ATTR_PURE
array_get_pool_i(struct array *array)
{
  return buffer_get_pool(array->buffer);
}
#define array_get_pool(array) \
  array_get_pool_i(&(array)->arr)

static inline void
array_clear_i(struct array *array)
{
  buffer_set_used_size(array->buffer, 0);
}
#define array_clear(array) \
  array_clear_i(&(array)->arr)

static inline unsigned int ATTR_PURE
array_count_i(const struct array *array)
{
  return array->buffer->used / array->element_size;
}
#define array_count(array) \
  array_count_i(&(array)->arr)
/* No need for the real count if all we're doing is comparing against 0 */
#define array_is_empty(array) \
  ((!array_is_created(array)) || ((array)->arr.buffer->used == 0))
#define array_not_empty(array) \
  ((array_is_created(array)) && ((array)->arr.buffer->used > 0))

static inline void
array_append_i(struct array *array, const void *data, unsigned int count)
{
  buffer_append_array(array->buffer, data, count, array->element_size);
}

#define array_append(array, data, count) \
  TYPE_CHECKS(void, ARRAY_TYPE_CHECK(array, data), \
  array_append_i(&(array)->arr, data, count))

static inline void
array_append_array_i(struct array *dest_array, const struct array *src_array)
{
  i_assert(dest_array->element_size == src_array->element_size);
  buffer_append_buf(dest_array->buffer, src_array->buffer, 0, SIZE_MAX);
}
#define array_append_array(dest_array, src_array) \
  TYPE_CHECKS(void, ARRAY_TYPES_CHECK(dest_array, src_array), \
  array_append_array_i(&(dest_array)->arr, &(src_array)->arr))

static inline void
array_insert_i(struct array *array, unsigned int idx,
         const void *data, unsigned int count)
{
  buffer_insert_array(array->buffer,
          MALLOC_MULTIPLY(idx, array->element_size),
          data, count, array->element_size);
}

#define array_insert(array, idx, data, count) \
  TYPE_CHECKS(void, ARRAY_TYPE_CHECK(array, data), \
  array_insert_i(&(array)->arr, idx, data, count))

static inline void
array_delete_i(struct array *array, unsigned int idx, unsigned int count)
{
  buffer_delete(array->buffer, MALLOC_MULTIPLY(idx, array->element_size),
          MALLOC_MULTIPLY(count, array->element_size));
}
#define array_delete(array, idx, count) \
  array_delete_i(&(array)->arr, idx, count)

static inline const void *
array_get_i(const struct array *array, unsigned int *count_r)
{
  *count_r = array_count_i(array);
  return array->buffer->data;
}
#define array_get(array, count) \
  ARRAY_TYPE_CAST_CONST(array)array_get_i(&(array)->arr, count)

static inline void *
array_get_copy_i(const struct array *array, pool_t pool, unsigned int *count_r)
{
  *count_r = array_count_i(array);
  if (array->buffer->used == 0)
    return NULL;
  return p_memdup(pool, array->buffer->data, array->buffer->used);
}
#define array_get_copy(array, pool, count) \
  ARRAY_TYPE_CAST_MODIFIABLE(array) \
    array_get_copy_i(&(array)->arr, pool, count)

/* Re: i_assert() vs. pure: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=51971#c1 */
static inline const void * ATTR_PURE
array_idx_i(const struct array *array, unsigned int idx)
{
  i_assert(idx < array->buffer->used / array->element_size);
  return CONST_PTR_OFFSET(array->buffer->data,
        MALLOC_MULTIPLY(idx, array->element_size));
}

#define array_front(array) array_idx(array, 0)
#define array_front_modifiable(array) array_idx_modifiable(array, 0)
#define array_back(array) array_idx(array, array_count(array)-1)
#define array_back_modifiable(array) array_idx_modifiable(array, array_count(array)-1)
#define array_pop_back(array) array_delete(array, array_count(array)-1, 1);
#define array_push_back(array, item) array_append(array, (item), 1)
#define array_pop_front(array) array_delete(array, 0, 1)
#define array_push_front(array, item) array_insert(array, 0, (item), 1)

#define array_idx(array, idx) \
  ARRAY_TYPE_CAST_CONST(array)array_idx_i(&(array)->arr, idx)
/* Using *array_idx() will fail if the compiler doesn't support typeof().
   The same can be done with array_idx_elem() for arrays that have pointers. */
#ifdef HAVE_TYPEOF
#  define array_idx_elem(array, idx) \
  (TRUE ? *array_idx(array, idx) : \
    COMPILE_ERROR_IF_TRUE(sizeof(**(array)->v) != sizeof(void *)))
#else
#  define array_idx_elem(array, idx) \
  (*(void **)array_idx_i(&(array)->arr, idx))
#endif

static inline void *
array_get_modifiable_i(struct array *array, unsigned int *count_r)
{
  *count_r = array_count_i(array);
  return buffer_get_modifiable_data(array->buffer, NULL);
}
#define array_get_modifiable(array, count) \
  ARRAY_TYPE_CAST_MODIFIABLE(array) \
    array_get_modifiable_i(&(array)->arr, count)

void *
array_idx_modifiable_i(const struct array *array, unsigned int idx) ATTR_PURE;
#define array_idx_modifiable(array, idx) \
  ARRAY_TYPE_CAST_MODIFIABLE(array) \
    array_idx_modifiable_i(&(array)->arr, idx)

void *array_idx_get_space_i(struct array *array, unsigned int idx);
#define array_idx_get_space(array, idx) \
  ARRAY_TYPE_CAST_MODIFIABLE(array) \
    array_idx_get_space_i(&(array)->arr, idx)

void array_idx_set_i(struct array *array, unsigned int idx, const void *data);
#define array_idx_set(array, idx, data) \
  TYPE_CHECKS(void, ARRAY_TYPE_CHECK(array, data), \
  array_idx_set_i(&(array)->arr, idx, data))

void array_idx_clear_i(struct array *array, unsigned int idx);
#define array_idx_clear(array, idx) \
  array_idx_clear_i(&(array)->arr, idx)

static inline void *
array_append_space_i(struct array *array)
{
  void *data;

  data = buffer_append_space_unsafe(array->buffer, array->element_size);
  memset(data, 0, array->element_size);
  return data;
}
#define array_append_space(array) \
  ARRAY_TYPE_CAST_MODIFIABLE(array)array_append_space_i(&(array)->arr)
#define array_append_zero(array) \
  (void)array_append_space_i(&(array)->arr)

void *array_insert_space_i(struct array *array, unsigned int idx);
#define array_insert_space(array, idx) \
  ARRAY_TYPE_CAST_MODIFIABLE(array) \
    array_insert_space_i(&(array)->arr, idx)

static inline void
array_copy(struct array *dest, unsigned int dest_idx,
     const struct array *src, unsigned int src_idx, unsigned int count)
{
  i_assert(dest->element_size == src->element_size);

  buffer_copy(dest->buffer, MALLOC_MULTIPLY(dest_idx, dest->element_size),
        src->buffer, MALLOC_MULTIPLY(src_idx, src->element_size),
        MALLOC_MULTIPLY(count, dest->element_size));
}

bool array_cmp_i(const struct array *array1,
     const struct array *array2) ATTR_PURE;
#define array_cmp(array1, array2) \
  array_cmp_i(&(array1)->arr, &(array2)->arr)

/* Test equality via a comparator */
bool array_equal_fn_i(const struct array *array1,
          const struct array *array2,
          int (*cmp)(const void*, const void *)) ATTR_PURE;
#define array_equal_fn(array1, array2, cmp) \
  TYPE_CHECKS(bool, \
  ARRAY_TYPES_CHECK(array1, array2) || \
  CALLBACK_TYPECHECK(cmp, int (*)(typeof(*(array1)->v), \
          typeof(*(array2)->v))), \
  array_equal_fn_i(&(array1)->arr, &(array2)->arr, \
       (int (*)(const void *, const void *))cmp))
bool array_equal_fn_ctx_i(const struct array *array1,
        const struct array *array2,
        int (*cmp)(const void*, const void *, const void *),
        const void *context) ATTR_PURE;
/* Same, but with a context pointer.
   context can't be void* as ``const typeof(context)'' won't compile,
   so ``const typeof(*context)*'' is required instead, and that requires a
   complete type. */
#define array_equal_fn_ctx(array1, array2, cmp, ctx) \
  TYPE_CHECKS(bool, \
  ARRAY_TYPES_CHECK(array1, array2) || \
  CALLBACK_TYPECHECK(cmp, int (*)(typeof(*(array1)->v), \
          typeof(*(array2)->v), \
          const typeof(*ctx)*)), \
  array_equal_fn_ctx_i(&(array1)->arr, &(array2)->arr, \
    (int (*)(const void *, const void *, const void *))cmp, ctx))

void array_reverse_i(struct array *array);
#define array_reverse(array) \
  array_reverse_i(&(array)->arr)

void array_sort_i(struct array *array, int (*cmp)(const void *, const void *));
#define array_sort(array, cmp) \
  TYPE_CHECKS(void, \
  CALLBACK_TYPECHECK(cmp, int (*)(typeof(*(array)->v), \
          typeof(*(array)->v))), \
  array_sort_i(&(array)->arr, (int (*)(const void *, const void *))cmp))

#define ARRAY_SEARCH_CALL(func, array, key, cmp) \
  TYPE_CHECKS(void *, \
    CALLBACK_TYPECHECK(cmp, int (*)(typeof(const typeof(*key) *), \
            typeof(*(array)->v))), \
    array_##func##_i( \
      &(array)->arr, (const void *)key, \
      (int (*)(const void *, const void *))cmp))

const void *array_bsearch_i(const struct array *array, const void *key,
                int (*cmp)(const void *, const void *));
static inline void *array_bsearch_modifiable_i(struct array *array, const void *key,
                 int (*cmp)(const void *, const void *))
{
  return (void *)array_bsearch_i(array, key, cmp);
}

#define array_bsearch(array, key, cmp) \
  ARRAY_TYPE_CAST_CONST(array) \
  ARRAY_SEARCH_CALL(bsearch, array, key, cmp)
#define array_bsearch_modifiable(array, key, cmp) \
  ARRAY_TYPE_CAST_MODIFIABLE(array) \
  ARRAY_SEARCH_CALL(bsearch_modifiable, array, key, cmp)

/* Returns pointer to first element for which cmp(key,elem)==0, or NULL */
const void *array_lsearch_i(const struct array *array, const void *key,
          int (*cmp)(const void *, const void *));
static inline void *array_lsearch_modifiable_i(struct array *array, const void *key,
                 int (*cmp)(const void *, const void *))
{
  return (void *)array_lsearch_i(array, key, cmp);
}

#define array_lsearch(array, key, cmp) \
  ARRAY_TYPE_CAST_CONST(array) \
  ARRAY_SEARCH_CALL(lsearch, array, key, cmp)
#define array_lsearch_modifiable(array, key, cmp) \
  ARRAY_TYPE_CAST_MODIFIABLE(array) \
  ARRAY_SEARCH_CALL(lsearch_modifiable, array, key, cmp)

/* Search a pointer from an array */
const void *array_lsearch_ptr_i(const struct array *array, const void *key);
#define array_lsearch_ptr(array, key) \
  TYPE_CHECKS(const void *, \
  COMPILE_ERROR_IF_TYPES_NOT_COMPATIBLE(***(array)->v, *(key)), \
  array_lsearch_ptr_i(&(array)->arr, key))
#define array_lsearch_ptr_modifiable(array, key) \
  (void *)array_lsearch_ptr(array, key)

bool array_lsearch_ptr_idx_i(const struct array *array, const void *key,
           unsigned int *idx_r);
#define array_lsearch_ptr_idx(array, key, idx_r) \
  TYPE_CHECKS(bool, \
  COMPILE_ERROR_IF_TYPES_NOT_COMPATIBLE(***(array)->v, *(key)), \
  array_lsearch_ptr_idx_i(&(array)->arr, key, idx_r))

#endif

Coverage Report

Created: 2026-08-08 06:29

Line	Count	Source
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		*/