Can we just null the end node's pointers on the destructor? this should dereference all the nodes.
BTW, I think there is a previous bug on that same behavior: https://issues.dlang.org/show_bug.cgi?id=5650
Comment #2 by safety0ff.bugz — 2014-06-13T19:41:18Z
RedBlackTree does not guarantee that remove operations won't invalidate iterators, this guarantee is only present for inserts. So I think this is acceptable.
As you've stated, we must use _left, _right and _parent to null out the pointers.
(In reply to Steven Schveighoffer from comment #1)
> Can we just null the end node's pointers on the destructor? this should
> dereference all the nodes.
This can be done in addition to Martin's solution, just call clear().
I'm not sure this will have a big impact:
The RedBlackTree's nodes form a cycle, a false pointer into any node will still cause the entire tree to be retained.
And since the begin & end pointers are always on the heap, as the number of nodes in the tree increases the likely hood of the begin & end being the ones causing the leak diminishes.
If this is a pervasive issue, perhaps a function which recursively nulls the pointers is in order (and optionally manually deallocates.)
Nulling would invalidate iterators, manually deallocating invalidates references.
Comment #3 by schveiguy — 2014-06-13T19:57:58Z
OK, I misunderstood. I thought the issue was that the red black tree itself was being pointed at, and that was causing the leak.
We certainly can null pointers as the nodes are deallocated. But the tree does not go through and destroy all the nodes if you just forget the tree (and I would argue it shouldn't). So this may solve the specific use case, but not the general one.
Comment #4 by safety0ff.bugz — 2014-06-13T20:04:32Z
(In reply to Steven Schveighoffer from comment #3)
> We certainly can null pointers as the nodes are deallocated. But the tree
> does not go through and destroy all the nodes if you just forget the tree
> (and I would argue it shouldn't).
Clear simply resets the begin & end pointers.
> So this may solve the specific use case, but not the general one.
The general case is only solved by precise GC.
We can only help specific use cases:
- Nulling on element removal.
- Manually specified complete destruction.
etc.
Comment #5 by github-bugzilla — 2014-10-19T16:41:51Z