TreeSet Drop implementation


#1

Very recently I’ve started playing with Rust.
Inspired by http://cglab.ca/~abeinges/blah/too-many-lists/book/README.html I have created simple Queue:

use std::rc::Rc;
use std::cell::RefCell;

pub struct Queue<T> {
    head: Link<T>,
    tail: Link<T>,
}

type Link<T> = Option<Rc<RefCell<Node<T>>>>;

struct Node<T> {
    item: T,
    previous: Link<T>,
}

impl<T> Queue<T> {   
    pub fn enque(&mut self, item: T) {
        ...
    }
    pub fn deque(&mut self) -> Option<T> {
        ...
    }
}

Implementing Drop for it is quite straithforward:

impl<T> Drop for Queue<T> {
    fn drop(&mut self) {
        while self.deque().is_some() {}
    }
}

Now I’m on a quest to implement something slightly more complicated, a TreeSet:

use std::cmp::Ordering;

pub struct TreeSet<T: PartialOrd> {
    root: Link<T>,
}

type Link<T> = Option<Box<Node<T>>>;

struct Node<T: PartialOrd> {
    item: T,
    left: Link<T>,
    right: Link<T>,
}

However, I can’t really figure out how Drop should look like in this case. I’m not really able to understand BTreeSet yet (not mentioning lots of unsafe code which I 'm trying not to use at this stage).


#2

I suspect you don’t actually need to implement Drop for that set. There’s no Rc-cycle like the queue has, so the Drop of the inner types (especially Box) should just do the right thing.


#3

Is your tree balanced? Then you won’t have any stack exhaustion issues on drop anyway. If the tree has a worst case of looking like a list, you might consider it.


#4

@bluss What do you mean? Dropping a ‘list like’ tree manually could be potentially more performant?


#5

The idea is that a recursive drop can exhaust the stack memory if the list is too long, whereas popping items one at a time keeps it all local. It might also perform better, but the memory is the first concern.


#6

Thank you all for the answers.