I suppose that I should convert that iterative_print procedure to the drop where instead of printing the node that has no childs I free the memory and pop the stack. This is what I've got:
impl Drop for Tree {
fn drop(&mut self) {
for c in self.childs.iter() {
let mut stack = vec![];
stack.push(c.clone());
while !stack.is_empty() {
let current = stack.pop().expect("empty");
for child in current.borrow().childs.iter() {
if !child.borrow().childs.is_empty() {
stack.push(Tree::get_parent(
child.borrow().childs.last().expect("no childs 2"),
).expect("no_parent"));
continue
} else {
std::mem::drop(child);
}
}
std::mem::drop(current);
}
}
}
}
Checking with valgrind I see no leaks, but Dropping is very slow, like if I'm doing extra work so I'm suspicious that it doesn't do things correctly. Especially when it comes to reference counting. I also suspect that because I'm cloning references to the stack I actually increase the life time of Rc here, so this code is all wrong. Any suggestions?
One questions: Why are you calling get_parent on an element of child.childs, wouldn't that always return child? (for a valid tree)
Would this work?
impl Drop for Tree {
fn drop(&mut self) {
let mut stack = vec![]; // reuse the stack allocation
for c in self.childs.iter().cloned() {
stack.push(c); // initialize the stack
// keep popping off of the stack till it is empty
while let Some(current) = stack.pop() {
let mut current = current.borrow_mut();
// extend the stack with the children, so we can handle them later
stack.extend_from_slice(¤t.childs);
// prevent current from recursing on drop,
// because we will clean up the children here
current.childs.clear();
// current will be automatically dropped here
}
}
}
}
this uses unstable feature, and I'm writing in stable branch.
Also it seems that your previous drop breaks my code. Perhaps it clears too aggressively? The one that is generated by the compiler doesn't break my code.
heh, sorry about that I normally use nightly so I didn't notice
Your right, fixed that here
impl Drop for Tree {
fn drop(&mut self) {
// reuse the stack allocation, take all children
let mut stack = std::mem::replace(&mut self.childs, Vec::new());
// keep popping off of the stack till it is empty
while let Some(mut current) = stack.pop() {
// only take the children if `current` `Tree` is going to be dropped
// right now if there are outstanding `Rc`s elsewhere,
// don't clean this up just yet
if let Some(current) = Rc::get_mut(&mut current) {
let current = RefCell::get_mut(current);
// extend the stack with the children, so we can handle them later
stack.extend_from_slice(¤t.childs);
// prevent current from recursing on drop,
// because we will clean up the children here
current.childs.clear();
}
// current will be automatically dropped here
}
}
}
I think you are storing Rc's elsewhere and those are the problem, not the drop implementation itself. The latest drop impl that I gave will drop every child that is currently available to be dropped (i.e. isn't being shared somewhere else).
Actually I've figured that removing the clone() in line 50 fixes stack overflow. Can you explain why? Clippy says that this clone is #[warn(clippy::redundant_clone)], but I wouldn't imagine that it will cause stack overflow.
Ahhhhhh, I forgot that Rc::get_mut will return None if there are any weak pointers active, but we don't care about weak pointers (because we are about to drop the last Rc which will invalidate all weak pointers anyways)!
Since children always have a weak pointer to their parent, this fools Rc::get_mut and turns the old drop into the recursive drop. But we can just check this Rc::strong_count directly to see if we are going to drop, and handle that accordingly.
impl Drop for Tree {
fn drop(&mut self) {
let mut stack = std::mem::replace(&mut self.childs, Vec::new());
while let Some(current) = stack.pop() {
if Rc::strong_count(¤t) == 1 {
let mut current = current.borrow_mut();
stack.extend_from_slice(¤t.childs);
current.childs.clear();
}
}
}
}
The reason why removing clone worked is because you were then dropping the parents as soon as possible, every time you overwrote tmp, not at the end of main. Adding the clone forced the full recursive drop at the end of main.
