[antlr-interest] Leaks in doubly-linked trees: implementing
'getParent'
Paul Johnson
gt54-antlr at cyconix.com
Tue Aug 9 04:45:45 PDT 2005
Some time ago there was a discussion about the need to occasionally look
up trees to find your current context (starting at
<http://www.antlr.org/pipermail/antlr-interest/2005-June/012822.html>,
through the threading on the website doesn't work well).
There was a school of thought that this is important in some situations,
and that it should be implemented with 'getParent', and over-riding
various other methods, which I suspect various people have done
independently (including myself).
However, there's a problem with the obvious implementation, which is:
class myAST : public antlr::CommonAST {
private:
RefAST up; //!< Parent node
...
};
The problem is that this leaks. The assignment 'up = parent' will
increase the parent's reference count. The problem comes when you
attempt to delete a branch of a tree:
// remove oldnode and its descendents, replace with newnode
newnode->setNextSibling(oldnode->getNextSibling());
previous->setNextSibling(newnode); // orphans oldnode
This orphans oldnode, but it won't delete it since the 'setNextSibling'
op doesn't reduce its reference count to zero (because oldnode's
children still reference it).
Does anyone have a bidirectional tree implementation that avoids this
problem? At first sight, one obvious fix may be to modify the library
code so that the reference count decrementing routines ignore references
from children.
Paul
More information about the antlr-interest
mailing list