qsort + structure problem

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

  1. 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.
     
    Excluded_Middle, Oct 26, 2004
    #1
    1. Advertising

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


    --
    Nils O. SelÄsdal
    www.utelsystems.com
     
    =?ISO-8859-1?Q?=22Nils_O=2E_Sel=E5sdal=22?=, Oct 26, 2004
    #2
    1. Advertising

  3. 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);
    > }
    >
    > 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
     
    Jonathan Adams, Oct 26, 2004
    #3
  4. 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
    #4
  5. 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);
    > }
    >
    > 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.


    --
    Tschau/Bye
    Herbert

    Visit http://www.ecomstation.de the home of german eComStation
     
    Herbert Rosenau, Oct 27, 2004
    #5
  6. 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
    #6
  7. 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 ***********/
     
    Excluded_Middle, Nov 2, 2004
    #7
  8. Excluded_Middle

    Old Wolf Guest

    (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?
    (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'

    >
    > void checkPtr(void *p)
    > {
    > if(p == NULL)
    > {
    > printf("out of memory\n");
    > freeAll();
    > exit(1);
    > }
    > }
    >
    > /*********** code End ***********/
     
    Old Wolf, Nov 4, 2004
    #8
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    16
    Views:
    553
    CBFalconer
    Dec 10, 2004
  2. c_programmer
    Replies:
    3
    Views:
    417
    Richard Bos
    Jun 9, 2005
  3. Replies:
    6
    Views:
    755
  4. qsort problem

    , Apr 6, 2008, in forum: C Programming
    Replies:
    12
    Views:
    598
    Barry Schwarz
    Apr 14, 2008
  5. Igal

    problem with qsort - Visual Studio

    Igal, May 21, 2008, in forum: C Programming
    Replies:
    0
    Views:
    560
Loading...

Share This Page