How would I use qsort to sort a struct with a char* member and a long member - I want to sort in ord

A

Angus Comber

Hello

Here is my code so far. Is this correct/incorrect/along the right
lines/other?

#include <stdio.h>
#include <string.h>
#include <search.h>
struct mystruct
{
long nKey;
char szIP[20];
};

int compare( const void *long1, const void *long2 );

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");
qsort( (void *)devlist, (size_t)4, sizeof( char * ), compare );

// bsearch is the next thing to work out how to do!
// void *bsearch( const void *key, const void *base, size_t num, size_t
width, int
// ( __cdecl *compare ) ( const void *elem1, const void *elem2 ) );
return 0;
}

int compare( const void* val1, const void* val2 )
{
struct mystruct *sp1 = (mystruct*)val1;
struct mystruct *sp2 = (mystruct*)val2;
// IS THIS CORRECT?
return (int)(sp1->nKey - sp2->nKey);
}

Angus Comber
(e-mail address removed)
 
L

Leor Zolman

On Thu, 5 Feb 2004 14:43:22 -0000, "Angus Comber"


Please use a short subject line, and put the complete text of your
question in the message body.
#include <stdio.h>
#include <string.h>
#include <search.h>
struct mystruct
{
long nKey;
char szIP[20];
};

So is this C or C++? If C++, fine. If C, in order to use "mystruct" as
a typename (without having to say "struct mystruct", add this:

typedef struct mystruct mystruct;
int compare( const void *long1, const void *long2 );

int main()
{
mystruct devlist[4];

To do the above in C, add the aforementioned typedef.
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");
qsort( (void *)devlist, (size_t)4, sizeof( char * ), compare );

// bsearch is the next thing to work out how to do!
// void *bsearch( const void *key, const void *base, size_t num, size_t
width, int
// ( __cdecl *compare ) ( const void *elem1, const void *elem2 ) );
return 0;
}

int compare( const void* val1, const void* val2 )
{
struct mystruct *sp1 = (mystruct*)val1;
struct mystruct *sp2 = (mystruct*)val2;
// IS THIS CORRECT?
return (int)(sp1->nKey - sp2->nKey);

If you want to sort in descending order, yes. If you want to sort in
_ascending_ order, flip the operands around.

Overall, a good first stab if you've never used qsort before.

Have fun,
-leor

Leor Zolman
BD Software
(e-mail address removed)
www.bdsoft.com -- On-Site Training in C/C++, Java, Perl & Unix
C++ users: Download BD Software's free STL Error Message
Decryptor at www.bdsoft.com/tools/stlfilt.html
 
A

Angus Comber

Hello

Thanks for that. I am using VC++ so it didn't complain at the mystruct
line!

However, real reason for replying is that on first call of compare function,
if I do this:

struct mystruct *sp1 = (mystruct*)val1;
struct mystruct *sp2 = (mystruct*)val2;
sp1->nKey is some wierd value - 775043377
sp2->nKey is 9

on the second call to compare the values are:
sp1->nKey is some wierd value - 775435825
sp2->nKey is 775043377

So I have definitely done something wrong!

Any ideas?



Leor Zolman said:
On Thu, 5 Feb 2004 14:43:22 -0000, "Angus Comber"


Please use a short subject line, and put the complete text of your
question in the message body.
#include <stdio.h>
#include <string.h>
#include <search.h>
struct mystruct
{
long nKey;
char szIP[20];
};

So is this C or C++? If C++, fine. If C, in order to use "mystruct" as
a typename (without having to say "struct mystruct", add this:

typedef struct mystruct mystruct;
int compare( const void *long1, const void *long2 );

int main()
{
mystruct devlist[4];

To do the above in C, add the aforementioned typedef.
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");
qsort( (void *)devlist, (size_t)4, sizeof( char * ), compare );

// bsearch is the next thing to work out how to do!
// void *bsearch( const void *key, const void *base, size_t num, size_t
width, int
// ( __cdecl *compare ) ( const void *elem1, const void *elem2 ) );
return 0;
}

int compare( const void* val1, const void* val2 )
{
struct mystruct *sp1 = (mystruct*)val1;
struct mystruct *sp2 = (mystruct*)val2;
// IS THIS CORRECT?
return (int)(sp1->nKey - sp2->nKey);

If you want to sort in descending order, yes. If you want to sort in
_ascending_ order, flip the operands around.

Overall, a good first stab if you've never used qsort before.

Have fun,
-leor

Leor Zolman
BD Software
(e-mail address removed)
www.bdsoft.com -- On-Site Training in C/C++, Java, Perl & Unix
C++ users: Download BD Software's free STL Error Message
Decryptor at www.bdsoft.com/tools/stlfilt.html
 
L

Leor Zolman

Hello

Thanks for that. I am using VC++ so it didn't complain at the mystruct
line!

However, real reason for replying is that on first call of compare function,
if I do this:

struct mystruct *sp1 = (mystruct*)val1;
struct mystruct *sp2 = (mystruct*)val2;
sp1->nKey is some wierd value - 775043377
sp2->nKey is 9

on the second call to compare the values are:
sp1->nKey is some wierd value - 775435825
sp2->nKey is 775043377

So I have definitely done something wrong!
Sorry, my bad. I just ran it, it worked, and I didn't look hard enough
at the ordering...it was actually not in descending order.

Here's the problem: in your qsort call:

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

the 3rd parameter should be
sizeof (mystruct)
instead of
sizeof (char *)

I failed to double-check against my own mental checklist for args to
qsort:
"base, nel, width, compare"
-leor

Any ideas?



Leor Zolman said:
On Thu, 5 Feb 2004 14:43:22 -0000, "Angus Comber"


Please use a short subject line, and put the complete text of your
question in the message body.
#include <stdio.h>
#include <string.h>
#include <search.h>
struct mystruct
{
long nKey;
char szIP[20];
};

So is this C or C++? If C++, fine. If C, in order to use "mystruct" as
a typename (without having to say "struct mystruct", add this:

typedef struct mystruct mystruct;
int compare( const void *long1, const void *long2 );

int main()
{
mystruct devlist[4];

To do the above in C, add the aforementioned typedef.
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");
qsort( (void *)devlist, (size_t)4, sizeof( char * ), compare );

// bsearch is the next thing to work out how to do!
// void *bsearch( const void *key, const void *base, size_t num, size_t
width, int
// ( __cdecl *compare ) ( const void *elem1, const void *elem2 ) );
return 0;
}

int compare( const void* val1, const void* val2 )
{
struct mystruct *sp1 = (mystruct*)val1;
struct mystruct *sp2 = (mystruct*)val2;
// IS THIS CORRECT?
return (int)(sp1->nKey - sp2->nKey);

If you want to sort in descending order, yes. If you want to sort in
_ascending_ order, flip the operands around.

Overall, a good first stab if you've never used qsort before.

Have fun,
-leor

Leor Zolman
BD Software
(e-mail address removed)
www.bdsoft.com -- On-Site Training in C/C++, Java, Perl & Unix
C++ users: Download BD Software's free STL Error Message
Decryptor at www.bdsoft.com/tools/stlfilt.html

Leor Zolman
BD Software
(e-mail address removed)
www.bdsoft.com -- On-Site Training in C/C++, Java, Perl & Unix
C++ users: Download BD Software's free STL Error Message
Decryptor at www.bdsoft.com/tools/stlfilt.html
 
A

Al Bowers

Angus said:
Hello

Here is my code so far. Is this correct/incorrect/along the right
lines/other?

You are on the right tract but have a few errors.
#include <stdio.h>
#include <string.h>
#include <search.h>

search.h is not a Standard C header file. To declare functions qsort
and bsearch use the header stdlib.h
Replace the search.h include with
#include said:
struct mystruct
{
long nKey;
char szIP[20];
};

int compare( const void *long1, const void *long2 );

int main()
{
mystruct devlist[4]; 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");
qsort( (void *)devlist, (size_t)4, sizeof( char * ), compare );

You are sorting the array of structs. sizeof(char *)is the wrong
element width. Make this:
qsort(devlist,4,sizeof *devlist,compare);
// bsearch is the next thing to work out how to do!
// void *bsearch( const void *key, const void *base, size_t num, size_t
width, int
// ( __cdecl *compare ) ( const void *elem1, const void *elem2 ) );
return 0;
}

int compare( const void* val1, const void* val2 )
{
struct mystruct *sp1 = (mystruct*)val1;

struct mystruct *sp1 = (struct mystruct *)val1;
or better:
const struct mystruct *sp1 = val1;
struct mystruct *sp2 = (mystruct*)val2;

same as above.
// IS THIS CORRECT?
return (int)(sp1->nKey - sp2->nKey);

This return statement has a potential problem in the operands in the
substraction may have values that could cause the long type to
overflow or underflow. It would be better to use something like:

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

CBFalconer

Angus said:
Here is my code so far. Is this correct/incorrect/along the
right lines/other?
.... snip most code ...

int compare( const void* val1, const void* val2 )
{
struct mystruct *sp1 = (mystruct*)val1;
struct mystruct *sp2 = (mystruct*)val2;
// IS THIS CORRECT?
return (int)(sp1->nKey - sp2->nKey);
}

Almost. See revisions below:

int compare(const void* val1, const void* val2)
{
const struct mystruct *sp1 = val1;
const struct mystruct *sp2 = val2;
/* Preserve const, no useless error hiding casts */

/* // comments are not correct without a C99 compiler */

if (sp1->nKey > sp2->nKey) return 1;
else if (sp1->nKey < sp2->nKey) return -1;
else return 0;
/* subtraction may overflow, fouling everything */
} /* compare */
 
A

Angus Comber

I am, as they say in Peckham, a plonker - I should have noticed that!

Thank you.

Angus


Leor Zolman said:
Hello

Thanks for that. I am using VC++ so it didn't complain at the mystruct
line!

However, real reason for replying is that on first call of compare function,
if I do this:

struct mystruct *sp1 = (mystruct*)val1;
struct mystruct *sp2 = (mystruct*)val2;
sp1->nKey is some wierd value - 775043377
sp2->nKey is 9

on the second call to compare the values are:
sp1->nKey is some wierd value - 775435825
sp2->nKey is 775043377

So I have definitely done something wrong!
Sorry, my bad. I just ran it, it worked, and I didn't look hard enough
at the ordering...it was actually not in descending order.

Here's the problem: in your qsort call:

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

the 3rd parameter should be
sizeof (mystruct)
instead of
sizeof (char *)

I failed to double-check against my own mental checklist for args to
qsort:
"base, nel, width, compare"
-leor

Any ideas?



Leor Zolman said:
On Thu, 5 Feb 2004 14:43:22 -0000, "Angus Comber"


Please use a short subject line, and put the complete text of your
question in the message body.


#include <stdio.h>
#include <string.h>
#include <search.h>
struct mystruct
{
long nKey;
char szIP[20];
};

So is this C or C++? If C++, fine. If C, in order to use "mystruct" as
a typename (without having to say "struct mystruct", add this:

typedef struct mystruct mystruct;


int compare( const void *long1, const void *long2 );

int main()
{
mystruct devlist[4];

To do the above in C, add the aforementioned typedef.

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");
qsort( (void *)devlist, (size_t)4, sizeof( char * ), compare );

// bsearch is the next thing to work out how to do!
// void *bsearch( const void *key, const void *base, size_t num, size_t
width, int
// ( __cdecl *compare ) ( const void *elem1, const void *elem2 ) );
return 0;
}

int compare( const void* val1, const void* val2 )
{
struct mystruct *sp1 = (mystruct*)val1;
struct mystruct *sp2 = (mystruct*)val2;
// IS THIS CORRECT?
return (int)(sp1->nKey - sp2->nKey);

If you want to sort in descending order, yes. If you want to sort in
_ascending_ order, flip the operands around.

Overall, a good first stab if you've never used qsort before.

Have fun,
-leor

}

Leor Zolman
BD Software
(e-mail address removed)
www.bdsoft.com -- On-Site Training in C/C++, Java, Perl & Unix
C++ users: Download BD Software's free STL Error Message
Decryptor at www.bdsoft.com/tools/stlfilt.html

Leor Zolman
BD Software
(e-mail address removed)
www.bdsoft.com -- On-Site Training in C/C++, Java, Perl & Unix
C++ users: Download BD Software's free STL Error Message
Decryptor at www.bdsoft.com/tools/stlfilt.html
 
R

Richard Heathfield

Leor said:
#include <stdio.h>
#include <string.h>
#include <search.h>
struct mystruct
{
long nKey;
char szIP[20];
};

So is this C or C++?

It's C. The newsgroup in which he posted it is a bit of a giveaway.
If you want to sort in descending order, yes. If you want to sort in
_ascending_ order, flip the operands around.

Overall, a good first stab if you've never used qsort before.

You could have showed him a better way (I'll avoid your typedef, but not
because I don't think it's a good idea):

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

return sp1->nKey < sk2->nKey ? -1: sp1->nKey > sp2->nKey;
}

This version avoids casting away constness, and doesn't invoke potential
overflow in the subtraction (and thus undefined behaviour).
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,900
Latest member
Nell636132

Latest Threads

Top