Why do I get a segmentation fault while trying to find the median of a Circular Queue?

[waqqassheikh]

The code is below. I get a segmentation fault in the "findMedian()" function. The logic behind the function is that the singleStepIterator goes to the next element, while the doubleStepIterator goes two steps ahead. Since doubleStep is going twice as fast as singleStep - when doubleStep will be at the head, singleStep will be at the median.

Am I right int thinking that the segmentation is caused by the line:
doubleStepIterator = doubleStepIterator->link->link;


CircularQueue.cpp

#include <iostream>

struct Node
{
	int value;
	Node *link;
};

class CircularQueue
{
		Node *head;
		void findParent(Node* &parent);
		int findMedian();
	public:
		CircularQueue();
		~CircularQueue();
		void add(int value);
		void remove();
		int count();
		void print();
		void sort();
		friend void median();
};

CircularQueue::CircularQueue()
{
	this->head = NULL;
}

CircularQueue::~CircularQueue()
{
	delete this;
}

void CircularQueue::add(int value){//}

void CircularQueue::findParent(Node* &parent)
{

	parent = this->head;
	while(parent->link!=this->head)
	{
		parent = parent->link;
	}
	return;	
}

void CircularQueue::remove(){//}
int CircularQueue::count(){//}

void CircularQueue::print()
{
	std::cout<<"\n>>";
	Node *iterator = new Node();
	iterator=head;
	for(int index=1; index<=this->count(); index++)
       //can iterator=iterator->link and index++ BOTH be written inside for loop???
	{
		std::cout<<iterator->value<<", ";
		iterator = iterator->link;		
	}
	std::cout<<std::endl;
	std::cout<<">>"<<this->count()<<" elements in Queue.\n";	
}

int CircularQueue::findMedian()//THIS FUNCTION CAUSES SEGMENTATION FAULT
{
	Node *singleStepIterator = this->head;
	Node *doubleStepIterator = this->head;
	std::cout<<"findMedian::Initialized Successfully\n";

	while(doubleStepIterator->link->link!=this->head)
	{
                std::cout<<"if you see this, life is good.\n";
		singleStepIterator = singleStepIterator->link;
		doubleStepIterator = doubleStepIterator->link->link;		
	}
	return singleStepIterator->value;				
}

void median()
{
	CircularQueue c;
	std::cout<<"Median::Initialized\n";
	int median = c.findMedian();
	std::cout<<"\n>>Median Value: "<<median<<"\n";
}

int main()
{
	CircularQueue *circular_queue = new CircularQueue();
	circular_queue->remove();
	
	circular_queue->add(1);
	circular_queue->print();

	circular_queue->add(2);
	circular_queue->print();

	circular_queue->add(3);
	circular_queue->print();

	circular_queue->add(4);
	circular_queue->print();

	median();//segmentation fault!
	circular_queue->remove();
	circular_queue->print();

	return 0;
}

[kfmfe04]

Am I right int thinking that the segmentation is caused by the line:
doubleStepIterator = doubleStepIterator->link->link;

Well, since head is NULL and never assigned to, doubleStepIterator is also NULL.

Also, please correct Line 32.

[D80DSL3A]

The problem arises from your use of a local instance of CircularQueue in the median(). Line 84 constructs c with head = NULL.
After findMedian() is called (line 86) line 70 assigns Node *doubleStepIterator = this->head; which = NULL.
The attempt to dereference doubleStepIterator on line 73 would cause a segmentation fault:
while(doubleStepIterator->link->link!=this->head)
The line you guessed at (line 77) would also cause this - if execution got that far.

Perhaps you should pass a reference to circular_queue to the median(), or make findMedian() public and call it directly in the main().

EDIT: kfmfe04 beat me to it! I Gotta reply faster or wait longer.

[waqqassheikh]

Thanks guys, that makes perfect sense - and thanks for the in-depth explanation fun2code. I put the 'friend function' in there just to practice using one. As you can see, i'm not very good with them. Otherwise, I would've certainly made findMedian() public.

One thing, what's wrong with line 32? Is it inadvisable to write a destructor like that? If so, please explain. Thanks.

[kfmfe04]

1. what kind of object did you allocate with new?
what kind of object are you deleting with delete this on line 32?
you have to make sure that you call delete on every object that you allocated by calling new.

2. if you understand destructors, you should never call delete this, whether in a destructor or not.
why? make sure you understand why.

3. I recommend that you learn how to use a debugger. In cases like this, I don't waste time acting as a human compiler. Instead, I cat your code into a file, build, and run it in a debugger. In less than 30 seconds, I know why your code is broken. Of course, you should try to write good/correct code all the time, but when you get stuck, do not hesitate to let the debugger find the problem for you - you may arrive at a solution much faster than you think.

[waqqassheikh]

1. That makes sense. Should have figured that one.

3. Yeah, I use a text editor to code and rely on the compiler diagnostics to spot compile-time errors. I'll get acquainted with debuggers.

Thanks a lot!!!

[waqqassheikh]

I want to clarify something:

-My destructor consists of delete this;;
-delete this calls on the destructor of my class, which calls delete this; again
-and so there's an infinite loop.

That's fine, and i've learnt my lesson ;) What I want to know is this:

i've used

delete this;

before in some other data structures i made, and those programs worked fine. Why didn't they hang if there was an infinite loop?

Sorry, if it's a dumb question.

[kfmfe04]

excellent - analyzing your code like this will make you a great C++ developer

it's not a dumb question - the reason is this: when you call delete in C++, it frees memory, but does not zero out anything. That means the behavior of your code becomes indeterminate.

also, you didn't mention where you called delete in your last question, but I suspect that you called it in some method that was not the destructor.

anyhow, the bottom line is, there is never a reason to call delete this

btw, using a text-editor to code is fine - I just use vim myself

[waqqassheikh]

I did call

delete this;

in the destructor (in those 'older' programs). Could you please explain what you mean by "zero out" in this context. Thanks a lot. Really appreciate this; (cheesy but couldn't help it.)

[D80DSL3A]

If I may expound a bit further (trying to add to kfme04's explanation) what needs to be deleted in the destructor are the Nodes which were allocated to the Queue.

Since the Queue is circular maybe a good way would be to start with head->next, follow the links all the way around to head (deleting each Node as you go) then finally delete head.
You can delete the Queue itself (since you allocated it with new in main() ) with
delete circular_queue; at the end of main(). This will invoke the destructor.
You're welcome for the help.

[kfmfe04]

sorry about that - the comment was a little bit out of context of your question.

what I meant was, suppose you had:

int* ptr = new int;
*ptr = 5;
delete ptr;

some people believe that Line 3 will free memory and set ptr to NULL - in fact, it only frees memory.

as a further illustration, you could copy Line 2 to Line 4 if you like. Many beginners think Line 4 would cause a crash, but in fact, you will get indeterminate behavior - it may crash at Line 4 or it may crash somewhere far away. This is much worse than a certain crash at Line 4 - sometimes, a segfault is your friend, if it crashes right at the point of your bug. If you do thread programming one day, you will find that the same difficulties apply - one of the reasons thread programming is difficult is the ease of creating race conditions that cause indeterminate behavior. It crashes, then it doesn't crash, then it crashes again five times, but then doesn't!

this is relevant for debugging because sometimes, when ptr to nothing is explicitly set to NULL, it is easier to locate the problem - it often makes your crashes determinate. For example, if you did this:

int* ptr = new int;
*ptr = 5;
delete ptr;
ptr = NULL;
*ptr = 5;  // will definitely crash here 

this is a Mickey-Mouse example. In real code, the pieces will be farther away from each other and not so obvious. However, this example illustrates that programming in C++ requires discipline and diligence, if you do not want to spend a lot of time debugging.

[waqqassheikh]

So, if i understand correctly, the proper C++ approach (Java's taught me many bad habits, it seems), I should:

-go through the queue
-delete each node
-and set to null, FTW??

[kfmfe04]

So, if i understand correctly, the proper C++ approach (Java's taught me many bad habits, it seems)

This happens more often than many Java developers would care to admit. What happens is, Java does so much for you that unfortunately, some Java programmers become dangerous C++ if they don't apply the discipline needed in C++.

In response to your steps, you need to do 1 and 2 (fun2code's suggestions are good) - it is up to you if you want to do 3.

[waqqassheikh]

I have no problem admitting it. I always liked C++ because things have a tendency to go wrong (although, I suppose i'd hate it if I'd have to use it for some large company project.)

Yeah, I'll do step 3. Might actually learn something.

Thanks a lot for your help, both of you!!!!!
Really really much appreicated!!!!!
:)

[kfmfe04]

np - glad you learned something :)

no worries - I have difficulties "undoing" paradigms when I learn new languages, too - eg trying not to use loops in R, or trying to use a stateless functional approach over OO in languages like Scala

gl