Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Assertion failure in rrb::Size::pop #77

Closed
krobelus opened this issue Mar 12, 2019 · 0 comments
Closed

Assertion failure in rrb::Size::pop #77

krobelus opened this issue Mar 12, 2019 · 0 comments

Comments

@krobelus
Copy link
Contributor

This program causes an assertion failure

fn main() {
    let mut x = im::Vector::new();
    for _ in 0..44 { x.push_back(0); }
    for _ in 0..20 { x.insert(0, 0); }
    x.insert(1, 0);
    for _ in 0..441 { x.push_back(0); }
    for _ in 0..58 { x.insert(0, 0); }
    x.insert(514, 0);
    for _ in 0..73 { x.push_back(0); }
    for _ in 0..10 { x.insert(0, 10); }
    x.insert(514, 0);
}

Here's what the tree looks like before the last insertion. It seems that the split is performed at the wrong chunk.
When we do x.insert(514, 0), we need to split at index 514 which corresponds to 514 - 4 - 64 = 446 within middle. Hence the split should be done in the last but one node, but it seems like the one before is used.

Should the middle be using a size table here?

length       648
middle_level 1
outer_f      [length = 4]
inner_f      [length = 64]
middle:
Nodes [length = 9], Size(507)
    Values [length = 2]
    Values [length = 64]
    Values [length = 64]
    Values [length = 64]
    Values [length = 64]
    Values [length = 64]
    Values [length = 64]
    Values [length = 64]
    Values [length = 57]
inner_b      [length = 64]
outer_b      [length = 9]
krobelus added a commit to krobelus/im-rs that referenced this issue Mar 12, 2019
Previously this was only done for nodes of level > 1.

Now the cases for level == 1 and level > 1 share some logic, this could be
refactored in future.

Fixes bodil#77
krobelus added a commit to krobelus/im-rs that referenced this issue Mar 12, 2019
If the node we push to the left is not completely dense, then we convert to a
size table. Previously this was only done for nodes of level > 1.

Now the cases for level == 1 and level > 1 share some logic, this could be
refactored in future.

Fixes bodil#77
krobelus added a commit to krobelus/im-rs that referenced this issue Mar 12, 2019
If the node we push to the left is not completely dense, then we convert to a
size table. Previously this was only done for nodes of level > 1.

Now the cases for level == 1 and level > 1 share some logic, this could be
refactored in future.

Fixes bodil#77
@bodil bodil closed this as completed in #79 Apr 8, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant