Mercurial > dovecot > core-2.2
view src/lib/bsearch-insert-pos.h @ 17825:12015689471c
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@dovecot.fi>
author | Phil Carmody <phil@dovecot.fi> |
---|---|
date | Mon, 22 Sep 2014 15:56:31 +0300 |
parents | 38ca85ccd5af |
children |
line wrap: on
line source
#ifndef BSEARCH_INSERT_POS_H #define BSEARCH_INSERT_POS_H /* 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); \ left_idx = 0; right_idx = (count); \ while (left_idx < right_idx) { \ idx = (left_idx + right_idx) / 2; \ \ if (getdata(data, idx) < (value)) \ left_idx = idx+1; \ else if (getdata(data, idx) > (value))\ right_idx = idx; \ else { \ *(idx_r) = idx; \ return TRUE; \ } \ } \ 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. */ bool ATTR_NOWARN_UNUSED_RESULT bsearch_insert_pos(const void *key, const void *base, unsigned int nmemb, size_t size, int (*cmp)(const void *, const void *), unsigned int *idx_r); #define bsearch_insert_pos(key, base, nmemb, size, cmp, idx_r) \ bsearch_insert_pos(key, base, nmemb, size + \ CALLBACK_TYPECHECK(cmp, int (*)(typeof(const typeof(*key) *), \ typeof(const typeof(*base) *))), \ (int (*)(const void *, const void *))cmp, idx_r) bool ATTR_NOWARN_UNUSED_RESULT array_bsearch_insert_pos_i(const struct array *array, const void *key, int (*cmp)(const void *, const void *), unsigned int *idx_r); #define array_bsearch_insert_pos(array, key, cmp, idx_r) \ array_bsearch_insert_pos_i(&(array)->arr + \ CALLBACK_TYPECHECK(cmp, int (*)(typeof(const typeof(*key) *), \ typeof(*(array)->v))), \ (const void *)key, (int (*)(const void *, const void *))cmp, idx_r) #endif