WebSVN – Kolibri OS – Diff – /contrib/sdk/sources/newlib/libc/search/bsearch.c


/*
 * bsearch.c
 * Original Author:	G. Haley
 * Rewritten by:	G. Noer
 *
 * Searches an array of nmemb members, the initial member of which is pointed
 * to by base, for a member that matches the object pointed to by key. The
 * contents of the array shall be in ascending order according to a comparison
 * function pointed to by compar. The function shall return an integer less
 * than, equal to or greater than zero if the first argument is considered to be
 * respectively less than, equal to or greater than the second. Returns a
 * pointer to the matching member of the array, or a null pointer if no match
 * is found.
 */
 
/*
FUNCTION
<>---binary search
 
INDEX
	bsearch
 
ANSI_SYNOPSIS
	#include 
	void *bsearch(const void *<[key]>, const void *<[base]>,
		size_t <[nmemb]>, size_t <[size]>,
		int (*<[compar]>)(const void *, const void *));
 
TRAD_SYNOPSIS
	#include 
	char *bsearch(<[key]>, <[base]>, <[nmemb]>, <[size]>, <[compar]>)
	char *<[key]>;
	char *<[base]>;
	size_t <[nmemb]>, <[size]>;
	int (*<[compar]>)();
 
DESCRIPTION
<> searches an array beginning at <[base]> for any element
that matches <[key]>, using binary search.  <[nmemb]> is the element
count of the array; <[size]> is the size of each element.
 
The array must be sorted in ascending order with respect to the
comparison function <[compar]> (which you supply as the last argument of
<>).
 
You must define the comparison function <<(*<[compar]>)>> to have two
arguments; its result must be negative if the first argument is
less than the second, zero if the two arguments match, and
positive if the first argument is greater than the second (where
``less than'' and ``greater than'' refer to whatever arbitrary
ordering is appropriate).
 
RETURNS
Returns a pointer to an element of <[array]> that matches <[key]>.  If
more than one matching element is available, the result may point to
any of them.
 
PORTABILITY
<> is ANSI.
 
No supporting OS subroutines are required.
*/
 
 
 
#include 
 
_PTR
_DEFUN (bsearch, (key, base, nmemb, size, compar),
	_CONST _PTR key _AND
	_CONST _PTR base _AND
	size_t nmemb _AND
	size_t size _AND
	int _EXFNPTR(compar, (const _PTR, const _PTR)))
{
  _PTR current;
  size_t lower = 0;
  size_t upper = nmemb;
  size_t index;
  int result;
 
  if (nmemb == 0 || size == 0)
    return NULL;
 
  while (lower < upper)
    {
      index = (lower + upper) / 2;
      current = (_PTR) (((char *) base) + (index * size));
 
      result = compar (key, current);
 
      if (result < 0)
        upper = index;
      else if (result > 0)
        lower = index + 1;
      else
	return current;
    }
 
  return NULL;
}

Rev 4874	Rev 4921
1	/*	1	/*
2	* bsearch.c	2	* bsearch.c
3	* Original Author: G. Haley	3	* Original Author: G. Haley
4	* Rewritten by: G. Noer	4	* Rewritten by: G. Noer
5	*	5	*
6	* Searches an array of nmemb members, the initial member of which is pointed	6	* Searches an array of nmemb members, the initial member of which is pointed
7	* to by base, for a member that matches the object pointed to by key. The	7	* to by base, for a member that matches the object pointed to by key. The
8	* contents of the array shall be in ascending order according to a comparison	8	* contents of the array shall be in ascending order according to a comparison
9	* function pointed to by compar. The function shall return an integer less	9	* function pointed to by compar. The function shall return an integer less
10	* than, equal to or greater than zero if the first argument is considered to be	10	* than, equal to or greater than zero if the first argument is considered to be
11	* respectively less than, equal to or greater than the second. Returns a	11	* respectively less than, equal to or greater than the second. Returns a
12	* pointer to the matching member of the array, or a null pointer if no match	12	* pointer to the matching member of the array, or a null pointer if no match
13	* is found.	13	* is found.
14	*/	14	*/
15		15
16	/*	16	/*
17	FUNCTION	17	FUNCTION
18	<>---binary search	18	<>---binary search
19		19
20	INDEX	20	INDEX
21	bsearch	21	bsearch
22		22
23	ANSI_SYNOPSIS	23	ANSI_SYNOPSIS
24	#include	24	#include
25	void bsearch(const void <[key]>, const void *<[base]>,	25	void bsearch(const void <[key]>, const void *<[base]>,
26	size_t <[nmemb]>, size_t <[size]>,	26	size_t <[nmemb]>, size_t <[size]>,
27	int (<[compar]>)(const void , const void *));	27	int (<[compar]>)(const void , const void *));
28		28
29	TRAD_SYNOPSIS	29	TRAD_SYNOPSIS
30	#include	30	#include
31	char *bsearch(<[key]>, <[base]>, <[nmemb]>, <[size]>, <[compar]>)	31	char *bsearch(<[key]>, <[base]>, <[nmemb]>, <[size]>, <[compar]>)
32	char *<[key]>;	32	char *<[key]>;
33	char *<[base]>;	33	char *<[base]>;
34	size_t <[nmemb]>, <[size]>;	34	size_t <[nmemb]>, <[size]>;
35	int (*<[compar]>)();	35	int (*<[compar]>)();
36		36
37	DESCRIPTION	37	DESCRIPTION
38	<> searches an array beginning at <[base]> for any element	38	<> searches an array beginning at <[base]> for any element
39	that matches <[key]>, using binary search. <[nmemb]> is the element	39	that matches <[key]>, using binary search. <[nmemb]> is the element
40	count of the array; <[size]> is the size of each element.	40	count of the array; <[size]> is the size of each element.
41		41
42	The array must be sorted in ascending order with respect to the	42	The array must be sorted in ascending order with respect to the
43	comparison function <[compar]> (which you supply as the last argument of	43	comparison function <[compar]> (which you supply as the last argument of
44	<>).	44	<>).
45		45
46	You must define the comparison function <<(*<[compar]>)>> to have two	46	You must define the comparison function <<(*<[compar]>)>> to have two
47	arguments; its result must be negative if the first argument is	47	arguments; its result must be negative if the first argument is
48	less than the second, zero if the two arguments match, and	48	less than the second, zero if the two arguments match, and
49	positive if the first argument is greater than the second (where	49	positive if the first argument is greater than the second (where
50	``less than'' and ``greater than'' refer to whatever arbitrary	50	``less than'' and ``greater than'' refer to whatever arbitrary
51	ordering is appropriate).	51	ordering is appropriate).
52		52
53	RETURNS	53	RETURNS
54	Returns a pointer to an element of <[array]> that matches <[key]>. If	54	Returns a pointer to an element of <[array]> that matches <[key]>. If
55	more than one matching element is available, the result may point to	55	more than one matching element is available, the result may point to
56	any of them.	56	any of them.
57		57
58	PORTABILITY	58	PORTABILITY
59	<> is ANSI.	59	<> is ANSI.
60		60
61	No supporting OS subroutines are required.	61	No supporting OS subroutines are required.
62	*/	62	*/
63		-
64	#include <_ansi.h>	-
65	#include	63
66	#include	64	#include
67		65
68	_PTR	66	_PTR
69	_DEFUN (bsearch, (key, base, nmemb, size, compar),	67	_DEFUN (bsearch, (key, base, nmemb, size, compar),
70	_CONST _PTR key _AND	68	_CONST _PTR key _AND
71	_CONST _PTR base _AND	69	_CONST _PTR base _AND
72	size_t nmemb _AND	70	size_t nmemb _AND
73	size_t size _AND	71	size_t size _AND
74	int _EXFNPTR(compar, (const _PTR, const _PTR)))	72	int _EXFNPTR(compar, (const _PTR, const _PTR)))
75	{	73	{
76	_PTR current;	74	_PTR current;
77	size_t lower = 0;	75	size_t lower = 0;
78	size_t upper = nmemb;	76	size_t upper = nmemb;
79	size_t index;	77	size_t index;
80	int result;	78	int result;
81		79
82	if (nmemb == 0 \|\| size == 0)	80	if (nmemb == 0 \|\| size == 0)
83	return NULL;	81	return NULL;
84		82
85	while (lower < upper)	83	while (lower < upper)
86	{	84	{
87	index = (lower + upper) / 2;	85	index = (lower + upper) / 2;
88	current = (_PTR) (((char ) base) + (index size));	86	current = (_PTR) (((char ) base) + (index size));
89		87
90	result = compar (key, current);	88	result = compar (key, current);
91		89
92	if (result < 0)	90	if (result < 0)
93	upper = index;	91	upper = index;
94	else if (result > 0)	92	else if (result > 0)
95	lower = index + 1;	93	lower = index + 1;
96	else	94	else
97	return current;	95	return current;
98	}	96	}
99		97
100	return NULL;	98	return NULL;
101	}	99	}

Subversion Repositories Kolibri OS

(root)/contrib/sdk/sources/newlib/libc/search/bsearch.c – Rev 4874 → 4921