How do I use bsearch() ?

[Amandil]

Hi, all.

I'd like to check whether a certain string (one that I got from a
user, or read from a file) is contained in a table of strings. The
format of the table is
char *table[] = { "string1", "string2", "string3", ..., NULL }
I wrote my own function that uses strcmp():
int table_lookup(ch ar *s, char *list[])
{
char *t;
int index = 0;

while ((t = list[index]) != NULL) {
if ( !strcmp(s, t)) {
return 1; /* Found */
}
index++;
}
return 0; /* Not found */
}

I imagine I could use the library function bsearch() to do the same,
and possibly quicker. I do not know, however, what the call to
bsearch() is supposed to look like. A copy of the standard is not very
helpful. I would try
char *t = bsearch(s, list, sizeof list, sizeof (char *), strcmp);
Will this work? Or did I do something wrong? (with faq 13.8 in mind)

[santosh]

Re: How do I use bsearch() ?

Amandil wrote:

Hi, all.
>
I'd like to check whether a certain string (one that I got from a
user, or read from a file) is contained in a table of strings. The
format of the table is
char *table[] = { "string1", "string2", "string3", ..., NULL }
I wrote my own function that uses strcmp():
int table_lookup(ch ar *s, char *list[])
{
char *t;
int index = 0;
>
while ((t = list[index]) != NULL) {
if ( !strcmp(s, t)) {
return 1; /* Found */
}
index++;
}
return 0; /* Not found */
}
>
I imagine I could use the library function bsearch() to do the same,
and possibly quicker. I do not know, however, what the call to
bsearch() is supposed to look like. A copy of the standard is not very
helpful. I would try
char *t = bsearch(s, list, sizeof list, sizeof (char *), strcmp);
Will this work? Or did I do something wrong? (with faq 13.8 in mind)

Firstly for bsearch to work your array of strings must already be sorted
by some convention and the comparison function that you supply to
bsearch must use the same convention.

You could do:

char *n = bsearch(s, &table, (sizeof table/sizeof table[0]),
sizeof table[0], compar);

[Richard Heathfield]

Re: How do I use bsearch() ?

Amandil said:

Hi, all.
>
I'd like to check whether a certain string (one that I got from a
user, or read from a file) is contained in a table of strings. The
format of the table is
char *table[] = { "string1", "string2", "string3", ..., NULL }

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void dump(const char **t, size_t n)
{
while(n--)
{
printf("%s\n", *t++);
}
}

int cmp(const void *vleft, const void *vright)
{
const char * const *left = vleft;
const char * const *right = vright;
return strcmp(*left, *right);
}
int main(void)
{
const char *table[] =
{
"now is the time",
"for all good men",
"to bring a bottle",
"to the party",
NULL
};
size_t num_elems = sizeof table / sizeof table[0];
const char *needle = "to bring a bottle";
const char **result = NULL;

puts("Before sort:");
dump(table, num_elems - 1);
qsort(table, num_elems - 1, sizeof table[0], cmp);
puts("After sort:");
dump(table, num_elems - 1);
printf("Searchi ng for \"%s\"\n", needle);
result = bsearch(&needle , table, num_elems - 1, sizeof table[0], cmp);
if(result != NULL)
{
printf("Found \"%s\" at position %d\n", *result, (int)(result -
table));
}
else
{
printf("Did not find \"%s\" in array.\n", needle);
}


return 0;
}

--
Richard Heathfield <http://www.cpax.org.uk >
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[Andrey Tarasevich]

Re: How do I use bsearch() ?

Harald van Dijk wrote:

...
Secondly, strcmp takes two parameters of type const char *. bsearch's
comparison function must take two parameters of type const void *. You
need to define a function such as
int mystrcmp(const void *a, const void *b) {
return strcmp(a, b);
}
...

The comparison function used by 'bsearch' receives pointers to the array
elements, which in the OP's case are themselves pointers. For this
reason your implementation of the comparison function is incorrect. The
correct implementation of the comparison function might look as follows

int mystrcmp(const void *a, const void *b) {
return strcmp(*(char* const*) a, *(char* const*) b);
}

(see also Richard Heathfield's message)

--
Best regards,
Andrey Tarasevich

[Harald van =?UTF-8?b?RMSzaw==?=]

Re: How do I use bsearch() ?

On Wed, 26 Mar 2008 16:23:51 -0700, Andrey Tarasevich wrote:

Harald van Dijk wrote:

>...
>Secondly, strcmp takes two parameters of type const char *. bsearch's
>comparison function must take two parameters of type const void *. You
>need to define a function such as
> int mystrcmp(const void *a, const void *b) {
> return strcmp(a, b);
> }
>...

>
The comparison function used by 'bsearch' receives pointers to the array
elements, which in the OP's case are themselves pointers. For this
reason your implementation of the comparison function is incorrect. The
correct implementation of the comparison function might look as follows
>
int mystrcmp(const void *a, const void *b) {
return strcmp(*(char* const*) a, *(char* const*) b);
}
>
(see also Richard Heathfield's message)

You're right, I messed up on that, and your fixed version is correct. For
a fix, however, I would probably choose to write it as

int mystrcmp(const void *_a, const void *_b) {
char *const *a = _a;
char *const *b = _b;
return strcmp(*a, *b);
}

In general, when casts aren't necessary, don't use them. In this case, an
implicit conversion would help you by letting you know when you
accidentally write const char ** instead of char *const *.