#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