Recursive DFS with all the nodes in an array

#1

I have a wide tree that’s represented as a Slab<{ children: ArrayVec<[{ index: usize, bound: B }; 32]> }>. I want to do a DFS on it but it’s really annoying because I’m trying to mutably borrow the array to get to the children, while I’m also mutably borrowing the array to get to the parent. How can I convince the compiler that it’s all good?

fn visit_branch<B, D, I, F>(
    tree: &mut RTree<B, D, I>,
    visit_leaf: &F,
    branch_id: I,
    reinsert: &mut Vec<(I, B)>,
) -> Update<B>
where
    B: Bound,
    I: ID,
    F: Fn(I, &D, &B) -> Update<B>,
{
    let mut dirty = false;

    let branch = &mut tree.branches[branch_id.into_usize()];
    //TODO: How to get your laundry eaten.
    let branch: *mut _ = branch;
    let branch = unsafe { &mut *branch };

    if branch.end {
        let leaves = &mut tree.leaves;
        branch.children.retain(|(id, bound)| {
            match visit_leaf(*id, &leaves[id.into_usize()], bound) {
                Update::Keep => true,
                Update::Remove => {
                    leaves.remove(id.into_usize());
                    dirty = true;
                    false
                }
                Update::Change(b) => {
                    reinsert.push((*id, b));
                    dirty = true;
                    false
                }
            }
        });
    } else {
        branch.children.retain(|(id, bound)| {
            match visit_branch(tree, visit_leaf, *id, reinsert) {
                Update::Keep => true,
                Update::Remove => {
                    tree.branches.remove(id.into_usize());
                    dirty = true;
                    false
                }
                Update::Change(b) => {
                    *bound = b;
                    dirty = true;
                    true
                }
            }
        });
    }

    if dirty {
        let mut bounds = branch.children.iter().map(|(_, bound)| bound);
        if let Some(&new_bound) = bounds.next() {
            Update::Change(bounds.fold(new_bound, |x, y| x.merge(y)))
        } else {
            Update::Remove
        }
    } else {
        Update::Keep
    }
}
#2

You can use split_at_mut

#3

How? The branches are laid out in a random order in memory, and it’s a slab, so it’s not like I can get a slice out of it anyway.

#4

Ah, I didn’t notice that.

Could you remove elements that you needed to work on and then add them back to the Slab. That should work if your tree is acyclic.

1 Like
#5
  • The slab will assign a new index to the branch, so updating the parent will be a pain.
  • That’s a big readability (and a small performance) hit for that safety.
  • Is it an especially bad idea to unsafely reborrow the parent pointer like I did above?
    let branch = &mut tree.branches[branch_id.into_usize()];
    let branch: *mut _ = branch;
    let branch: &mut _ = unsafe { &mut *branch };

Edit: Assuming the tree is a tree and this isn’t UB, it should be safe, right?

#6

As long as you are never aliasing mutable references, it should be fine. What I would do is create a small helper function that checks (at the very least in debug mode), that you are not aliasing mutable references, and use that helper function to get multiple mutable references .