Adding upstream version 1:2.3.19.1+dfsg1.upstream/1%2.3.19.1+dfsg1upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 420 insertions, 0 deletions

diff --git a/src/lib/array.h b/src/lib/array.h
new file mode 100644
index 0000000..9349e8a
--- /dev/null
+++ b/src/lib/array.h
@@ -0,0 +1,420 @@
+#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)
+#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 = \
+		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)))
+
+
+#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, 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)->arr.buffer->used == 0)
+#define array_not_empty(array) \
+	((array)->arr.buffer->used > 0)
+
+static inline void
+array_append_i(struct array *array, const void *data, unsigned int count)
+{
+	buffer_append(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->buffer, 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, idx * array->element_size,
+		      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)
+
+/* 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, 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, dest_idx * dest->element_size,
+		    src->buffer, src_idx * src->element_size,
+		    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))
+
+void *array_bsearch_i(struct array *array, const void *key,
+		      int (*cmp)(const void *, const void *));
+#define array_bsearch(array, key, cmp) \
+	TYPE_CHECKS(void *, \
+	CALLBACK_TYPECHECK(cmp, int (*)(typeof(const typeof(*key) *), \
+					typeof(*(array)->v))), \
+	ARRAY_TYPE_CAST_MODIFIABLE(array)array_bsearch_i(&(array)->arr, \
+		(const void *)key, (int (*)(const void *, const void *))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_CALL(modifiable, array, key, cmp) \
+	TYPE_CHECKS(void *, \
+	CALLBACK_TYPECHECK(cmp, int (*)(typeof(const typeof(*key) *), \
+					typeof(*(array)->v))), \
+	array_lsearch##modifiable##i( \
+		&(array)->arr, (const void *)key, \
+		(int (*)(const void *, const void *))cmp))
+#define array_lsearch(array, key, cmp)					\
+	ARRAY_TYPE_CAST_CONST(array)ARRAY_LSEARCH_CALL(_, array, key, cmp)
+#define array_lsearch_modifiable(array, key, cmp)			\
+	ARRAY_TYPE_CAST_MODIFIABLE(array)ARRAY_LSEARCH_CALL(_modifiable_, array, key, cmp)
+
+#endif