trie_db/nibble/
leftnibbleslice.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
15use crate::rstd::cmp::{self, Ordering};
16
17use crate::nibble::{
18	nibble_ops::{self, NIBBLE_PER_BYTE},
19	NibbleSlice,
20};
21
22/// A representation of a nibble slice which is left-aligned. The regular `NibbleSlice` is
23/// right-aligned, meaning it does not support efficient truncation from the right side.
24///
25/// This is an immutable struct. No operations actually change it.
26pub struct LeftNibbleSlice<'a> {
27	bytes: &'a [u8],
28	len: usize,
29}
30
31impl<'a> LeftNibbleSlice<'a> {
32	/// Constructs a byte-aligned nibble slice from a byte slice.
33	pub fn new(bytes: &'a [u8]) -> Self {
34		LeftNibbleSlice { bytes, len: bytes.len() * NIBBLE_PER_BYTE }
35	}
36
37	/// Returns the length of the slice in nibbles.
38	pub fn len(&self) -> usize {
39		self.len
40	}
41
42	/// Get the nibble at a nibble index padding with a 0 nibble. Returns None if the index is
43	/// out of bounds.
44	pub fn at(&self, index: usize) -> Option<u8> {
45		if index < self.len() {
46			Some(nibble_ops::left_nibble_at(self.bytes, index))
47		} else {
48			None
49		}
50	}
51
52	/// Returns a new slice truncated from the right side to the given length. If the given length
53	/// is greater than that of this slice, the function just returns a copy.
54	pub fn truncate(&self, len: usize) -> Self {
55		LeftNibbleSlice { bytes: self.bytes, len: cmp::min(len, self.len) }
56	}
57
58	/// Returns whether the given slice is a prefix of this one.
59	pub fn starts_with(&self, prefix: &LeftNibbleSlice<'a>) -> bool {
60		self.truncate(prefix.len()) == *prefix
61	}
62
63	/// Returns whether another regular (right-aligned) nibble slice is contained in this one at
64	/// the given offset.
65	pub fn contains(&self, partial: &NibbleSlice, offset: usize) -> bool {
66		(0..partial.len()).all(|i| self.at(offset + i) == Some(partial.at(i)))
67	}
68
69	fn cmp(&self, other: &Self) -> Ordering {
70		let common_len = cmp::min(self.len(), other.len());
71		let common_byte_len = common_len / NIBBLE_PER_BYTE;
72
73		// Quickly compare the common prefix of the byte slices.
74		match self.bytes[..common_byte_len].cmp(&other.bytes[..common_byte_len]) {
75			Ordering::Equal => {},
76			ordering => return ordering,
77		}
78
79		// Compare nibble-by-nibble (either 0 or 1 nibbles) any after the common byte prefix.
80		for i in (common_byte_len * NIBBLE_PER_BYTE)..common_len {
81			let a = self.at(i).expect("i < len; len == self.len() qed");
82			let b = other.at(i).expect("i < len; len == other.len(); qed");
83			match a.cmp(&b) {
84				Ordering::Equal => {},
85				ordering => return ordering,
86			}
87		}
88
89		// If common nibble prefix is the same, finally compare lengths.
90		self.len().cmp(&other.len())
91	}
92}
93
94impl<'a> PartialEq for LeftNibbleSlice<'a> {
95	fn eq(&self, other: &Self) -> bool {
96		let len = self.len();
97		if other.len() != len {
98			return false
99		}
100
101		// Quickly compare the common prefix of the byte slices.
102		let byte_len = len / NIBBLE_PER_BYTE;
103		if self.bytes[..byte_len] != other.bytes[..byte_len] {
104			return false
105		}
106
107		// Compare nibble-by-nibble (either 0 or 1 nibbles) any after the common byte prefix.
108		for i in (byte_len * NIBBLE_PER_BYTE)..len {
109			let a = self.at(i).expect("i < len; len == self.len() qed");
110			let b = other.at(i).expect("i < len; len == other.len(); qed");
111			if a != b {
112				return false
113			}
114		}
115
116		true
117	}
118}
119
120impl<'a> Eq for LeftNibbleSlice<'a> {}
121
122impl<'a> PartialOrd for LeftNibbleSlice<'a> {
123	fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
124		Some(self.cmp(other))
125	}
126}
127
128impl<'a> Ord for LeftNibbleSlice<'a> {
129	fn cmp(&self, other: &Self) -> Ordering {
130		self.cmp(other)
131	}
132}
133
134#[cfg(feature = "std")]
135impl<'a> std::fmt::Debug for LeftNibbleSlice<'a> {
136	fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
137		for i in 0..self.len() {
138			let nibble = self.at(i).expect("i < self.len(); qed");
139			match i {
140				0 => write!(f, "{:01x}", nibble)?,
141				_ => write!(f, "'{:01x}", nibble)?,
142			}
143		}
144		Ok(())
145	}
146}
147
148#[cfg(test)]
149mod tests {
150	use super::*;
151
152	#[test]
153	fn test_len() {
154		assert_eq!(LeftNibbleSlice::new(&[]).len(), 0);
155		assert_eq!(LeftNibbleSlice::new(&b"hello"[..]).len(), 10);
156		assert_eq!(LeftNibbleSlice::new(&b"hello"[..]).truncate(7).len(), 7);
157	}
158
159	#[test]
160	fn test_at() {
161		let slice = LeftNibbleSlice::new(&b"\x01\x23\x45\x67"[..]).truncate(7);
162		assert_eq!(slice.at(0), Some(0));
163		assert_eq!(slice.at(6), Some(6));
164		assert_eq!(slice.at(7), None);
165		assert_eq!(slice.at(8), None);
166	}
167
168	#[test]
169	fn test_starts_with() {
170		assert!(
171			LeftNibbleSlice::new(b"hello").starts_with(&LeftNibbleSlice::new(b"heli").truncate(7))
172		);
173		assert!(
174			!LeftNibbleSlice::new(b"hello").starts_with(&LeftNibbleSlice::new(b"heli").truncate(8))
175		);
176	}
177
178	#[test]
179	fn test_contains() {
180		assert!(LeftNibbleSlice::new(b"hello").contains(&NibbleSlice::new_offset(b"ello", 0), 2));
181		assert!(LeftNibbleSlice::new(b"hello").contains(&NibbleSlice::new_offset(b"ello", 1), 3));
182		assert!(!LeftNibbleSlice::new(b"hello").contains(&NibbleSlice::new_offset(b"allo", 1), 3));
183		assert!(!LeftNibbleSlice::new(b"hello").contains(&NibbleSlice::new_offset(b"ello!", 1), 3));
184	}
185
186	#[test]
187	fn test_cmp() {
188		assert!(LeftNibbleSlice::new(b"hallo") < LeftNibbleSlice::new(b"hello"));
189		assert!(LeftNibbleSlice::new(b"hello") > LeftNibbleSlice::new(b"hallo"));
190		assert_eq!(
191			LeftNibbleSlice::new(b"hello").cmp(&LeftNibbleSlice::new(b"hello")),
192			Ordering::Equal
193		);
194
195		assert!(
196			LeftNibbleSlice::new(b"hello\x10") < LeftNibbleSlice::new(b"hello\x20").truncate(11)
197		);
198		assert!(
199			LeftNibbleSlice::new(b"hello\x20").truncate(11) > LeftNibbleSlice::new(b"hello\x10")
200		);
201
202		assert!(
203			LeftNibbleSlice::new(b"hello\x10").truncate(11) < LeftNibbleSlice::new(b"hello\x10")
204		);
205		assert!(
206			LeftNibbleSlice::new(b"hello\x10") > LeftNibbleSlice::new(b"hello\x10").truncate(11)
207		);
208		assert_eq!(
209			LeftNibbleSlice::new(b"hello\x10")
210				.truncate(11)
211				.cmp(&LeftNibbleSlice::new(b"hello\x10").truncate(11)),
212			Ordering::Equal
213		);
214	}
215}
trie_db/nibble/leftnibbleslice.rs

trie_db/nibble/
leftnibbleslice.rs
