NAME

KS_binary_search — search utility functions

SYNOPSIS

#include <libks/search.h>

type *
KS_binary_search(type *v, size_t n, int (*cmp)(type *haystack, needle), needle);

DESCRIPTION

The search API provides functions for finding elements in data structures.

The KS_binary_search() function performs a binary search of the sorted vector v with n number of elements. It searches for the first element in which the cmp predicate yields a match as signalled by returning zero. If haystack is less than needle, cmp must return an integer less than zero. If haystack is greater than needle, cmp must return an integer greater than zero. The needle can be of any type and is passed as is to the cmp function. It returns a pointer to the found element on success and NULL if nothing was found.

EXAMPLES

struct page {
	int id;
};

static int
page_cmp(const struct page *page, int id)
{
	if (page->id < id)
		return -1;
	if (page->id > id)
		return 1;
	return 0;
}

const struct page *
find_page_by_id(const struct page *pages, size_t n, int id)
{
	return KS_binary_search(pages, n, id);
}

AUTHORS

Anton Lindqvist <anton@basename.se>