orlp / slotmap

Slotmap data structure for Rust
zlib License
1.08k stars 70 forks source link

[linked list example] `pop_head()`/`pop_tail()` is wrongly implemented #120

Open ge9 opened 2 months ago

ge9 commented 2 months ago

(Linked list example: https://github.com/orlp/slotmap/blob/master/examples/doubly_linked_list.rs ) In pop_head() and pop_tail() functions, there are no appropriate handling of new head/tail nodes, producing dangling pointer in them. We can just call remove() funtion like this,

    pub fn pop_head(&mut self) -> Option<T> {
        self.remove(self.head)
    }
    pub fn pop_tail(&mut self) -> Option<T> {
        self.remove(self.tail)

Or copy-pasting remove() and omit unnecessary ifs:

    pub fn pop_head(&mut self) -> Option<T> {
        self.sm.remove(self.head).map(|old_head| {
            self.head = old_head.next;
            if let Some(next_node) = self.sm.get_mut(old_head.next) {
                next_node.prev = old_head.prev;
            } else {
                self.tail = old_head.prev;//=null
            }
            old_head.value
        })
    }
    pub fn pop_tail(&mut self) -> Option<T> {
        self.sm.remove(self.tail).map(|old_tail| {
            if let Some(prev_node) = self.sm.get_mut(old_tail.prev) {
                prev_node.next = old_tail.next;
            } else {
                self.head = old_tail.next;//=null
            }
            self.tail = old_tail.prev;
            old_tail.value
        })
    }