bsearch for Windows ce

V

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
 
B

Ben Pfaff

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

CBFalconer

val said:
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.
 
B

Ben Pfaff

[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.
 
K

Keith Thompson

CBFalconer said:
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().
 
P

pete

val said:
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;
}
 
V

val

Ben Pfaff said:
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.
 
V

val

CBFalconer said:
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.
 
V

val

pete said:
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
 
C

CBFalconer

val said:
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.
 
C

CBFalconer

Randy said:
(e-mail address removed) says...
... about VC for WinCE missing bsearch() ...
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.
 
P

pete

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

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top