hash_trie/
traits.rs

1use crate::result::BitError;
2use alloc::fmt::Debug;
3use core::{convert::{TryFrom, TryInto}, hash::{Hash, Hasher}, mem, ops::*};
4
5macro_rules! bit_count_one {
6    ( $bit:expr) => {
7        if $bit.count_ones() != 1 {
8            return Err(BitError::CountNotEqualToOne);
9        }
10    };
11}
12
13macro_rules! bit_found {
14    ( $self:expr, $bit:expr) => {
15        bit_count_one!($bit);
16        if $self & $bit == 0 {
17            return Err(BitError::NotFound);
18        }
19    };
20}
21
22macro_rules! bit_not_found {
23    ( $self:expr, $bit:expr) => {
24        bit_count_one!($bit);
25        if $self & $bit == 1 {
26            return Err(BitError::Found);
27        }
28    };
29}
30
31macro_rules! bit_in_range {
32    ( $type:ty, $index:expr) => {
33        if $index >= <$type>::max_ones() {
34            return Err(BitError::Range);
35        }
36    };
37}
38
39/// `AsUsize` supports conversion to usize for values within the word's index range.
40pub trait AsUsize {
41    /// Simply cast or convert the value to a usize.
42    #[must_use]
43    fn as_usize(&self) -> usize;
44}
45impl AsUsize for u8 { fn as_usize(&self) -> usize {*self as usize} }
46impl AsUsize for u16 { fn as_usize(&self) -> usize {*self as usize} }
47impl AsUsize for u32 { fn as_usize(&self) -> usize {*self as usize} }
48impl AsUsize for u64 { fn as_usize(&self) -> usize {*self as usize} }
49impl AsUsize for u128 { fn as_usize(&self) -> usize {*self as usize} }
50impl AsUsize for usize { fn as_usize(&self) -> usize {*self} }
51
52/// `BitContains` supports testing to see if a bit is present in the word or not.
53pub trait BitContains {
54    /// Check whether the word contains the bit or return BitError::CountNotEqualToOne if the bit is invalid.
55    /// 
56    /// e.g. `0b110110.bit_contains(0b100) == true`
57    fn bit_contains(&self, bit: Self) -> Result<bool, BitError>;
58}
59impl BitContains for u8 { fn bit_contains(&self, bit: Self) -> Result<bool, BitError> {bit_count_one!(bit); Ok((self & bit) != 0)} }
60impl BitContains for u16 { fn bit_contains(&self, bit: Self) -> Result<bool, BitError> {bit_count_one!(bit); Ok((self & bit) != 0)} }
61impl BitContains for u32 { fn bit_contains(&self, bit: Self) -> Result<bool, BitError> {bit_count_one!(bit); Ok((self & bit) != 0)} }
62impl BitContains for u64 { fn bit_contains(&self, bit: Self) -> Result<bool, BitError> {bit_count_one!(bit); Ok((self & bit) != 0)} }
63impl BitContains for u128 { fn bit_contains(&self, bit: Self) -> Result<bool, BitError> {bit_count_one!(bit); Ok((self & bit) != 0)} }
64impl BitContains for usize { fn bit_contains(&self, bit: Self) -> Result<bool, BitError> {bit_count_one!(bit); Ok((self & bit) != 0)} }
65
66/// `BitIndex` supports counting less significant 1s in the word (1s to the right of the bit).
67pub trait BitIndex {
68    /// Count less significant 1s in the word (1s to the right of the bit) or return either BitError::CountNotEqualToOne or BitError::NotFound.
69    /// 
70    /// e.g. `0b110110.bit_index(0b100) == 1`
71    fn bit_index(&self, bit: Self) -> Result<usize, BitError>;
72}
73impl BitIndex for u8 { fn bit_index(&self, bit: Self) -> Result<usize, BitError> {bit_found!(self, bit); Ok((self & (bit - 1)).count_ones() as usize)} }
74impl BitIndex for u16 { fn bit_index(&self, bit: Self) -> Result<usize, BitError> {bit_found!(self, bit); Ok((self & (bit - 1)).count_ones() as usize)} }
75impl BitIndex for u32 { fn bit_index(&self, bit: Self) -> Result<usize, BitError> {bit_found!(self, bit); Ok((self & (bit - 1)).count_ones() as usize)} }
76impl BitIndex for u64 { fn bit_index(&self, bit: Self) -> Result<usize, BitError> {bit_found!(self, bit); Ok((self & (bit - 1)).count_ones() as usize)} }
77impl BitIndex for u128 { fn bit_index(&self, bit: Self) -> Result<usize, BitError> {bit_found!(self, bit); Ok((self & (bit - 1)).count_ones() as usize)} }
78impl BitIndex for usize { fn bit_index(&self, bit: Self) -> Result<usize, BitError> {bit_found!(self, bit); Ok((self & (bit - 1)).count_ones() as usize)} }
79
80/// `BitInsert` supports inserting a bit into the word.
81pub trait BitInsert {
82    /// Insert the bit into the word or return either BitError::CountNotEqualToOne or BitError::Found.
83    /// 
84    /// e.g. `0b10010.bit_insert(0b100) == 0b10110`
85    fn bit_insert(&self, bit: Self) -> Result<Self, BitError> where Self: Sized;
86}
87impl BitInsert for u8 { fn bit_insert(&self, bit: Self) -> Result<Self, BitError> {bit_not_found!(self, bit); Ok(self | bit)} }
88impl BitInsert for u16 { fn bit_insert(&self, bit: Self) -> Result<Self, BitError> {bit_not_found!(self, bit); Ok(self | bit)} }
89impl BitInsert for u32 { fn bit_insert(&self, bit: Self) -> Result<Self, BitError> {bit_not_found!(self, bit); Ok(self | bit)} }
90impl BitInsert for u64 { fn bit_insert(&self, bit: Self) -> Result<Self, BitError> {bit_not_found!(self, bit); Ok(self | bit)} }
91impl BitInsert for u128 { fn bit_insert(&self, bit: Self) -> Result<Self, BitError> {bit_not_found!(self, bit); Ok(self | bit)} }
92impl BitInsert for usize { fn bit_insert(&self, bit: Self) -> Result<Self, BitError> {bit_not_found!(self, bit); Ok(self | bit)} }
93
94/// `BitRemove` supports removing a bit from the word.
95pub trait BitRemove {
96    /// Remove the bit from the word or return either BitError::CountNotEqualToOne or BitError::NotFound.
97    /// 
98    /// e.g. `0b10110.bit_remove(0b100) == 0b10010`
99    fn bit_remove(&self, bit: Self) -> Result<Self, BitError> where Self: Sized;
100}
101impl BitRemove for u8 { fn bit_remove(&self, bit: Self) -> Result<Self, BitError> {bit_found!(self, bit); Ok(self ^ bit)} }
102impl BitRemove for u16 { fn bit_remove(&self, bit: Self) -> Result<Self, BitError> {bit_found!(self, bit); Ok(self ^ bit)} }
103impl BitRemove for u32 { fn bit_remove(&self, bit: Self) -> Result<Self, BitError> {bit_found!(self, bit); Ok(self ^ bit)} }
104impl BitRemove for u64 { fn bit_remove(&self, bit: Self) -> Result<Self, BitError> {bit_found!(self, bit); Ok(self ^ bit)} }
105impl BitRemove for u128 { fn bit_remove(&self, bit: Self) -> Result<Self, BitError> {bit_found!(self, bit); Ok(self ^ bit)} }
106impl BitRemove for usize { fn bit_remove(&self, bit: Self) -> Result<Self, BitError> {bit_found!(self, bit); Ok(self ^ bit)} }
107
108/// `CountOnes` supports counting 1s in the word. (i.e. a call to the standard `count_ones()` function)
109pub trait CountOnes {
110    /// Count the number of 1s in the word using `count_ones()`.
111    /// 
112    /// e.g. `0b10110.count_ones_t() == 3`
113    #[must_use]
114    fn count_ones_t(&self) -> usize;
115}
116impl CountOnes for u8 { fn count_ones_t(&self) -> usize {self.count_ones() as usize} }
117impl CountOnes for u16 { fn count_ones_t(&self) -> usize {self.count_ones() as usize} }
118impl CountOnes for u32 { fn count_ones_t(&self) -> usize {self.count_ones() as usize} }
119impl CountOnes for u64 { fn count_ones_t(&self) -> usize {self.count_ones() as usize} }
120impl CountOnes for u128 { fn count_ones_t(&self) -> usize {self.count_ones() as usize} }
121impl CountOnes for usize { fn count_ones_t(&self) -> usize {self.count_ones() as usize} }
122
123/// `LogB` provides log_2 of the word size.
124pub trait LogB {
125    /// Get the log_2 of the word size.
126    /// 
127    /// e.g. `u32::log_b() == 5`
128    #[must_use]
129    fn log_b() -> usize;
130}
131impl LogB for u8 { fn log_b() -> usize {3} }
132impl LogB for u16 { fn log_b() -> usize {4} }
133impl LogB for u32 { fn log_b() -> usize {5} }
134impl LogB for u64 { fn log_b() -> usize {6} }
135impl LogB for u128 { fn log_b() -> usize {7} }
136impl LogB for usize {
137    fn log_b() -> usize {
138        match mem::size_of::<usize>() {
139            1 => 3,
140            2 => 4,
141            4 => 5,
142            8 => 6,
143            16 => 7,
144            _ => panic!()
145        }
146    }
147}
148
149/// `MaskLogB` provides a mask of 1s equal to the log_2 of the word size.
150pub trait MaskLogB<T> {
151    /// Get the mask, length log_2 of the word size.
152    /// 
153    /// e.g. `u32::mask_log_b() == 0b11111`
154    #[must_use]
155    fn mask_log_b() -> T;
156}
157impl <T: From<u8>> MaskLogB<T> for u8 { fn mask_log_b() -> T {0b111.into()} }
158impl <T: From<u8>> MaskLogB<T> for u16 { fn mask_log_b() -> T {0b1111.into()} }
159impl <T: From<u16>> MaskLogB<T> for u32 { fn mask_log_b() -> T {0b11111.into()} }
160impl <T: From<u16>> MaskLogB<T> for u64 { fn mask_log_b() -> T {0b111111.into()} }
161impl <T: From<u16>> MaskLogB<T> for u128 { fn mask_log_b() -> T {0b1111111.into()} }
162impl <T: From<u16>> MaskLogB<T> for usize {
163    fn mask_log_b() -> T {
164        match mem::size_of::<usize>() {
165            1 => 0b111,
166            2 => 0b1111,
167            4 => 0b11111,
168            8 => 0b111111,
169            16 => 0b1111111,
170            _ => panic!()
171        }.into()
172    }
173}
174
175/// `MaxOnes` provides a count of the number of bits that can be stored for a given type
176pub trait MaxOnes {
177    /// Get the maximum number of bits that can be set to 1.
178    /// 
179    /// e.g. `u32::max_ones() == 32`
180    #[must_use]
181    fn max_ones() -> usize;
182}
183impl MaxOnes for u8 { fn max_ones() -> usize {8} }
184impl MaxOnes for u16 { fn max_ones() -> usize {16} }
185impl MaxOnes for u32 { fn max_ones() -> usize {32} }
186impl MaxOnes for u64 { fn max_ones() -> usize {64} }
187impl MaxOnes for u128 { fn max_ones() -> usize {128} }
188impl MaxOnes for usize { fn max_ones() -> usize {8 * mem::size_of::<usize>()} }
189
190/// `NthBit` provides a word with only the nth bit set to 1.
191pub trait NthBit {
192    /// Get the nth bit of the given word size.
193    /// 
194    /// e.g. `u32::nth_bit(4) == 0b10000`
195    fn nth_bit(n: usize) -> Result<Self, BitError> where Self: Sized;
196}
197impl NthBit for u8 { fn nth_bit(n: usize) -> Result<Self, BitError> {bit_in_range!(u8, n); Ok(1_u8 << n)} }
198impl NthBit for u16 { fn nth_bit(n: usize) -> Result<Self, BitError> {bit_in_range!(u16, n); Ok(1_u16 << n)} }
199impl NthBit for u32 { fn nth_bit(n: usize) -> Result<Self, BitError> {bit_in_range!(u32, n); Ok(1_u32 << n)} }
200impl NthBit for u64 { fn nth_bit(n: usize) -> Result<Self, BitError> {bit_in_range!(u64, n); Ok(1_u64 << n)} }
201impl NthBit for u128 { fn nth_bit(n: usize) -> Result<Self, BitError> {bit_in_range!(u128, n); Ok(1_u128 << n)} }
202impl NthBit for usize { fn nth_bit(n: usize) -> Result<Self, BitError> {bit_in_range!(usize, n); Ok(1_usize << n)} }
203
204/// `Hashword` lists the requirements on hash values.
205pub trait Hashword: BitAnd + Clone + Debug + From<<Self as Shr<usize>>::Output> + MaxOnes + PartialEq + Shr<usize> + 'static {}
206impl <H: BitAnd + Clone + Debug + From<<Self as Shr<usize>>::Output> + MaxOnes + PartialEq + Shr<usize>> Hashword
207for H where H: BitAnd + Clone + Debug + From<<Self as Shr<usize>>::Output> + MaxOnes + PartialEq + Shr<usize> + 'static {}
208
209/// `Flagword` lists the requirements on CNode indices.
210pub trait Flagword<H: Hashword>: AsUsize + BitContains + BitIndex + BitInsert + BitRemove + Clone + CountOnes + Debug + Default + TryFrom<<H as BitAnd>::Output> + LogB + MaskLogB<H> + MaxOnes + NthBit + PartialEq + 'static {}
211impl <H: Hashword, F: AsUsize + BitContains + BitIndex + BitInsert + BitRemove + Clone + CountOnes + Debug + Default + TryFrom<<H as BitAnd>::Output> + LogB + MaskLogB<H> + MaxOnes + NthBit + PartialEq> Flagword<H>
212for F where F: AsUsize + BitContains + BitIndex + BitInsert + BitRemove + Clone + CountOnes + Debug + Default + TryFrom<<H as BitAnd>::Output> + LogB + MaskLogB<H> + MaxOnes + NthBit + PartialEq + 'static {}
213
214/// `Key` lists the requirements on the key type for the hash array mapped trie to function.
215pub trait Key: Clone + Debug + Eq + PartialEq + Hash + Send + Sync + 'static {}
216impl <T: Clone + Debug + Eq + PartialEq + Hash + Send + Sync + 'static> Key
217for T where T: Clone + Debug + Eq + PartialEq + Hash + Send + Sync + 'static {}
218
219/// `Value` lists the requirements on the value type for the hash array mapped trie to function.
220pub trait Value: Clone + Debug + Send + Sync + 'static {}
221impl <T: Clone + Debug + Send + Sync + 'static> Value
222for T where T: Clone + Debug + Send + Sync + 'static {}
223
224/// `HashLike` provides a means to assert that two types will hash identically.
225pub trait HashLike<T> {}
226impl <T> HashLike<T> for T {}
227
228/// `HasherBv` provides a generalization of the Hasher trait to support different word sizes for the hash values.
229pub trait HasherBv<B, V>: Default + 'static {
230    #[must_use]
231    fn hash(&self, value: &V) -> B;
232}
233macro_rules! hasher_bv_impl {
234    ( $type:ty ) => {
235        impl <V: Default + Hash + 'static, H: Default + Hasher + 'static> HasherBv<$type, V> for H {
236            fn hash(&self, value: &V) -> $type {
237                let mut hasher = H::default();
238                value.hash(&mut hasher);
239                hasher.finish().try_into().unwrap()
240            }
241        }
242    };
243}
244hasher_bv_impl!(u8);
245hasher_bv_impl!(u16);
246hasher_bv_impl!(u32);
247hasher_bv_impl!(u64);
hash_trie/traits.rs

hash_trie/
traits.rs
