patricia_trie/
node.rs

1// Copyright 2015-2018 Parity Technologies (UK) Ltd.
2// This file is part of Parity.
3
4// Parity is free software: you can redistribute it and/or modify
5// it under the terms of the GNU General Public License as published by
6// the Free Software Foundation, either version 3 of the License, or
7// (at your option) any later version.
8
9// Parity is distributed in the hope that it will be useful,
10// but WITHOUT ANY WARRANTY; without even the implied warranty of
11// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12// GNU General Public License for more details.
13
14// You should have received a copy of the GNU General Public License
15// along with Parity.  If not, see <http://www.gnu.org/licenses/>.
16
17use elastic_array::ElasticArray36;
18use nibbleslice::NibbleSlice;
19use nibblevec::NibbleVec;
20use super::DBValue;
21
22/// Partial node key type.
23pub type NodeKey = ElasticArray36<u8>;
24
25/// Type of node in the trie and essential information thereof.
26#[derive(Eq, PartialEq, Debug, Clone)]
27pub enum Node<'a> {
28	/// Null trie node; could be an empty root or an empty branch entry.
29	Empty,
30	/// Leaf node; has key slice and value. Value may not be empty.
31	Leaf(NibbleSlice<'a>, &'a [u8]),
32	/// Extension node; has key slice and node data. Data may not be null.
33	Extension(NibbleSlice<'a>, &'a [u8]),
34	/// Branch node; has array of 16 child nodes (each possibly null) and an optional immediate node data.
35	Branch([&'a [u8]; 16], Option<&'a [u8]>),
36}
37
38/// A Sparse (non mutable) owned vector struct to hold branch keys and value
39#[derive(Eq, PartialEq, Debug, Clone)]
40pub struct Branch {
41	data: Vec<u8>,
42	ubounds: [usize; 18],
43	has_value: bool,
44}
45
46impl Branch {
47	fn new(a: [&[u8]; 16], value: Option<&[u8]>) -> Self {
48		let mut data = Vec::with_capacity(a.iter().map(|inner| inner.len()).sum());
49		let mut ubounds = [0; 18];
50		for (inner, ub) in a.iter().zip(ubounds.iter_mut().skip(1)) {
51			data.extend_from_slice(inner);
52			*ub = data.len();
53		}
54		if let Some(value) = value {
55			data.extend(value);
56			ubounds[17] = data.len();
57		}
58		Branch { data, ubounds, has_value: value.is_some() }
59	}
60
61	/// Get the node value, if any
62	pub fn get_value(&self) -> Option<&[u8]> {
63		if self.has_value {
64			Some(&self.data[self.ubounds[16]..self.ubounds[17]])
65		} else {
66			None
67		}
68	}
69
70	/// Test if the node has a value
71	pub fn has_value(&self) -> bool {
72		self.has_value
73	}
74}
75
76impl ::std::ops::Index<usize> for Branch {
77	type Output = [u8];
78	fn index(&self, index: usize) -> &[u8] {
79		assert!(index < 16);
80		&self.data[self.ubounds[index]..self.ubounds[index + 1]]
81	}
82}
83
84/// An owning node type. Useful for trie iterators.
85#[derive(Debug, PartialEq, Eq)]
86pub enum OwnedNode {
87	/// Empty trie node.
88	Empty,
89	/// Leaf node: partial key and value.
90	Leaf(NibbleVec, DBValue),
91	/// Extension node: partial key and child node.
92	Extension(NibbleVec, DBValue),
93	/// Branch node: 16 children and an optional value.
94	Branch(Branch),
95}
96
97impl<'a> From<Node<'a>> for OwnedNode {
98	fn from(node: Node<'a>) -> Self {
99		match node {
100			Node::Empty => OwnedNode::Empty,
101			Node::Leaf(k, v) => OwnedNode::Leaf(k.into(), DBValue::from_slice(v)),
102			Node::Extension(k, child) => OwnedNode::Extension(k.into(), DBValue::from_slice(child)),
103			Node::Branch(c, val) => OwnedNode::Branch(Branch::new(c, val)),
104		}
105	}
106}
patricia_trie/node.rs

patricia_trie/
node.rs
