From 1f0b3ea95f45146b6860a37f43bc02b62891e354 Mon Sep 17 00:00:00 2001 From: Phil Carmody Date: Mon, 22 Sep 2014 15:56:31 +0300 Subject: [PATCH] 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 --- src/lib/bsearch-insert-pos.h | 15 ++++++++++----- 1 file changed, 10 insertions(+), 5 deletions(-) diff --git a/src/lib/bsearch-insert-pos.h b/src/lib/bsearch-insert-pos.h index 52552d0b51..1378df47f1 100644 --- a/src/lib/bsearch-insert-pos.h +++ b/src/lib/bsearch-insert-pos.h @@ -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. */ -- 2.47.3