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(char *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]

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(char *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);

 

[Harald van Dijk]

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(char *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)

You've got the right idea, but this shouldn't compile, and it wouldn't
work even if it did.

Firstly, sizeof list is not the number of elements in list. It's the
number of bytes in list. You need to pass the number of elements, which
is sizeof table / sizeof table[0]. Please note that it's _not_ sizeof
list / sizeof list[0]. list, despite being declared as an array, is a
pointer, and sizeof list is the size of this pointer.

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

Thirdly, you need to keep this array sorted for bsearch to work. You've
done so now, but are you sure you can keep it that way reliably? If
you're not sure, you would need to call qsort on the array at program
startup.

If you pay attention to those three points, you should be able to get
your program working with bsearch. However, is it the right approach
here? It's fine if you want to figure out how to make things work, but if
the list won't change at runtime, consider taking a look at tools such as
gperf, which may be able to create a better alternative.

 

[Eric Sosman]

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(char *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)

No, it won't work. First, strcmp() is the wrong function
to use, as explained in the FAQ. Second, sizeof list is the
size of one char**, not the number of elements in the array
(see Question 6.21). Third, the array includes a NULL element
you do *not* want to search, so you need to omit that from the
element count. Fourth, you can't use bsearch() unless you know
the array elements are in non-decreasing order (as defined by
your comparison function). Fifth and finally, if you want to
use the same comparison function with both qsort() and bsearch()
(highly recommended), then the first argument to bsearch() must
be a pointer to the same kind of thing found in the array -- that
is, not a char* but a char**, not s but &s.

Personally, I don't like bsearch() much and seldom use it.
It's got too many arguments for me to keep straight, and when
the sought item isn't present bsearch() just says "Not here!"
without telling you where the nearest neighbors were. Still,
it can be used if you want to use it.

 

[Richard Heathfield]

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("Searching 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;
}

 

[Andrey Tarasevich]

...
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)

 

[Harald van Dijk]

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 *.