Search functions

Binary search algorithm. More...

Macros
#define	csnip_Bsearch(itype, u, au_lessthan_key, N, ret)
	Binary search. More...

Detailed Description

The csnip_Bsearch() macro provides a binary seach facility that improves on libc's bsearch interface in a number of ways:

1. bsearch() can only be used to find exact matches, or determine whether there is a match. Frequently (or, dare I say, usually), however, one wants to find the closest value in the array, not necessarily an exact match. For such cases, bsearch doesn't work, but csnip_Bsearch() can be used.
2. Easier to use interface. Bsearch requires implementation of a separate comparison function, and is not type safe; csnip_Bsearch() does not have these problems.
3. Has the potential to be faster than bsearch() because it's not necessary to dereference a function pointer for each comparison.

Macro Definition Documentation

csnip_Bsearch

#define csnip_Bsearch	(		itype,
			u,
			au_lessthan_key,
			N,
			ret
	)

Statement macro. Find the smallest index i in a sorted array such that the i-th entry is at least as large as a specified key. If no such index exists return N, the size of the array.

Parameters

itype	integral type used for the return value. itype is also used for indexing.
u	dummy variable for the comparison expression.
au_lessthan_key	expression in u that evaluates to true if the u-th entry of the array is less than the key, and false otherwise.
N	the size of the array.
ret	lvalue of type itype to store the result index.

Note

By default the csnip_Bsearch function finds the lowest index i such that a[i] >= key. To find the lowest index such that a[i] > key, the au_lessthan_key expression can be set to a less-than-or-equal expression.