oasis_core_runtime/storage/mkvs/tree/
remove.rs

1use anyhow::Result;
2
3use crate::storage::mkvs::{
4    cache::Cache,
5    tree::{
6        Depth, Key, KeyTrait, NodeBox, NodeKind, NodePointer, NodePtrRef, NodeRef, Tree, Value,
7    },
8};
9
10use super::lookup::FetcherSyncGet;
11
12impl Tree {
13    /// Remove entry with given key, returning the value at the key if the key was previously
14    /// in the database.
15    pub fn remove(&mut self, key: &[u8]) -> Result<Option<Vec<u8>>> {
16        let boxed_key = key.to_vec();
17        let pending_root = self.cache.borrow().get_pending_root();
18
19        // Remember where the path from root to target node ends (will end).
20        self.cache.borrow_mut().mark_position();
21
22        let (new_root, _, old_val) = self._remove(pending_root, 0, &boxed_key)?;
23        self.cache.borrow_mut().set_pending_root(new_root);
24
25        Ok(old_val)
26    }
27
28    fn _remove(
29        &mut self,
30        ptr: NodePtrRef,
31        bit_depth: Depth,
32        key: &Key,
33    ) -> Result<(NodePtrRef, bool, Option<Value>)> {
34        let node_ref = self
35            .cache
36            .borrow_mut()
37            .deref_node_ptr(ptr.clone(), Some(FetcherSyncGet::new(key, true)))?;
38
39        match classify_noderef!(?node_ref) {
40            NodeKind::None => {
41                // Remove from nil node.
42                Ok((NodePointer::null_ptr(), false, None))
43            }
44            NodeKind::Internal => {
45                // Remove from internal node and recursively collapse the path, if needed.
46                let node_ref = node_ref.unwrap();
47                let (changed, old_val): (bool, Option<Value>);
48                let (remaining_leaf, remaining_left, remaining_right): (
49                    Option<NodeRef>,
50                    Option<NodeRef>,
51                    Option<NodeRef>,
52                );
53                if let NodeBox::Internal(ref mut n) = *node_ref.borrow_mut() {
54                    // Remove from internal node and recursively collapse the branch, if
55                    // needed.
56                    let bit_length = bit_depth + n.label_bit_length;
57
58                    if key.bit_length() < bit_length {
59                        // Lookup key is too short for the current n.Label, so it doesn't exist.
60                        return Ok((ptr, false, None));
61                    }
62
63                    let (new_child, c, o) = if key.bit_length() == bit_length {
64                        self._remove(n.leaf_node.clone(), bit_depth, key)?
65                    } else if key.get_bit(bit_length) {
66                        self._remove(n.right.clone(), bit_length, key)?
67                    } else {
68                        self._remove(n.left.clone(), bit_length, key)?
69                    };
70
71                    changed = c;
72                    old_val = o;
73
74                    if key.bit_length() == bit_length {
75                        n.leaf_node = new_child;
76                    } else if key.get_bit(bit_length) {
77                        n.right = new_child;
78                    } else {
79                        n.left = new_child;
80                    }
81
82                    // Fetch and check the remaining children.
83                    // NOTE: The leaf node is always included with the internal node.
84                    remaining_leaf = n.leaf_node.borrow().node.clone();
85                    remaining_left = self
86                        .cache
87                        .borrow_mut()
88                        .deref_node_ptr(n.left.clone(), Some(FetcherSyncGet::new(key, true)))?;
89                    remaining_right = self
90                        .cache
91                        .borrow_mut()
92                        .deref_node_ptr(n.right.clone(), Some(FetcherSyncGet::new(key, true)))?;
93                } else {
94                    unreachable!("node kind is Internal");
95                }
96
97                // If exactly one child including LeafNode remains, collapse it.
98                match remaining_leaf {
99                    Some(_) => match remaining_left {
100                        Some(_) => (),
101                        None => match remaining_right {
102                            None => {
103                                let nd_leaf = noderef_as!(node_ref, Internal).leaf_node.clone();
104                                noderef_as_mut!(node_ref, Internal).leaf_node =
105                                    NodePointer::null_ptr();
106                                self.cache.borrow_mut().remove_node(ptr);
107                                return Ok((nd_leaf, true, old_val));
108                            }
109                            Some(_) => (),
110                        },
111                    },
112                    None => {
113                        let mut nd_child: Option<NodeRef> = None;
114                        let mut node_ptr: NodePtrRef = NodePointer::null_ptr();
115                        let mut both_children = true;
116                        match remaining_left {
117                            Some(_) => match remaining_right {
118                                None => {
119                                    node_ptr = noderef_as!(node_ref, Internal).left.clone();
120                                    noderef_as_mut!(node_ref, Internal).left =
121                                        NodePointer::null_ptr();
122                                    nd_child = remaining_left;
123                                    both_children = false;
124                                }
125                                Some(_) => (),
126                            },
127                            None => match remaining_right {
128                                None => (),
129                                Some(_) => {
130                                    node_ptr = noderef_as!(node_ref, Internal).right.clone();
131                                    noderef_as_mut!(node_ref, Internal).right =
132                                        NodePointer::null_ptr();
133                                    nd_child = remaining_right;
134                                    both_children = false;
135                                }
136                            },
137                        }
138
139                        if !both_children {
140                            // If child is an internal node, also fix the label.
141                            if let Some(nd_child) = nd_child {
142                                if let NodeKind::Internal = classify_noderef!(nd_child) {
143                                    if let NodeBox::Internal(ref mut inode) = *nd_child.borrow_mut()
144                                    {
145                                        inode.label = noderef_as!(node_ref, Internal).label.merge(
146                                            noderef_as!(node_ref, Internal).label_bit_length,
147                                            &inode.label,
148                                            inode.label_bit_length,
149                                        );
150                                        inode.label_bit_length +=
151                                            noderef_as!(node_ref, Internal).label_bit_length;
152                                        inode.clean = false;
153                                        node_ptr.borrow_mut().clean = false;
154                                    }
155                                }
156                            }
157
158                            self.cache.borrow_mut().remove_node(ptr);
159                            return Ok((node_ptr, true, old_val));
160                        }
161                    }
162                };
163
164                // Two or more children including leaf_node remain, just mark dirty bit.
165                if changed {
166                    noderef_as_mut!(node_ref, Internal).clean = false;
167                    ptr.borrow_mut().clean = false;
168                    // No longer eligible for eviction as it is dirty.
169                    self.cache
170                        .borrow_mut()
171                        .rollback_node(ptr.clone(), NodeKind::Internal);
172                }
173
174                Ok((ptr, changed, old_val))
175            }
176            NodeKind::Leaf => {
177                // Remove from leaf node.
178                let node_ref = node_ref.unwrap();
179                if noderef_as!(node_ref, Leaf).key == *key {
180                    let old_val = noderef_as!(node_ref, Leaf).value.clone();
181                    self.cache.borrow_mut().remove_node(ptr);
182                    return Ok((NodePointer::null_ptr(), true, Some(old_val)));
183                }
184
185                Ok((ptr, false, None))
186            }
187        }
188    }
189}
oasis_core_runtime/storage/mkvs/tree/remove.rs

oasis_core_runtime/storage/mkvs/tree/
remove.rs
