qsort of malloc'ed structs

[Bidule]

Hi,

I'm trying to sort structs defined as follows:

struct combinationRec {
float score;
char* name;
};

The number of structs and the length of the "name" field are not known
at compile time.
I've been struggling with this code all afternoon...
I believe I'm sticking to what's explained into the C faq. This is
probably not the case because qsort just crashes on me!

Does anyone have an idea why ?

Matt



/*
* qsort of malloc'ed structs
*/

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

struct combinationRec {
float score;
char* name;
};

// Score sorting function
int scoreSort(const void *p1, const void *p2) {
struct combinationRec *sp1 = *(struct combinationRec * const *)p1;
struct combinationRec *sp2 = *(struct combinationRec * const *)p2;
if (sp1->score < sp2->score) return -1;
if (sp1->score > sp2->score) {return +1;}
else {return 0;}
}

int main(int argc, char* argv[])
{
combinationRec *allCombinations;
combinationRec *currComb;

int i, j;
int numStructs;
int nameLength;
char letter;

randomize();
numStructs = rand()%15+1;
if ( (allCombinations = (combinationRec *) malloc( sizeof
(combinationRec)*numStructs)) == NULL ) {
printf("Not enough memory to allocate buffer\n");
exit(EXIT_FAILURE);
}

for (i=0; i<numStructs; i++) {
currComb = &allCombinations;

nameLength = rand()%15+1;

if ( (currComb->name = (char *) malloc( sizeof (char)*(
nameLength + 1 ))) == NULL ) {
printf("Not enough memory to allocate buffer\n");
exit(EXIT_FAILURE);
}

currComb->score = (float) (rand()% 50) / 3.14159;
for (j=0; j<nameLength; j++) {
letter = rand()%26 + 'A';
currComb->name[j] = letter;
}
currComb->name[nameLength] = '\0';
}

// Display structs before sort
printf("Before sort:\n");
for (i=0; i<numStructs; i++) {
printf("struct no. %2i: score=%7.3f name=%s\n",
i,
allCombinations.score,
allCombinations.name
);
}

printf("Calling qsort\n");

// Sort structs by score
qsort(allCombinations, numStructs , sizeof( allCombinations[0] ),
scoreSort);

// Show sorted scores
printf("Sorted:\n");
for (i=0; i<numStructs; i++) {
printf("struct no. %2i: score=%7.3f name=%s\n",
i,
allCombinations.score,
allCombinations.name
);
}

// Cleanup
for (i=0; i<numStructs; ++i) {
free((void *)allCombinations.name);
}
free((void *)allCombinations);


// Exit
return 0;
}

 

[Flash Gordon]

Hi,

I'm trying to sort structs defined as follows:

struct combinationRec {
float score;

Why use float rather than double? In general, if you need a floating
point type double should be your default choice unless you have a
specific reason for using something else. After all, floats keep getting
converted to doubles anyway.

char* name;
};

The number of structs and the length of the "name" field are not known
at compile time.
I've been struggling with this code all afternoon...
I believe I'm sticking to what's explained into the C faq. This is
probably not the case because qsort just crashes on me!

Does anyone have an idea why ?

Well, I've got a few comments on the code, one of which is the reported
problem. The first is that it doesn't compile if fed to a C compiler.
I suspect you have been using a C++ compiler which is a serious mistake
since that is a different language.

/*
* qsort of malloc'ed structs
*/

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

struct combinationRec {
float score;
char* name;
};

// Score sorting function
int scoreSort(const void *p1, const void *p2) {
struct combinationRec *sp1 = *(struct combinationRec * const *)p1;
struct combinationRec *sp2 = *(struct combinationRec * const *)p2;

Don't cast to/from void* pointers, you don't need to if you do it write.
Also you seem not to understand the difference in positions of const and
what it means. In this case a simple:

const struct combinationRec *sp1 = p1;
const struct combinationRec *sp2 = p2;

It's the mess you made of this that is the problem. Look again at the
definition of qsort and the parameters it passes to your comparison
function. Note that I don't have as much indirection as you.

if (sp1->score < sp2->score) return -1;
if (sp1->score > sp2->score) {return +1;}
else {return 0;}
}

int main(int argc, char* argv[])
{
combinationRec *allCombinations;
combinationRec *currComb;

Both the above lines are errors since C, unlike C++, does not
automatically create type aliases when you define a struct.
struct combinationRec *allCombinations;
struct combinationRec *currComb;

int i, j;
int numStructs;
int nameLength;
char letter;

randomize();

There is no such function as randomise. Perhaps you should look up srand
in your documentation.

numStructs = rand()%15+1;
if ( (allCombinations = (combinationRec *) malloc( sizeof
(combinationRec)*numStructs)) == NULL ) {

In C you don't need the cast, and in any case you don't have a type
named combinationRec. The cast is ugly and prevents the compiler
prodicing a required diagnistic if you forget to include stdlib.h.

if ( (allCombinations =
malloc( numstructs * sizeof *allCombinations)) == NULL ) {

Note also using sizeof *ptrname, much less likely to make an error that way.

printf("Not enough memory to allocate buffer\n");
exit(EXIT_FAILURE);
}

for (i=0; i<numStructs; i++) {
currComb = &allCombinations;

nameLength = rand()%15+1;

if ( (currComb->name = (char *) malloc( sizeof (char)*(
nameLength + 1 ))) == NULL ) {

sizeof(char) is 1 by *definition*. So so following is fine:
if ( (currComb->name = malloc( nameLength + 1 )) == NULL ) {

printf("Not enough memory to allocate buffer\n");
exit(EXIT_FAILURE);
}

currComb->score = (float) (rand()% 50) / 3.14159;
for (j=0; j<nameLength; j++) {
letter = rand()%26 + 'A';
currComb->name[j] = letter;
}
currComb->name[nameLength] = '\0';
}

// Display structs before sort
printf("Before sort:\n");
for (i=0; i<numStructs; i++) {
printf("struct no. %2i: score=%7.3f name=%s\n",
i,
allCombinations.score,
allCombinations.name
);
}

printf("Calling qsort\n");

// Sort structs by score

// style comments don't exist in the original C standard, they have been
added by the latest standard, but conforming compilers are rare. Also,
they are a bad idea for Usenet posts because they don't survive line
wrapping.

qsort(allCombinations, numStructs , sizeof( allCombinations[0] ),
scoreSort);

// Show sorted scores
printf("Sorted:\n");
for (i=0; i<numStructs; i++) {
printf("struct no. %2i: score=%7.3f name=%s\n",
i,
allCombinations.score,
allCombinations.name
);
}

// Cleanup
for (i=0; i<numStructs; ++i) {
free((void *)allCombinations.name);

Again, the cast isn't needed in C.
free(allCombinations.name);

}
free((void *)allCombinations);

free(allCombinations);

// Exit

Not a very helpful comment.

 

[Robert Harris]

Hi,

I'm trying to sort structs defined as follows:

struct combinationRec {
float score;
char* name;
};

The number of structs and the length of the "name" field are not known
at compile time.
I've been struggling with this code all afternoon...
I believe I'm sticking to what's explained into the C faq. This is
probably not the case because qsort just crashes on me!

Does anyone have an idea why ?

Matt



/*
* qsort of malloc'ed structs
*/

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

struct combinationRec {
float score;
char* name;
};

// Score sorting function
int scoreSort(const void *p1, const void *p2) {
struct combinationRec *sp1 = *(struct combinationRec * const *)p1;
struct combinationRec *sp2 = *(struct combinationRec * const *)p2;

These lines should read:
const struct combinationRec *sp1 = (const struct combinationRec *)p1;
const struct combinationRec *sp2 = (const struct combinationRec *)p2;

if (sp1->score < sp2->score) return -1;
if (sp1->score > sp2->score) {return +1;}
else {return 0;}
}
[snip]

// Sort structs by score
qsort(allCombinations, numStructs , sizeof( allCombinations[0] ),
scoreSort);
[snip]

 

[Robin Haigh]

Hi,

I'm trying to sort structs defined as follows:

struct combinationRec {
float score;
char* name;
};

The number of structs and the length of the "name" field are not known
at compile time.
I've been struggling with this code all afternoon...
I believe I'm sticking to what's explained into the C faq. This is
probably not the case because qsort just crashes on me!

Does anyone have an idea why ?

Matt



/*
* qsort of malloc'ed structs
*/

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

struct combinationRec {
float score;
char* name;
};

// Score sorting function
int scoreSort(const void *p1, const void *p2) {
struct combinationRec *sp1 = *(struct combinationRec * const *)p1;
struct combinationRec *sp2 = *(struct combinationRec * const *)p2;
if (sp1->score < sp2->score) return -1;
if (sp1->score > sp2->score) {return +1;}
else {return 0;}
}

int main(int argc, char* argv[])
{
combinationRec *allCombinations;
combinationRec *currComb;

int i, j;
int numStructs;
int nameLength;
char letter;

randomize();
numStructs = rand()%15+1;
if ( (allCombinations = (combinationRec *) malloc( sizeof
(combinationRec)*numStructs)) == NULL ) {
printf("Not enough memory to allocate buffer\n");
exit(EXIT_FAILURE);
}

[etc]

There are two ways of doing it:

Plan A: create an array of structs, and sort them in place (actually copying
around the contents)

Plan B: create an array of pointers, and sort the pointers according to the
data they point to

You're basically doing Plan A, but your comparison routine belongs to Plan
B. This is where the confusion has come in

 

[CBFalconer]

These lines should read:
const struct combinationRec *sp1 = (const struct combinationRec *)p1;
const struct combinationRec *sp2 = (const struct combinationRec *)p2;

Please leave blank lines between quotations and your material.

As pointed out by Flash, those lines should read:

const struct combinationRec *sp1 = p1;
const struct combinationRec *sp2 = p2;

Casts are evil, to be avoided, and normally wrong.

--
"The power of the Executive to cast a man into prison without
formulating any charge known to the law, and particularly to
deny him the judgement of his peers, is in the highest degree
odious and is the foundation of all totalitarian government
whether Nazi or Communist." -- W. Churchill, Nov 21, 1943

 

[Bidule]

Flash Gordon a écrit :

Well, I've got a few comments on the code, one of which is the reported
problem. The first is that it doesn't compile if fed to a C compiler. I
suspect you have been using a C++ compiler which is a serious mistake
since that is a different language.

True. And actually, this is a very good piece of advice. When compiling
in pure C mode, I get informative error messages.

Thanks for those who have answered. It works well now.

Matt