c programming - getting SegFault..

jinn · 2007-02-12 14:05:18

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 >

drakosha · 2007-02-12 15:36:41

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

phrakture · 2007-02-12 16:23:24

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.

Cerebral · 2007-02-13 00:19:54

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)

jinn · 2007-02-14 22:37:16

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.

Arch Linux

#1 2007-02-12 14:05:18

c programming - getting SegFault..

#2 2007-02-12 15:36:41

Re: c programming - getting SegFault..

#3 2007-02-12 16:23:24

Re: c programming - getting SegFault..

#4 2007-02-13 00:19:54

Re: c programming - getting SegFault..

#5 2007-02-14 22:37:16

Re: c programming - getting SegFault..

Board footer