C++

Forum

 
Having Problem with bsearch and can't figure out

mendozae (94)
I have this small program just to test the library function "bsearch". I tried everything but could not figure out why I am getting the value of "noShowStudent" 0x00000000 <bad Pointer>
can somebody tell me what I am doing wrong..

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
#include <stdio.h>
#include <stdlib.h>
int Compare(const void *elemA, const void *elemB);

int main ()
{
   const char *attendees[] = {"JOSE", "Xenon Man", "Wonder Woman", "The Green Lantern", "The Flash"};
   char *noShowStudent;
   int noShowCntr;
        
    //How many registrant did not attend the first meeting 
    printf ("Not Present:\n");
    for (noShowCntr = 0; noShowCntr < 5; noShowCntr++)
    {
        noShowStudent = (char*)bsearch("Wonder Woman", attendees, 5, sizeof(const char*), Compare);
        if ( noShowStudent == NULL) 
            printf ("BINGO");
        else
            printf ("NO BiNGO");
    }

   return 0;
}

int Compare(const void *elemA, const void *elemB)
{
    if (*(int*)elemA == *(int*)elemB)
        return 0;
    else
        if (*(int*)elemA < *(int*)elemB)
            return -1;
        else
            return 1; 
}
modoran (2077)
What's this on line 15 ?
sizeof(const char*)

This will always return 4 on x86 and 8 on x64 arhitectures, probably not what you want.

Use strcmp() directly instead of your program.
andywestken (4087)
sizeof(const char*) is correct here. The fourth param of bsearch is the size of an element (which are char*s in the case of this array). The third param (here 5) is the number of elems in the array.

bsearch
http://www.cplusplus.com/reference/clibrary/cstdlib/bsearch/

But the Compare function doesn't make sense. The elements are char*s, as you appear to know on line 15. So why are you using int as the type for the comparison?

As you have no nulls in your array, you can use something along the lines of

1
2
3
4
5
6
7
 
int Compare(const void *elemA, const void *elemB)
{
    const char* pszA = (const char*)elemA;      // search key is just a char*
    const char* pszB = *((const char**)elemB);  // elem are passed as char** values

    return strcmp(pszA, pszB); // strcmp() follows the right rules for Compare
}


But if there are nulls, you will have to protect strcmp() from them.

If you want to keep the treatment of the key and elem the same, cast-wise, yu have to pass the address of the key on line 15 instead of the value.

1
2
 
        const char* findMe = "Wonder Woman";
        noShowStudent = (char*)bsearch(&findMe, attendees, 5, sizeof(const char*), Compare);


whch works with

1
2
3
4
5
6
7
 
int Compare(const void *elemA, const void *elemB)
{
    const char* pszA = *((const char**)elemA);      // search key is just a char*
    const char* pszB = *((const char**)elemB);  // elem are passed as char** values

    return strcmp(pszA, pszB); // strcmp() follows the right rules for Compare
}


The symmetric form can be used with qsort, too. So is quite commonly used. But beware of mixing char arrays (which store chars contiguously, in fixed size blocks) with char* arrays (where the address of the string is in the array, but the string is stored elsewhere) e.g

1
2
3
 
char char_array[][20] = {"some", "example", "strings", "here"};

char* ptr_array[] = {"some", "example", "strings", "here"};


And does BINGO means you cannot find a student? (That they've turned up?)

Note that the return value from bsearch in this case is actually a char**, not a char. So to see the returned value you need:

1
2
3
4
5
 
char **noShowStudent;

noShowStudent = (char**)bsearch("Wonder Woman", attendees, ...  // etc

printf("found = %s\n", *noShowStudent);


Andy

PS As attendees is an array of const char*s, I suggest you make noShowStudent const as well. And you know that sizeof(attendees)/sizeof(attendees[0]) gives you the number of elements in the array? (so you don't have to keep the count in step with the array yourself.)

PPS The int Compare is broken as it is used, even to compare ints.

You either have to pass the key by address.

Or cast for the first param (the key) using just (int).

1
2
3
4
5
6
7
8
9
10
 
int Compare(const void *elemA, const void *elemB)
{
    if ((int)elemA == *(int*)elemB)
        return 0;
    else
        if ((int)elemA < *(int*)elemB)
            return -1;
        else
            return 1; 
}


or you can make it ore debug friendly by using temporary variable (these will be optimised out in the release build, so they have zero effect on performance)

1
2
3
4
5
6
7
8
9
10
11
12
13
 
int Compare(const void *elemA, const void *elemB)
{
    int iA = (int)elemA;
    int iB = *(int*)elemB;

    if (iA == iB)
        return 0;
    else
        if (iA < iB)
            return -1;
        else
            return 1; 
}


BUT what this does, when used with a char* array, is compare the memory addresses of the string. And one copy of a string (e.g. the "Wonder Woman" on line 15) does not necessarily have the same address as another copy of the string (e.g. the one on line 7). So your original code (with the repaired Compare function) would might never find a match.
Last edited on
guestgulkan (2942)
andywestken wrote:
BUT what this does, when used with a char* array, is compare the memory addresses of the string. And one copy of a string (e.g. the "Wonder Woman" on line 15) does not have the same address as another copy of the string (e.g. the one on line 7). So you original code (with the repaired Compare) would never find a match.


I did write a reply to the original post mentioning just this thing - BUT lo and behold after checking it out I found that GCC and MSVC gave both string literals the same address - and after correcting the program it did find a match! - so I removed my post.

But the C++ standards document does say that:
Whether all string literals are distinct (that is, are stored in nonoverlapping objects) is implementation defined.
The effect of attempting to modify a string literal is undefined.


andywestken (4087)
@guestgulkan

Regarding the shared or othwerwise storage of string literals, I've added necessarily to my post and changed would to might.

But if the key value had been stored in a local, or otherwise buffer, like

1
2
 
        const char find_key[] = "Wonder Woman";
        noShowStudent = (char**)bsearch(find_key, attendees, 5, sizeof(const char*), Compare);


=> no address-based matches :-(

1
2
 
        const char* find_key = "Wonder Woman";
        noShowStudent = (char**)bsearch(find_key, attendees, 5, sizeof(const char*), Compare);


=> address-based matches ;-)

Andy
Last edited on
mendozae (94)
This is the main that call the functions: the main ran a series of test on the function. This is an instructors file so we as his student should not modify it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
 
#define INSTRUCTOR_FILE  /* STUDENTS: DO NOT DEFINE THIS IN YOUR FILE(S) */

/****************************************************************************
 * Everything in this file was written to help test/verify your code and must
 * not be altered in any way.  Do not rename this file or copy anything from
 * it into your file(s).  This file does not necessarily represent good coding
 * technique, proper formatting/style, or meet the requirements your code must
 * meet.  You do not need to understand the code in this file to write yours.
 ***************************************************************************/
#ifdef INSTRUCTOR_FILE

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

#define Elements(array) (sizeof(array)/sizeof((array)[0]))

int Compare(const void *elemA, const void *elemB);
void SortStudents(const char *studentList[], size_t studentCount);
void DisplayClassStatus(const char *registrants[], size_t registrantCount,
                        const char *attendees[], size_t attendeeCount);


int main(void)
{
   const char *registrants0[] =
   {
      "Xenon Man", "Wonder Woman", "jose", "The Green Lantern", "The Flash"
   };
   const char *attendees0[] =
   {
      "The Flash", "The Green Lantern", "Wonder Woman", "Joahwana", "Xenon Man"
   };
   const char *registrants1[] =
   {
      "Al", "Tough Guy", "Mae East", "Bill", "Avenger", "Jo", "Mary",
      "Agitation King", "Elvis", "Zabo The Great", "Slim Jim",
      "Stinky The Clown", "Carl Crumb", "What's On Second", "Aces Wild",
      "Night Flyer"
   };
   const char *attendees1[] =
   {
      "Al", "Tough Guy", "Mae East", "Bill", "Jo", "Mary", "Petty Patty",
      "Elmer Fudd", "Elvis", "Slim Jim", "Stinky The Clown", "Carl Crumb",
      "Ned Nasty", "Who's On First", "Aces Wild", "Night Flyer",
      "Carl Clean"
   }; 
   /* Initial test of comparison function */
   if (Compare(&registrants0[1], &registrants0[0]) >= 0 ||
       Compare(&registrants0[0], &registrants0[0]) != 0 ||
       Compare(&registrants0[0], &registrants0[1]) <= 0)
   {
      fprintf(stderr, "Comparison function failed!\n");
      return EXIT_FAILURE;
   }
   
   /* Display status of class #0 before sorting registrants and attendees. */
   printf("Class #0 before sorting:\n");
   DisplayClassStatus(registrants0, Elements(registrants0),
                      attendees0,   Elements(attendees0));
   printf("\n");
   SortStudents(registrants0, Elements(registrants0));
   SortStudents(attendees0, Elements(attendees0));

   /* Display status of class #0 after sorting registrants and attendees. */
   printf("Class #0 after sorting:\n");
   DisplayClassStatus(registrants0, Elements(registrants0),
                      attendees0,   Elements(attendees0));
   printf("\n");


   /* Display status of class #1 before sorting registrants and attendees. */
   printf("Class #1 before sorting:\n");
   DisplayClassStatus(registrants1, Elements(registrants1),
                      attendees1,   Elements(attendees1));
   printf("\n");
   SortStudents(registrants1, Elements(registrants1));
   SortStudents(attendees1, Elements(attendees1));

   /* Display status of class #1 after sorting registrants and attendees. */
   printf("Class #1 after sorting:\n");
   DisplayClassStatus(registrants1, Elements(registrants1),
                      attendees1,   Elements(attendees1));
   printf("\n");
   getchar();
   return EXIT_SUCCESS;
}
#endif




I ran a series of test on the Compare furnished by by AndyWestken and it failed the test. This is the one I tested and failed. I don't know why it failed

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
 
//FILE NAME IS main_driver.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*THIS WAS TESTED IT PASSED THE COMPARE TEST BUT IS NO BETTER THAN THE PROGRAM I WROTE
 int Compare(const void *elemA, const void *elemB)
{
   return(strcmp(*(char **)elemA, *(char **)elemB));
} 
*/
//THIS IS CLOSED TO MY ORIGINAL PROGRAM EXCEPT THE TYPECAST WAS CHANGED FROM (int*) to (char*)
//THIS WAS TESTED IT PASSED THE COMPARE TEST BUT IS NO BETTER THAN THE PROGRAM WITH (int*) TYPECAST
int Compare(const void *elemA, const void *elemB)
{

    if (*(char *)elemA == *(char*)elemB)
        return 0;
    else
        if (*(char*)elemA < *(char*)elemB)
            return -1;
        else
            return 1; 
} 

/*THIS WAS SUGGESTED BY a AndyWestken PROGRAMMER AT THE FORUM AND the function FAILED THE COMPARE TEST
int Compare(const void *elemA, const void *elemB)
{
    const char* pszA = *((const char**)elemA);      // search key is just a char*
    const char* pszB = *((const char**)elemB);  // elem are passed as char** values

    return strcmp(pszA, pszB); // strcmp() follows the right rules for Compare
} 


*/

void SortStudents(const char *studentList[], size_t studentCount)
{
    int sortCntr;
    qsort((void *)studentList, studentCount, sizeof(char*), Compare);
    for (sortCntr = 0; sortCntr < (int)studentCount; sortCntr++)
       printf ("%s\n ",studentList[sortCntr]);
    return;
}
/*
const char *registrants0[] = {"Xenon Man", "Wonder Woman", "jose", "The Green Lantern", "The Flash"};
const char *attendees0[]   = {"The Flash", "The Green Lantern", "Wonder Woman", "Joahwana", "Xenon Man"};
*/
void DisplayClassStatus(const char *registrants[], size_t registrantCount,
                        const char *attendees[], size_t attendeeCount)
{ 
    int noShowCntr, notRegisCntr;
    char **noShowStudent , **notRegisStudent;
        
    //who is the registrant who did not attend the first meeting 
    printf ("Not Present:\n");
    for (noShowCntr = 0; noShowCntr < (int)registrantCount; ++noShowCntr)
    {
        noShowStudent = (char**)bsearch((void*)&registrants[noShowCntr], (void*)attendees, attendeeCount, sizeof(char*), Compare);
        if (!noShowStudent)
        {
            printf ("%s\n", registrants[noShowCntr]);
        }
    } 
    //who attended the first meeting but is not a  Registered student 
    printf ("Not Registered:\n");
    for (notRegisCntr = 0; notRegisCntr < (int)attendeeCount; ++notRegisCntr)
    {
        notRegisStudent = (char**)bsearch((void*)&attendees[notRegisCntr],(void*)registrants, registrantCount, sizeof(char*), Compare); 
        if (!notRegisStudent)
        {
            printf ("%s\n", attendees[notRegisCntr]);
        }
    }
    return;
}

So I decided to use my original function except I change the the type cast of compare from (int*) to (char*)

The problem now is variable "noShowStudent " and "notRegisStudent " are closed to identical but "noShowStudent " is returning a valid address and "notRegisStudent " is always returning an address "0x00000000.

WHY THAT IS THE ONE BUGGING ME.
guestgulkan (2942)

There are two may issues I see (which goes all the way back to your original post)

1. The bsearch is short for binary search - for this function to work correctly your array needs to be sorted in order.

So trying to be search on an out of order array like this is pointless.
1
2
3
4
 
const char *registrants0[] =
   {
      "Xenon Man", "Wonder Woman", "jose", "The Green Lantern", "The Flash"
   };



2. Given that each item in the array is a const char* and the address of
each item in the array is passed as the second parameter to the bsearch function as void* - in other words the original poiter type before the void* cast was const char**.
Soyour compare function should look like this:
1
2
3
4
5
6
7
8
9
10
11
 
int Compare(const void *elemA, const void *elemB)
{

    if ((const char *)elemA == *(const char**)elemB)
        return 0;
    else
        if ((const char*)elemA < *(const char**)elemB)
            return -1;
        else
            return 1; 
}



So here is your original post - working (touch wood) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
#include <stdio.h>
#include <cstdlib>


int Compare( const void *elemA,  const void *elemB);


int main()
{



    //bsearch require a sorted list
    const char *attendees[] = {"JOSE", "The Flash", "The Green Lantern", "Wonder Woman", "Xenon Man"};
   char *noShowStudent;
   int noShowCntr;


    printf ("Not Present:\n");

        //bsearch will return a pointer  the found item or 0 if not found.
        void * pv =bsearch("The Green Lantern", attendees, 5, sizeof(const char*), Compare);
        if ( pv !=NULL)
        {
            //found it if the return of bsearch function !=0
            printf ("BINGO  - Found   ");
            printf ( "%s",*(char**)pv );//print the found name to confirm
        }
        else
            printf ("NO BiNGO");


   return 0;
}


int Compare( const void *elemA,  const void *elemB)
{
    char *p1,*p2;


    if ((const char*)elemA == *(const char**)elemB) //notivce the way we recast the send parameter
        return 0;
    else
        if ( (const char*)elemA < *(const char**)elemB)
            return -1;
        else
            return 1;
}


***BUT note as said earlier by AndyWestken and myself - the compiler
may not put all string literals that are the same at the same address so to speak (refer to previous posts)
but I found that the sode as I gave worked in MSVC and GCC.

Topic archived. No new replies allowed.