bsearch for Windows ce

[val]

Hi,
I found that Windows CE doesn't include bsearch function.
Can somebody point me into right direction in order to solve that issue
Thanks,
val

[Ben Pfaff]

Re: bsearch for Windows ce

valrub@hotmail. com (val) writes:
[color=blue]
> I found that Windows CE doesn't include bsearch function.[/color]

Here's a replacement for it with an (in my opinion) improved
interface. It's from a real program, so criticism and bug
reports are welcomed.

/* Compares A and B, given auxiliary data AUX, and returns a
strcmp()-type result. */
typedef int algo_compare_fu nc (const void *a, const void *b, void *aux);

/* Searches ARRAY, which contains COUNT of SIZE bytes each, using
a binary search. Returns any element that equals VALUE, if
one exists, or a null pointer otherwise. ARRAY must ordered
according to COMPARE. AUX is passed to COMPARE as auxiliary
data. */
void *
binary_search (const void *array, size_t count, size_t size,
void *value,
algo_compare_fu nc *compare, void *aux)
{
assert (array != NULL);
assert (count <= INT_MAX);
assert (compare != NULL);

if (count != 0)
{
const unsigned char *first = array;
int low = 0;
int high = count - 1;

while (low <= high)
{
int middle = (low + high) / 2;
const unsigned char *element = first + middle * size;
int cmp = compare (value, element, aux);

if (cmp > 0)
low = middle + 1;
else if (cmp < 0)
high = middle - 1;
else
return (void *) element;
}
}

return NULL;
}

--
"What is appropriate for the master is not appropriate for the novice.
You must understand the Tao before transcending structure."
--The Tao of Programming

[CBFalconer]

Re: bsearch for Windows ce

val wrote:[color=blue]
>
> I found that Windows CE doesn't include bsearch function. Can
> somebody point me into right direction in order to solve that.[/color]

bsearch() is a standard C function, and has been since at least
1989. Complain to the compiler vendor. It has nothing to do with
the OS.

The other choice is to write your own, under another name, as Ben
has suggested. But that way you cannot take advantage of possible
system optimizations.

--
Chuck F (cbfalconer@yah oo.com) (cbfalconer@wor ldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net> USE worldnet address!

[Ben Pfaff]

Re: bsearch for Windows ce

CBFalconer <cbfalconer@yah oo.com> writes:

[bsearch]
[color=blue]
> The other choice is to write your own, under another name, as Ben
> has suggested. But that way you cannot take advantage of possible
> system optimizations.[/color]

It's doubtful whether there are meaningful optimizations for a
function that will probably spend most of its time calling
another function via a pointer. On modern architectures trying
to optimize bsearch() is probably a lost cause. I note, for
example, that the implementation of bsearch in glibc is written
in C without much attempt at optimization.
--
Ben Pfaff
email: blp@cs.stanford .edu
web: http://benpfaff.org

[Keith Thompson]

Re: bsearch for Windows ce

CBFalconer <cbfalconer@yah oo.com> writes:[color=blue]
> val wrote:[color=green]
> >
> > I found that Windows CE doesn't include bsearch function. Can
> > somebody point me into right direction in order to solve that.[/color]
>
> bsearch() is a standard C function, and has been since at least
> 1989. Complain to the compiler vendor. It has nothing to do with
> the OS.[/color]

He may be using a freestanding implementation, which isn't required to
support bsearch().

--
Keith Thompson (The_Other_Keit h) kst-u@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[pete]

Re: bsearch for Windows ce

val wrote:[color=blue]
>
> Hi,
> I found that Windows CE doesn't include bsearch function.
> Can somebody point me into right direction in
> order to solve that issue[/color]

void *b_search(const void *key, const void *base,
size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
size_t odd_mask, bytes;
const char *center, *high, *low;
int comp;

odd_mask = ((size ^ (size - 1)) >> 1) + 1;
low = base;
bytes = nmemb == 0 ? size : size + 1;
center = low + nmemb * size;
comp = 0;
while (bytes != size) {
if (comp > 0) {
low = center;
} else {
high = center;
}
bytes = high - low;
center = low + ((bytes & odd_mask ? bytes - size : bytes) >> 1);
comp = compar(key, center);
if (comp == 0) {
return (void *)center;
}
}
return NULL;
}

--
pete

[pete]

Re: bsearch for Windows ce

Ben Pfaff wrote:[color=blue]
>
> valrub@hotmail. com (val) writes:
>[color=green]
> > I found that Windows CE doesn't include bsearch function.[/color]
>
> Here's a replacement for it with an (in my opinion) improved
> interface. It's from a real program, so criticism and bug
> reports are welcomed.[/color]
[color=blue]
> assert (count <= INT_MAX);[/color]
[color=blue]
> int low = 0;
> int high = count - 1;
> int middle = (low + high) / 2;[/color]

low, high and middle should all be size_t.

--
pete

[val]

Re: bsearch for Windows ce

Ben Pfaff <blp@cs.stanfor d.edu> wrote in message news:<87d61fq64 b.fsf@benpfaff. org>...[color=blue]
> valrub@hotmail. com (val) writes:
>[color=green]
> > I found that Windows CE doesn't include bsearch function.[/color]
>
> Here's a replacement for it with an (in my opinion) improved
> interface. It's from a real program, so criticism and bug
> reports are welcomed.
>
> /* Compares A and B, given auxiliary data AUX, and returns a
> strcmp()-type result. */
> typedef int algo_compare_fu nc (const void *a, const void *b, void *aux);
>
> /* Searches ARRAY, which contains COUNT of SIZE bytes each, using
> a binary search. Returns any element that equals VALUE, if
> one exists, or a null pointer otherwise. ARRAY must ordered
> according to COMPARE. AUX is passed to COMPARE as auxiliary
> data. */
> void *
> binary_search (const void *array, size_t count, size_t size,
> void *value,
> algo_compare_fu nc *compare, void *aux)
> {
> assert (array != NULL);
> assert (count <= INT_MAX);
> assert (compare != NULL);
>
> if (count != 0)
> {
> const unsigned char *first = array;
> int low = 0;
> int high = count - 1;
>
> while (low <= high)
> {
> int middle = (low + high) / 2;
> const unsigned char *element = first + middle * size;
> int cmp = compare (value, element, aux);
>
> if (cmp > 0)
> low = middle + 1;
> else if (cmp < 0)
> high = middle - 1;
> else
> return (void *) element;
> }
> }
>
> return NULL;
> }[/color]

Thank you Ben, it really help me.

[val]

Re: bsearch for Windows ce

CBFalconer <cbfalconer@yah oo.com> wrote in message news:<412D2E1C. 6C17EA15@yahoo. com>...[color=blue]
> val wrote:[color=green]
> >
> > I found that Windows CE doesn't include bsearch function. Can
> > somebody point me into right direction in order to solve that.[/color]
>
> bsearch() is a standard C function, and has been since at least
> 1989. Complain to the compiler vendor. It has nothing to do with
> the OS.
>
> The other choice is to write your own, under another name, as Ben
> has suggested. But that way you cannot take advantage of possible
> system optimizations.[/color]

bsearch() is a standard C function - yes, I agree, but for some
unknown reason it doesn't supported by Microsoft CE .NET package,
which include Platform Builder and eMbedded Visual C++ 4, even in the
stdlib.h in that versions it doesn't exist.

[val]

Re: bsearch for Windows ce

pete <pfiland@mindsp ring.com> wrote in message news:<412D63D8. 7072@mindspring .com>...[color=blue]
> val wrote:[color=green]
> >
> > Hi,
> > I found that Windows CE doesn't include bsearch function.
> > Can somebody point me into right direction in
> > order to solve that issue[/color]
>
> void *b_search(const void *key, const void *base,
> size_t nmemb, size_t size,
> int (*compar)(const void *, const void *))
> {
> size_t odd_mask, bytes;
> const char *center, *high, *low;
> int comp;
>
> odd_mask = ((size ^ (size - 1)) >> 1) + 1;
> low = base;
> bytes = nmemb == 0 ? size : size + 1;
> center = low + nmemb * size;
> comp = 0;
> while (bytes != size) {
> if (comp > 0) {
> low = center;
> } else {
> high = center;
> }
> bytes = high - low;
> center = low + ((bytes & odd_mask ? bytes - size : bytes) >> 1);
> comp = compar(key, center);
> if (comp == 0) {
> return (void *)center;
> }
> }
> return NULL;
> }[/color]


thank you pete

[CBFalconer]

Re: bsearch for Windows ce

val wrote:[color=blue]
> CBFalconer <cbfalconer@yah oo.com> wrote[color=green]
>> val wrote:[color=darkred]
>>>
>>> I found that Windows CE doesn't include bsearch function. Can
>>> somebody point me into right direction in order to solve that.[/color]
>>
>> bsearch() is a standard C function, and has been since at least
>> 1989. Complain to the compiler vendor. It has nothing to do with
>> the OS.
>>
>> The other choice is to write your own, under another name, as Ben
>> has suggested. But that way you cannot take advantage of possible
>> system optimizations.[/color]
>
> bsearch() is a standard C function - yes, I agree, but for some
> unknown reason it doesn't supported by Microsoft CE .NET package,
> which include Platform Builder and eMbedded Visual C++ 4, even in the
> stdlib.h in that versions it doesn't exist.[/color]

IMO you should ask for your money back. A useful rule is never to
use Microsoft products, they usually foul standards.

--
Chuck F (cbfalconer@yah oo.com) (cbfalconer@wor ldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net> USE worldnet address!

[Randy Howard]

Re: bsearch for Windows ce

In article <412E6DFA.E60B8 FF9@yahoo.com>, cbfalconer@yaho o.com says...[color=blue]
> IMO you should ask for your money back.[/color]

Good luck getting a refund from MS over a standards violation.
Thanks for the laugh.

--
Randy Howard
To reply, remove FOOBAR.

[CBFalconer]

Re: bsearch for Windows ce

Randy Howard wrote:[color=blue]
> cbfalconer@yaho o.com says...
>[/color]
... about VC for WinCE missing bsearch() ...[color=blue]
>[color=green]
>> IMO you should ask for your money back.[/color]
>
> Good luck getting a refund from MS over a standards violation.
> Thanks for the laugh.[/color]

I said 'ask', not 'get'. The important thing is that he learns to
not buy anything with the MS stamp or the Schildt name on it.

However, he might be able to actually do something through small
claims court. Once he gets a judgement he can seize anything of
theirs to satisfy it, which would leave room for constructive
imagination.

--
Chuck F (cbfalconer@yah oo.com) (cbfalconer@wor ldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net> USE worldnet address!

[pete]

Re: bsearch for Windows ce

val wrote:[color=blue]
>
> pete <pfiland@mindsp ring.com>
> wrote in message news:<412D63D8. 7072@mindspring .com>...[color=green]
> > val wrote:[color=darkred]
> > >
> > > Hi,
> > > I found that Windows CE doesn't include bsearch function.
> > > Can somebody point me into right direction in
> > > order to solve that issue[/color]
> >
> > void *b_search(const void *key, const void *base,[/color][/color]
[color=blue]
> thank you pete[/color]

You're welcome. I wrote a new one, with a riddle.
What difference does it make whether or not
the break statement is commented out?

void *b_search(const void *key, const void *base,
size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
int comp;
size_t odd_mask, bytes;
const char *high, *low, *found;

found = NULL;
if (nmemb != 0) {
odd_mask = size ^ size - 1;
low = base;
high = low + nmemb * size;
do {
bytes = high - low;
base = low
+ ((bytes & odd_mask ? bytes - size : bytes) >> 1);
comp = compar(key, base);
if (comp == 0) {
found = base;
/**
break;
/*//**/
}
*(comp > 0 ? &low : &high) = base;
} while (bytes != size);
}
return (void *)found;
}

--
pete