/rust/registry/src/index.crates.io-1949cf8c6b5b557f/radix_trie-0.3.0/src/keys.rs

Source
use endian_type::{BigEndian, LittleEndian};
use nibble_vec::Nibblet;
use std::path::{Path, PathBuf};

/// Trait for types which can be used to key a Radix Trie.
///
/// Types that implement this trait should be convertible to a vector of half-bytes (nibbles)
/// such that no two instances of the type convert to the same vector.
/// To protect against faulty behaviour, the trie will **panic** if it finds two distinct keys
/// of type `K` which encode to the same `Nibblet`, so be careful!
///
/// If you would like to implement this trait for your own type, you need to implement
/// *either* `encode_bytes` or `encode`. You only need to implement one of the two.
/// If you don't implement one, your code will **panic** as soon you use the trie.
/// There is no performance penalty for implementing `encode_bytes` instead of `encode`,
/// so it is preferred except in the case where you require half-byte precision.
///
/// Many standard types implement this trait already. Integer types are encoded *big-endian*
/// by default but can be encoded little-endian using the `LittleEndian<T>` wrapper type.
pub trait TrieKey: PartialEq + Eq {
    /// Encode a value as a vector of bytes.
    fn encode_bytes(&self) -> Vec<u8> {
        panic!("implement this method or TrieKey::encode");
    }

    /// Encode a value as a NibbleVec.
    #[inline]
    fn encode(&self) -> Nibblet {
        Nibblet::from_byte_vec(self.encode_bytes())
    }
}

/// Key comparison result.
#[derive(Debug)]
pub enum KeyMatch {
    /// The keys match up to the given index.
    Partial(usize),
    /// The first key is a prefix of the second.
    FirstPrefix,
    /// The second key is a prefix of the first.
    SecondPrefix,
    /// The keys match exactly.
    Full,
}

/// Compare two Trie keys.
///
/// Compares `first[start_idx .. ]` to `second`, i.e. only looks at a slice of the first key.
#[inline]
pub fn match_keys(start_idx: usize, first: &Nibblet, second: &Nibblet) -> KeyMatch {
    let first_len = first.len() - start_idx;
    let min_length = ::std::cmp::min(first_len, second.len());

    for i in 0..min_length {
        if first.get(start_idx + i) != second.get(i) {
            return KeyMatch::Partial(i);
        }
    }

    match (first_len, second.len()) {
        (x, y) if x < y => KeyMatch::FirstPrefix,
        (x, y) if x == y => KeyMatch::Full,
        _ => KeyMatch::SecondPrefix,
    }
}

/// Check two keys for equality and panic if they differ.
#[inline]
pub fn check_keys<K: ?Sized>(key1: &K, key2: &K)
where
    K: TrieKey,
{
    if *key1 != *key2 {
        panic!("multiple-keys with the same bit representation.");
    }
}

// --- TrieKey Implementations for standard types --- ///

// This blanket implementation goes into play when specialization is stabilized
// impl<T> TrieKey for T where T: Into<Vec<u8>> + Clone + Eq + PartialEq {
// fn encode_bytes(&self) -> Vec<u8> {
// self.clone().into()
// }
// }

impl TrieKey for Vec<u8> {
    #[inline]
    fn encode_bytes(&self) -> Vec<u8> {
        self.clone()
    }
}

impl TrieKey for [u8] {
    #[inline]
    fn encode_bytes(&self) -> Vec<u8> {
        self.to_vec()
    }
}

impl TrieKey for String {
    #[inline]
    fn encode_bytes(&self) -> Vec<u8> {
        self.as_bytes().encode_bytes()
    }
}

impl TrieKey for str {
    #[inline]
    fn encode_bytes(&self) -> Vec<u8> {
        self.as_bytes().encode_bytes()
    }
}

impl<T: ?Sized + TrieKey> TrieKey for &T {
    #[inline]
    fn encode_bytes(&self) -> Vec<u8> {
        (**self).encode_bytes()
    }
}

impl<T: ?Sized + TrieKey> TrieKey for &mut T {
    #[inline]
    fn encode_bytes(&self) -> Vec<u8> {
        (**self).encode_bytes()
    }
}

impl TrieKey for i8 {
    #[inline]
    fn encode_bytes(&self) -> Vec<u8> {
        let mut v: Vec<u8> = Vec::with_capacity(1);
        v.push(*self as u8);
        v
    }
}

impl TrieKey for u8 {
    #[inline]
    fn encode_bytes(&self) -> Vec<u8> {
        let mut v: Vec<u8> = Vec::with_capacity(1);
        v.push(*self);
        v
    }
}

#[cfg(unix)]
impl TrieKey for PathBuf {
    fn encode_bytes(&self) -> Vec<u8> {
        use std::ffi::OsString;
        use std::os::unix::ffi::OsStringExt;
        let str: OsString = self.clone().into();
        str.into_vec()
    }
}

#[cfg(unix)]
impl TrieKey for Path {
    fn encode_bytes(&self) -> Vec<u8> {
        use std::os::unix::ffi::OsStrExt;
        self.as_os_str().as_bytes().encode_bytes()
    }
}

#[cfg(windows)]
impl TrieKey for PathBuf {
    fn encode_bytes(&self) -> Vec<u8> {
        self.as_os_str().as_encoded_bytes().to_vec()
    }
}

#[cfg(windows)]
impl TrieKey for Path {
    fn encode_bytes(&self) -> Vec<u8> {
        self.as_os_str().as_encoded_bytes().to_vec()
    }
}

impl<T> TrieKey for LittleEndian<T>
where
    T: Eq + Copy,
{
    fn encode_bytes(&self) -> Vec<u8> {
        self.as_byte_slice().encode_bytes()
    }
}

impl<T> TrieKey for BigEndian<T>
where
    T: Eq + Copy,
{
    fn encode_bytes(&self) -> Vec<u8> {
        self.as_byte_slice().to_vec()
    }
}

macro_rules! int_keys {
    ( $( $t:ty ),* ) => {
        $(
        impl TrieKey for $t {
            fn encode_bytes(&self) -> Vec<u8> {
                let be: BigEndian<$t> = From::from(*self);
                be.encode_bytes()
            }
        }
        )*
    };
}

int_keys!(u16, u32, u64, i16, i32, i64, usize, isize);

macro_rules! vec_int_keys {
  ( $( $t:ty ),* ) => {
      $(
      impl TrieKey for Vec<$t> {
          fn encode_bytes(&self) -> Vec<u8> {
              let mut v = Vec::<u8>::with_capacity(self.len() * std::mem::size_of::<$t>());
              for u in self {
                  v.extend_from_slice(&u.to_be_bytes());
              }
              v
          }
      }
      )*
   };
}

vec_int_keys!(u16, u32, u64, i16, i32, i64, usize, isize);

#[cfg(test)]
mod test {
    pub trait DefaultTrieKey {
        fn encode_bytes(&self) -> Vec<u8>;
    }

    impl<T: Into<Vec<u8>> + Clone + PartialEq + Eq> DefaultTrieKey for T {
        #[inline]
        fn encode_bytes(&self) -> Vec<u8> {
            self.clone().into()
        }
    }

    macro_rules! encode_bytes {
        ($e:expr) => {
            (&$e).encode_bytes()
        };
    }

    #[test]
    fn test_autoref_specialization() {
        let _ = encode_bytes!([0_u8]);
        let _ = encode_bytes!("hello");
        let _ = encode_bytes!("hello".to_string());
    }
}

Coverage Report

Created: 2026-03-31 07:09

Line	Count	Source
1		use endian_type::{BigEndian, LittleEndian};
2		use nibble_vec::Nibblet;
3		use std::path::{Path, PathBuf};
4
5		/// Trait for types which can be used to key a Radix Trie.
6		///
7		/// Types that implement this trait should be convertible to a vector of half-bytes (nibbles)
8		/// such that no two instances of the type convert to the same vector.
9		/// To protect against faulty behaviour, the trie will panic if it finds two distinct keys
10		/// of type `K` which encode to the same `Nibblet`, so be careful!
11		///
12		/// If you would like to implement this trait for your own type, you need to implement
13		/// either `encode_bytes` or `encode`. You only need to implement one of the two.
14		/// If you don't implement one, your code will panic as soon you use the trie.
15		/// There is no performance penalty for implementing `encode_bytes` instead of `encode`,
16		/// so it is preferred except in the case where you require half-byte precision.
17		///
18		/// Many standard types implement this trait already. Integer types are encoded big-endian
19		/// by default but can be encoded little-endian using the `LittleEndian<T>` wrapper type.
20		pub trait TrieKey: PartialEq + Eq {
21		/// Encode a value as a vector of bytes.
22	0	fn encode_bytes(&self) -> Vec<u8> {
23	0	panic!("implement this method or TrieKey::encode");
24		}
25
26		/// Encode a value as a NibbleVec.
27		#[inline]
28	0	fn encode(&self) -> Nibblet {
29	0	Nibblet::from_byte_vec(self.encode_bytes())
30	0	} Unexecuted instantiation: <alloc::vec::Vec<u8> as radix_trie::keys::TrieKey>::encode Unexecuted instantiation: <_ as radix_trie::keys::TrieKey>::encode
31		}
32
33		/// Key comparison result.
34		#[derive(Debug)]
35		pub enum KeyMatch {
36		/// The keys match up to the given index.
37		Partial(usize),
38		/// The first key is a prefix of the second.
39		FirstPrefix,
40		/// The second key is a prefix of the first.
41		SecondPrefix,
42		/// The keys match exactly.
43		Full,
44		}
45
46		/// Compare two Trie keys.
47		///
48		/// Compares `first[start_idx .. ]` to `second`, i.e. only looks at a slice of the first key.
49		#[inline]
50	0	pub fn match_keys(start_idx: usize, first: &Nibblet, second: &Nibblet) -> KeyMatch {
51	0	let first_len = first.len() - start_idx;
52	0	let min_length = ::std::cmp::min(first_len, second.len());
53
54	0	for i in 0..min_length {
55	0	if first.get(start_idx + i) != second.get(i) {
56	0	return KeyMatch::Partial(i);
57	0	}
58		}
59
60	0	match (first_len, second.len()) {
61	0	(x, y) if x < y => KeyMatch::FirstPrefix,
62	0	(x, y) if x == y => KeyMatch::Full,
63	0	_ => KeyMatch::SecondPrefix,
64		}
65	0	} Unexecuted instantiation: radix_trie::keys::match_keys Unexecuted instantiation: radix_trie::keys::match_keys
66
67		/// Check two keys for equality and panic if they differ.
68		#[inline]
69	0	pub fn check_keys<K: ?Sized>(key1: &K, key2: &K)
70	0	where
71	0	K: TrieKey,
72		{
73	0	if key1 != key2 {
74	0	panic!("multiple-keys with the same bit representation.");
75	0	}
76	0	} Unexecuted instantiation: radix_trie::keys::check_keys::<alloc::vec::Vec<u8>> Unexecuted instantiation: radix_trie::keys::check_keys::<_>
77
78		// --- TrieKey Implementations for standard types --- ///
79
80		// This blanket implementation goes into play when specialization is stabilized
81		// impl<T> TrieKey for T where T: Into<Vec<u8>> + Clone + Eq + PartialEq {
82		// fn encode_bytes(&self) -> Vec<u8> {
83		// self.clone().into()
84		// }
85		// }
86
87		impl TrieKey for Vec<u8> {
88		#[inline]
89	0	fn encode_bytes(&self) -> Vec<u8> {
90	0	self.clone()
91	0	} Unexecuted instantiation: <alloc::vec::Vec<u8> as radix_trie::keys::TrieKey>::encode_bytes Unexecuted instantiation: <alloc::vec::Vec<u8> as radix_trie::keys::TrieKey>::encode_bytes
92		}
93
94		impl TrieKey for [u8] {
95		#[inline]
96	0	fn encode_bytes(&self) -> Vec<u8> {
97	0	self.to_vec()
98	0	}
99		}
100
101		impl TrieKey for String {
102		#[inline]
103	0	fn encode_bytes(&self) -> Vec<u8> {
104	0	self.as_bytes().encode_bytes()
105	0	}
106		}
107
108		impl TrieKey for str {
109		#[inline]
110	0	fn encode_bytes(&self) -> Vec<u8> {
111	0	self.as_bytes().encode_bytes()
112	0	}
113		}
114
115		impl<T: ?Sized + TrieKey> TrieKey for &T {
116		#[inline]
117	0	fn encode_bytes(&self) -> Vec<u8> {
118	0	(**self).encode_bytes()
119	0	}
120		}
121
122		impl<T: ?Sized + TrieKey> TrieKey for &mut T {
123		#[inline]
124	0	fn encode_bytes(&self) -> Vec<u8> {
125	0	(**self).encode_bytes()
126	0	}
127		}
128
129		impl TrieKey for i8 {
130		#[inline]
131	0	fn encode_bytes(&self) -> Vec<u8> {
132	0	let mut v: Vec<u8> = Vec::with_capacity(1);
133	0	v.push(*self as u8);
134	0	v
135	0	}
136		}
137
138		impl TrieKey for u8 {
139		#[inline]
140	0	fn encode_bytes(&self) -> Vec<u8> {
141	0	let mut v: Vec<u8> = Vec::with_capacity(1);
142	0	v.push(*self);
143	0	v
144	0	}
145		}
146
147		#[cfg(unix)]
148		impl TrieKey for PathBuf {
149	0	fn encode_bytes(&self) -> Vec<u8> {
150		use std::ffi::OsString;
151		use std::os::unix::ffi::OsStringExt;
152	0	let str: OsString = self.clone().into();
153	0	str.into_vec()
154	0	}
155		}
156
157		#[cfg(unix)]
158		impl TrieKey for Path {
159	0	fn encode_bytes(&self) -> Vec<u8> {
160		use std::os::unix::ffi::OsStrExt;
161	0	self.as_os_str().as_bytes().encode_bytes()
162	0	}
163		}
164
165		#[cfg(windows)]
166		impl TrieKey for PathBuf {
167		fn encode_bytes(&self) -> Vec<u8> {
168		self.as_os_str().as_encoded_bytes().to_vec()
169		}
170		}
171
172		#[cfg(windows)]
173		impl TrieKey for Path {
174		fn encode_bytes(&self) -> Vec<u8> {
175		self.as_os_str().as_encoded_bytes().to_vec()
176		}
177		}
178
179		impl<T> TrieKey for LittleEndian<T>
180		where
181		T: Eq + Copy,
182		{
183	0	fn encode_bytes(&self) -> Vec<u8> {
184	0	self.as_byte_slice().encode_bytes()
185	0	}
186		}
187
188		impl<T> TrieKey for BigEndian<T>
189		where
190		T: Eq + Copy,
191		{
192	0	fn encode_bytes(&self) -> Vec<u8> {
193	0	self.as_byte_slice().to_vec()
194	0	} Unexecuted instantiation: <endian_type::BigEndian<isize> as radix_trie::keys::TrieKey>::encode_bytes Unexecuted instantiation: <endian_type::BigEndian<usize> as radix_trie::keys::TrieKey>::encode_bytes Unexecuted instantiation: <endian_type::BigEndian<i32> as radix_trie::keys::TrieKey>::encode_bytes Unexecuted instantiation: <endian_type::BigEndian<u32> as radix_trie::keys::TrieKey>::encode_bytes Unexecuted instantiation: <endian_type::BigEndian<i16> as radix_trie::keys::TrieKey>::encode_bytes Unexecuted instantiation: <endian_type::BigEndian<u16> as radix_trie::keys::TrieKey>::encode_bytes Unexecuted instantiation: <endian_type::BigEndian<i64> as radix_trie::keys::TrieKey>::encode_bytes Unexecuted instantiation: <endian_type::BigEndian<u64> as radix_trie::keys::TrieKey>::encode_bytes
195		}
196
197		macro_rules! int_keys {
198		( $( $t:ty ),* ) => {
199		$(
200		impl TrieKey for $t {
201	0	fn encode_bytes(&self) -> Vec<u8> {
202	0	let be: BigEndian<$t> = From::from(*self);
203	0	be.encode_bytes()
204	0	} Unexecuted instantiation: <u16 as radix_trie::keys::TrieKey>::encode_bytes Unexecuted instantiation: <u32 as radix_trie::keys::TrieKey>::encode_bytes Unexecuted instantiation: <u64 as radix_trie::keys::TrieKey>::encode_bytes Unexecuted instantiation: <i16 as radix_trie::keys::TrieKey>::encode_bytes Unexecuted instantiation: <i32 as radix_trie::keys::TrieKey>::encode_bytes Unexecuted instantiation: <i64 as radix_trie::keys::TrieKey>::encode_bytes Unexecuted instantiation: <usize as radix_trie::keys::TrieKey>::encode_bytes Unexecuted instantiation: <isize as radix_trie::keys::TrieKey>::encode_bytes
205		}
206		)*
207		};
208		}
209
210		int_keys!(u16, u32, u64, i16, i32, i64, usize, isize);
211
212		macro_rules! vec_int_keys {
213		( $( $t:ty ),* ) => {
214		$(
215		impl TrieKey for Vec<$t> {
216	0	fn encode_bytes(&self) -> Vec<u8> {
217	0	let mut v = Vec::<u8>::with_capacity(self.len() * std::mem::size_of::<$t>());
218	0	for u in self {
219	0	v.extend_from_slice(&u.to_be_bytes());
220	0	}
221	0	v
222	0	} Unexecuted instantiation: <alloc::vec::Vec<u16> as radix_trie::keys::TrieKey>::encode_bytes Unexecuted instantiation: <alloc::vec::Vec<u32> as radix_trie::keys::TrieKey>::encode_bytes Unexecuted instantiation: <alloc::vec::Vec<u64> as radix_trie::keys::TrieKey>::encode_bytes Unexecuted instantiation: <alloc::vec::Vec<i16> as radix_trie::keys::TrieKey>::encode_bytes Unexecuted instantiation: <alloc::vec::Vec<i32> as radix_trie::keys::TrieKey>::encode_bytes Unexecuted instantiation: <alloc::vec::Vec<i64> as radix_trie::keys::TrieKey>::encode_bytes Unexecuted instantiation: <alloc::vec::Vec<usize> as radix_trie::keys::TrieKey>::encode_bytes Unexecuted instantiation: <alloc::vec::Vec<isize> as radix_trie::keys::TrieKey>::encode_bytes
223		}
224		)*
225		};
226		}
227
228		vec_int_keys!(u16, u32, u64, i16, i32, i64, usize, isize);
229
230		#[cfg(test)]
231		mod test {
232		pub trait DefaultTrieKey {
233		fn encode_bytes(&self) -> Vec<u8>;
234		}
235
236		impl<T: Into<Vec<u8>> + Clone + PartialEq + Eq> DefaultTrieKey for T {
237		#[inline]
238		fn encode_bytes(&self) -> Vec<u8> {
239		self.clone().into()
240		}
241		}
242
243		macro_rules! encode_bytes {
244		($e:expr) => {
245		(&$e).encode_bytes()
246		};
247		}
248
249		#[test]
250		fn test_autoref_specialization() {
251		let _ = encode_bytes!([0_u8]);
252		let _ = encode_bytes!("hello");
253		let _ = encode_bytes!("hello".to_string());
254		}
255		}