fides/structs/radix_tree/
split_node.rs

1
2use astro_format::IntoBytes;
3use std::error::Error;
4use super::{RadixTree, RadixNode};
5
6impl<K, V> RadixTree<K, V>
7where
8    K: Eq + std::hash::Hash + Clone + std::cmp::Ord + IntoBytes,
9    V: Clone + IntoBytes,
10{
11    pub fn split_node(&mut self, node_hash: [u8; 32], split_position: usize) -> Result<([u8; 32], [u8; 32]), Box<dyn Error>> {
12
13        if let Some(old_node) = self.nodes.remove(&node_hash) {
14
15            if split_position < old_node.key.len() {
16                
17                let (left_key_part, right_key_part) = old_node.key.split_at(split_position);
18
19                let right_node = RadixNode {
20                    key: right_key_part[1..].to_vec(),
21                    children: old_node.children,
22                    value: old_node.value,
23                };
24
25                let right_node_hash = right_node.hash();
26
27                for child_hash in right_node.children.values() {
28                    self.parents.insert(*child_hash, right_node_hash);
29                }
30
31                self.nodes.insert(right_node_hash, right_node);
32                
33                let mut left_node = RadixNode::new();
34
35                left_node.key = left_key_part.to_vec();
36
37                left_node.children.insert(right_key_part[0].clone(), right_node_hash);
38
39                let left_node_hash = left_node.hash();
40
41                self.nodes.insert(left_node_hash, left_node);
42
43                if self.root == node_hash {
44                    self.root = left_node_hash;
45                }
46
47                // Link the left node to the original node's parent
48                if let Some(parent_hash) = self.parents.remove(&node_hash) {
49                    self.parents.insert(left_node_hash, parent_hash);
50                    if let Some(parent) = self.nodes.get_mut(&parent_hash) {
51                        parent.children.insert(left_key_part[0].clone(), left_node_hash);
52                    }
53                }
54
55                // Set the parent of the right node to be the new left node
56                self.parents.insert(right_node_hash, left_node_hash);
57
58                return Ok((left_node_hash, right_node_hash))
59            } else {
60                Err("Node can't be split")?
61            }
62        } else {
63            Err("Node doesn't exist!")?
64        }
65    }
66
67}
fides/structs/radix_tree/split_node.rs

fides/structs/radix_tree/
split_node.rs
