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

How do I use bsearch() ?

P: n/a
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)
Mar 25 '08 #1
Share this Question
Share on Google+
4 Replies


P: n/a
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(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);

Mar 25 '08 #2

P: n/a
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;
}

--
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
Mar 25 '08 #3

P: n/a
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
Mar 26 '08 #4

P: n/a
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 *.
Mar 27 '08 #5

This discussion thread is closed

Replies have been disabled for this discussion.