81 lines
2.2 KiB
C
81 lines
2.2 KiB
C
/* bsearch.c - bsearch routine for the stdlib ANSI library */
|
|
|
|
/* Copyright 1992-1993 Wind River Systems, Inc. */
|
|
|
|
/*
|
|
modification history
|
|
--------------------
|
|
01c,08feb93,jdi documentation cleanup for 5.1.
|
|
01b,20sep92,smb documentation additions.
|
|
01a,19jul92,smb written and documented
|
|
*/
|
|
|
|
/*
|
|
DESCRIPTION
|
|
|
|
INCLUDE FILE: stdlib.h
|
|
|
|
SEE ALSO: American National Standard X3.159-1989
|
|
|
|
NOMANUAL
|
|
*/
|
|
|
|
#include "vxWorks.h"
|
|
#include "stdlib.h"
|
|
|
|
/******************************************************************************
|
|
*
|
|
* bsearch - perform a binary search (ANSI)
|
|
*
|
|
* This routine searches an array of <nmemb> objects, the initial element of
|
|
* which is pointed to by <base0>, for an element that matches the object
|
|
* pointed to by <key>. The <size> of each element of the array is specified
|
|
* by <size>.
|
|
*
|
|
* The comparison function pointed to by <compar> is called with two arguments
|
|
* that point to the <key> object and to an array element, in that order. The
|
|
* function shall return an integer less than, equal to, or greater than zero if
|
|
* the <key> object is considered, respectively, to be less than, to match, or
|
|
* to be greater than the array element. The array shall consist of all the
|
|
* elements that compare greater than the <key> object, in that order.
|
|
*
|
|
* INCLUDE FILES: stdlib.h
|
|
*
|
|
* RETURNS:
|
|
* A pointer to a matching element of the array, or a NULL pointer
|
|
* if no match is found. If two elements compare as equal, which element
|
|
* is matched is unspecified.
|
|
*/
|
|
|
|
void * bsearch
|
|
(
|
|
FAST const void * key, /* element to match */
|
|
const void * base0, /* initial element in array */
|
|
size_t nmemb, /* array to search */
|
|
FAST size_t size, /* size of array element */
|
|
FAST int (*compar) (const void *, const void *) /* comparison function */
|
|
)
|
|
{
|
|
FAST const char * base = base0;
|
|
FAST const void * p;
|
|
FAST int lim;
|
|
FAST int cmp;
|
|
|
|
for (lim = nmemb; lim != 0; lim >>= 1)
|
|
{
|
|
p = base + (lim >> 1) * size;
|
|
cmp = (*compar)(key, p);
|
|
|
|
if (cmp == 0)
|
|
return (CHAR_FROM_CONST (p));
|
|
|
|
if (cmp > 0)
|
|
{ /* key > p: move right */
|
|
base = (CHAR_FROM_CONST (p) + size);
|
|
lim--;
|
|
}
|
|
}
|
|
|
|
return (NULL);
|
|
}
|