tetsy_trie_db/nibble/
mod.rs

1// Copyright 2019 Parity Technologies
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! Nibble oriented methods.
16
17use crate::node::NodeKey;
18use crate::rstd::cmp;
19
20pub use self::leftnibbleslice::LeftNibbleSlice;
21
22mod nibblevec;
23mod nibbleslice;
24mod leftnibbleslice;
25
26/// Utility methods to work on radix 16 nibble.
27pub mod nibble_ops {
28	use super::*;
29
30	/// Single nibble length in bit.
31	pub const BIT_PER_NIBBLE : usize = 4;
32	/// Number of nibble per byte.
33	pub const NIBBLE_PER_BYTE : usize = 2;
34	/// Number of child for a branch (trie radix).
35	pub const NIBBLE_LENGTH : usize = 16;
36	/// Nibble (half a byte).
37	pub const PADDING_BITMASK: u8 = 0x0F;
38	/// Size of header.
39	pub const CONTENT_HEADER_SIZE: u8 = 1;
40
41	/// Mask a byte, keeping left nibble.
42	#[inline(always)]
43	pub fn pad_left(b: u8) -> u8 {
44		b & !PADDING_BITMASK
45	}
46
47	/// Mask a byte, keeping right byte.
48	#[inline(always)]
49	pub fn pad_right(b: u8) -> u8 {
50		b & PADDING_BITMASK
51	}
52
53	/// Get u8 nibble value at a given index of a byte.
54	#[inline(always)]
55	pub fn at_left(ix: u8, b: u8) -> u8 {
56		if ix == 1 {
57			b & PADDING_BITMASK
58		} else {
59			b >> BIT_PER_NIBBLE
60		}
61	}
62
63	/// Get u8 nibble value at a given index in a left aligned array.
64	#[inline(always)]
65	pub fn left_nibble_at(v1: &[u8], ix: usize) -> u8 {
66		at_left(
67			(ix % NIBBLE_PER_BYTE) as u8,
68			v1[ix / NIBBLE_PER_BYTE]
69		)
70	}
71
72	/// Get u8 nibble value at a given index in a `NibbleSlice`.
73	#[inline(always)]
74	pub fn at(s: &NibbleSlice, i: usize) -> u8 {
75		let ix = (s.offset + i) / NIBBLE_PER_BYTE;
76		let pad = (s.offset + i) % NIBBLE_PER_BYTE;
77		at_left(pad as u8, s.data[ix])
78	}
79
80	/// Push u8 nibble value at a given index into an existing byte.
81	#[inline(always)]
82	pub fn push_at_left(ix: u8, v: u8, into: u8) -> u8 {
83		into | if ix == 1 {
84			v
85		} else {
86			v << BIT_PER_NIBBLE
87		}
88	}
89
90	#[inline]
91	/// Calculate the number of needed padding a array of nibble length `i`.
92	pub fn number_padding(i: usize) -> usize {
93		i % NIBBLE_PER_BYTE
94	}
95
96	/// The nibble shifts needed to align.
97	/// We use two value, one is a left shift and
98	/// the other is a right shift.
99	pub const SPLIT_SHIFTS: (usize, usize) = (4, 4);
100
101	/// Count the biggest common depth between two left aligned packed nibble slice.
102	pub fn biggest_depth(v1: &[u8], v2: &[u8]) -> usize {
103		let upper_bound = cmp::min(v1.len(), v2.len());
104		for a in 0 .. upper_bound {
105			if v1[a] != v2[a] {
106				return a * NIBBLE_PER_BYTE + left_common(v1[a], v2[a]);
107			}
108		}
109		upper_bound * NIBBLE_PER_BYTE
110	}
111
112	/// Calculate the number of common nibble between two left aligned bytes.
113	#[inline(always)]
114	pub fn left_common(a: u8, b: u8) -> usize {
115		if a == b {
116			2
117		} else if pad_left(a) == pad_left(b) {
118			1
119		} else {
120			0
121		}
122	}
123
124	/// Shifts right aligned key to add a given left offset.
125	/// Resulting in possibly padding at both left and right
126	/// (example usage when combining two keys).
127	pub fn shift_key(key: &mut NodeKey, offset: usize) -> bool {
128		let old_offset = key.0;
129		key.0 = offset;
130		if old_offset > offset {
131			// shift left
132			let (s1, s2) = nibble_ops::SPLIT_SHIFTS;
133			let kl = key.1.len();
134			(0..kl - 1).for_each(|i| key.1[i] = key.1[i] << s2 | key.1[i+1] >> s1);
135			key.1[kl - 1] = key.1[kl - 1] << s2;
136			true
137		} else if old_offset < offset {
138			// shift right
139			let (s1, s2) = nibble_ops::SPLIT_SHIFTS;
140			key.1.push(0);
141			(1..key.1.len()).rev().for_each(|i| key.1[i] = key.1[i - 1] << s1 | key.1[i] >> s2);
142			key.1[0] = key.1[0] >> s2;
143			true
144		} else {
145			false
146		}
147	}
148
149}
150
151/// Backing storage for `NibbleVec`s.
152pub(crate) type BackingByteVec = smallvec::SmallVec<[u8; 36]>;
153
154/// Owning, nibble-oriented byte vector. Counterpart to `NibbleSlice`.
155/// Nibbles are always left aligned, so making a `NibbleVec` from
156/// a `NibbleSlice` can get costy.
157#[cfg_attr(feature = "std", derive(Debug))]
158#[derive(Clone, PartialEq, Eq)]
159pub struct NibbleVec {
160	inner: BackingByteVec,
161	len: usize,
162}
163
164/// Nibble-orientated view onto byte-slice, allowing nibble-precision offsets.
165///
166/// This is an immutable struct. No operations actually change it.
167///
168/// # Example
169/// ```snippet
170/// use patricia_trie::nibbleslice::NibbleSlice;
171/// fn main() {
172///   let d1 = &[0x01u8, 0x23, 0x45];
173///   let d2 = &[0x34u8, 0x50, 0x12];
174///   let d3 = &[0x00u8, 0x12];
175///   let n1 = NibbleSlice::new(d1);			// 0,1,2,3,4,5
176///   let n2 = NibbleSlice::new(d2);			// 3,4,5,0,1,2
177///   let n3 = NibbleSlice::new_offset(d3, 1);	// 0,1,2
178///   assert!(n1 > n3);							// 0,1,2,... > 0,1,2
179///   assert!(n1 < n2);							// 0,... < 3,...
180///   assert!(n2.mid(3) == n3);					// 0,1,2 == 0,1,2
181///   assert!(n1.starts_with(&n3));
182///   assert_eq!(n1.common_prefix(&n3), 3);
183///   assert_eq!(n2.mid(3).common_prefix(&n1), 3);
184/// }
185/// ```
186#[derive(Copy, Clone)]
187pub struct NibbleSlice<'a> {
188	data: &'a [u8],
189	offset: usize,
190}
191
192/// Iterator type for a nibble slice.
193pub struct NibbleSliceIterator<'a> {
194	p: &'a NibbleSlice<'a>,
195	i: usize,
196}
197
tetsy_trie_db/nibble/mod.rs

tetsy_trie_db/nibble/
mod.rs
