Struggling with bsearch - on a struct!

[Angus Comber]

Hello

I have received a lot of help on my little project here. Many thanks.

I have a struct with a string and a long member. I have worked out how to
qsort the struct on both members. I can do a bsearch on the long member
(nKey) but I am struggling to do a search using the string member.

The code I am running appears below. It doesn't crash or anything. It is
just that when I do the last bsearch using "192.168.1. 3" I SHOULD find the
item with nKey: 7.

Any help would be MUCH appreciated.
#include <stdio.h>
#include <string.h>
#include <search.h>
struct mystruct
{
long nKey;
char szIP[20];
};
int compare( const void *val1, const void *val2 );
int IPcompare( const void* arg1, const void* arg2 );
int main()
{
mystruct devlist[4];
devlist[0].nKey = 9;
strcpy(devlist[0].szIP, "192.168.1. 1");
devlist[1].nKey = 2;
strcpy(devlist[1].szIP, "192.168.1. 2");
devlist[2].nKey = 7;
strcpy(devlist[2].szIP, "192.168.1. 3");
devlist[3].nKey = 1;
strcpy(devlist[3].szIP, "192.168.1. 4");
printf("Values before qsort\n");
printf("Item %u, IP: %s, Key: %u\n", 0, devlist[0].szIP, devlist[0].nKey);
printf("Item %u, IP: %s, Key: %u\n", 1, devlist[1].szIP, devlist[1].nKey);
printf("Item %u, IP: %s, Key: %u\n", 2, devlist[2].szIP, devlist[2].nKey);
printf("Item %u, IP: %s, Key: %u\n", 3, devlist[3].szIP, devlist[3].nKey);
qsort( (void *)devlist, (size_t)4, sizeof( mystruct ), compare );
// Now print out - see if anything change
printf("Values after qsort\n");
printf("Item %u, IP: %s, Key: %u\n", 0, devlist[0].szIP, devlist[0].nKey);
printf("Item %u, IP: %s, Key: %u\n", 1, devlist[1].szIP, devlist[1].nKey);
printf("Item %u, IP: %s, Key: %u\n", 2, devlist[2].szIP, devlist[2].nKey);
printf("Item %u, IP: %s, Key: %u\n", 3, devlist[3].szIP, devlist[3].nKey);

// Now lets qsort by IP Address
qsort( (void *)devlist, (size_t)4, sizeof( mystruct ), IPcompare );
printf("Values after IP Address qsort\n");
printf("Item %u, IP: %s, Key: %u\n", 0, devlist[0].szIP, devlist[0].nKey);
printf("Item %u, IP: %s, Key: %u\n", 1, devlist[1].szIP, devlist[1].nKey);
printf("Item %u, IP: %s, Key: %u\n", 2, devlist[2].szIP, devlist[2].nKey);
printf("Item %u, IP: %s, Key: %u\n", 3, devlist[3].szIP, devlist[3].nKey);

const long nKey = 2L;
// Looking for IP by Key
printf("Looking for an IP address by key (DeviceID) - Search where nKey =
2\n");
mystruct* rr = (mystruct*) bsearch(&nKey, devlist, 4, sizeof(mystruct ),
compare );
if( rr )
printf( "IP address: %s found (searched using key %u\n", rr->szIP,
rr->nKey );
else
printf( "IP Address not found!\n" );

printf("Now we look for a a key (DeviceID) by IP address - search on
192.168.1.3\n") ;
const char* szIP = "192.168.1. 3";
// key, base search data, num, width, cmp_func
mystruct* fnd = (mystruct*) bsearch(&szIP, devlist, 4, sizeof(mystruct ),
IPcompare ); // This line not working!!!
if( fnd )
printf( "nKey: %u found (searched using %s\n", fnd->nKey, fnd->szIP );
else
printf( "nKey NOT found!\n" );
return 0;
}
int compare( const void* val1, const void* val2 )
{
struct mystruct* sp1 = (mystruct*)val1 ;
struct mystruct *sp2 = (mystruct*)val2 ;
return (int)(sp1->nKey - sp2->nKey);
}
int IPcompare( const void* arg1, const void* arg2 ) // char **arg1, char
**arg2 )
{
/* Compare all of both strings: */
struct mystruct *sp1 = (mystruct*)arg1 ;
struct mystruct *sp2 = (mystruct*)arg2 ;
return _strcmpi( sp1->szIP, sp2->szIP );
}

The output I get is:

Values before qsort
Item 0, IP: 192.168.1.1, Key: 9
Item 1, IP: 192.168.1.2, Key: 2
Item 2, IP: 192.168.1.3, Key: 7
Item 3, IP: 192.168.1.4, Key: 1
Values after qsort
Item 0, IP: 192.168.1.4, Key: 1
Item 1, IP: 192.168.1.2, Key: 2
Item 2, IP: 192.168.1.3, Key: 7
Item 3, IP: 192.168.1.1, Key: 9
Values after IP Address qsort
Item 0, IP: 192.168.1.1, Key: 9
Item 1, IP: 192.168.1.2, Key: 2
Item 2, IP: 192.168.1.3, Key: 7
Item 3, IP: 192.168.1.4, Key: 1
Looking for an IP address by key (DeviceID) - Search where nKey = 2
IP address: 192.168.1.2 found (searched using key 2
Now we look for a a key (DeviceID) by IP address - search on 192.168.1.3
nKey NOT found!
Press any key to continue

[Malcolm]

"Angus Comber" <an***@iteloffi ce.com.PLEASENO SPAM> wrote in message

const char* szIP = "192.168.1. 3";
// key, base search data, num, width, cmp_func
mystruct* fnd = (mystruct*) bsearch(&szIP, devlist, 4, sizeof(mystruct ),
IPcompare ); // This line not working!!! int IPcompare( const void* arg1, const void* arg2 ) // char **arg1, char
**arg2 )
{
/* Compare all of both strings: */
struct mystruct *sp1 = (mystruct*)arg1 ;
struct mystruct *sp2 = (mystruct*)arg2 ;
return _strcmpi( sp1->szIP, sp2->szIP );
}

You are passing bsearch() a char **, but the comparison function is
expecting two mystruct *s.
What you need to do is make a temporary mystruct

mystruct comp;
comp.szIP = szIP;
bsearch(&comp ... );

[Richard Heathfield]

Angus Comber wrote:

Hello

I have received a lot of help on my little project here. Many thanks.

I have a struct with a string and a long member. I have worked out how to
qsort the struct on both members. I can do a bsearch on the long member
(nKey) but I am struggling to do a search using the string member.

The code I am running appears below. It doesn't crash or anything. It is
just that when I do the last bsearch using "192.168.1. 3" I SHOULD find the
item with nKey: 7.

Any help would be MUCH appreciated.
#include <stdio.h>
#include <string.h>
#include <search.h>
This is not a standard header.
struct mystruct
{
long nKey;
char szIP[20];
};
int compare( const void *val1, const void *val2 );
int IPcompare( const void* arg1, const void* arg2 );
int main()
Better: int main(void)
{
mystruct devlist[4];
Syntax error. Should be:

struct mystruct devlist[4];
devlist[0].nKey = 9;
strcpy(devlist[0].szIP, "192.168.1. 1");
devlist[1].nKey = 2;
strcpy(devlist[1].szIP, "192.168.1. 2");
devlist[2].nKey = 7;
strcpy(devlist[2].szIP, "192.168.1. 3");
devlist[3].nKey = 1;
strcpy(devlist[3].szIP, "192.168.1. 4");
Why not:

struct mystruct devlist[] =
{
{ 9, "192.168.1. 1" },
{ 2, "192.168.1. 2" },
{ 7, "192.168.1. 3" },
{ 1, "192.168.1. 4" }
};
size_t n = sizeof devlist / sizeof devlist[0];
size_t i;
printf("Values before qsort\n");
printf("Item %u, IP: %s, Key: %u\n", 0, devlist[0].szIP, devlist[0].nKey);
printf("Item %u, IP: %s, Key: %u\n", 1, devlist[1].szIP, devlist[1].nKey);
printf("Item %u, IP: %s, Key: %u\n", 2, devlist[2].szIP, devlist[2].nKey);
printf("Item %u, IP: %s, Key: %u\n", 3, devlist[3].szIP, devlist[3].nKey);
Undefined behaviour (%u expects unsigned int, not signed long).

for(i = 0; i < n; i++)
{
printf("Item %u, IP: %s, Key: %ld\n",
(unsigned)i,
devlist[i].szIP,
devlist[0].nKey);
}

qsort( (void *)devlist, (size_t)4, sizeof( mystruct ), compare );
qsort(devlist, n, sizeof devlist[0], compare);
// Now print out - see if anything change
printf("Values after qsort\n");
printf("Item %u, IP: %s, Key: %u\n", 0, devlist[0].szIP, devlist[0].nKey);
printf("Item %u, IP: %s, Key: %u\n", 1, devlist[1].szIP, devlist[1].nKey);
printf("Item %u, IP: %s, Key: %u\n", 2, devlist[2].szIP, devlist[2].nKey);
printf("Item %u, IP: %s, Key: %u\n", 3, devlist[3].szIP, devlist[3].nKey);
Or just:

for(i = 0; i < n; i++)
{
printf("Item %u, IP: %s, Key: %ld\n",
(unsigned)i,
devlist[i].szIP,
devlist[0].nKey);
}
// Now lets qsort by IP Address
qsort( (void *)devlist, (size_t)4, sizeof( mystruct ), IPcompare );
qsort(devlist, n, sizeof devlist[0], IPcompare);
printf("Values after IP Address qsort\n");
printf("Item %u, IP: %s, Key: %u\n", 0, devlist[0].szIP, devlist[0].nKey);
printf("Item %u, IP: %s, Key: %u\n", 1, devlist[1].szIP, devlist[1].nKey);
printf("Item %u, IP: %s, Key: %u\n", 2, devlist[2].szIP, devlist[2].nKey);
printf("Item %u, IP: %s, Key: %u\n", 3, devlist[3].szIP, devlist[3].nKey);
for(i = 0; i < n; i++)
{
printf("Item %u, IP: %s, Key: %ld\n",
(unsigned)i,
devlist[i].szIP,
devlist[0].nKey);
}
const long nKey = 2L;
Are you using a C99 compiler? If so, which one? If not, defining a new
object here is an error.
// Looking for IP by Key
printf("Looking for an IP address by key (DeviceID) - Search where nKey =
2\n");
mystruct* rr = (mystruct*) bsearch(&nKey, devlist, 4, sizeof(mystruct ),
compare );
No no no. Look, firstly, you've got the array sorted by IP address, so
there's no earthly point in looking for an nKey using bsearch(). Secondly,
you've included an utterly spurious cast which masks the very significant
error of having failed to #include <stdlib.h> - and thirdly, you did
another of them thar defining variables halfway down your code.

If you want to search for an nKey, do it like this.

1) at the top somewhere:

#include <stdlib.h>

2) at the top somewhere, define:

struct mystruct Key = {0};
struct mystruct *rr = NULL;

3) back down here again, make sure it's sorted by nKey:

qsort(devlist, n, sizeof devlist[0], compare);

4) Set up the key you're looking for:

Key.nKey = 2L;

5) Now we can bsearch:

rr = bsearch(&Key, devlist, n, sizeof devlist[0], compare);

/* If that line gives you a diagnostic, make sure you have <stdlib.h>
included. If it /still/ gives you a diagnostic, choose whether you want to
write C or C++. If you wish to write C, use a C compiler, not a C++
compiler. */

if(rr != NULL)
{
/* you found one! */

if( rr )
printf( "IP address: %s found (searched using key %u\n", rr->szIP,
rr->nKey );
else
printf( "IP Address not found!\n" );

printf("Now we look for a a key (DeviceID) by IP address - search on
192.168.1.3\n") ;
This time, we want to search the other way, so first we must sort the other
way:

qsort(devlist, n, sizeof devlist[0], IPcompare);

const char* szIP = "192.168.1. 3";
No, let's just:

strcpy(Key.szIP , "192.168.1. 3");

// key, base search data, num, width, cmp_func
mystruct* fnd = (mystruct*) bsearch(&szIP, devlist, 4, sizeof(mystruct ),
IPcompare ); // This line not working!!!
rr = bsearch(&Key, devlist, n, sizeof devlist[0], IPcompare);

if(rr != NULL)
{
/* found! */
if( fnd )
printf( "nKey: %u found (searched using %s\n", fnd->nKey, fnd->szIP );
else
printf( "nKey NOT found!\n" );
return 0;
}
int compare( const void* val1, const void* val2 )
{
struct mystruct* sp1 = (mystruct*)val1 ;
struct mystruct *sp2 = (mystruct*)val2 ;
return (int)(sp1->nKey - sp2->nKey);
}
int compare(const void *val1, const void *val2)
{
const struct mystruct *sp1 = val1;
const struct mystruct *sp2 = val2;
return sp1->nKey < sp2->nKey ? -1 : sp1->nKey > sp2->nKey;
}
int IPcompare( const void* arg1, const void* arg2 ) // char **arg1, char
**arg2 )
{
/* Compare all of both strings: */
struct mystruct *sp1 = (mystruct*)arg1 ;
struct mystruct *sp2 = (mystruct*)arg2 ;
return _strcmpi( sp1->szIP, sp2->szIP );
}

int IPcompare(const void *arg1, const void *arg2)
{
const struct mystruct *sp1 = arg1;
const struct mystruct *sp2 = arg2;
return strcmp(sp1->szIP, sp2->szIP);
}

--
Richard Heathfield : bi****@eton.pow ernet.co.uk
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton

[nrk]

Angus Comber wrote:

Hello

I have received a lot of help on my little project here. Many thanks.

I have a struct with a string and a long member. I have worked out how to
qsort the struct on both members. I can do a bsearch on the long member
(nKey) but I am struggling to do a search using the string member.

The code I am running appears below. It doesn't crash or anything. It is
just that when I do the last bsearch using "192.168.1. 3" I SHOULD find the
item with nKey: 7.

Any help would be MUCH appreciated.

<Atrociously indented code snipped>

Here's your code (indented, and long lines broken, but otherwise unchanged),
so that humans can make some sense out of it, along with comments:

#include <stdio.h>
#include <string.h>
#include <search.h>
Non-standard header. You definitely want stdlib.h as that's where you get
declarations for qsort and bsearch. So remove this, and insert:
#include <stdlib.h>

struct mystruct
{
long nKey;
char szIP[20];
};

int compare( const void *val1, const void *val2 );
int IPcompare( const void* arg1, const void* arg2 );

int main() {
mystruct devlist[4];

devlist[0].nKey = 9;
strcpy(devlist[0].szIP, "192.168.1. 1");
devlist[1].nKey = 2;
strcpy(devlist[1].szIP, "192.168.1. 2");
devlist[2].nKey = 7;
strcpy(devlist[2].szIP, "192.168.1. 3");
devlist[3].nKey = 1;
strcpy(devlist[3].szIP, "192.168.1. 4");

printf("Values before qsort\n");
printf("Item %u, IP: %s, Key: %u\n", 0, devlist[0].szIP,
devlist[0].nKey);

%u is for unsigned int. Since nKey is a long, why not use %ld?

printf("Item %u, IP: %s, Key: %u\n", 1, devlist[1].szIP,
devlist[1].nKey);
printf("Item %u, IP: %s, Key: %u\n", 2, devlist[2].szIP,
devlist[2].nKey);
printf("Item %u, IP: %s, Key: %u\n", 3, devlist[3].szIP,
devlist[3].nKey);

qsort( (void *)devlist, (size_t)4, sizeof( mystruct ), compare );

You don't need that cast to void *. Nor the cast to size_t. Get rid of
them both. Also, instead of hardcoding the 4, you can say:

qsort(devlist, sizeof devlist/sizeof devlist[0], sizeof(devlist[0]),
compare);

// Now print out - see if anything change
printf("Values after qsort\n");
printf("Item %u, IP: %s, Key: %u\n", 0, devlist[0].szIP,
devlist[0].nKey);
printf("Item %u, IP: %s, Key: %u\n", 1, devlist[1].szIP,
devlist[1].nKey);
printf("Item %u, IP: %s, Key: %u\n", 2, devlist[2].szIP,
devlist[2].nKey);
printf("Item %u, IP: %s, Key: %u\n", 3, devlist[3].szIP,
devlist[3].nKey);

// Now lets qsort by IP Address
qsort( (void *)devlist, (size_t)4, sizeof( mystruct ), IPcompare );

This qsort can also be similarly rewritten.

printf("Values after IP Address qsort\n");
printf("Item %u, IP: %s, Key: %u\n", 0, devlist[0].szIP,
devlist[0].nKey);
printf("Item %u, IP: %s, Key: %u\n", 1, devlist[1].szIP,
devlist[1].nKey);
printf("Item %u, IP: %s, Key: %u\n", 2, devlist[2].szIP,
devlist[2].nKey);
printf("Item %u, IP: %s, Key: %u\n", 3, devlist[3].szIP,
devlist[3].nKey);

const long nKey = 2L;
// Looking for IP by Key
printf("Looking for an IP address by key (DeviceID) - Search where nKey"
" = 2\n");
mystruct* rr = (mystruct*) bsearch(&nKey, devlist, 4, sizeof(mystruct ),
compare );

Read the description of bsearch carefully. Particularly, what it expects
from the compare function. Here's what my man page says:

The compar routine is expected to have two arguments which point to the key
object and to an array member, in that order, and should return an
integer less than, equal to, or greater than zero if the key object is
found, respectively, to be less than, to match, or be greater than the
array member.

Notice the parameters to the compare function. The first is a pointer to
the key object, and the second to an array member. Your array members are
all struct mystruct. But your key object is a const long!! However, your
compare function expects the key object to also be a struct mystruct.
What's the solution? Write a new compare function and use that instead:

int srchcmp_nKey(co nst void *keyp, const void *memp) {
const long *key = keyp;
const struct mystruct *mem = memp;

return (*key < mem->nKey) ? -1 : (*key > mem->nKey);
}

Also, there is no need to cast the returned void * from bsearch. One
important thing that you've failed to notice here is that your second qsort
re-sorts the array based on the szIP field. Since it is no longer sorted
on the nKey field, the results of the bsearch are meaningless. If you find
your key, well and good. But if you don't, there's no guarantee that the
key is not present, since your array wasn't sorted in key order. Having
the array sorted in key order is a pre-condition for bsearch to give
meaningful results.

if( rr )
printf( "IP address: %s found (searched using key %u\n", rr->szIP,
rr->nKey );
else
printf( "IP Address not found!\n" );

printf("Now we look for a a key (DeviceID) by IP address - search on"
" 192.168.1.3\n") ;
const char* szIP = "192.168.1. 3";
// key, base search data, num, width, cmp_func
mystruct* fnd = (mystruct*) bsearch(&szIP, devlist, 4, sizeof(mystruct ),
IPcompare );

Again, problem with the compare function. Also note that szIP already is a
pointer to the string that you want to act as the key. You don't need to
pass &szIP. Just pass szIP.

mystruct *fnd = bsearch(szIP, devlist, sizeof devlist/sizeof devlist[0],
sizeof devlist[0], srchcmp_szIP);

and here's the compare function:

int srchcmp_szIP(co nst void *keyp, const void *memp) {
const char *key = keyp;
const struct mystruct *mem = memp;

return strcmp(keyp, mem->szIP);
}

Since it is IP addresses that your comparing, why waste cycles doing a case
independent compare? Simply do a straight string compare.

if( fnd )
printf("nKey: %u found (searched using %s\n", fnd->nKey, fnd->szIP);
else
printf( "nKey NOT found!\n" );
return 0;
}
int compare( const void* val1, const void* val2 )
{
struct mystruct* sp1 = (mystruct*)val1 ;
struct mystruct *sp2 = (mystruct*)val2 ;
return (int)(sp1->nKey - sp2->nKey);
}

int IPcompare( const void* arg1, const void* arg2 )
{
/* Compare all of both strings: */
struct mystruct *sp1 = (mystruct*)arg1 ;
struct mystruct *sp2 = (mystruct*)arg2 ;
return _strcmpi( sp1->szIP, sp2->szIP );

That's a non-standard function. There seems to be no real need to use one
here.

}

HTH,
-nrk.

ps: If you used tabs to intend your code, convert them to spaces before
posting it on usenet. Many newsreaders and servers don't handle tabs all
that well.

--
Remove devnull for email

[Al Bowers]

Angus Comber wrote:

Hello

I have received a lot of help on my little project here. Many thanks.

I have a struct with a string and a long member. I have worked out how to
qsort the struct on both members. I can do a bsearch on the long member
(nKey) but I am struggling to do a search using the string member.

The code I am running appears below. It doesn't crash or anything. It is
just that when I do the last bsearch using "192.168.1. 3" I SHOULD find the
item with nKey: 7.

Unless there is a correlation (and there doesn't appear to be one with
your data), you should not sort by the key and the bsearch by the IP, or
vise versa. If the sort the array of structs by the key, then you need
to search by a key. And, if you sort by the IP, you need to search by
the IP.

To correct this problem and other errors in your code:

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

struct mystruct
{
long nKey;
char szIP[20];
};

int compare( const void *val1, const void *val2 );
int IPcompare( const void* arg1, const void* arg2 );

int main(void)
{
int i;
struct mystruct devlist[4], tmp, *fnd;
devlist[0].nKey = 9;
strcpy(devlist[0].szIP, "192.168.1. 1");
devlist[1].nKey = 2;
strcpy(devlist[1].szIP, "192.168.1. 2");
devlist[2].nKey = 7;
strcpy(devlist[2].szIP, "192.168.1. 3");
devlist[3].nKey = 1;
strcpy(devlist[3].szIP, "192.168.1. 4");
puts("Values before qsort");
for(i = 0; i < 4;i++)
printf("Item %d, IP: %s, Key: %ld\n", i, devlist[i].szIP,
devlist[i].nKey);
/* sort by key */
qsort( devlist, 4, sizeof *devlist, compare );
puts("Values after qsort by key");
for(i = 0; i < 4;i++)
printf("Item %d, IP: %s, Key: %ld\n", i, devlist[i].szIP,
devlist[i].nKey);
/* search by key */
tmp.nKey = 2;
if((fnd = bsearch(&tmp,de vlist,4,sizeof *devlist,
compare)) != NULL)
printf("The key %ld was found, and the Ip is %s\n",
fnd->nKey, fnd->szIP);
else puts("key %ld was not found", tmp.nKey);

/* Now lets qsort by IP Address */
qsort( devlist, 4, sizeof *devlist, IPcompare );
puts("Values after IP Address qsort");
for(i = 0;i < 4;i++)
printf("Item %d, IP: %s, Key: %ld\n", i, devlist[i].szIP,

devlist[i].nKey);
/* search for IP address */
puts("Now we look for a a key (DeviceID) by "
"IP address - search on 192.168.1.3");
strcpy(tmp.szIP ,"192.168.1.3") ;
if((fnd = bsearch(&tmp, devlist, 4, sizeof *devlist,
IPcompare)) != NULL)
printf( "nKey: %ld found (searched using %s\n", fnd->nKey ,

fnd->szIP );
else puts("nKey, NOT found!" );
return 0;
}

int compare( const void* val1, const void* val2 )
{ /* Sort by key */
const struct mystruct* sp1 = val1;
const struct mystruct *sp2 = val2;

return (sp2->nKey>sp1->nKey)?-1:(sp2->nKey != sp1->nKey);
}

int IPcompare( const void* arg1, const void* arg2 )
{
/* Sort by IP */
const struct mystruct *sp1 = arg1;
const struct mystruct *sp2 = arg2;

return strcmp( sp1->szIP, sp2->szIP );
}
--
Al Bowers
Tampa, Fl USA
mailto: xa******@myrapi dsys.com (remove the x to send email)
http://www.geocities.com/abowers822/