You are not logged in.
I am having trouble finding the cause of segfault in function makeTree.
If I comment only the while loop, I get segfault..
If I comment only the qsort line, I get segfault..
If I comment the while and qsort I DONT get segfault.. Obviously this tells me that there are errors in both these places.. But I cant see it..
All segfaults are run-time..
// the compare function for qsort.
int compareFreq (const void *a, const void *b) {
const Tree *t1 = *(Tree**) a;
const Tree *t2 = *(Tree**) b; //need to cast a & b, since cannot dereference void.
int diff = (t1 -> freq) - (t2 -> freq);
return ((diff >= 0) ? ((diff > 0) ? -1: 0) : +1);
}
/* Implement the Huffmann algorithm (generate an encoding tree for a given character distribution)
* will return a pointer to a Tree */
Tree *makeTree(RateTable dist) {
Tree *forest[TABLE_SIZE];
for(int c=0; c < TABLE_SIZE; c++) {
if( (dist[c]) > 0) {
forest[c] = (Tree*)malloc(sizeof(Tree)); //allocate space for the pointer Tree.
assert(forest[c] != NULL);
forest[c] -> left = NULL;
forest[c] -> right = NULL;
forest[c] -> ch = c;
forest[c] -> freq = dist[c];
}
}
Tree *t1, *t2; // two tree's with the least freqs, need to sort with qsort
Tree *t; // the tree created from t1 and t2
t1 = (Tree*)malloc(sizeof(Tree));
t2 = (Tree*)malloc(sizeof(Tree));
t1 = (Tree*)malloc(sizeof(Tree));
qsort(forest, TABLE_SIZE, sizeof(Tree), compareFreq); // sort decreasing
int c = TABLE_SIZE-1;
while(c > 0) {
//make tree balanced, switch t1 and t2 for every even number c
if ( (c % 2) == 0) {
t1 = forest[c];
t2 = forest[c-1];
}
else {
t2 = forest[c];
t1 = forest[c-1];
}
(t -> left) = t1;
(t -> right)= t2;
(t -> ch) = 0;
(t -> freq) = (t1->freq) + (t2->freq);
//free the mem that was allocated above in for-loop, except forest[0]
if (c != 0)
free(forest[c]);
forest[c-1] = t;
--c;
}
return forest[0]; // the last remaining tree,
in the mainfile:
printf("Hello world..\n");
Tree *forest = makeTree(dist);
typedef struct _Tree {
struct _Tree *left;
struct _Tree *right; /* not in a leaf */
int ch; /* only in a leaf */
int freq; /* occurence rate of the character */
} Tree;
yilima@Estergon:0 > ./a.out infile.txt outfile
Hello world..
[1] 5591 segmentation fault ./a.out infile.txt outfile
yilima@Estergon:139 >
The ultimate Archlinux release name: "I am your father"
Offline
use a debugger:
gcc [b]-g[/b] ...
then:
gdb ./a.out
in gdb:
run infile.txt outfile
when core happens use:
where
- this will give you the stack - which will probably be helpful
Offline
Segfaults are common in C/C++ programming. One of the greatest skills you can learn, at this level, is debugging.
There's quite a few potential bugs in the above code. Usually when you're dealing with pointers you NEED to check for NULL.
t1 = (Tree*)malloc(sizeof(Tree));
t2 = (Tree*)malloc(sizeof(Tree));
t1 = (Tree*)malloc(sizeof(Tree));
That is a memory leak (t1 is reallocated, and the original memory for t1 is lost). It appears 't' is never allocated either, which is most likely your segfault.
Also note:
while(c > 0) {
.... snip ....
if (c != 0)
That condition will always succeed due to the conditions of the while loop.
Offline
Here's a few things I see:
Tree *t1, *t2; // two tree's with the least freqs, need to sort with qsort
Tree *t; // the tree created from t1 and t2
t1 = (Tree*)malloc(sizeof(Tree));
t2 = (Tree*)malloc(sizeof(Tree));
t1 = (Tree*)malloc(sizeof(Tree));
I don't see why you're malloc'ing t1 and t2. You only need to malloc t, as far as I can tell.
(t -> left) = t1;
(t -> right)= t2;
(t -> ch) = 0;
(t -> freq) = (t1->freq) + (t2->freq);
This entire block will segfault since t isn't allocated. Additionally, the last line will segfault if t1==NULL or t2==NULL
//free the mem that was allocated above in for-loop, except forest[0]
if (c != 0)
free(forest[c]);
forest[c-1] = t;
--c;
}
This probably won't cause a segfault, but it'll make your output wrong - you'll probably want to reallocate t to a new struct after you've assigned forest[c-1]=t;
Anyway, I also very-much agree with the others that learning gdb and debugging skills in general would be a great asset to you.
Oh, also,
int compareFreq (const void *a, const void *b) {
const Tree *t1 = *(Tree**) a;
const Tree *t2 = *(Tree**) b; //need to cast a & b, since cannot dereference void.
int diff = (t1 -> freq) - (t2 -> freq);
return ((diff >= 0) ? ((diff > 0) ? -1: 0) : +1);
}
If either t1 or t2 are NULL, this will segfault - you should probably check for that.
Last edited by Cerebral (2007-02-13 00:26:33)
Offline
Thanks alot guys.. Helped alot. I have also now learned more about gdb, I can create breakpoints and step throught the code.. This has been the most helpful, as I can now perfectly see where the segfaults occur.
The ultimate Archlinux release name: "I am your father"
Offline