sorting a hash table

[dough]

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.

 

[Alexei A. Frounze]

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

 

[Jack Klein]

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.

 

[Michael Press]

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 Mair]

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