binary search More...

#include "cgul_common.h"
#include "cgul_exception.h"

Include dependency graph for cgul_binary_search.h:

This graph shows which files directly or indirectly include this file:

Functions
CGUL_EXPORT void *	cgul_binary_search (cgul_exception_t cex, const void key, const void *v, size_t v_count, size_t element_size, cgul_binary_search__compare_t f)

CGUL_EXPORT void *	cgul_binary_search_pointers (cgul_exception_t cex, const void key, const void **v, size_t v_count, cgul_binary_search__compare_t f)

CGUL_EXPORT void *	cgul_binary_search_ceiling (cgul_exception_t cex, const void key, const void *v, size_t v_count, size_t element_size, cgul_binary_search__compare_t f)

CGUL_EXPORT void *	cgul_binary_search_ceiling_pointers (cgul_exception_t cex, const void key, const void **v, size_t v_count, cgul_binary_search__compare_t f)

CGUL_EXPORT void *	cgul_binary_search_floor (cgul_exception_t cex, const void key, const void *v, size_t v_count, size_t element_size, cgul_binary_search__compare_t f)

CGUL_EXPORT void *	cgul_binary_search_floor_pointers (cgul_exception_t cex, const void key, const void **v, size_t v_count, cgul_binary_search__compare_t f)

CGUL_EXPORT int	cgul_binary_search_irange (cgul_exception_t cex, int low, int high, int(f)(int, void ), void data)

Variables
CGUL_BEGIN_C typedef int(*	cgul_binary_search__compare_t )(const void search_key, const void array_element)

Detailed Description

Binary search an array.

Author: Paul Serice

Function Documentation

§ cgul_binary_search()

CGUL_EXPORT void* cgul_binary_search	(	cgul_exception_t *	cex,
		const void *	key,
		const void *	v,
		size_t	v_count,
		size_t	element_size,
		cgul_binary_search__compare_t	f
	)

Generic search with the same parameter signature as stdlib's bsearch(). v is a pointer to the top of your array. v_count is the number of elements in v. element_size is the number of contiguous bytes that comprise each element. The void* return value is a pointer to the element that matched key. If more than one element matches key, any of the matching elements could be returned. If no match was found, the return value is NULL.

Parameters

[in]	cex	c-style exception
[in]	key	value to search for
[in]	v	array of sorted elements to search
[in]	v_count	number of elements in `v`
[in]	element_size	size of each element in `v`
[in]	f	comparison function

Returns: pointer to matching element or NULL if there was no match

§ cgul_binary_search_pointers()

CGUL_EXPORT void* cgul_binary_search_pointers	(	cgul_exception_t *	cex,
		const void *	key,
		const void **	v,
		size_t	v_count,
		cgul_binary_search__compare_t	f
	)

If your array is already composed of pointers, you can directly call this function. v will be searched using f in the same manner as described in cgul_binary_search().

Parameters

[in]	cex	c-style exception
[in]	key	value to search for
[in]	v	array of pointers to sorted elements to search
[in]	v_count	number of elements in `v`
[in]	f	comparison function

Returns: pointer to matching element or NULL if there was no match

§ cgul_binary_search_ceiling()

CGUL_EXPORT void* cgul_binary_search_ceiling	(	cgul_exception_t *	cex,
		const void *	key,
		const void *	v,
		size_t	v_count,
		size_t	element_size,
		cgul_binary_search__compare_t	f
	)

Peform a binary search for the smallest element that is greater than or equal to the search key key. This function has the same parameter signature as stdlib's bsearch(). v is a pointer to the top of your array. v_count is the number of elements in v. element_size is the number of contiguous bytes that comprise each element. The void* return value is a pointer to the ceiling element. If there is more than one ceiling element, any of the matching elements could be returned. If no match was found, the return value is NULL.

Parameters

[in]	cex	c-style exception
[in]	key	value to search for
[in]	v	array of sorted elements to search
[in]	v_count	number of elements in `v`
[in]	element_size	size of each element in `v`
[in]	f	comparison function

Returns: pointer to matching element or NULL if there was no match

§ cgul_binary_search_ceiling_pointers()

CGUL_EXPORT void* cgul_binary_search_ceiling_pointers	(	cgul_exception_t *	cex,
		const void *	key,
		const void **	v,
		size_t	v_count,
		cgul_binary_search__compare_t	f
	)

If your array is already composed of pointers, you can directly call this function. v will be searched using f in the same manner as described in cgul_binary_search_ceiling().

Parameters

[in]	cex	c-style exception
[in]	key	value to search for
[in]	v	array of pointers to sorted elements to search
[in]	v_count	number of elements in `v`
[in]	f	comparison function

Returns: pointer to matching element or NULL if there was no match

§ cgul_binary_search_floor()

CGUL_EXPORT void* cgul_binary_search_floor	(	cgul_exception_t *	cex,
		const void *	key,
		const void *	v,
		size_t	v_count,
		size_t	element_size,
		cgul_binary_search__compare_t	f
	)

Peform a binary search for the largest element that is less than or equal to the search key key. This function has the same parameter signature as stdlib's bsearch(). v is a pointer to the top of your array. v_count is the number of elements in v. element_size is the number of contiguous bytes that comprise each element. The void* return value is a pointer to the floor element. If there is more than one floor element, any of the matching elements could be returned. If no match was found, the return value is NULL.

Parameters

[in]	cex	c-style exception
[in]	key	value to search for
[in]	v	array of sorted elements to search
[in]	v_count	number of elements in `v`
[in]	element_size	size of each element in `v`
[in]	f	comparison function

Returns: pointer to matching element or NULL if there was no match

§ cgul_binary_search_floor_pointers()

CGUL_EXPORT void* cgul_binary_search_floor_pointers	(	cgul_exception_t *	cex,
		const void *	key,
		const void **	v,
		size_t	v_count,
		cgul_binary_search__compare_t	f
	)

If your array is already composed of pointers, you can directly call this function. v will be searched using f in the same manner as described in cgul_binary_search_floor().

Parameters

[in]	cex	c-style exception
[in]	key	value to search for
[in]	v	array of pointers to sorted elements to search
[in]	v_count	number of elements in `v`
[in]	f	comparison function

Returns: pointer to matching element or NULL if there was no match

§ cgul_binary_search_irange()

CGUL_EXPORT int cgul_binary_search_irange	(	cgul_exception_t *	cex,
		int	low,
		int	high,
		int()(int, void )	f,
		void *	data
	)

This function performs a binary search over the range of integers [low, high) where low is the inclusive lower bound of the range and high is the exclusive upper bound of the range. For each iteration, the user-supplied callback function f will be called with the user-supplied client data data and the next integer to test. f should return less than zero, zero, or greater than zero if the integer passed into f is less than, equal to, or greater than the target index.

This function only returns whether a match was found. If the index where the match occurred is required, the client must arrange for it to be returned through the client data data.

To perform a binary search over an array, call this function as follows:

    binary_search_irange(0, length, f, data);

However, to perform a binary search over the inclusive mathematical range [xmin, xmax], call this function as follows:

    binary_search_irange(xmin, xmax + 1, f, data);

Parameters

[in]	cex	c-style exception
[in]	low	inclusive lower bound
[in]	high	exclusive upper bound
[in]	f	callback function
[in]	data	client data

Returns: whether a match was found

Variable Documentation

§ cgul_binary_search__compare_t

CGUL_BEGIN_C typedef int(* cgul_binary_search__compare_t) (const void *search_key, const void *array_element)

This typedef is the interface the client must define in order to perform a binary search of the search key search_key. The comparison function should return less than zero, zero, or greater than zero if search_key is less than, equal to, or greater than the array element array_element respectively.

Parameters

[in]	search_key	search key
[in]	array_element	array element

Returns: result of comparison

Functions

Variables

Detailed Description

Function Documentation

§ cgul_binary_search()

§ cgul_binary_search_pointers()

§ cgul_binary_search_ceiling()

§ cgul_binary_search_ceiling_pointers()

§ cgul_binary_search_floor()

§ cgul_binary_search_floor_pointers()

§ cgul_binary_search_irange()

Variable Documentation

§ cgul_binary_search__compare_t