qsort + structure problem

[Excluded_Middle]

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);
}

but qsort is not working.Please help me
Also if some can tell me how to make sorting code for name.

 

[=?ISO-8859-1?Q?=22Nils_O=2E_Sel=E5sdal=22?=]

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);
}

but qsort is not working.Please help me
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);
}

 

[Jonathan Adams]

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);
}

but qsort is not working.Please help me
Also if some can tell me how to make sorting code for name.

See the strcmp() function.

Cheers,
- jonathan

 

[Andrey Tarasevich]

...
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);
}

 

[Herbert Rosenau]

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);
}

but qsort is not working.Please help me
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.

 

[Andrey Tarasevich]

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.

 

[Excluded_Middle]

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 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 add();
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;

if(strcmp(cmd,"add")==0)
add();

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 message not found
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;
}

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

scanf("%d\n",&id); //reads msg id

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 ***********/

 

[Old Wolf]

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?
(This is why C++ comments are bad on Usenet)
Also you should post the contents of a.h

/************ FUNCTION PROTOTYPES **************/
void checkPtr(void *p);
void performAction(char *cmd);
void printList();
void add();
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,
and in some cases it can cause trouble. (Read the FAQ for more info).

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

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;

if(strcmp(cmd,"add")==0)
add();

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 message not found
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
for freeing a message, rather than freeing messageText
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;
}


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

scanf("%d\n",&id); //reads msg id

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
what your instructor found.

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'