JP-Ellis/rust-skiplist

SkipMap bugs

jacksoom opened this issue · 2 comments

version: skiplist = "0.3.0"
Demo:

        let mut sm = SkipMap::new();
        sm.insert(1,1);
        sm.insert(2,2);
        sm.insert(3,3);
        println!("{}", sm.len());
        sm.remove(&3);
        sm.remove(&2);
        sm.remove(&1);

Because of Random number ,Sometimes there will be accidental panic
Panic info:
thread 'main' panicked at 'attempt to subtract with overflow', /Users/jacksoom/.cargo/registry/src/mirrors.ustc.edu.cn-61ef6e0cd06fb9b8/skiplist-0.3.0/src/skipmap.rs:753:25

Thanks for the suggested fix. I suspect this might be a deeper issue than that, but I'll check. Strange that it wasn't caught in the tests though.

Ok. (*prev_node).links_len[lvl] should be greater than zero

  for (lvl, &prev_node) in prev_nodes.iter().rev().enumerate() {
                    if (*prev_node).links[lvl] == Some(return_node) {
                        (*prev_node).links[lvl] = (*return_node).links[lvl];
                        (*prev_node).links_len[lvl] += (*return_node).links_len[lvl] - 1;
                    } else {
                            (*prev_node).links_len[lvl] -= 1;
                    }
                }