# qsort + structure problem

Discussion in 'C Programming' started by Excluded_Middle, Oct 26, 2004.

1. ### Excluded_MiddleGuest

Suppose I have a struct

typdef struct foo
{
int age;
char *name;
}foo;

now I made a list of foo using

foo **li;
li = (foo **)calloc(size,sizeof(foo*));

then i add some element in foo like

foo * elem;
elem = (foo*)malloc(sizeof(foo));

elem->age = some int;
elem->name = some char* allocated by malloc

*(li + i) = elem; // put elem at li

ok my list is created and look good. now here is the question: I try
qsort to sort list by age and and name;

for age I use

qsort(*li,count,sizeof(foo *),mycmp);

void mycmp(const void *p1,const void p2)
{
const struct foo *ma = p1;
const struct foo *mb = p2;
int age1,age2;
age1 = ma->age;
age2 = mb->age;

return(age1 - age2);
}

Also if some can tell me how to make sorting code for name.

Excluded_Middle, Oct 26, 2004

2. ### =?ISO-8859-1?Q?=22Nils_O=2E_Sel=E5sdal=22?=Guest

Excluded_Middle wrote:
> Suppose I have a struct
>
> typdef struct foo
> {
> int age;
> char *name;
> }foo;
>
> now I made a list of foo using
>
> foo **li;
> li = (foo **)calloc(size,sizeof(foo*));
>
> then i add some element in foo like
>
> foo * elem;
> elem = (foo*)malloc(sizeof(foo));
>
> elem->age = some int;
> elem->name = some char* allocated by malloc
>
> *(li + i) = elem; // put elem at li
>
> ok my list is created and look good. now here is the question: I try
> qsort to sort list by age and and name;
>
> for age I use
>
> qsort(*li,count,sizeof(foo *),mycmp);
>
> void mycmp(const void *p1,const void p2)
> {
> const struct foo *ma = p1;
> const struct foo *mb = p2;
> int age1,age2;
> age1 = ma->age;
> age2 = mb->age;
>
> return(age1 - age2);
> }
>
> Also if some can tell me how to make sorting code for name.

The qsort compare function gives you a pointer to the elements,
since your elements seems themselves to be pointers:

void mycmp(const void *p1,const void p2)
{
const struct foo **ma = p1;
const struct foo **mb = p2;
int age1,age2;
age1 = (*ma)->age;
age2 = (*mb)->age;

return(age1 - age2);
}

--
Nils O. SelĂ„sdal
www.utelsystems.com

=?ISO-8859-1?Q?=22Nils_O=2E_Sel=E5sdal=22?=, Oct 26, 2004

In article <>,
(Excluded_Middle) wrote:

> typdef struct foo
> {
> int age;
> char *name;
> }foo;

....
> foo **li;
> li = (foo **)calloc(size,sizeof(foo*));

....
> *(li + i) = elem; // put elem at li

....
> qsort(*li,count,sizeof(foo *),mycmp);
>
> void mycmp(const void *p1,const void p2)

^ missing *
> {
> const struct foo *ma = p1;
> const struct foo *mb = p2;

The arguments to mycmp are members of the array (i.e. (li + i) for
some i), without any dereferencing (i.e. not *(li + i)). So you need
something like:

const struct foo **map = p1;
const struct foo **mbp = p2;

const struct foo *ma = *map;
const struct foo *mb = *mbp;

instead of what you have currently.

> int age1,age2;
> age1 = ma->age;
> age2 = mb->age;
>
> return(age1 - age2);
> }
>
> Also if some can tell me how to make sorting code for name.

See the strcmp() function.

Cheers,
- jonathan

4. ### Andrey TarasevichGuest

Excluded_Middle wrote:
> ...
> qsort(*li,count,sizeof(foo *),mycmp);
>
> void mycmp(const void *p1,const void p2)
> {
> const struct foo *ma = p1;
> const struct foo *mb = p2;
> int age1,age2;
> age1 = ma->age;
> age2 = mb->age;
>
> return(age1 - age2);
> }
>
> but qsort is not working.
> ...

Your 'li' is an array of pointers to 'foo' structures. In order to sort
it using 'qsort' you need to do two things

1. Provide correct arguments to 'qsort'

In this case the correct way to call 'qsort' is

qsort(li, count, sizeof(foo*), mycmp);

Note the absence of '*' before 'li'. For some reason no one mentioned
this problem yet.

I would also suggest replacing 'sizeof(foo*)' with 'sizeof *li'.

qsort(li, count, sizeof *li, mycmp);

2. Provide a correct comparison function to 'qsort'

Firstly, note that parameters of the comparison function will hold
pointers-to-pointers-to-'foo', not pointers-to-'foo', as you seem to
assume.

Secondly, comparison function shall be declared as returning 'int', not
'void'.

Thirdly, in general case comparing two 'int' values by subtracting one
from another can lead to overflow thus causing undefined behavior.
Apparently in your case the overflow is unlikely, since these 'int'
values are in range 0...100 (or, say, 0...200 to add a bit of optimism
to this generally pessimistic message , but just in case I'll
demonstrate the safer technique in the code below.

For example, the comparison function can be implemented as follows

int mycmp(const void *p1, const void *p2)
{
const foo *ma = *(const foo *const *) p1;
const foo *mb = *(const foo *const *) p2;
int age1, age2;
age1 = ma->age;
age2 = mb->age;
return (age1 > age2) - (age1 < age2);
}

--
Best regards,
Andrey Tarasevich

Andrey Tarasevich, Oct 26, 2004
5. ### Herbert RosenauGuest

On Tue, 26 Oct 2004 10:25:58 UTC, (Excluded_Middle)
wrote:

> Suppose I have a struct
>
> typdef struct foo
> {
> int age;
> char *name;
> }foo;
>
> now I made a list of foo using
>
> foo **li;
> li = (foo **)calloc(size,sizeof(foo*));

> then i add some element in foo like
>
> foo * elem;
> elem = (foo*)malloc(sizeof(foo));
>
> elem->age = some int;
> elem->name = some char* allocated by malloc
>
> *(li + i) = elem; // put elem at li
>
> ok my list is created and look good. now here is the question: I try
> qsort to sort list by age and and name;
>
> for age I use
>
> qsort(*li,count,sizeof(foo *),mycmp);

qsort requies the size of an element to sort, not the size of an
pointer to an element.

> void mycmp(const void *p1,const void p2)

mycmp requirs 2 pointers not a pointer and a void to be an compare
function for qsort

> {
> const struct foo *ma = p1;
> const struct foo *mb = p2;
> int age1,age2;
> age1 = ma->age;
> age2 = mb->age;
>
> return(age1 - age2);
> }
>
> Also if some can tell me how to make sorting code for name.

You have
- undefined behavior - hidden by an unneeded cast
- too may bugs in data assignments and prototypes.

--
Tschau/Bye
Herbert

Visit http://www.ecomstation.de the home of german eComStation

Herbert Rosenau, Oct 27, 2004
6. ### Andrey TarasevichGuest

Herbert Rosenau wrote:
>>
>> for age I use
>>
>> qsort(*li,count,sizeof(foo *),mycmp);

>
> qsort requies the size of an element to sort, not the size of an
> pointer to an element.
> ...

Array 'li' actually contains pointers to elements and that's what the OP
is trying to sort, which means that 'sizeof' part is correct. The rest
isn't.

--
Best regards,
Andrey Tarasevich

Andrey Tarasevich, Oct 27, 2004
7. ### Excluded_MiddleGuest

I did my assignment before I got the first reply but anyway I learned
more from you guys. The only problem I had when my teacher check the
assignment is memory leak. I don't know where I made mistake may be
you guys can tell me since my teacher just check the leak by a some
linux command and he didn't give me any positive feedback about
it.Also you can tell me about where I can improve my programming in c.

/**************** Code ********************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "a.h" // defination of some constants and message
struct

/************ FUNCTION PROTOTYPES **************/
void checkPtr(void *p); //if malloc or calloc returns null
void performAction(char *cmd); //perform action according to passed
arguments
void printList();
void deleteMsg();
int find(int id);
int sbi(const void *a,const void *b);
int sbt(const void *a,const void *b);
void freeAll();

message *list;
int currentSize;
int counter = 0;
char *cmdBuffer; // for reading command lines

int main()
{
currentSize = INITIAL_CAPACITY;

list = (message *)calloc(INITIAL_CAPACITY,sizeof(message));
checkPtr(list);

cmdBuffer = (char *) malloc(MAX_CMD_LEN);
checkPtr(cmdBuffer);

while((scanf("%s",cmdBuffer)) != EOF)
{
performAction(cmdBuffer);
}
freeAll();
return 0;
}

void performAction(char *cmd)
{
int f,fid;

else if(strcmp(cmd,"delete")==0)
deleteMsg();

else if(strcmp(cmd,"find")==0)
{
scanf("%d",&fid);
f = find(fid);
if(f != -1)
{
printf("%s\n",((list + f))->messageText);
}
}

else if(strcmp(cmd,"output")==0)
printList();

else if(strcmp(cmd,"sortById")==0)
{
qsort(list,counter,sizeof(message),sbi);
}

else if(strcmp(cmd,"sortByText")==0)
qsort(list,counter,sizeof(message),sbt); //printf("Sorting list by
text\n");
}

int sbi(const void *a,const void *b)
{
return (((message *)a)->messageId - ((message *)b)->messageId);
}

int sbt(const void *a,const void *b)
{
const char *cs = (const char *)(((message *)a)->messageText);
const char *ct = (const char *)(((message *)b)->messageText);
return (strcmp(cs,ct));
}

void deleteMsg()
{
int id,i,index;
char *tmpTxt;
message *tmp;
scanf("%d",&id);

index = find(id);

if(index == -1)
return;

//printf("Deleting\n");
tmp = (list + index); //list[index]
tmpTxt = tmp->messageText;

free(tmpTxt);
//free(tmp);
counter--;

for(i = index;i < counter;i++)
{
*(list + i) = *(list + (i+1));
}
}

int find(int id)
{
message *tmp;
int i;
for(i = 0; i < counter; i++)
{
tmp = (list + i);
if((tmp->messageId) == id)
return i;
}
return -1;
}

{
int id,len;
int i;
char *txt;
char *str; //string withour newline character and exact length
message *msg;
message *tmp;

txt = (char *) malloc(MAX_TEXT_LEN);
checkPtr(txt);

fgets(txt,MAX_TEXT_LEN,stdin); //reads a line from stdin and save it
in txt

// skip if find the msg with same id
if(find(id) != -1)
{
free(txt);
return;
}

/***** If the list of pointer is full then allocate more space ****/
if(counter == currentSize)
{
currentSize += CAPACITY_INCREMENT;
tmp = (message *)realloc((void *)list,currentSize *
sizeof(message));
checkPtr(tmp);
list = tmp;
}

len = strlen(txt); //length of string
str = (char *) malloc(len); //create a string of exact mesg length
checkPtr(str);
*(txt+(len-1)) = '\0'; //remove trailing newline
strcpy(str,txt); //copy txt to str
free(txt); //don't need txt str is in diffrent location

msg = (list + counter++);
msg->messageId = id;
msg->messageText = str;
}

void printList()
{
message *tmp;
int i;
for(i = 0; i < counter; i++)
{
tmp = (list + i);
//printf("%d\n",tmp->messageId);
printf("%s\n",tmp->messageText);
}
}

void freeAll()
{
message *tmp;
char *str;
int i;
for(i = 0; i < counter; i++)
{
tmp = (list + i);
free(tmp->messageText);
}
free(list);
free(cmdBuffer);
}

void checkPtr(void *p)
{
if(p == NULL)
{
printf("out of memory\n");
freeAll();
exit(1);
}
}

/*********** code End ***********/

Excluded_Middle, Nov 2, 2004
8. ### Old WolfGuest

(Excluded_Middle) wrote:
> Thank you all for reply,
> I did my assignment before I got the first reply but anyway I learned
> more from you guys. The only problem I had when my teacher check the
> assignment is memory leak. I don't know where I made mistake
>
> /**************** Code ********************/
> #include <stdio.h>
> #include <stdlib.h>
> #include <string.h>
> #include "a.h" // defination of some constants and message
> struct

Struct what?
Also you should post the contents of a.h

>
> /************ FUNCTION PROTOTYPES **************/
> void checkPtr(void *p);
> void performAction(char *cmd);
> void printList();
> void deleteMsg();
> int find(int id);
> int sbi(const void *a,const void *b);
> int sbt(const void *a,const void *b);
> void freeAll();
>
> message *list;
> int currentSize;
> int counter = 0;

Global variables, brrr. It would be better to put these three
in a struct at least (since they are all related to the same
conceptual object).

An expert programmer would declare this in main() and pass
it to whatever functions need it.
This means that you could have another list within the same
program, if you wanted, and it also makes it very clear which
parts of the program are affected if you change the structure
of the list. (This principle is called 'encapsulation').

However this makes freeing it slightly more complicated
(you can't just have a freeAll() function like you do now),
so you can hold off on this improvement until you've sorted
out all the other problems.

> char *cmdBuffer; // for reading command lines

This could be declared (and freed) within main().

> int main()
> {
> currentSize = INITIAL_CAPACITY;
>
> list = (message *)calloc(INITIAL_CAPACITY,sizeof(message));

It looks like your instructor didn't teach malloc very well:
list = malloc(INITIAL_CAPACITY * sizeof *list);

It is pointless to use 'calloc' if you're allocating pointers
(it doesn't necessarily set them to NULL). If you actually want
all the members of 'list' to start off as NULL then you'll have
to write a loop to go through and set them one by one.
(Looking at your code, I think it works fine if they are not
NULLed).

> checkPtr(list);
>
> cmdBuffer = (char *) malloc(MAX_CMD_LEN);

cmdBuffer = malloc(MAX_CMD_LEN);

Casting the return value of malloc gains you absolutely nothing,

Also, since MAX_CMD_LEN changes then there is no need to use
dynamic allocation at all -- it is merely a source of errors.

char cmdBuffer[MAX_CMD_LEN];

at the start of main(). Then you don't have to check a pointer
and you don't have to free it.

> checkPtr(cmdBuffer);
>
> while((scanf("%s",cmdBuffer)) != EOF)
> {
> performAction(cmdBuffer);
> }
> freeAll();
> return 0;
> }
>
> void performAction(char *cmd)
> {
> int f,fid;
>
>
> else if(strcmp(cmd,"delete")==0)
> deleteMsg();
>
> else if(strcmp(cmd,"find")==0)
> {
> scanf("%d",&fid);

You should check this scanf() call for failure, like you did
with the previous scanf.

> f = find(fid);
> if(f != -1)
> {
> printf("%s\n",((list + f))->messageText);
> }
> }
>
> else if(strcmp(cmd,"output")==0)
> printList();
>
> else if(strcmp(cmd,"sortById")==0)
> {
> qsort(list,counter,sizeof(message),sbi);

As others have suggested: sizeof *list.
Then if you ever change list to something other than "message *"
you don't have to go through and change all your sizeof's.

> }
>
> else if(strcmp(cmd,"sortByText")==0)
> qsort(list,counter,sizeof(message),sbt); > }
>
> int sbi(const void *a,const void *b)
> {
> return (((message *)a)->messageId - ((message *)b)->messageId);
> }
>
> int sbt(const void *a,const void *b)
> {
> const char *cs = (const char *)(((message *)a)->messageText);
> const char *ct = (const char *)(((message *)b)->messageText);

These variables are unnecessary. The casts are unnecessary,
unless messageText is not a char*, which I don't know since you
didn't include the text of "a.h".

> return (strcmp(cs,ct));

"return" doesn't need brackets. (It's not a function).
return strcmp( ((message *)a)->messageText,
((message *)b)->messageText );

> }
>
> void deleteMsg()
> {
> int id,i,index;
> char *tmpTxt;
> message *tmp;
> scanf("%d",&id);

Again, check the return value of scanf

> index = find(id);
>
> if(index == -1)
> return;
>
> //printf("Deleting\n");
> tmp = (list + index); //list[index]
> tmpTxt = tmp->messageText;
>
> free(tmpTxt);
> //free(tmp);

Right, you don't need to free tmp, because the whole of
'list' is allocated as one chunk.
So you could have saved some effort with:

free( list[index].messageText );

instead of all that stuff from "Deleting\n" onwards.

It would probably be better design to have a function
all over the place. (Then if you added another string to
the message structure, you would only have to add the
free() call in one place).

> counter--;
>
> for(i = index;i < counter;i++)
> {
> *(list + i) = *(list + (i+1));

Or just: list = list[i+1]

> }
> }
>
> int find(int id)
> {
> message *tmp;
> int i;
> for(i = 0; i < counter; i++)
> {
> tmp = (list + i);
> if((tmp->messageId) == id)
> return i;

Again you don't need this temp variable:
if (list.messageId == id)
would have been just fine.

> }
> return -1;
> }

>
> {
> int id,len;
> int i;
> char *txt;
> char *str;
>//string withour newline character and exact length
> message *msg;
> message *tmp;
>

Check scanf for failure.

>
> txt = (char *) malloc(MAX_TEXT_LEN);

Lose the cast. But as I mentioned before, it would be better
to not use dynamic allocation at all here:
char txt[MAX_TEXT_LEN];
That reduces the chance of memory leaks.

> checkPtr(txt);
>
> fgets(txt,MAX_TEXT_LEN,stdin);

Check fgets for failure.

> // skip if find the msg with same id
> if(find(id) != -1)
> {
> free(txt);
> return;
> }

You should do that before you input the txt, perhaps.

>
> /***** If the list of pointer is full then allocate more space ****/
> if(counter == currentSize)
> {
> currentSize += CAPACITY_INCREMENT;
> tmp = (message *)realloc((void *)list,currentSize *
> sizeof(message));
> checkPtr(tmp);

tmp = realloc(list, currentSize * sizeof *list);

> list = tmp;
> }
>
> len = strlen(txt); //length of string

Length of string, really? (avoid useless comments)

> str = (char *) malloc(len);
> checkPtr(str);
> *(txt+(len-1)) = '\0';
> strcpy(str,txt);
> free(txt);

This would be a memory leak if len is 0. Maybe that is

Also your code is a little non-idiomatic (by which I mean, I
thought it was wrong at first). This code is easier to follow:

txt[--len] = '\0';
str = malloc(len + 1);
checkPtr(str);
strcpy(str, txt);

because 'len' reflects the actual length of the string, at all times.

> msg = (list + counter++);
> msg->messageId = id;
> msg->messageText = str;
> }
>
> void printList()
> {
> message *tmp;
> int i;
> for(i = 0; i < counter; i++)
> {
> tmp = (list + i);
> //printf("%d\n",tmp->messageId);
> printf("%s\n",tmp->messageText);
> }
> }
>
> void freeAll()
> {
> message *tmp;
> char *str;
> int i;
> for(i = 0; i < counter; i++)
> {
> tmp = (list + i);
> free(tmp->messageText);
> }
> free(list);
> free(cmdBuffer);
> }

Same again, you could have written those two without 'tmp'

>
> void checkPtr(void *p)
> {
> if(p == NULL)
> {
> printf("out of memory\n");
> freeAll();
> exit(1);
> }
> }
>
> /*********** code End ***********/

Old Wolf, Nov 4, 2004