By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
435,454 Members | 3,191 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 435,454 IT Pros & Developers. It's quick & easy.

bsearch for Windows ce

P: n/a
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
Nov 14 '05 #1
Share this Question
Share on Google+
13 Replies


P: n/a
va****@hotmail.com (val) writes:
I found that Windows CE doesn't include bsearch function.


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_func (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_func *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
Nov 14 '05 #2

P: n/a
val wrote:

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


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 (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Nov 14 '05 #3

P: n/a
CBFalconer <cb********@yahoo.com> writes:

[bsearch]
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.


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: bl*@cs.stanford.edu
web: http://benpfaff.org
Nov 14 '05 #4

P: n/a
CBFalconer <cb********@yahoo.com> writes:
val wrote:

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


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.


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

--
Keith Thompson (The_Other_Keith) ks***@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.
Nov 14 '05 #5

P: n/a
val wrote:

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


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
Nov 14 '05 #6

P: n/a
Ben Pfaff wrote:

va****@hotmail.com (val) writes:
I found that Windows CE doesn't include bsearch function.
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.

assert (count <= INT_MAX); int low = 0;
int high = count - 1;
int middle = (low + high) / 2;


low, high and middle should all be size_t.

--
pete
Nov 14 '05 #7

P: n/a
val
Ben Pfaff <bl*@cs.stanford.edu> wrote in message news:<87************@benpfaff.org>...
va****@hotmail.com (val) writes:
I found that Windows CE doesn't include bsearch function.


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_func (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_func *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;
}


Thank you Ben, it really help me.
Nov 14 '05 #8

P: n/a
val
CBFalconer <cb********@yahoo.com> wrote in message news:<41***************@yahoo.com>...
val wrote:

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


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.


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.
Nov 14 '05 #9

P: n/a
val
pete <pf*****@mindspring.com> wrote in message news:<41***********@mindspring.com>...
val wrote:

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


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;
}

thank you pete
Nov 14 '05 #10

P: n/a
val wrote:
CBFalconer <cb********@yahoo.com> wrote
val wrote:

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


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.


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.


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

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Nov 14 '05 #11

P: n/a
In article <41***************@yahoo.com>, cb********@yahoo.com says...
IMO you should ask for your money back.


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

--
Randy Howard
To reply, remove FOOBAR.
Nov 14 '05 #12

P: n/a
Randy Howard wrote:
cb********@yahoo.com says...
... about VC for WinCE missing bsearch() ...
IMO you should ask for your money back.


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


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 (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Nov 14 '05 #13

P: n/a
val wrote:

pete <pf*****@mindspring.com>
wrote in message news:<41***********@mindspring.com>...
val wrote:

Hi,
I found that Windows CE doesn't include bsearch function.
Can somebody point me into right direction in
order to solve that issue
void *b_search(const void *key, const void *base,

thank you pete


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
Nov 14 '05 #14

This discussion thread is closed

Replies have been disabled for this discussion.