sorting a hash table

Discussion in 'C Programming' started by dough, Oct 3, 2005.

  1. dough

    dough Guest

    I have a hash table with seperate chaining with a bunch of words in it.
    Here is my declaration:

    typedef struct word *word;
    struct word
    {
    int count;
    char *s;
    word next;
    };

    typedef struct table *table;
    struct table
    {
    int size;
    word *table;
    };


    After I fill the table(t) with words, I want to sort it with qsort().
    However, I know my declaration here is wrong somehow:

    total(t) gets the total number of words in the table.
    here is my call to qsort():

    qsort( t->table, total(t), sizeof(word), compare );


    here is my compare() function:

    int compare(const void *a, const void *b)
    {
    word wa = malloc(sizeof(wa));
    word wb = malloc(sizeof(wb));

    wa = *(const word const *) a;
    wb = *(const word const *) b;

    if( (wb->count) - (wa->count) == 0 )
    {
    return( strcmp(wb->s, wa->s) );
    }

    return ( (wb->count) - (wa->count) );
    }

    Somehow, wb and wa are not getting the right values. wa seems to get an
    actual word but wb is left NULL and i end up with a bus error. Any
    advice on this matter would be much appreciated.
    dough, Oct 3, 2005
    #1
    1. Advertising

  2. "dough" <> wrote in message
    news:...
    > I have a hash table with seperate chaining with a bunch of words in it.
    > Here is my declaration:
    >
    > typedef struct word *word;


    ^^^ I'm not sure it's generally a good idea to have the same name for
    different things.

    > struct word
    > {
    > int count;
    > char *s;
    > word next;
    > };
    >
    > typedef struct table *table;
    > struct table
    > {
    > int size;
    > word *table;


    ^^^ now you have 3 things named table. Scary...
    And here table seems to be a ptr to a ptr to a struct word according to your
    definitions. I'm not sure this is what you want.

    > };
    >
    >
    > After I fill the table(t) with words, I want to sort it with qsort().
    > However, I know my declaration here is wrong somehow:
    >
    > total(t) gets the total number of words in the table.
    > here is my call to qsort():
    >
    > qsort( t->table, total(t), sizeof(word), compare );


    sizeof(word) is sizeof(ptr to struct word), so, you're about to sort
    pointers?

    > here is my compare() function:
    >
    > int compare(const void *a, const void *b)
    > {
    > word wa = malloc(sizeof(wa));
    > word wb = malloc(sizeof(wb));


    Ouch. You're allocating as much memory for pointers wa and wb as their own
    size... Are you sure the following won't be enough:
    word wa, wb;
    ?

    > wa = *(const word const *) a;
    > wb = *(const word const *) b;


    Are you sure you need 1st asterisk?

    > if( (wb->count) - (wa->count) == 0 )
    > {


    Where did you free memory allocated by malloc()? C's not Java...

    > return( strcmp(wb->s, wa->s) );
    > }



    Where did you free memory allocated by malloc()? C's not Java...

    > return ( (wb->count) - (wa->count) );
    > }
    >
    > Somehow, wb and wa are not getting the right values. wa seems to get an
    > actual word but wb is left NULL and i end up with a bus error. Any
    > advice on this matter would be much appreciated.


    Your code is very very bad. Maybe because you don't understand what you
    wrote (and worse if you don't understand what you want) you can't get it to
    work.

    Alex
    Alexei A. Frounze, Oct 3, 2005
    #2
    1. Advertising

  3. dough

    Jack Klein Guest

    On 2 Oct 2005 21:10:21 -0700, "dough" <> wrote in
    comp.lang.c:

    > I have a hash table with seperate chaining with a bunch of words in it.
    > Here is my declaration:
    >
    > typedef struct word *word;


    Using typedef to create pointers to data objects is dangerous, and
    generally poor programming practice. This is despite the fact that
    some instructors and books recommend it.

    > struct word
    > {
    > int count;
    > char *s;
    > word next;


    OK, so this member is actually 'struct word *next'.

    > };
    >
    > typedef struct table *table;


    As above, dangerous. Likely to cause confusion.

    > struct table
    > {
    > int size;
    > word *table;


    So this member is actually 'struct word **next'.

    > };
    >
    >
    > After I fill the table(t) with words, I want to sort it with qsort().


    What is the __exact__ definition of 't'?

    > However, I know my declaration here is wrong somehow:
    >
    > total(t) gets the total number of words in the table.
    > here is my call to qsort():
    >
    > qsort( t->table, total(t), sizeof(word), compare );


    I have no idea what you are doing here, or if you are doing what you
    think you are doing.

    Assuming that 't' is defined as a pointer to a 'struct table', and is
    actually initialized to point to a 'struct table', the first value you
    are passing to qsort() is 't->table', which has the type 'pointer to a
    pointer to a struct word'. So all that this actually points to is a
    pointer.

    > here is my compare() function:
    >
    > int compare(const void *a, const void *b)
    > {
    > word wa = malloc(sizeof(wa));
    > word wb = malloc(sizeof(wb));


    There's a serious problem here, not the least of which is that you
    don't free() the memory you allocated, so you are creating a memory
    leak. Let's lose the typedef's and see what you are really defining
    above:

    struct word *wa = malloc(sizeof(struct word *));
    struct word *wb = malloc(sizeof(struct word *));

    You are allocating enough memory for the size of a pointer to a
    structure, and assigning it to a pointer to that structure type. Since
    the structure contains a pointer to its own type, plus other members,
    its size must be greater than the size of the pointer.

    > wa = *(const word const *) a;
    > wb = *(const word const *) b;


    Let's lose the typedef's here, as well.

    wa = *(const struct word * const *) a;
    wb = *(const struct word * const *) b;

    As near as I can tell, since you haven't shown us the actual
    definition of 't', you are copying two structures into allocated
    memory that is not large enough to hold them. You have generated
    undefined behavior.

    >
    > if( (wb->count) - (wa->count) == 0 )
    > {
    > return( strcmp(wb->s, wa->s) );
    > }
    >
    > return ( (wb->count) - (wa->count) );
    > }
    >
    > Somehow, wb and wa are not getting the right values. wa seems to get an
    > actual word but wb is left NULL and i end up with a bus error. Any
    > advice on this matter would be much appreciated.


    The first thing you need to do is get rid of the typedef's. Don't
    ever use them for pointers that you will actually be dereferencing,
    you are getting lost behind them.

    Really, really, REALLY get rid of those typedef's.

    Then there is this. The qsort() function sorts arrays, not linked
    lists. If you want to sort a linked list, you need a different
    algorithm, one that is not provided in the C standard library.

    --
    Jack Klein
    Home: http://JK-Technology.Com
    FAQs for
    comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
    comp.lang.c++ http://www.parashift.com/c -faq-lite/
    alt.comp.lang.learn.c-c++
    http://www.contrib.andrew.cmu.edu/~ajo/docs/FAQ-acllc.html
    Jack Klein, Oct 3, 2005
    #3
  4. In article <>,
    Jack Klein <> wrote:

    > On 2 Oct 2005 21:10:21 -0700, "dough" <> wrote in
    > comp.lang.c:
    >
    > > I have a hash table with seperate chaining with a bunch of words in it.
    > > Here is my declaration:
    > >
    > > typedef struct word *word;

    >
    > Using typedef to create pointers to data objects is dangerous, and
    > generally poor programming practice. This is despite the fact that
    > some instructors and books recommend it.


    Would you detail the dangers? I can only think that it
    might make it more likely that some one will evaluate an
    invalid pointer.

    --
    Michael Press
    Michael Press, Oct 6, 2005
    #4
  5. dough

    Michael Mair Guest

    Michael Press wrote:
    > In article <>,
    > Jack Klein <> wrote:
    >
    >
    >>On 2 Oct 2005 21:10:21 -0700, "dough" <> wrote in
    >>comp.lang.c:
    >>
    >>
    >>>I have a hash table with seperate chaining with a bunch of words in it.
    >>> Here is my declaration:
    >>>
    >>>typedef struct word *word;

    >>
    >>Using typedef to create pointers to data objects is dangerous, and
    >>generally poor programming practice. This is despite the fact that
    >>some instructors and books recommend it.

    >
    > Would you detail the dangers? I can only think that it
    > might make it more likely that some one will evaluate an
    > invalid pointer.


    Well, try to get a "const struct word*" from the typedef "word".
    If you use "const word", you get a "struct word * const".
    People not aware of this may run into trouble. Let alone volatile.

    Another thing is "forgetting" that one is dealing with a pointer
    which is particularly nasty if you work with void * and get
    back your objects by cast...

    These are just two but I saw enough bugs with a pointer typedef
    at the bottom to avoid them for the future. One saved "*" is not
    worth it.

    Cheers
    Michael
    --
    E-Mail: Mine is an /at/ gmx /dot/ de address.
    Michael Mair, Oct 6, 2005
    #5
    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. vikas
    Replies:
    3
    Views:
    506
    CBFalconer
    Aug 16, 2007
  2. rp
    Replies:
    1
    Views:
    491
    red floyd
    Nov 10, 2011
  3. Williams, Chris
    Replies:
    3
    Views:
    96
    Florian Gross
    Dec 13, 2004
  4. Srijayanth Sridhar
    Replies:
    19
    Views:
    595
    David A. Black
    Jul 2, 2008
  5. IanW
    Replies:
    3
    Views:
    121
    Ian Stuart
    Dec 14, 2005
Loading...

Share This Page