Why is this a leak?

[ChetZ]

Hello,

While checking for leaks in my code I was directed to:
Node* &son = this->sons[c]
where
Node is the following object:

class Node{
	public:
		int count;
		double val;
		Node* father;
		std::map<int,Node*> sons;	

I can't see why this is leaking.
Please help!

Thanks!

[Athar]

It's likely that you created the node via new, but never deleted it. As a result, any memory allocated by the map won't be freed either.

[ChetZ]

so here's where it's leaking:

Node* Node::insertAllPrefixes(const double *pattern, const int pattern_size, const int l){
	//l corresponds to the discretization level	
	count += 1;
	if (pattern_size == 0) return this;
	const double c = (double)floor(pow(2,l)*pattern[0]);
	Node*  &son = this->sons[c];
	if ( son == NULL) { 
		son = new Node(this,c);
	}
	return son->insertAllPrefixes(pattern+1, pattern_size-1,l);  		
}

Yes, I do create 'son' via new but I don't delete it because once filled-up Node* becomes a tree I traverse in some other class for other calculations.

here's my destructor:

Node::~Node(){
	if (sons.empty()) return;
	
	map<int,Node*>::iterator it;
	
	for (it = sons.begin(); it!=sons.end(); it++ ) {
		delete(it->second);
	} 
}

am I missing something ?

[vlad from moscow]

Can you explain why are you using reference Node* &son ? It is very interesting! And I will explain you why there is a memory leak.

[ChetZ]

So, I'm creating a reference "son" to refer to sons[c] (which is of type Node*), and if I haven't seen c before (so that sons[c] doesn't exist) I create a new son with value c and (update this Node's map<int,Node*>).

[Athar]

Yes, I do create 'son' via new but I don't delete it

They are deleted in the destructor. You have to delete the root node once you no longer need the tree.
If you don't, you shouldn't be surprised that the tool you're using tells you there is a memory leak.

[ChetZ]

I do delete the root at the end.
The problem seems to be the reference &son.
because now I changed the code to:

Node* Node::insertAllPrefixes(const double *pattern, const int pattern_size, const int l){
	//l corresponds to the discretization level	
	count += 1;
	if (pattern_size == 0) return this;
	const double c = (double)floor(pow(2,l)*pattern[0]);
	if ( this->sons[c] == NULL) { 
		this->sons[c] = new Node(this,c);
	}
	return this->sons[c]->insertAllPrefixes(pattern+1, pattern_size-1,l);  		
}

and the problem seems to have been resolved.

[ne555]

//son = new Node(this,c);
Node::~Node(){
	if (sons.empty()) return;
	
	map<int,Node*>::iterator it;
	
	for (it = sons.begin(); it!=sons.end(); it++ ) {
		delete(it->second);
	} 
}

I would like to see that constructor. Because if you have a double link, stack overflow.

If this is a tree, then there is no need to store pointers in the container.

[ChetZ]

I would like to see that constructor.

Node::Node(Node* f, double newVal){
	count = 0;
	val = newVal;
	father= f;
}

Because if you have a double link, stack overflow.
If this is a tree, then there is no need to store pointers in the container.

umm ... well it's a prefix tree where each node has multiple sons. But can you please elaborate your point on the double link and stack overflow?

[ne555]

I thought that you've got a non-directed graph. So A is neighbour of B and B is neighbour of A.

	for (it = sons.begin(); it!=sons.end(); it++ ) {
		delete(it->second);
	}

When you destruct a node, you destruct its neighbours first. A will destroy B.
But, as A is neighbour of B, it will try to delete it first.
The destructor will be calling each other, infinite recursion, causing stack overflow.

But if you've got a tree, then you can use composition. std::map<int,Node> sons;
just don't use operator[] as you don't have a default constructor (replace it with find and insert)