Resolved Segmentation fault when trying to traverse a linked list

Discussion in 'Mac Programming' started by gravity black, Oct 19, 2011.

  1. gravity black, Oct 19, 2011
    Last edited by a moderator: Oct 20, 2011

    gravity black macrumors newbie

    Joined:
    Oct 18, 2011
    #1
    Hey everyone, this is my first time posting, so hopefully i won't commit some kind of egregious faux pas.

    Anyways, I'm trying to create and read back a simple linked list in C++. So far, I think I've built it and filled it with 10 different arrays of characters of about 22 characters each. (They are simple questions written in english.) My program compiles fine, and it runs, but only to a certain point. When it gets to the following line:


    Code:
    cout << current->info << " "<<endl; //outputs the 'info' component of the 
                                                        //current node
    
    ...it stops and says "Segmentation fault". I'm not sure what it could be, though I'm new at this so it may be obvious. Previous to this line, I have the following lines:

    Code:
    head = buildlist(); //calls a function to build the list, and sets head
                              //equal to the first node. (i think)
    current = head; //sets current  equal to head.
    
    The other, lesser problem that is probably the cause of this is that when I print out the various 'link' values as they're built, they have the following values:

    first = 0x100100080
    first->link = 0x10010090
    first->info = This is statement 1.
    second = 0x10010090
    second->link = 0x1001000a0
    second->info = This is statement 2.
    third = 0x1001000a0
    third->link = 0x1001000b0
    third->info = This is statement 3.
    .
    .
    .
    last = 0x100100110
    last->link = 0
    last->info = This is statement 10.


    ...Now all this seems fine and good, but after this is done and I set 'head' equal to the function, and then ask it to print out 'head', it gives me this:

    head= 0x7fff70464b00
    head->link= 0x7fff704614a0
    head->info = ?핂?

    ...The info here is really very weird, and it's obviously not equivalent to the array of characters "This is statement 1." I feel that this might be because I'm setting the 'head' wrong. I want it to be equal to the first node of the list, but I'm not sure if setting it equal to the function call that builds the entire list is the way to do that.

    The way I have the program written, it's supposed to iterate over each item in the list and print out the info in each. (10 items in all). It [should] do this by first setting 'current = head', and then after each iteration setting 'current = current->link'.

    For some reason, though, it only iterates two complete times, giving me garbled output each time, and then on the third time, it gives me a Segmentation fault instead of printing the info. It looks something like this:

    now, we're inside the final while loop
    current= 0x7fff70464b00
    current->link= 0x7fff704614a0
    current->info= ?핂?

    current= 0x7fff704614a0
    current->link= 0x7fff8295ed7e
    current->info= L?Iz??

    current= 0x7fff8295ed7e
    current->link= 0xe589485500000000
    Segmentation fault

    ... So anyone have any ideas? I apologize if this is too much information, but I wanted to be as thorough as possible without simply posting my code, (it's for a school assignment, and I wanted to keep everything on the "up and up"). That being said, if there's other information anyone needs to make a guess at what's going on, please just let me know.

    Also, I'm running this on a 2008 intel-based Macbook, OS X Snow Leopard (Ver. 10.6.8)
     
  2. jiminaus macrumors 65816

    jiminaus

    Joined:
    Dec 16, 2010
    Location:
    Sydney
    #2
    If you're getting first = 0x100100080 while you're build this list, but head = 0x7fff70464b00 after the returning from buildlist(), then buildlist() doesn't seem to be returning the right pointer. What are you actually returning in buildlist(), ie what is/are the return statment(s) in buildlist().
     
  3. subsonix macrumors 68040

    Joined:
    Feb 2, 2008
    #3
    It's hard to tell without seeing the implementation of the list. But, current->info probably does not point to where you think it does. Are these lines from your list or is it from using the list? You can simplify the list a great deal by making a list class and using private variables, if this is not what you are currently doing.
     
  4. gravity black thread starter macrumors newbie

    Joined:
    Oct 18, 2011
    #4
    You know, that's a good question. I looked and the function definition doesn't have a return statement to speak of, (like the 'return 0' commonly found at the end of main functions, etc.) I inserted

    Code:
    return first;
    
    at the end of the buildlist() function. This immediately did away with the segmentation fault, and output ten items, which was great. They are also are at the right 'locations', so that's good, but the info is either not there or it's still garbled. I've included this output below:

    Code:
    now, we're inside the final while loop
    current= 0x100100080
    current->info= 
    now, we're inside the final while loop
    current= 0x100100090
    current->info= &q?
    now, we're inside the final while loop
    current= 0x1001000a0
    current->info= 
    now, we're inside the final while loop
    current= 0x1001000b0
    current->info= 
    now, we're inside the final while loop
    current= 0x1001000c0
    current->info= ?
    now, we're inside the final while loop
    current= 0x1001000d0
    current->info= 
    now, we're inside the final while loop
    current= 0x1001000e0
    current->info= 
    now, we're inside the final while loop
    current= 0x1001000f0
    current->info= 
    now, we're inside the final while loop
    current= 0x100100100
    current->info= 
    now, we're inside the final while loop
    current= 0x100100110
    current->info= KFp?
    
    ...so I'm not sure if it's just not passing the info right, or what.

    Well, in the previous post, the stuff in the code blocks was from my code, and the other stuff were just print statements that I put in there to help debug it, if that's what you're asking. I guess I could make a class out of it, but I was trying to do it with a struct. I was under the impression it would be harder to implement with a class than with a struct.

    Now that I've eliminated the seg fault, got 10 items returning, and got the nodes pointing to the right places, I can't figure out why the info is not right, when it was there within the function itself.

    [thanks for the fast replies, by the way]
     
  5. subsonix macrumors 68040

    Joined:
    Feb 2, 2008
    #5
    I understand this, but the question was really if the code you posted was internal to your list or from elsewhere like say, main. The implementation of the list will show where you're problem is, but you have not posted that so we are left guessing more or less.

    The point was not that you should not represent you nodes as structs but that you can hide internal details inside a class. That way you don't have to pass internal details around to different functions that operate on the list, instead those internal details are known by the functions by the use of private variables since they will share scope with the class functions.


    That is why it would help if you posted the code.
     
  6. jiminaus macrumors 65816

    jiminaus

    Joined:
    Dec 16, 2010
    Location:
    Sydney
    #6
    How are you setting the info member of each node? Where is the source string comming from? What is the type of the info member, for example, perhaps char* info or char info[23]?
     
  7. gravity black, Oct 19, 2011
    Last edited: Oct 19, 2011

    gravity black thread starter macrumors newbie

    Joined:
    Oct 18, 2011
    #7
    This is how I'm creating the arrays of characters:
    Code:
     char statements[10][25] = {{"This is statement #1."},
                                {"This is statement #2."},
                                {"This is statement #3."},
                                {"This is statement #4."},
                                {"This is statement #5."},
                                {"This is statement #6."},
                                {"This is statement #7."},
                                {"This is statement #8."},
                                {"This is statement #9."},
                                {"This is statement #10."}};
    
    Then I'm setting the info member of each node by saying basically 'newNode->info = statements[num];'. The type of the info member is char* info, as you guessed. I'm sorry to keep you guys guessing, I know how frustrating that is. Our professor is just really strict about posting/ getting your code from anywhere so I'm trying to avoid that. I guess I'm just looking for qualitative help- so I appreciate any help you can provide.
     
  8. gravity black thread starter macrumors newbie

    Joined:
    Oct 18, 2011
    #8
    After answering your last question I noticed that where I declare the info member in the struct definition and where I declare the array in the function, I use two slightly different syntaxes of 'char*' and 'char', respectively. When I try to change them to match one another, I get the following compile error:

    In function ‘nodeType* buildlist()’:
    error: invalid conversion from ‘char*’ to ‘char’

    (that's if I take the '*' away in the struct definition). If I try to add a '*' where I declare the array, I get the following:

    warning: deprecated conversion from string constant to ‘char*’

    Not sure if this sheds any light on it or not, but thought I'd let you know.
     
  9. jiminaus macrumors 65816

    jiminaus

    Joined:
    Dec 16, 2010
    Location:
    Sydney
    #9
    Is statement a local variable of buildlist()?
     
  10. gravity black thread starter macrumors newbie

    Joined:
    Oct 18, 2011
    #10
    Yes, it would seem. I'm starting to think that's part of the problem- that it can't get the array out of the function within the 'info' member. I just don't understand because I thought it was written to the linked list. I didn't know I also had to pass out statements[][].
     
  11. jiminaus macrumors 65816

    jiminaus

    Joined:
    Dec 16, 2010
    Location:
    Sydney
    #11
    What happens to local variables when you leave a function?

    Have you learnt about the C string functions or the C++ std::string class?
     
  12. gravity black thread starter macrumors newbie

    Joined:
    Oct 18, 2011
    #12
    Lol, I must've forgot to mention, but I'm very new to this. I'm not sure if the question was rhetorical or not but I guess the local variables are erased- I don't know. Like I said, I thought that they would be copied to the list, or something.

    As for the string class, we're supposed to be passing in the statements as arrays of characters, not strings- that's why I'm doing it like that.

    Is there some way to declare the character array differently so that I can return it at the end of the function? (I'm guessing that's what I need to do). When I try to return it as the code is now, I get the following error:


    In function ‘nodeType* buildListForward()’:
    error: cannot convert ‘char (*)[25]’ to ‘nodeType*’ in return

    I have no idea what this means- though perhaps some sleep will help.
     
  13. chown33 macrumors 604

    Joined:
    Aug 9, 2009
    #13
    It's not going to shed any light unless you post the code that defines the struct. The struct that defines a node is fundamental. You haven't shown any code for it yet.

    Second, post the code that causes the error message you posted. We can't debug code descriptions. Why would you make us guess what the actual code is?
     
  14. jiminaus, Oct 19, 2011
    Last edited: Oct 19, 2011

    jiminaus macrumors 65816

    jiminaus

    Joined:
    Dec 16, 2010
    Location:
    Sydney
    #14
    It wasn't rhetorical. I wanted you to think about the lifetime of your variables.

    The statement current->info = statements[0] doesn't copy the string at statements[0]. It assigns the address of statements[0] to current->info.

    If you assign the address of a local variable (or part there of, as in your case) and then return the address from a function, the address is now going to point to memory that's been "erased" (actually it's been deallocated/freed). It won't be a valid address anymore.

    That's why inside your buildlist function, the info members pointed to valid strings. But outside of your buildlist function, the info members no longer point to valid string.


    Move statements from being within buildlist to outside of and just before buildlist. This will change it to a global variable and it will exist for the lifetime of your program. Then the addresses being stored in your node's info member will be valid after the call to buildlist returns.

    This is a hack, it's ugly, I hate, it's bad; but it's probably the quickest way to move you forward.


    A better solution would be to change info in the node struct from being char* info to char info[25]. Then use memcpy to copy the string from the statements array into a node's info array.
     
  15. gravity black, Oct 19, 2011
    Last edited by a moderator: Oct 20, 2011

    gravity black thread starter macrumors newbie

    Joined:
    Oct 18, 2011
    #15
    I'm sorry, I know that's frustrating, but as I mentioned earlier, I'm trying to avoid posting the entirety of my code because of ethics rules my professor has outlined, (which I don't necessarily agree with). That's why I've only shown my code in a piecemeal fashion.

    Thanks! That did exactly what I needed. I appreciate your thinking, and yes, I agree that it's not pretty but it gets the job done, and I can go back and refine it further down the road.

    I like this, and I'll probably do it this way in a bit. I've got a long way to go on my program, but the problem that I opened the thread for has been solved, and I can't thank you enough for that. Cheers.
     
  16. chown33 macrumors 604

    Joined:
    Aug 9, 2009
    #16
    Then you need to user your school's resources. Like teaching assistants, lab assistants, or whoever you're supposed to use for help when you can't figure it out yourself.

    Personally, I fail to see how it would violate ethics to post:
    Code:
    struct node
    {
      struct node * next;
      char * whatever;
    };
    
    Or whatever your actual code is. If you don't understand it, then you don't understand it, and you need help. Not showing a struct definition is making it impossible to diagnose the problem. Therefore, you need to use some resource that allows you to show your struct definition.

    BTW, that struct definition is quite different from:
    Code:
    struct node
    {
      struct node * next;
      char whatever[25];
    };
    It would be a good idea if you understood why those are different. If you can't figure it out yourself, then you really need to ask someone who can explain the code you wrote.
     
  17. gravity black thread starter macrumors newbie

    Joined:
    Oct 18, 2011
    #17
    Again, I apologize; however the problem has been solved. I can't see how you can say it's impossible to diagnose the problem when someone else on the thread just did it... like literally right before you wrote that.
     
  18. mark_wilkins macrumors member

    Joined:
    Aug 26, 2003
    #18
    hey gravity_black:

    The piece that you're missing, which I think other people have touched on, is a strong understanding of how variables work in C and C++. Here are some of the basic ideas:

    When your program launches, before your code ever gets to run, there's a small chunk of code that the compiler adds that sets up your program's environment. Part of this is setting up two types of memory that your program can use, called the "stack" and the "heap."

    When you add data to the stack, it's added to the end. Think of the stack as a large array of data that can get longer and longer as new data is added. Data on the stack can be thrown away, but only in reverse order that it was allocated. There are usually limitations in size on the stack, for various reasons related to the efficiency of the machine operations used to read data out of it.

    The heap consists of data that you allocate yourself using the malloc function or one of a number of similar functions, or C++'s "new" keyword. Basically, anything large goes here because the only practical size limitations are your RAM and swap space.

    In a C or C++ program, local variables in functions are what the stack contains. Global variables, I believe, usually get collected together at the very top of the stack so that they never go away. When you define a pointer as a local variable, only the space for that memory address gets put on the stack, not the space for what it points to. And, when you leave the function, the little chunk of space that holds that memory address gets thrown away, so you'd better have stored its contents somewhere else (in a return value, somewhere in allocated memory in the heap, or a global variable) if you ever want to get back to the contents again.

    Now, what your program was doing by defining an array variable and assigning a literal set of values to it was putting all those strings directly on the stack. It'll work fine while you're within that function, but once your function exits, all that data (local to the function) gets thrown away. You could define that array variable as global, but that would prevent you from ever replacing any of those strings with anything longer, because if you tried you'd be stepping on other data on the stack. Assigning literal values like that is something you only would want to do for data that will never ever change in size.

    It is critical to get comfortable with what types of data definitions get allocated in the stack and which get allocated in the heap, because only the heap allocations will persist beyond your function's lifespan. Your goal should normally be to store only temporary information in the stack and the bulk of your program's data in the heap. C++ aids you with this because instantiating a class with "new <class>" automatically puts that object's data on the heap for you.
     

Share This Page