dovecot-2.2: lib: array - new linear search helper

[dovecot at dovecot.org]

details:   http://hg.dovecot.org/dovecot-2.2/rev/1bbec03202e0
changeset: 18132:1bbec03202e0
user:      Phil Carmody <phil at dovecot.fi>
date:      Mon Jan 05 22:12:48 2015 +0200
description:
lib: array - new linear search helper
There are large numbers of array_foreach loops which do nothing but search
for the first element which matches some key. This can be abstracted out
into a helper.

Signed-off-by: Phil Carmody <phil at dovecot.fi>

diffstat:

 src/lib/array.c |  16 ++++++++++++++++
 src/lib/array.h |  20 ++++++++++++++++++++
 2 files changed, 36 insertions(+), 0 deletions(-)

diffs (51 lines):

diff -r 6078354e6238 -r 1bbec03202e0 src/lib/array.c
--- a/src/lib/array.c	Fri Dec 26 17:28:30 2014 +0200
+++ b/src/lib/array.c	Mon Jan 05 22:12:48 2015 +0200
@@ -138,3 +138,19 @@
 	return bsearch(key, array->buffer->data,
 		       count, array->element_size, cmp);
 }
+
+const void *array_lsearch_i(const struct array *array, const void *key,
+			    int (*cmp)(const void *, const void *))
+{
+	const void * const data = buffer_get_data(array->buffer, NULL);
+	const unsigned int s = array->element_size;
+	unsigned int idx;
+
+	for (idx = 0; idx < array_count_i(array); idx++) {
+		if (cmp(key, CONST_PTR_OFFSET(data, idx * s)) == 0) {
+			return PTR_OFFSET(data, idx * s);
+		}
+	}
+
+	return NULL;
+}
diff -r 6078354e6238 -r 1bbec03202e0 src/lib/array.h
--- a/src/lib/array.h	Fri Dec 26 17:28:30 2014 +0200
+++ b/src/lib/array.h	Mon Jan 05 22:12:48 2015 +0200
@@ -316,4 +316,24 @@
 						typeof(*(array)->v))), \
 		(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)			\
+	array_lsearch##modifiable##i(					\
+		&(array)->arr +						\
+		CALLBACK_TYPECHECK(cmp, int (*)(typeof(const typeof(*key) *), \
+						typeof(*(array)->v))),	\
+		(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