How do I use bsearch() ?

Discussion in 'C Programming' started by Amandil, Mar 25, 2008.

  1. Amandil

    Amandil Guest

    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)
     
    Amandil, Mar 25, 2008
    #1
    1. Advertising

  2. Amandil

    santosh Guest

    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);
     
    santosh, Mar 25, 2008
    #2
    1. Advertising

  3. On Tue, 25 Mar 2008 12:25:23 -0700, 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)


    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.
     
    Harald van Dijk, Mar 25, 2008
    #3
  4. Amandil

    Eric Sosman Guest

    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)


    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.

    --
     
    Eric Sosman, Mar 25, 2008
    #4
  5. 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
     
    Richard Heathfield, Mar 25, 2008
    #5
  6. 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
     
    Andrey Tarasevich, Mar 26, 2008
    #6
  7. 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 *.
     
    Harald van Dijk, Mar 27, 2008
    #7
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Artie Gold

    Re: bsearch in C

    Artie Gold, Aug 7, 2003, in forum: C Programming
    Replies:
    0
    Views:
    418
    Artie Gold
    Aug 7, 2003
  2. Richard Heathfield

    Re: bsearch in C

    Richard Heathfield, Aug 7, 2003, in forum: C Programming
    Replies:
    0
    Views:
    414
    Richard Heathfield
    Aug 7, 2003
  3. Eric Sosman

    Re: bsearch in C

    Eric Sosman, Aug 7, 2003, in forum: C Programming
    Replies:
    9
    Views:
    526
    Richard Heathfield
    Aug 12, 2003
  4. Ramprasad A Padmanabhan

    a small bsearch example

    Ramprasad A Padmanabhan, Oct 28, 2003, in forum: C Programming
    Replies:
    1
    Views:
    3,809
    Mark Gordon
    Oct 28, 2003
  5. Ramprasad A Padmanabhan

    bsearch script segfault

    Ramprasad A Padmanabhan, Dec 4, 2003, in forum: C Programming
    Replies:
    11
    Views:
    506
    Ramprasad A Padmanabhan
    Dec 5, 2003
Loading...

Share This Page