Segmentation faults in C

Haku72 · 11-19-2009, 12:25 PM

Hey guys! I've always looked through this forum but I never registered until just now because I'm having some issues with a program of mine and I figured I could try asking around here..

First, here's my section of the code in question:

-------------------------------------------------------------

Code:

typedef struct GraphHelp{
    int color;
    int parent;
    int source;
    ListRef neighbors;
}GraphHelp;

typedef GraphHelp* GraphHelpRef;

typedef struct Graph{
    int order;
    int size;
    int BFSsource;
    GraphHelpRef *graph;
}Graph;

/*** Constructors-Destructors ***/
GraphRef newGraph(int n){
    int i=0;
    GraphHelpRef *array = (GraphHelpRef *)malloc(n * sizeof(GraphHelpRef));
    GraphRef G = (Graph*)malloc(sizeof(GraphRef) * n);
    if(!G){
        printf("error allocating memory for Graph.\n");
        exit(1);
    }

    for (i=0; i<n;i++){
        GraphHelpRef temp = malloc(sizeof(GraphHelp));
        temp->color = i;
        temp->parent=NIL;
        temp->source = NIL;
        temp->neighbors = newList();
        printf("%d",i);
        array[n]=temp;
        printf(" done initializing\n");
    }

    G->graph = (GraphHelpRef *)&array[0];
    G->BFSsource=NIL;
    G->order=n;
    G->size=0;
    return G;
}

-------------------------------------------------------------

ListRef is another ADT I made, and is 100% functional. it's initialized by the newList() function, as shown above. GraphRef is declared in my header file.

GraphHelp was my way of giving up on trying to fit 4 arrays into one structure..as that was causing me issues too.. all the variables in GraphHelp can be moved back to Graph but they all have to be arrays. I couldn't figure out how to make 4 dynamic arrays in my own struct so I just did what is above as a means of "simplifying" things.

So...my issue is with the newGraph function... I am certain that I am making a mess of the pointers, memory allocation, and arrays because my program will give me segmentation faults whenever I try writing to:

(some GraphRef)->graph[x]->(anything).

I've tried everything but I cant seem to figure out how to do this correctly.. can anybody help find my mistake/help me correct it? I would appreciate any input very much!! :-)

If you have any questions, please don't hesitate to ask me.

sarum1990 · 11-19-2009, 12:29 PM

Quote:

Originally Posted by Haku72

Code:

        array[n]=temp;

I think you mean

Code:

       array[i]=temp;

since array[n] is always outside of the allocated memory for array

but in general for seg faults I would just drop the code into gdb, then when the seg fault happens you can at least determine what line of code it is on.

johnsfine · 11-19-2009, 01:01 PM

Quote:

Originally Posted by sarum1990

array[n] is always outside of the allocated memory for array

That bug is most likely the direct cause of the seg fault. But I'm pretty sure the seg fault would not occur on that line.

Quote:

in general for seg faults I would just drop the code into gdb, then when the seg fault happens you can at least determine what line of code it is on.

So would I. But that usually isn't enough.

Maybe the seg fault occurs inside the next call to malloc() after the bug (those cases are particularly hard for a beginner to debug). Maybe the seg fault occurs much later as a consequence of array[0] never being initialized, but that still may occur sooner than any consequence of the memory clobber at array[n].

I agree with you about which bug causes the seg fault. But I think there is another error in the posted code:

Code:

    GraphRef G = (Graph*)malloc(sizeof(GraphRef) * n);

What is the purpose of the multiply by n in that line?
Is the function supposed to return one initialized Graph or an array of Graph objects? If an array, why is only the first one initialized? Maybe this is setup for some n squared operation in which it is correct to have n Graphs and the first one initialized to own n GraphHelp objects. But more likely the OP hasn't yet figured out what exactly newGraph is supposed to build.

sarum1990 · 11-19-2009, 01:22 PM

You are correct, actually right after I posted that I realized that in this situation gdb would probably not be enough to single-handedly determine the cause of the seg fault. After I caught the array[n] error I stopped looking for others, but the extra *n is also mysterious, nice catch, and thank you for clarifying my gdb comment.

Haku72 · 11-19-2009, 01:42 PM

The array[n] issue was indeed the problem! I have it up and working with no seg faults now. woo~! Thanks you guys, both of you helped me so much! I can never find little mistakes like that easily..

Code:

 GraphRef G = (Graph*)malloc(sizeof(GraphRef) * n);

It is supposed to be a single graph. The extra * n was from how I originally set up the project (without GraphHelp), good catch- I deleted it now and all still works perfectly. With that little bit out of the way, does the memory allocation look alright? I was confused about it at first, but I think its fine?

As for gdb, I've only used it once or twice (almost a year ago), and I never really messed with it again. I usually just spend a lot of time sifting through code trying to figure it out. Probably not the most efficient way, huh? =P

I'll try gdb out, thanks for the recommendation guys.

I really appreciate your help! :-)

ta0kira · 11-19-2009, 03:27 PM

Quote:

Originally Posted by Haku72

As for gdb, I've only used it once or twice (almost a year ago), and I never really messed with it again. I usually just spend a lot of time sifting through code trying to figure it out. Probably not the most efficient way, huh? =P

There's no substitute for going through your own code by hand, especially after you've been away from it for a while, to check for bugs. gdb will tell you about bugs that manifest themselves, but it won't find bugs that only have adverse effects outside of a testing environment. A good tool for bug searching is valgrind, which will tell you where you've failed to free memory, plus many other useful things.
Kevin Barry

sarum1990 · 11-19-2009, 06:23 PM

Valgrind looks pretty interesting, I haven't heard of it before, but I think I'll take a look at it tonight. I have a program at home that could probably use some touch ups in memory allocation and freeing.

Haku,

To me it looks like you memory allocation is all fine. All of your allocations can be referenced from the returned pointer G, so you shouldn't have any memory leaks in this constructor. Just make sure you free everything you malloced if you ever need to destroy the structure.

Cheers