SkipMap bugs
jacksoom opened this issue · 2 comments
jacksoom commented
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
JP-Ellis commented
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.
jacksoom commented
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;
}
}