A question about muterr


I was trying to update the parent_ptr after insert a key in the tree. But it occurs BorrowMutError.

the wrong message

    //struct
pub struct Leaf<K: Key, V: Record, const FANOUT: usize> {
    pub num_keys: usize,
    pub keys: Vec<Option<K>>,
    pub records: Vec<Option<RecordPtr<V>>>,
    pub parent: Option<NodeWeakPtr<K, V, FANOUT>>,
    pub prev: Option<NodeWeakPtr<K, V, FANOUT>>,
    pub next: Option<NodeWeakPtr<K, V, FANOUT>>,
}

#[derive(Debug)]
pub struct Interior<K: Key, V: Record, const FANOUT: usize> {
    pub num_keys: usize,
    pub keys: Vec<Option<K>>,
    pub children: Vec<Option<NodePtr<K, V, FANOUT>>>,
    pub parent: Option<NodeWeakPtr<K, V, FANOUT>>,
}

#[derive(Debug, Default)]
pub enum Node<K: Key, V: Record, const FANOUT: usize> {
    #[default]
    Invalid,
    Leaf(Leaf<K, V, FANOUT>),
    Interior(Interior<K, V, FANOUT>),
}

:smiling_face_with_tear:
thank you all,please help me

Welcome @qsstcl! I am starting to understand a little about your tree structure, but I have some comments and requests before going further:

  • It is difficult to tell the line number where the error occurs from what you posted. Please post the complete output from running cargo in the terminal.

  • Your first post is an image and it would be much better for reading and copy-pasting the text if you post it as you did in your third message.

  • It would also be much easier for others to help if they can run your complete code, or a minimal version of it that shows the problem. Could you please create a playground or post a link to your source code or git repo?

2 Likes

thank you
I'll modify it

1 Like
  1. Cargo result
    Compiling bplus-tree v0.1.0 (/home/qss/bplustree_final)
    Finished dev [unoptimized + debuginfo] target(s) in 1.23s
    Running target/debug/bplus-tree
    thread 'main' panicked at src/btree/btree.rs:322:59:
    already borrowed: BorrowMutError
    note: run with RUST_BACKTRACE=1 environment variable to display a backtrace

  2. src code

                    {
                        let right_borrow_mut = new_right.borrow_mut();
                        let right_children_num = right_borrow_mut.interior().unwrap().num_keys;
                        for i in 0..right_children_num {
                            if let Some(child) = &right_borrow_mut.interior().unwrap().children[i] {
                                let mut child_mut = child.borrow_mut();
                                match child_mut.interior_mut().as_mut() { 
                                    Some(child)=>{
                                        child.parent = Some(Rc::downgrade(&new_right));
                                        drop(child_mut)
                                    }
                                    _=>()
                                }
                            }
                        }
                        
                    }

3.github repo link
qsstcl/BPTree: a simple B+ Tree implemented by Rust (github.com)

Thank you! I was able to run the code in your repo, which is great.

This line is failing when trying to unwrap the Option returned from upgrade:

let parent= parent.unwrap().upgrade().unwrap();

With this error:

     Running `target/debug/bplus-tree`
thread 'main' panicked at src/btree/btree.rs:248:47:
called `Option::unwrap()` on a `None` value
stack backtrace:
   0: rust_begin_unwind
             at /rustc/79e9716c980570bfd1f666e3b16ac583f0168962/library/std/src/panicking.rs:597:5
   1: core::panicking::panic_fmt
             at /rustc/79e9716c980570bfd1f666e3b16ac583f0168962/library/core/src/panicking.rs:72:14
   2: core::panicking::panic
             at /rustc/79e9716c980570bfd1f666e3b16ac583f0168962/library/core/src/panicking.rs:127:5
   3: core::option::Option<T>::unwrap
             at /rustc/79e9716c980570bfd1f666e3b16ac583f0168962/library/core/src/option.rs:935:21
   4: bplus_tree::btree::btree::BPTree<K,V,_>::insert_into_parent
             at ./src/btree/btree.rs:248:21
   5: bplus_tree::btree::btree::BPTree<K,V,_>::insert
             at ./src/btree/btree.rs:173:13
   6: bplus_tree::main
             at ./src/main.rs:19:5
   7: core::ops::function::FnOnce::call_once
             at /rustc/79e9716c980570bfd1f666e3b16ac583f0168962/library/core/src/ops/function.rs:250:5
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.

You probably didn't get a backtrace because you haven't set the RUST_BACKTRACE env variable to 1.

The Weak::upgrade doc says:
Returns None if the inner value has since been dropped.

Thank you !! But the real problem is that when inserting 9,the parent_ptr of children is not right which happened in insert_into_parent.so i am facing the mut_err when trying to fix the ptr problem

I'm looking at the large block of code below this line that is commented:

                //codes below have problems of borrow_mut

               // {
               //     let left_borrow_mut = new_left.borrow_mut();
               //     let left_children_num = left_borrow_mut.interior().unwrap().num_keys;

...

Is this commented code meant to be used, but you're getting compiler errors? Or are you referring to other code?

I'm just trying to clarify what you meant.

Edit: When I uncomment that block of code, I get the error you originally mentioned. So it seems that the commented code is what you're referring to. I'll take a closer look at it.

This will take some time so I will reply tomorrow.

Thanks, you are so kind :sob:

One problem is that left_borrow needs to be dropped before the block of code (part of the code that was commented earlier) that sets the parent fields in the right node's children:

                    drop(left_borrow); // <<<<<<<<<

                    {
                        let right_borrow_mut = new_right.borrow_mut();
                        let right_children_num = right_borrow_mut.interior().unwrap().num_keys;
                        for i in 0..right_children_num {

That change fixes the problem you reported. I assume the drop is needed is because the new right node contains some of the children from the old left node. With that change the test runs farther, but then there is a different problem at line 15 of main.

An unrelated issue is that I think you'll need to drop the parent_borrow before recursively calling insert_into_parent:

                    drop(parent_borrow); // <<<<<<<<<<<<
                    self.insert_into_parent(new_left, spilt_key, new_right)

Although that change doesn't seem to help with any of the known problems.

I have some higher level comments:

  • The use of RefCell makes the code difficult to follow and somewhat fragile, since borrows must be dropped at just the right places. I suspect there will be more bugs related to borrows.
  • There are lots of memory allocations due to the use of Rc and Vec.
  • Instead of Vec, arrays could be used since the FANOUT is a constant. This will reduce memory allocations.
  • Another approach for allocating Nodes is to have the slice of children contain indexes into a slab of Node objects (using the slab or slotmap crate, for example), with one slab for each btree. Then using Rc and RefCell would not be necessary, which would be less complex, and memory allocations would be reduced. However, it is also easy to create bugs when using indexes to refer to Nodes, since just like RefCell there is no compile time checking that the indexes are valid. So I think the biggest advantage is the reduced allocations.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.