Access Violation / Seg Fault

Hello all,

I'm currently coding a simulation for a theoretical game called Angels and Mortals. As a simulation, it plays itself out without user input, and depending on different starting conditions, the results will be different.

So far, my backend is nearly complete, and will eventually feed into an OpenGL frontend where I'll be able to see the "game board" to see what's going on. Right now, output is to the console :P

The backend is what's causing me the problem so far. My game "pieces" are coded as class objects, and represented in a doubly-linked list. The problem is, I seem to have developed an access violation, but I have no idea why - this exact line was working previously and didn't throw up any seg faults as it does now. Essentially - I have no idea what's going wrong, and I'm pretty confused as to how to fix this.

Here's the line in question that my debugger ( CodeBlocks ) tells me is causing the problem :

Code:

angels = angels->next;

To put that into context, here's the relevant class :

Code:

class Angel { private: int xcoord, ycoord; public: void create(int, int); void move(); void setcoords(int, int); void editcoords(int, int); int readxc(); int readyc(); Angel *next; Angel *prev; ~Angel(); };

And the object angels is just an object of class Angel.

To aid in further contexting, here's the loop in which I supposedly get a seg fault :

Code:

if(mortals->next != NULL) // ... check that there are actually mortals in play. { while(angels->next != NULL) { angels->move(); if(angels->readxc() == 0) angels->editcoords(1,0); // fix coord == 0 if(angels->readyc() == 0) angels->editcoords(0,1); // fix coord == 0 if(angels->readxc() > BOARD_X) angels->editcoords(-1,0); if(angels->readyc() > BOARD_Y) angels->editcoords(0,-1); gotoxy(angels->readxc(), angels->readyc()); // go to new coords cout << "O"; angels = angels->next; // next node } }

For those who are either very brave or very kind, or have too much time on their hands, here's a pastebin of the entire application :

Main .cpp - http://pastebin.com/m58bfdeb0 - culprit on line 184
Angel.h - http://pastebin.com/m166973f4
Mortal.h - http://pastebin.com/m50f40c64
Settings.h - http://pastebin.com/m768f6067

My coding environment is Dev-CPP on Windows Vista.

Thanks for any help,
Quentin

You shouldn't manage the list yourself unless you've proven you need to do that. It would be far better and more robust to use e.g. std::list.

Using std::list isn't going to teach me to build custom lists, or how to handle seg faults :P

A seg fault is the equivilent of driving up on the curb when you are learning to drive. You don't practice how to drive on the curb more gracefully. You gracefully avoid driving on the curb.

I know a seg fault isn't something I want to do. Yet, I have one, and need to find it and fix it. I'll most likely have others in the future at some point, so being able to do so is essential. Such answers, master5001, aren't helping in the slightest, I'm sorry to say.

So yes, the curb is a problem. But I'm on the curb - teach me how to get off it.

How do we solve a seg fault?
Well, there are generally several ways.
First, you can try: take the address of the pointer. Use a proper debugger (such as VC), and add a breakpoint when the data in the memory area where the pointer resides changes. It should break when created, when assigned and (IMPORTANT!) when DELETED. Go from there and try to figure WHY it was deleted when it shouldn't.

This is probably the biggest type of seg faults in a list.
Another is data corruption. You can tell them apart if you have a good debugger (like VC), since it might fill deleted data with a known pattern (0xFEFEFEFE for VC). If it isn't deleted, then it's probably corrupted or something else.

And if dwks's hypothesis is correct - you can know by ALWAYS setting ALL pointers to NULL before ANY use and ANY assignment.

Looking at your code:

Code:

if(mortals->next != NULL) // ... check that there are actually mortals in play. { while(angels->next != NULL) { angels->move(); if(angels->readxc() == 0) angels->editcoords(1,0); // fix coord == 0 if(angels->readyc() == 0) angels->editcoords(0,1); // fix coord == 0 if(angels->readxc() > BOARD_X) angels->editcoords(-1,0); if(angels->readyc() > BOARD_Y) angels->editcoords(0,-1); gotoxy(angels->readxc(), angels->readyc()); // go to new coords cout << "O"; angels = angels->next; // next node } }

What if mortals or angels is NULL to begin with? Of course, that shouldn't cause it to segfault at the "next node" line. But it's still something to consider.

Anyway . . . I think this code is a little mixed-up.

Code:

for(int i = 0; i < NUMBER_MORTALS; i++) { mortals->create(rand() % PIECE_SPREAD + 1, rand() % PIECE_SPREAD + 1); // create at a random position mortals->next = new Mortal; // Current mortal's next pointer now points to a new Mortal mortals->next->prev = mortals; // The new node's previous pointer points to the current node // DEBUG /* cout << "Mortal created at " << mortals->readxc() << ", " << mortals->readyc() << ".\n"; // DEBUG LINE Sleep(100); // DEBUG LINE */ mortals = mortals->next; // Move to the newly-created Mortal node Sleep(1); }

The call to mortals->create() initializes the mortals object -- the already-existing mortals object, mind. Then you go and add a new object, which is not initialized -- and guess what? You never set its next pointer, so it's probably set to something strange.

I think you meant to call mortals->next->create().

On a side note, create() would work very well as a constructor.

[edit] Okay, I guess me finding (possible?) segfaults in your code isn't going to help you find them, either. :)

How did I find it? I figured that angels->next must be invalid. So the first place to check was where angels->next was initialized. That led me to the block of code I posted.

I guess the rest was being suspicious about whether angels->next->next really was initialized. :)

[Assuming my analysis is right, of course, and that it actually isn't.]
[/edit]

I need more code than this to give you a better explanation of what is going wrong. Or at the very least I need to confirm my hypothesis. You are probably not correctly setting next, or perhaps you are not correctly allocating the initial node in your list.

[edit]Sorry, I just noticed the links... I am a bit sleep deprived today.[/edit]

Actually, the problem is that when you create angels (and mortals, you just don't get far enough to encounter that problem), the next-pointer of the NEW object (after you do angels = angels->next at the end of the loop is not set to NULL, so you never know that you reach the end of the list.

--
Mats

Following up on master5001's second thought:

Code:

Angel *angelroot; // Root note Angel *angels; // Conductor node angelroot = new Angel; // Pointer *angelroot points to an Angel object angelroot->next = NULL; // The next pointer is NULL. angelroot->prev = NULL; // Set the conductor pointer to the root of the list mortals = mortalroot; angels = angelroot;

It looks okay, although that sort of code should really be in the constructor for Angel.

I was going to mention all of those public variables you have in your classes -- that's generally not a good idea. The class should handle its internal variables itself, most of the time.

Make the constructor set all pointers to NULL, as well. Good practice! Less bugs and easier to track down problems!

And whilst we are on the bandwagon of "telling you what to improve":
Make a list-class, then either include that inside your Angel/Mortal classes, or inherit from it.

Make the list class have all the necessary functions to add, remove and find objects within the class. That is a MUCH better way to practice than to write the same bit of code several times over.

Also, when learning new things, it's a good idea to try on ONE thing [e.g. make sure you can create a bunch of angels and find them back again, before you try making mortals - or the other way around].

--
Mats

Thanks to everyone for their help so far !

matsp was correct, it was a non-NULL pointer error. I've now added

Code:

next = NULL; prev = NULL;

to my constructors, and that's solved the problem - only to reveal a further segfault, a little further down the line.

Line is now 292, giving the same error. I'm trying to get my head around which part I messed up this time :P

Code:

else // If it dies this turn, create link between nodes and destroy current node { mortals->next->prev = mortals->prev; // The next node's previous pointer points to the previous node // FOLLOWING LINE CAUSES SEG FAULT mortals->prev->next = mortals->next; // The previous node's next pointer points to the next node mortals->~Mortal(); // Call Destructor deaths++; }

If anyone sees something drastically obvious, please feel free to point it out. If not, I might work it out myself in a few :)

[EDIT]
Would it be something to do with mortals->next not having a value ( non-NULL, again ) ? *Checks*
[/EDIT]

Code:

mortals->prev->next = mortals->next; // The previous node's next pointer points to the next node mortals->~Mortal(); // Call Destructor

1. Don't ever call the destructor manually! You probably want to make a copy of mortals->next, and then delete mortals [or delete a copy of mortals after you do mortals = mortals->next - whichever you prefer].

2. You are trying to set the next pointer of a prev-pointer that is NULL. Check for mortals->prev == NULL and skip this step [you probably should move mortalsroot instead in that case].

--
Mats

Code:

mortals->~Mortal(); // Call Destructor

Never, ever call a destructor directly. Seriously. If you dynamically allocated memory (which you did), just delete it.

Code:

delete mortals;

[edit] And then your mortals variable will be invalid, but matsp has already pointed that out. [/edit]

Check for NULL before accessing any pointer ever, Korhedron. Your lead node should be seg faulting.

Quote:

Originally Posted by dwks

Never, ever call a destructor directly.

There is only but one precious exception to this rule that I have encountered on a regular basis. Using the placement new operator. If you don't know what that even is, then you should not be toying with manual destructors.

Thanks for all the help ! I've solved that last problem by side-stepping it - checking for NULL, and if so, just skipping the action - which isn't technically correct in the game, but I'll fix that later. Right now, as the debugger keeps pointing out segfaults as I continue, I'm more worried about the fact that the program is starting to look like Swiss cheese. I clearly haven't catered for the exception of a node being the leading or trailing node, so I need a way to cater for it now.

You'll probably recommend std::list again, but knowing these lists will probably change at some point - is there anything else you'd suggest ? Should I write a list class and inherit my Angel and Mortal classes from that ?

Thanks again for all the great help, I'm learning a lot,
Q

Quote:

There is only but one precious exception to this rule that I have encountered on a regular basis. Using the placement new operator. If you don't know what that even is, then you should not be toying with manual destructors.

Yes, it's true. http://yosefk.com/c++fqa/dtor.html#fqa-11.9
But I think we can safely assume that the OP doesn't need to know that at the moment. :)

[edit]

Quote:

Should I write a list class and inherit my Angel and Mortal classes from that ?

That sounds like a plausible idea. However, it would make more sense to create a list class that can handle Angels and Mortals. Are you familiar with templates? [/edit]

Quote:

Originally Posted by master5001

There is only but one precious exception to this rule that I have encountered on a regular basis. Using the placement new operator. If you don't know what that even is, then you should not be toying with manual destructors.

That is correct. Placement new is not a common operation in normal programs, so I'd say that it's fair to say "Never call the destructor", without adding the exception case.

--
Mats

dwks, I'm not familiar with templates, but I wasn't familiar with linked lists until this project, nor did I understand the importance of pointers. This is the largest C++ app I've written, and I haven't actually written in a few year prior to the last few weeks. So, I'm learning everything as I go.

Would you suggest templates then ? I've looked into inheritance, polymorphism and the like, and understand the concepts, so could probably go about writing a class to manage my lists. It probably wouldn't be much good, but it would at least be less messy :P

This thread is suffering from too many programmers spoiling the top-down reading order. Some of us should stop posting, or go out and design a bulletin board that takes into account when users started typing their posts. Or automatically refreshes the page (in the background, without disturbing your typing) every ten or thirty seconds. Or something. :)

[edit] See what I mean? Okay.

Quote:

dwks, I'm not familiar with templates, but I wasn't familiar with linked lists until this project, nor did I understand the importance of pointers. This is the largest C++ app I've written, and I haven't actually written in a few year prior to the last few weeks. So, I'm learning everything as I go.

Would you suggest templates then ? I've looked into inheritance, polymorphism and the like, and understand the concepts, so could probably go about writing a class to manage my lists. It probably wouldn't be much good, but it would at least be less messy :P

Maybe you should just make use of what you already know -- templates would suit the problem better, but hey.

Just call the inherited classes AngelList and MortalList or something like that, not just "Angel". It's a collection of Angels. ;) [/edit]

Quote:

Originally Posted by Korhedron

dwks, I'm not familiar with templates, but I wasn't familiar with linked lists until this project, nor did I understand the importance of pointers. This is the largest C++ app I've written, and I haven't actually written in a few year prior to the last few weeks. So, I'm learning everything as I go.

Would you suggest templates then ? I've looked into inheritance, polymorphism and the like, and understand the concepts, so could probably go about writing a class to manage my lists. It probably wouldn't be much good, but it would at least be less messy :P

I personally would avoid templates for now - yes, you can get very powerful programs in a few lines with templates, but it's also a more advanced concept.

--
Mats

I do agree. I need to get more in the habit of quoting the person I am replying to often because I notice that I frequently slip in between a post I am replying to and another person who is replying to the same thing, but then it looks as if they are questioning me. Or it looks like duplicate information. Or when I end up having someone slip in between me and my intended person I am responding to, I look like I am arguing.

Korhedron, the first person to reply to you mentioned a template that does the linked list functions for you. I highly recommend reading up on pointers a bit before tackling templates, however. If you are having difficulty with pointers, you should understand them before going on to things that are too advanced since they are a staple of the language.

Just to return to this lists class :

All of my problems are arising from me accessing the previous or next pointer on a node that doesn't have a previous or next node. So, technically, all I need is to :

1. Make sure all pointers are NULL when declared
2. Check for NULL before doing any operation that uses these pointers.

I don't see how writing a list object will help. It'll remove about four lines of code in total ( the stuff duplicated in Angel and Mortal classes ), but I'm struggling to see that I can include code to manage my pointers inside the object itself. The objects are what makes the list, and the operations on pointers are done "between objects", not from inside an object... In this way, I'm very confused.

There are TWO advantages of doing a list class:
1. You separate the list handling from your other code - so you can work on making the list class work correctly separately from making other code work correctly [you have a list component that is "known good", so you don't need to worry about it].

2. It teaches you how to use inheritance to achieve more complex stuff. This is of course a completely non-technical reason - but an equally good one when you are learning. [And if the purpose here wasn't to learn, then we'd be back at recommendin std::list].

--
Mats

Mats, thanks again. Though, I'm still struggling to imagine placing the list management code INSIDE the objects themselves. I can put in my next and prev pointers, but the code from going from one node to the other, and the code for deleting a node - that can't fit inside the actual object, so that code won't be a "known good", it'll just be exactly the same as I currently have.

Or am I entirely deluded ? :P

Quote:

Originally Posted by Korhedron

Just to return to this lists class :

All of my problems are arising from me accessing the previous or next pointer on a node that doesn't have a previous or next node. So, technically, all I need is to :

1. Make sure all pointers are NULL when declared
2. Check for NULL before doing any operation that uses these pointers.

Yeah, pretty much. Plus never calling destructors, but that's probably not something you'll do once you know you shouldn't.

Quote:

I don't see how writing a list object will help. It'll remove about four lines of code in total ( the stuff duplicated in Angel and Mortal classes ), but I'm struggling to see that I can include code to manage my pointers inside the object itself. The objects are what makes the list, and the operations on pointers are done "between objects", not from inside an object... In this way, I'm very confused.

Some operations, like deleting a list item, you simply can't really do from "inside" one of the list objects. You do sort of need a controller class or function or whatever.

But I think you're right, a list object wouldn't help much in this case -- because it's a linked list. You can't really have a AngelList::delete() method for linked lists.

Deleting objects is the hard part, I think. You have to keep in mind the fact that the root object could change. (So maybe returning a new root from the delete() function or whatever would be a good idea.) The list could become completely empty.

One mistake I consistently made when I was creating my first linked lists, something that you're doing too, was assume that the linked list always had at least one object. It just confuses everything. Write your code carefully, so that the root object can be NULL.

[edit] Beaten again -- by two posts! What is it with this thread? :p

Quote:

but the code from going from one node to the other

That's easy -- just call traverse() or whatever in the next node.

Quote:

and the code for deleting a node - that can't fit inside the actual object

Yeah, that's a bit tougher. It would probably be easier to have an AngelList to do that . . . .
[/edit]

Something like this (actually, the Angel and Mortal are nodes, not lists - because the list is a separate thing.

Code:

class Node { public: Node *next; Node *prev; Node() : next(0), prev(0) {}; }; class List { private: Node *first; Node *last; public: List() : first(0), last(0); void Insert(Node &); void Remove(Node &); }; class Angel : public Node { ... your angel definition goes here ... }; class Mortal : public Node { ... } List AngelList; List MortalList;

--
Mats

Also, doing this gives you a natural progression to learning templates, because the problems you'll encounter working with this code are the main motivation behind templates.

I just wanted to mention that I like the idea of the debug info being output to a file but
with that I was getting nothing until I put some endl 's in there to flush it to file before the segfaults.
Now things like this show up and are very helpful:

Code:

fout << "12 " << "mortals->next->next= " << mortals->next->next << endl;

interesting thread , thanks

FWIW: endl is equivalent to printing a newline and then calling fout.flush(). So if for some reason you want to flush the output without printing a newline, well, now you know how. :)