A seg fault. Gotta love those.

This is a discussion on A seg fault. Gotta love those. within the C++ Programming forums, part of the General Programming Boards category; So, I'm having issues with a certain seg fault. I don't really understand what's causing it. I can perform the ...

  1. #1
    Registered User
    Join Date
    Nov 2010
    Posts
    17

    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;
    }
    Last edited by MSZShadow; 09-09-2011 at 09:02 AM.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Just because curBall exists doesn't mean curBall->high exists.

  3. #3
    Registered User
    Join Date
    Nov 2010
    Posts
    17
    Quote Originally Posted by tabstop View Post
    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.
    Last edited by MSZShadow; 09-08-2011 at 07:27 PM.

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

  5. #5
    Registered User
    Join Date
    Nov 2010
    Posts
    17
    Quote Originally Posted by tabstop View Post
    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.
    Last edited by MSZShadow; 09-08-2011 at 07:48 PM.

  6. #6
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,422
    A couple of things i noticed:

    firstpicture and secondpicture do not seem to have any size?

    EDIT: Oh i see there is code missing
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  7. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    The other choice is that curBall is not NULL, but also doesn't point anywhere meaningful.

    But still: at the underlined line, you're not checking whether curBall is NULL before typing curBall->high, which is silly.

  8. #8
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Since you are making classes out of all of this, make default constructors that set those pointers to NULL.


    Quzah.
    Hope is the first step on the road to disappointment.

  9. #9
    Registered User
    Join Date
    Nov 2010
    Posts
    17
    Quote Originally Posted by rogster001 View 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
    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.
    Last edited by MSZShadow; 09-09-2011 at 06:05 AM.

  10. #10
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

  11. #11
    Registered User
    Join Date
    Nov 2010
    Posts
    17
    Quote Originally Posted by tabstop View Post
    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.
    Last edited by MSZShadow; 09-09-2011 at 09:04 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. gotta love my teacher
    By misplaced in forum C++ Programming
    Replies: 7
    Last Post: 10-21-2004, 01:09 AM
  2. gotta love linker errors
    By dantestwin in forum C++ Programming
    Replies: 3
    Last Post: 07-08-2004, 05:53 PM
  3. gotta love those jaggies....*cough*
    By jverkoey in forum Game Programming
    Replies: 9
    Last Post: 04-22-2003, 08:44 PM
  4. You gotta see this...
    By Scourfish in forum A Brief History of Cprogramming.com
    Replies: 10
    Last Post: 03-22-2002, 05:54 AM
  5. gotta be a better way than this?
    By The Gweech in forum C++ Programming
    Replies: 15
    Last Post: 09-10-2001, 12:52 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21