The most weird problem I've EVER seen

[h9uest]

I'm working on a problem on topcoder, and below is the code I've got so far.
To illustrate the problem, compile the code with "g++ -std=c++0x main.cc" and run the program. You will see "segmentation fault".

Now, uncomment the line printing "hello"(in function minSumlength).
You see everything behaves correctly.

Why? Please enlighten me! Thanks a lot!

P.S. environment:
gcc 4.4.3
OS, ubuntu 10.04

#include <iostream>
#include <string>
#include <set>
#include <vector>
#include <unordered_map>
using namespace std;

#define DEBUG_showtree

typedef long long INT;

class PrefixFreeSuperset
{
	private:
		class TreeNode
		{
			friend class PrefixFreeSuperset;

			string str;
			TreeNode * parent;
			TreeNode * left;
			TreeNode * right;

			//bool valid;
			bool dead;

			TreeNode(string s)
			{
				str = s;
				left = right = parent = NULL;

				//valid = false;
				dead = false;
			};
		};


		vector<string> vec;
		vector<string> superset;
		INT num; //num of nodes to be generated
		INT sumlength;
		TreeNode * root;
		vector<TreeNode *> cand;
		unordered_map<string, TreeNode *> generated;
		
		void formTree(string);
		void bfsConstructNodes();
		void kickAdjust();



		/*		debugging tools		*/
		void showTree(TreeNode *);

	public:
		INT minSumLength(vector<string>, INT);
};

void PrefixFreeSuperset::showTree(PrefixFreeSuperset::TreeNode * node)
{
	if(node == NULL)
	{
		return;
	};
	cout << node->left << endl;

	showTree(node->left);
	cout << "node addr= " << node << "; ";
	cout << "node->str= " << node->str << "; ";
	cout << "node->dead= " << node->dead << "; ";
	if(node->parent != NULL)
	{
		cout << "node->parent addr= " << node->parent << "; ";
	}
	else
	{
		cout << "node->parent is NULL; ";
	};
	if(node->left != NULL)
	{
		cout << "node->left addr= " << node->left << "; ";
	}
	else
	{
		cout << "node->left is NULL; ";
	};
	if(node->right != NULL)
	{
		cout << "node->right addr= " << node->right << "; ";
	}
	else
	{
		cout << "node->right is NULL; ";
	};

	cout << endl << endl;

	showTree(node->right);
};



// construct upwards until meeting with root
void PrefixFreeSuperset::formTree(string s)
{
	TreeNode * node;
	TreeNode * pare;
	while(s != "")
	{
		if(generated.find(s) == generated.end())
		{
			// generate new node
			if(node == NULL)
			{
				node = new TreeNode(s);
				generated[s] = node;
				node->dead = true;
			}
			else
			{
				pare = new TreeNode(s);
				generated[s] = pare;

				node->parent = pare;
				if(node->str[node->str.size()-1] == '0')
				{
					pare->left = node;
				}
				else
				{
					pare->right = node;
				};

				node = pare;
			};
		}
		else
		{
			TreeNode * tmp = generated[s];
			node->parent = tmp;
			//tmp->dead = true;
			if(node->str[node->str.size()-1] == '0')
			{
				tmp->left = node;
			}
			else
			{
				tmp->right = node;
			};

			if(tmp->left != NULL && tmp->right != NULL)
			{
				tmp->dead = true;
			};

			break;
		};

		s = s.substr(0, s.size()-1);
	};

	if(s == "")
	{
		node->parent = root;
		if(node->str == "0")
		{
			root->left = node;
		}
		else
		{
			root->right = node;
		};
	};
};

INT PrefixFreeSuperset::minSumLength(vector<string> vec, INT k)
{
	this->vec = vec;
	num = k - vec.size();
	sumlength = 0;

	superset = vec;


	root = new TreeNode("");
	// bottom up: form tree
	for(size_t i=0; i<vec.size(); i++)
	{
		//cout << "hello\n";
		formTree(vec[i]);
	};
	if(root->left != NULL && root->right != NULL)
	{
		root->dead = root->left->dead && root->right->dead;
	};

#ifdef DEBUG_showtree
	cout << generated.size() << endl;
	showTree(root);
#endif

	if(num > 0)
	{
		// FIXME
		if(root->dead)
		{
			return -1;
		};

		// breadth first search, generate num nodes
	//	bfsConstructNodes();

	//	kickAdjust();

		for(size_t i=0; i<num; i++)
		{
			//superset.push_back(cand[i]);
		};
	}

	for(size_t i=0; i<superset.size(); i++)
	{
		sumlength += superset[i].size();
	};


	if(sumlength > 1000000000000000000)
	{
		return -2;
	};

	return sumlength;
};

int main()
{
	PrefixFreeSuperset s;

	string arr [] = {"010", "00", "011", "1"};
	vector<string> vec(arr, arr+sizeof(arr)/sizeof(string));
	INT k = 5;

	cout << s.minSumLength(vec, k) << endl;
	return 0;
};

[coder777]

On the lines 106/107 you leave 'node' and 'pare' uninitialized.

You get to line 124 or 164 and there the crash starts...

[Gaminic]

Also, you don't need a ';' after '}'. Probably not an error, but it reduces readability [in my opinion], as you normally only see '};' after a class declaration.

[h9uest]

Thanks for the reply!

@coder777:
I'm afraid that's not the problem.
In fact, the programming problem had a complex background and it's not possible to explain my solution clearly in a few sentences without drawing some diagrams. I might have to do this and post the solution and its background if no one is able to help me find the problem from a purely technical perspective.

In fact, it is guaranteed that when line 124 or 164 gets executed, they will have valid values. If you run my code, you'll see the output proves what I say. The segmentation fault is not due to an improper operation(-> operator in this case) on a NULL pointer; instead, it is because of the function showTree(). As you can tell, I'm doing an inorder traversal to cout the state of each node in the tree using recursion; The real problem is, I am in a dead loop of recursion(in showTree()) and finally my program appears to run out of stack and access some unauthorized memory. You may verify this by taking a look at the output. I print out the address of left children when doing inorder traversal, so you can see a repeated pattern of addresses. (the loop is in the left branch)


The weird thing is:
if we uncomment line 189, the program prints correct results! The addresses(and other info) printed out are EXACTLY correct. More importantly, we don't see a repeated pattern of addresses! This is incredible, because cout something does not change the structure of the tree; if the tree has a loop between two treenodes, the loop structure will NOT disappear simply because I cout hello or hi(it worked with hi as well)!


Please enlighten me!!! Thanks a lot.

[viliml]

try replacing the "\n" with endl.

[Pravesh Koirala]

At line 106 and 107
I believe you wanted

	TreeNode * node = NULL;
	TreeNode * pare = NULL;

instead of

	TreeNode * node;
	TreeNode * pare;

If this solves your problem, I'll *enlighten* (hehe, couldn't stop myself from writing this) you as to why your program didn't crashed after you uncommented the "hello"

[cire]

In fact, it is guaranteed that when line 124 or 164 gets executed, they will have valid values.

No, it's not. It doesn't take much to see it, either.

When you reach line 113 for the first time, node is not initialized and contains junk.

Because this junk is unlikely to evaluate to NULL, pare gets a new value. Then you use the junk in node, resulting in undefined behavior. Be enlightened. These are the types of hard-to-track down problems you get with wild pointers, if you're unlucky enough not to crash.

[Gaminic]

P.S.: The big boys use "nullptr" now!

[h9uest]

Thank you all for the replies!

@Pravesh & cire:
You are the men!
I double checked with c++ standard, and it doesn't specify the default value of a pointer, so it must be some random value. Well, I had the mistaken impression that pointers have NULL as their default values. And that's my downfall.

I kinda see why. When the stack of formTree() gets destroyed and then created again, the node and pare have the old values. Now with my solution diagram, it makes perfect sense why I have a dead loop in the tree.

An interesting question will be, why does my situation change when I decide to cout some random stuff? Purely luck?

Well, thank you guys very much! I'm indeed *enlightened*, and it feels soooo great! :)