Thread: A seg fault. Gotta love those.

So, I'm having issues with a certain seg fault. I don't really understand what's causing it.
I can perform the following operations with curBall, which is class Ball* type.

Code:

curBall->val
curBall != NULL

It seems though, that when I attempt to perform the following operations that it segfaults.

Code:

curBall->high != NULL
curBall->high->high != NULL

These occur when curBall != NULL is true, so I don't see why these would cause seg faults (or, at least the first of the two).

Part of the problem is that this is a class-assigned TopCoder problem, so I'm not sure what kind of debugging tools I have at my disposal...

The class definition is included in the full code, which is at the end of this post.
I have what seems to be the trouble spot underlined. It's near the end of the whole file.

Code:

#include <map>
#include <vector>
#include <cmath>
#include <iostream>
using namespace std;


class Ball
{
	public:
		int val;
		Ball* low;
		Ball* high;
		Ball() : val(0), low(NULL), high(NULL) { }
};


class OneDimensionalBalls
{
	public:
	long long countValidGuesses(vector <int> firstPicture, vector <int> secondPicture);
	long long cvg(int v);
	map <int, Ball*> FP;
	map <int, Ball*> SP;
};


long long OneDimensionalBalls::countValidGuesses(vector <int> firstPicture, vector <int> secondPicture)
{
	long long rv = 0; // Number of valid guesses.
	map <int, int> v; // Map of the velocities to be considered, to prevent looking at same velocities twice. Index is the velocity, value is also the velocity.
	map <int, int>::iterator it;
	int velocity; // Current velocity being considered.
	int i; // Loop control, iteration, etc.
	Ball* curBall;
	
	
	// Passing the picture data to class variables, so other functions can access and organize.
	for(i=0; i < firstPicture.size(); i++)
	{
		curBall = new Ball;
		curBall->val = firstPicture[i];
		curBall->high = NULL;
		curBall->low = NULL;
		FP[curBall->val] = curBall;
	}
	
	for(i=0; i < secondPicture.size(); i++)
	{
		curBall = new Ball;
		curBall->val = secondPicture[i];
		curBall->high = NULL;
		curBall->low = NULL;
		SP[curBall->val] = curBall;
	}
	
	// Get the velocities to be examined
	for(i=0; i < secondPicture.size(); i++)
	{
		// Find a velocity, get its absolute value, and add it to the list to be examined.
		velocity = firstPicture[0] - secondPicture[i];
		velocity = abs(velocity);
		if(velocity != 0)
			v[velocity] = velocity;
	}

	
	// Get the number of guesses for all velocities
	for(it = v.begin(); it != v.end(); it++)
		rv += cvg(it->second);
	
	return rv;
}


long long OneDimensionalBalls::cvg(int v)
{	
	long long rv = 1; // Number of valid guesses for this velocity. Assumed to be 1 for math simplicity.
	int i = 0; // Used to count how many consecutive balls in FP have two associated balls in SP.
	map <int, Ball*>::iterator fit; // Used to locate specified balls in the first picture.
	map <int, Ball*>::iterator sit; // Used to locate specified balls in the second picture.
	Ball* curBall; // Ball currently being examined and/or tampered with.
			
	// Iterate through the first picture to find potential pairs.
	for(fit = FP.begin(); fit != FP.end(); fit++)
	{
		// Find the low in the second picture that corresponds to the velocity.
		sit = SP.find(fit->second->val - v);
		
		// If a match wasn't found, set the low to NULL.
		if(sit == SP.end())
		{
			fit->second->low = NULL;
		}
		else
		{
			// Otherwise, connect the two.
			fit->second->low = sit->second;
			sit->second->high = fit->second;
		}
		
		// Find the high in the second picture that corresponds to the velocity.
		sit = SP.find(fit->second->val + v);
		
		// If a match wasn't found, set the high to NULL.
		if(sit == SP.end())
		{
			fit->second->high = NULL;
		}
		else
		{
			// Otherwise, connect the two.
			fit->second->high = sit->second;
			sit->second->low = fit->second;
		}
	}
		
	// Check to be sure all values in FP have at least one value in SP they match.
	for(fit = FP.begin(); fit != FP.end(); fit++)
	{
		curBall = fit->second;
		
		// If the current ball has nothing it's linked to, there is no valid guess.
		if(curBall->low == NULL && curBall->high == NULL)
		{
			return 0;
		}
		
		// If the current ball has no lower ball, but has a higher ball.
		if(curBall->low == NULL && curBall->high != NULL)
		{
			// Remove all connections to curBall->high. This ball can only be linked to curBall.
			if(curBall->high->high != NULL)
			{
				curBall->high->high->low = NULL;
				curBall->high->high = NULL;
			}
			curBall->high->low = NULL;
			curBall->high = NULL;		
		}
		// If the current ball has a lower ball, but no higher ball.
		else if(curBall->low != NULL && curBall->high == NULL)
		{
		
			// Then traverse backwards one ball at a time with curBall through all linked balls, and destroy all links traversed.
			while(curBall->low != NULL)
			{
				curBall = curBall->low;
				curBall->high->low = NULL;
				curBall->high = NULL;
			}
		}
	}
	
	// At this point, all balls in FP that are still linked should have a high and low assigned to them.
	for(fit = FP.begin(); fit != FP.end(); fit++)
	{
		// Grab the current ball.
		curBall = fit->second;
		i = 1;

                if(fit->second->high == NULL && fit->second->low == NULL)
                {
                        continue;
                }
		
		if(curBall != NULL)
		{
			if(curBall->high != NULL)
			{
				while(curBall->high->high != NULL)
				{
					// Find the next "mountain peak". If there is one, move to it and count it.
					i++;
					curBall = curBall->high->high;
			
					// Destroy connections on the previous "mountain peak" in the set.
					curBall->low->low->low->high = NULL;
					curBall->low->low->low = NULL;
					curBall->low->low->high = NULL;
					curBall->low->low = NULL;
				}
			}
		}
		
		// On the final "mountain peak" on this set. Destroy the connections so it's not counted twice.
		curBall->low->high = NULL;
		curBall->low = NULL;
		curBall->high->low = NULL;
		curBall->high = NULL;
		
		// Multiply the current return value with this new value.
		rv *= (i+1);
	}
	
	return rv;
}

Originally Posted by tabstop

Just because curBall exists doesn't mean curBall->high exists.

I know that. But assuming curBall exists, the boolean expression curBall->high != NULL shouldn't cause a seg fault, right...? After all, you're testing to see if curBall->high exists.

Edit: If you missed it, that was one of the issues I found and mentioned in the beginning of my post. I reverted it back to what I was aiming for: curBall->high->high != NULL when I posted it here.

Originally Posted by tabstop

But if curBall->high doesn't exist (i.e. is NULL) then using it, which you do when you say curBall->high->high, is only going to give you SIGSEGV. You have to check the pointer is non-NULL before you put -> behind it.

Yeah, I realize that.

For clarity, I ran that code with the same set of input while changing that statement to see when it would stop causing a seg fault. Nothing else in the code changed.

These are the things I changed it between.
while (curBall != NULL) Success. curBall != NULL is true.
while (curBall->high != NULL) SEGMENTATION FAULT
And of course, that would mean
while (curBall->high->high != NULL) SEGMENTATION FAULT

I had set it back to curBall->high->high only because that's what I wished to achieve in the code. My problem is mainly that I don't know why curBall->high != NULL would cause a seg fault, when curBall exists.

I'll add an if(curBall->high != NULL) before the while loop, in an attempt to catch this. Although, I can't see that making any significant difference at the moment.

Edit: I added it in the program, and as I thought, nothing really changed. The only significant difference is now it seems to be segfaulting at the if statement.
I also added the if statement in the code in my original post.

A couple of things i noticed:

firstpicture and secondpicture do not seem to have any size?

EDIT: Oh i see there is code missing

Since you are making classes out of all of this, make default constructors that set those pointers to NULL.


Quzah.

Originally Posted by rogster001

A couple of things i noticed:

firstpicture and secondpicture do not seem to have any size?

EDIT: Oh i see there is code missing

Yeah. I'm not responsible for the main program, which obtains those values.

I'll add some sample data, in the event someone tries to check my logic:

Sample values can look something like this:

Code:

firstPicture = { 4, 2, 6 }
secondPicture = { 5, 2, 4, 3, 1, 7, 8 }

Each value in firstPicture is a position of a ball in a single dimension. All Balls have the same velocity Magnitude. Every ball is moving, and the balls can pass through each other. In secondPicture, no two balls are on top of each other, so every value in firstPicture must correspond to only one value in secondPicture. The other values in secondPicture would be new balls. My function(s) are called in order to determine the number of valid guesses of how the balls may have moved.

For this sample input, potential velocities would be 1, 2, 3, 5, and 6.
Velocity 1 would result in 4 valid guesses.
2 would result in 1, 3 would result in 2, both 5 and 6 would result in 0.


In orignal post/program: added constructors for Ball, and check if curBall != NULL.

Still seems to cause a segmentation fault at curBall->high != NULL.

Originally Posted by tabstop

I'm not sure why this coming from TopCoder would restrict your ability to use a debugger, which is what you should be doing this whole time, to see exactly what line you are on when you crash and what the values of all your variables are.

You may want to also check your algorithm; it is possible that if curBall->high->high exists that curBall->high->high->low->low->low->high must also exist, but I don't see any reason (just looking at the code) that that would have to be true.

I don't know what kind of tools I have at my disposal in the TopCoder arena, really. My professor has a driver program, but whenever I try to compile the whole program, the compiler complains about things in his driver program. I'm going to a TA's office today to look into that.

And thanks. I'm in the process of checking the algorithm now. I know that it fails on the first time through the function cvg(), assuming the number of valid guesses isn't 0. So, I'm working from there.

Edit: It appears that the algorithm is correct (at least, for the first input, which results in a segfault). I'll look into it more, just to be sure...

Edit2: Solved this segfault by adding this in the last for loop of cvg().

Code:

        if(fit->second->high == NULL && fit->second->low == NULL)
        {
            continue;
        }

Now when I run through the gradescript, 47 out of 50 inputs come out valid. Two result in slightly incorrect values, and one results in a seg fault.
I'll come back to this part of the lab later (Only three points off, as opposed to 50 if I don't complete the other one...) to take a look at these errors.