| 1 |
#[derive(Debug, Clone, Copy, PartialEq, Eq)] |
| 2 |
#[repr(transparent)] |
| 3 |
pub struct TreeEntry(u16); |
| 4 |
|
| 5 |
const LEAF_BIT: u16 = 1u16.rotate_right(1); |
| 6 |
|
| 7 |
#[derive(Debug, Clone, Copy, PartialEq, Eq)] |
| 8 |
pub enum NodeType { |
| 9 |
Leaf(u16), |
| 10 |
Branch(u16), |
| 11 |
} |
| 12 |
|
| 13 |
impl TreeEntry { |
| 14 |
pub const MAX_INDEX: usize = LEAF_BIT as usize - 1; |
| 15 |
|
| 16 |
#[inline] |
| 17 |
pub fn leaf(value: u16) -> TreeEntry { |
| 18 |
TreeEntry(value | LEAF_BIT) |
| 19 |
} |
| 20 |
|
| 21 |
#[inline] |
| 22 |
pub fn branch(child_index: usize) -> Result<TreeEntry, &'static str> { |
| 23 |
if child_index > Self::MAX_INDEX { |
| 24 |
return Err("tree index out of range"); |
| 25 |
} |
| 26 |
Ok(TreeEntry(child_index as u16)) |
| 27 |
} |
| 28 |
|
| 29 |
#[inline] |
| 30 |
pub fn as_type(self) -> NodeType { |
| 31 |
let TreeEntry(entry) = self; |
| 32 |
let value = entry & !LEAF_BIT; |
| 33 |
if value == entry { |
| 34 |
NodeType::Branch(value) |
| 35 |
} |
| 36 |
else { |
| 37 |
NodeType::Leaf(value) |
| 38 |
} |
| 39 |
} |
| 40 |
|
| 41 |
#[allow(dead_code)] |
| 42 |
#[inline] |
| 43 |
pub fn set_as_branch(&mut self, child_index: usize) { |
| 44 |
self.0 = (child_index as u16) & !LEAF_BIT; |
| 45 |
} |
| 46 |
|
| 47 |
#[allow(dead_code)] |
| 48 |
#[inline] |
| 49 |
pub fn is_leaf(self) -> bool { |
| 50 |
self.0 & LEAF_BIT == LEAF_BIT |
| 51 |
} |
| 52 |
|
| 53 |
#[allow(dead_code)] |
| 54 |
#[inline] |
| 55 |
pub fn as_value(self) -> u16 { |
| 56 |
self.0 & !LEAF_BIT |
| 57 |
} |
| 58 |
} |
| 59 |
|
| 60 |
#[cfg(test)] |
| 61 |
mod tests { |
| 62 |
use super::*; |
| 63 |
use core::mem; |
| 64 |
#[test] |
| 65 |
fn tree_entry_works() { |
| 66 |
assert_eq!(mem::size_of::<TreeEntry>(), 2); |
| 67 |
assert_eq!(LEAF_BIT, 0x8000); |
| 68 |
let mut leaf0 = TreeEntry::leaf(0); |
| 69 |
assert!(leaf0.is_leaf()); |
| 70 |
assert_eq!(leaf0, TreeEntry::leaf(0x8000)); |
| 71 |
assert_eq!(leaf0.as_value(), 0); |
| 72 |
let leaf1 = TreeEntry::leaf(1); |
| 73 |
assert!(leaf1.is_leaf()); |
| 74 |
assert_eq!(leaf1, TreeEntry::leaf(0x8001)); |
| 75 |
assert_eq!(leaf1.as_value(), 1); |
| 76 |
let branch0 = TreeEntry::branch(0).unwrap(); |
| 77 |
let branch1 = TreeEntry::branch(0x7fff).unwrap(); |
| 78 |
assert!(!branch0.is_leaf()); |
| 79 |
assert_eq!(branch0.as_value(), 0); |
| 80 |
assert!(!branch1.is_leaf()); |
| 81 |
assert_eq!(branch1.as_value(), 0x7fff); |
| 82 |
assert!(TreeEntry::branch(0x8000).is_err()); |
| 83 |
assert_eq!(leaf0.as_type(), NodeType::Leaf(0)); |
| 84 |
assert_eq!(leaf1.as_type(), NodeType::Leaf(1)); |
| 85 |
assert_eq!(branch0.as_type(), NodeType::Branch(0)); |
| 86 |
assert_eq!(branch1.as_type(), NodeType::Branch(0x7fff)); |
| 87 |
leaf0.set_as_branch(0); |
| 88 |
assert!(!leaf0.is_leaf()); |
| 89 |
assert_eq!(leaf0.as_type(), NodeType::Branch(0)); |
| 90 |
leaf0.set_as_branch(0x8000); |
| 91 |
assert_eq!(leaf0.as_type(), NodeType::Branch(0)); |
| 92 |
leaf0.set_as_branch(0x7fff); |
| 93 |
assert_eq!(leaf0.as_type(), NodeType::Branch(0x7fff)); |
| 94 |
} |
| 95 |
} |