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(_) => {
100                        if remaining_left.is_none() && remaining_right.is_none() {
101                            let nd_leaf = noderef_as!(node_ref, Internal).leaf_node.clone();
102                            noderef_as_mut!(node_ref, Internal).leaf_node = NodePointer::null_ptr();
103                            self.cache.borrow_mut().remove_node(ptr);
104                            return Ok((nd_leaf, true, old_val));
105                        }
106                    }
107                    None => {
108                        let mut nd_child: Option<NodeRef> = None;
109                        let mut node_ptr: NodePtrRef = NodePointer::null_ptr();
110                        let mut both_children = true;
111                        match remaining_left {
112                            Some(_) => {
113                                if remaining_right.is_none() {
114                                    node_ptr = noderef_as!(node_ref, Internal).left.clone();
115                                    noderef_as_mut!(node_ref, Internal).left =
116                                        NodePointer::null_ptr();
117                                    nd_child = remaining_left;
118                                    both_children = false;
119                                }
120                            }
121                            None => {
122                                if remaining_right.is_some() {
123                                    node_ptr = noderef_as!(node_ref, Internal).right.clone();
124                                    noderef_as_mut!(node_ref, Internal).right =
125                                        NodePointer::null_ptr();
126                                    nd_child = remaining_right;
127                                    both_children = false;
128                                }
129                            }
130                        }
131
132                        if !both_children {
133                            // If child is an internal node, also fix the label.
134                            if let Some(nd_child) = nd_child {
135                                if let NodeKind::Internal = classify_noderef!(nd_child) {
136                                    if let NodeBox::Internal(ref mut inode) = *nd_child.borrow_mut()
137                                    {
138                                        inode.label = noderef_as!(node_ref, Internal).label.merge(
139                                            noderef_as!(node_ref, Internal).label_bit_length,
140                                            &inode.label,
141                                            inode.label_bit_length,
142                                        );
143                                        inode.label_bit_length +=
144                                            noderef_as!(node_ref, Internal).label_bit_length;
145                                        inode.clean = false;
146                                        node_ptr.borrow_mut().clean = false;
147                                    }
148                                }
149                            }
150
151                            self.cache.borrow_mut().remove_node(ptr);
152                            return Ok((node_ptr, true, old_val));
153                        }
154                    }
155                };
156
157                // Two or more children including leaf_node remain, just mark dirty bit.
158                if changed {
159                    noderef_as_mut!(node_ref, Internal).clean = false;
160                    ptr.borrow_mut().clean = false;
161                    // No longer eligible for eviction as it is dirty.
162                    self.cache
163                        .borrow_mut()
164                        .rollback_node(ptr.clone(), NodeKind::Internal);
165                }
166
167                Ok((ptr, changed, old_val))
168            }
169            NodeKind::Leaf => {
170                // Remove from leaf node.
171                let node_ref = node_ref.unwrap();
172                if noderef_as!(node_ref, Leaf).key == *key {
173                    let old_val = noderef_as!(node_ref, Leaf).value.clone();
174                    self.cache.borrow_mut().remove_node(ptr);
175                    return Ok((NodePointer::null_ptr(), true, Some(old_val)));
176                }
177
178                Ok((ptr, false, None))
179            }
180        }
181    }
182}
oasis_core_runtime/storage/mkvs/tree/remove.rs

oasis_core_runtime/storage/mkvs/tree/
remove.rs
