Segmentation fault...

ok i have this astar search code which is pretty big...in some cases i get a segmentation fault and in others everything runs just fine...the weird thing is that the segmentation fault only occurs if i run this using g++ on unix...borland C++ never gave me a segmentation fault...

i'll attach the .cpp file here for borland C++ but if noone looks at it, can you tell me which operations would likely cause this segmentation fault...since the code is so big i don't really know where to look for the problem...and this is worsened by the fact that everything ran just fine in borland c++...except i used to get a warning that i'm comparing signed and unsigned variables someplace...but i don't think tat's related to this...

anyway here are some areas:
- i use a map to store nodes...
- i use lots of strings in the code e.g. in the node class to check for node names...
- i have a vector of strings in the code as well which i define as:
vector<string> CityConnections...
- i don't use any sort of array in the code...

Regards,

Farooq

ok after careful consideration i realize that the segmentation fault is occuring because of the following code where i use a vector of strings which i have delcared in the Node class...I delcare it like this: vector <string> CityConnections
Also, worthy of note is that i'm using a map of nodes in the code below...could anyone detect how i'm accessing memory i'm not supposed to in this vector?

Code:

---

map <string, Node *>::iterator i = CityNode.find(thisNode->CityName);
                        for(int j=0; j < ((i->second)->CityConnections).size(); j++)
                        {
                          //IS THE SUCCESSOR OF thisNode THE PARENT OF thidNode?

                          if (thisNode == startNode)
                          {
                              map <string, Node *>::iterator k = CityNode.find((i->second)->CityConnections[j]);  //ITERATOR POINTING TO THIS SUCCESSOR
                              newNode = new Node;

                              newNode -> CityName = (k->second)-> CityName;
                              newNode -> x = (k->second)-> x;
                              newNode -> y = (k->second)-> y;
                              newNode -> type = (k->second)-> type;

                              SUCCESSORS.push_back( newNode );
                          }
                          else if (!((i->second)->CityConnections[j] == thisNode->parent->CityName) )
                          {
                              map <string, Node *>::iterator k = CityNode.find((i->second)->CityConnections[j]);  //ITERATOR POINTING TO THIS SUCCESSOR
                              newNode = new Node;

                              newNode -> CityName = (k->second)-> CityName;
                              newNode -> x = (k->second)-> x;
                              newNode -> y = (k->second)-> y;
                              newNode -> type = (k->second)-> type;

                              SUCCESSORS.push_back( newNode );
                          }

                        }

---

thanks!

Farooq

Segmentation faults usually happen when you try to access an array/vector/etc out of bounds, like if the vector size is 10 and you access spot 11. Some compilers won't complain unless a problem occurs, others will complain every time.

Nevermind, you asked what usually caused it but then I missed that your second post says you already know about accessing invalid memory. Sorry to tell you what you already know :)

Are all of your find functions guaranteed to find something? If not, then I assume they would point to CityNode.end() instead of an element in CityNode if nothing is found (been awhile since I've worked with maps so I'm not positive) causing problems when you try to access data members.

Using a debugger is the best way to find out what's going wrong.. unfortunately I'm not familiar enough with gdb to tell you how it would help.

Remember when I said you shouldn't use the array subcript operator [] with your map because it could crash if the name is not found? Well, using find will also crash if the name is not found if you don't check the result before using it. It is possible (not necessarily likely) that your segmentation fault is coming because a string is not found.

Try adding a check for

(k != CityNode.end())

after the call to find to make sure that you aren't using an invalid iterator after a failed find.

ya u're right...it is guaranteed that the first iterator i will point to some CityNode...but it is not guaranteed whether k wil point to something because it is possible that i have a node for which the vector of strings CityConnections is empty (means that node is not connected to anything)...

i think this could be the error...i'll try putting the check in and see if it works...

Thanks again guys...

Farooq

ok if i comment the above code i don't get any segmentation fault...but when i uncomment it and add the condition before the if that check whether k != CityNode.end()...i still get the segmentation fault...anyone have a good idea of how to check if CityConnections[j] has something...

there's another weird thing happening...if i run my code on Borland C++ where i don't get any segmentation faults...i get a route to the goal as the answer...the weird thing is that if i weigh down the program a little bit...e.g by putting a cout << "abc"; somewhere in its execution...my answer is completely different? through the same algorithm!

i think this whole mess up is because of memory problems...the segmentation fault is probably the same reason as you guys quotes...any ideas around this...

i have to submit this on monday!

Regards,

Farooq

ok one more thing guys...i commented out code and eventually the error appears because of this line:

Code:

---

SUCCESSORS.push_back(newNode);

---

SUCCESSORS is a vector of Nodes, defined like:

Code:

---

vector <Node *> SUCCESSORS;

---

the segmentation fault occurs if i have this statement twice like in the code in my earlier post...if i remove it from either one of the if() conditions there's no segmentation error...what do u think?

Regards,

Farooq

ok after painstaking debugging (without gnu!)...i realize the segmentation fault is occuring because of this line:

Code:

---

map <string, Node *>::iterator k = CityNode.find((i->second)->CityConnections[j]);  //ITERATOR POINTING TO THIS SUCCESSOR

---

so u're right jlou...but the weird thing is that even with the condition to not get into this part as you said before is not helping out...

thanks.

Farooq

ok i'm officially giving up now...here are some facts if anyone out there can come up with some suggestion as to what is going wrong...

1) CityNode will have a listing of all Node names and the iterator pointing to it is 'guaranteed' to find a name match.

2) CityConnections is a vector of strings inside the Node class which stores which other nodes a particular node is connected to...if you use an iterator to this, a match between an element in CityConnections and a Node in CityNode is 'guaranteed' to happen...

because of these two facts...even when i place checks in case there is no match, i still get a segmentation fault...

3) the segmentation fault does not come instantaneously on running...it occurs after the looping is almost over...meaning right before the end of the search...i iterated to check this...

4) it never occurs whichever inputfile i use when i use the Borland C++ compiler...only problem is that I have to submit the code which can be compiled on unix using GNC...

anyway thanks a lot guys...

Regards,

Farooq

is it possible that this is because of reading from text files (.txt) vs. reading from files with the extension (.in)...

i'm saying this because i can't find the source of the segmentation fault and my .txt case files all work fine...however, only some of the .in files work for me...the rest end up with segmentation faults...

plz look at my previous couple of posts to sort out what could be a possible error...i think it might be too late for this assignment but i have another one coming up and i want to be prepared for that...

thanks!

Farooq

The file extension makes no difference in C++ standard file i/o. The only difference is whether you're writing ASCII files or binary files. In this case they're both ASCII.

Sorry I can't be of more help Farooq, but you will have to just keep plugging away at debugging this. If you've narrowed it down to a certain piece of code, then separate that code into parts. Use temporary variables to check each return value to make sure it's valid, and if you are using debug output statements (like a cout after each line) then add one for each thing you do.

For example:

Code:

---

map <string, Node *>::iterator i = CityNode.find(thisNode->CityName);
if (i == CityNode.end())
{
    std::cout << "Unable to find thisNode->CityNode" << std::endl;
    return;
}

if (i->second == 0)
{
    std::cout << "i->second is Null!" << std::endl;
    return;
}

std::vector<std::string>::iterator j = (i->second)->CityConnections.begin();
for(; j != (i->second)->CityConnections.end(); ++j)
{
    std::string currentConnection = *j;

    //IS THE SUCCESSOR OF thisNode THE PARENT OF thidNode?

    if (thisNode == startNode)
    {
        //ITERATOR POINTING TO THIS SUCCESSOR
        map <string, Node *>::iterator k = CityNode.find(currentConnection);

        if (k == CityNode.end())
        {
            std::cout << "unable to find in CityNode: ";
            std::cout << currentConnection << std::endl;
            return;
        }

        if (k->second == 0)
        {
            std::cout << "k->second is Null!" << std::endl;
            return;
        }

        newNode = new Node;

        newNode -> CityName = (k->second)-> CityName;
        newNode -> x = (k->second)-> x;
        newNode -> y = (k->second)-> y;
        newNode -> type = (k->second)-> type;

        SUCCESSORS.push_back( newNode );
    }
    else if (!(currentConnection == thisNode->parent->CityName) )
    {
        //ITERATOR POINTING TO THIS SUCCESSOR
        map <string, Node *>::iterator k = CityNode.find(currentConnection);

        if (k == CityNode.end())
        {
            std::cout << "unable to find in CityNode: ";
            std::cout << currentConnection << std::endl;
            return;
        }

        if (k->second == 0)
        {
            std::cout << "k->second is Null!" << std::endl;
            return;
        }

        newNode = new Node;

        newNode -> CityName = (k->second)-> CityName;
        newNode -> x = (k->second)-> x;
        newNode -> y = (k->second)-> y;
        newNode -> type = (k->second)-> type;

        SUCCESSORS.push_back( newNode );
    }
}

---

First, notice how I used an iterator to iterate through the vector. It is different than array syntax, but safer, since using array syntax lets you attempt to access data outside the bounds of the array with no way to check it.

Secondly, noticed how I tried to check each value before I used it the next time. This is important because it will help you narrow down the problem.

Good luck!

hi Jlou...thanks so much for the code...unfortunately the output is exactly the same as in the code that i had given...i've used several methods and all to pinpoint that the segmentation fault happens when i use the map find function to define my iterator i...the problem is that the program works fine for most inputfiles but not for others...

even if i don't have all the checks in my code it won't really matter...because the files i use and the code i have to define my MAP ensure that there can be no error...i might sound a but optimistic when i say this...but this is for an assignment and quite a few things were already specified in it...so it's more like the best case scenario and we aren't required to do much error handling...

in any case...that segmentation fault is coming from someplace within the code...i guess i'll leave it at just that...i wish testing was done on the Borland C++ compiler...

anyway thanks a zillion for ur help...

Best Regards,

Farooq