dovecot-2.2: lib: bsearch - make BINARY_NUMBER_SEARCH more widel...

[dovecot at dovecot.org]

details:   http://hg.dovecot.org/dovecot-2.2/rev/12015689471c
changeset: 17825:12015689471c
user:      Phil Carmody <phil at dovecot.fi>
date:      Mon Sep 22 15:56:31 2014 +0300
description:
lib: bsearch - make BINARY_NUMBER_SEARCH more widely usable
This template is more widely usable if we do not hard-code into it the
method of accessing the value being compared. For the default case
we already use, this accessor is just a simple array dereferencing
macro.

As rewriting with the array access happens in the preprocessor, the
code generated is completely unchanged.

Expected future use:

:  #define MY_GETTER(array, index) ((array)[(index)].index_field)
:  #define MY_BINARY_SEARCH(data, count, value, idx_r)                  \
:          BINARY_NUMERIC_SEARCH(MY_GETTER, data, count, value, idx_r);

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

diffstat:

 src/lib/bsearch-insert-pos.h |  15 ++++++++++-----
 1 files changed, 10 insertions(+), 5 deletions(-)

diffs (39 lines):

diff -r 979e5a007248 -r 12015689471c src/lib/bsearch-insert-pos.h
--- a/src/lib/bsearch-insert-pos.h	Thu Sep 18 17:46:18 2014 +0200
+++ b/src/lib/bsearch-insert-pos.h	Mon Sep 22 15:56:31 2014 +0300
@@ -1,18 +1,19 @@
 #ifndef BSEARCH_INSERT_POS_H
 #define BSEARCH_INSERT_POS_H
 
-/* Binary search template */
-#define BINARY_NUMBER_SEARCH(data, count, value, idx_r) \
+/* Binary search template - getdata must be the name of a pure function
+   or a function-like macro that takes the two obvious parameters. */
+#define BINARY_NUMERIC_SEARCH(getdata, data, count, value, idx_r)	\
 	unsigned int idx, left_idx, right_idx;        \
 						      \
 	i_assert((count) < INT_MAX);                  \
-	idx = 0; left_idx = 0; right_idx = (count);   \
+	left_idx = 0; right_idx = (count);	      \
 	while (left_idx < right_idx) {                \
 		idx = (left_idx + right_idx) / 2;     \
 						      \
-		if ((data)[idx] < (value))            \
+		if (getdata(data, idx) < (value))     \
 			left_idx = idx+1;             \
-		else if ((data)[idx] > (value))       \
+		else if (getdata(data, idx) > (value))\
 			right_idx = idx;              \
 		else {                                \
 			*(idx_r) = idx;               \
@@ -21,6 +22,10 @@
 	}                                             \
 	return FALSE
 
+#define BINARY_SEARCH_ARRAY_GET(array, index) ((array)[(index)])
+#define BINARY_NUMBER_SEARCH(data, count, value, idx_r)			\
+	BINARY_NUMERIC_SEARCH(BINARY_SEARCH_ARRAY_GET, data, count, value, idx_r);
+
 /* If key is found, returns TRUE and sets idx_r to the position where the key
    was found. If key isn't found, returns FALSE and sets idx_r to the position
    where the key should be inserted. */