use super::bucket::Bucket;
use super::node::DhtNode;
const K: usize = 8;
pub enum BucketTreeNode {
Internal {
left: Box<BucketTreeNode>,
right: Box<BucketTreeNode>,
min_id: [u8; 20],
max_id: [u8; 20],
},
Leaf { bucket: Bucket },
}
impl BucketTreeNode {
pub fn new_leaf(bucket: Bucket) -> Self {
Self::Leaf { bucket }
}
fn new_internal(left: Box<BucketTreeNode>, right: Box<BucketTreeNode>) -> Self {
let min_id = left.min_id();
let max_id = right.max_id();
Self::Internal {
left,
right,
min_id,
max_id,
}
}
pub fn is_leaf(&self) -> bool {
matches!(self, Self::Leaf { .. })
}
pub fn min_id(&self) -> [u8; 20] {
match self {
Self::Internal { min_id, .. } => *min_id,
Self::Leaf { bucket } => *bucket.min_id(),
}
}
pub fn max_id(&self) -> [u8; 20] {
match self {
Self::Internal { max_id, .. } => *max_id,
Self::Leaf { bucket } => *bucket.max_id(),
}
}
fn dig(&self, key: &[u8; 20]) -> Option<&BucketTreeNode> {
match self {
Self::Internal { left, right, .. } => {
if left.is_in_range(key) {
Some(left)
} else {
Some(right)
}
}
Self::Leaf { .. } => None,
}
}
fn dig_mut(&mut self, key: &[u8; 20]) -> Option<&mut BucketTreeNode> {
match self {
Self::Internal { left, right, .. } => {
if left.is_in_range(key) {
Some(left)
} else {
Some(right)
}
}
Self::Leaf { .. } => None,
}
}
pub fn is_in_range(&self, key: &[u8; 20]) -> bool {
let min = self.min_id();
let max = self.max_id();
key.as_slice() >= min.as_slice() && key.as_slice() <= max.as_slice()
}
pub fn bucket(&self) -> Option<&Bucket> {
match self {
Self::Leaf { bucket } => Some(bucket),
Self::Internal { .. } => None,
}
}
pub fn bucket_mut(&mut self) -> Option<&mut Bucket> {
match self {
Self::Leaf { bucket } => Some(bucket),
Self::Internal { .. } => None,
}
}
pub fn left(&self) -> Option<&BucketTreeNode> {
match self {
Self::Internal { left, .. } => Some(left),
Self::Leaf { .. } => None,
}
}
pub fn right(&self) -> Option<&BucketTreeNode> {
match self {
Self::Internal { right, .. } => Some(right),
Self::Leaf { .. } => None,
}
}
pub fn split(&mut self, local_id: &[u8; 20]) {
match self {
Self::Leaf { bucket } => {
if !bucket.split_allowed() {
tracing::debug!("Bucket split rejected: not allowed");
return;
}
let right_bucket = bucket.split();
let left_bucket = std::mem::replace(
bucket,
Bucket::new_for_range(0, [0u8; 20], [0xFFu8; 20], *local_id),
);
let left_node = Box::new(BucketTreeNode::new_leaf(left_bucket));
let right_node = Box::new(BucketTreeNode::new_leaf(right_bucket));
*self = Self::new_internal(left_node, right_node);
tracing::debug!(
"Bucket split: left prefix={}, right prefix={}",
match self.left() {
Some(BucketTreeNode::Leaf { bucket }) => bucket.prefix_length(),
_ => 0,
},
match self.right() {
Some(BucketTreeNode::Leaf { bucket }) => bucket.prefix_length(),
_ => 0,
}
);
}
Self::Internal { .. } => {
panic!("split() called on non-leaf node");
}
}
}
}
pub fn find_tree_node_for<'a>(root: &'a BucketTreeNode, key: &[u8; 20]) -> &'a BucketTreeNode {
match root {
BucketTreeNode::Leaf { .. } => root,
BucketTreeNode::Internal { .. } => {
let child = root.dig(key).expect("internal node must have children");
find_tree_node_for(child, key)
}
}
}
pub fn find_tree_node_for_mut<'a>(
root: &'a mut BucketTreeNode,
key: &[u8; 20],
) -> &'a mut BucketTreeNode {
match root {
BucketTreeNode::Leaf { .. } => root,
BucketTreeNode::Internal { .. } => {
let child = root.dig_mut(key).expect("internal node must have children");
find_tree_node_for_mut(child, key)
}
}
}
pub fn find_bucket_for<'a>(root: &'a BucketTreeNode, key: &[u8; 20]) -> &'a Bucket {
let leaf = find_tree_node_for(root, key);
match leaf {
BucketTreeNode::Leaf { bucket } => bucket,
BucketTreeNode::Internal { .. } => unreachable!("find_tree_node_for returned internal"),
}
}
pub fn find_bucket_for_mut<'a>(root: &'a mut BucketTreeNode, key: &[u8; 20]) -> &'a mut Bucket {
let leaf = find_tree_node_for_mut(root, key);
match leaf {
BucketTreeNode::Leaf { bucket } => bucket,
BucketTreeNode::Internal { .. } => unreachable!("find_tree_node_for returned internal"),
}
}
pub fn find_closest_k_nodes(root: &BucketTreeNode, key: &[u8; 20]) -> Vec<DhtNode> {
let mut nodes = Vec::with_capacity(K);
collect_closest_from_all_buckets(root, key, &mut nodes);
nodes
}
fn collect_closest_from_all_buckets(
root: &BucketTreeNode,
key: &[u8; 20],
nodes: &mut Vec<DhtNode>,
) {
let mut all_buckets = Vec::new();
enumerate_buckets(root, &mut all_buckets);
for bucket in &all_buckets {
for node in bucket.nodes() {
if !node.is_bad() {
nodes.push(node.clone());
}
}
}
let key_copy = *key;
nodes.sort_by(|a, b| {
let da = a.distance_to(&key_copy);
let db = b.distance_to(&key_copy);
da.cmp(&db)
});
nodes.truncate(K);
}
pub fn enumerate_buckets<'a>(root: &'a BucketTreeNode, buckets: &mut Vec<&'a Bucket>) {
match root {
BucketTreeNode::Leaf { bucket } => {
buckets.push(bucket);
}
BucketTreeNode::Internal { left, right, .. } => {
enumerate_buckets(left, buckets);
enumerate_buckets(right, buckets);
}
}
}
pub fn count_buckets(root: &BucketTreeNode) -> usize {
match root {
BucketTreeNode::Leaf { .. } => 1,
BucketTreeNode::Internal { left, right, .. } => count_buckets(left) + count_buckets(right),
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::net::SocketAddr;
fn make_local_node() -> DhtNode {
DhtNode::new([0u8; 20], "127.0.0.1:6881".parse::<SocketAddr>().unwrap())
}
#[test]
fn test_leaf_node_creation() {
let local = make_local_node();
let bucket = Bucket::new(&local);
let node = BucketTreeNode::new_leaf(bucket);
assert!(node.is_leaf());
assert!(node.bucket().is_some());
assert!(node.left().is_none());
assert!(node.right().is_none());
}
#[test]
fn test_is_in_range() {
let local = make_local_node();
let bucket = Bucket::new(&local);
let node = BucketTreeNode::new_leaf(bucket);
let zero_id = [0u8; 20];
let max_id = [0xFFu8; 20];
assert!(node.is_in_range(&zero_id));
assert!(node.is_in_range(&max_id));
}
#[test]
fn test_find_tree_node_for() {
let local = make_local_node();
let bucket = Bucket::new(&local);
let root = BucketTreeNode::new_leaf(bucket);
let key = [0x42u8; 20];
let found = find_tree_node_for(&root, &key);
assert!(found.is_leaf());
}
#[test]
fn test_enumerate_buckets_single() {
let local = make_local_node();
let bucket = Bucket::new(&local);
let root = BucketTreeNode::new_leaf(bucket);
let mut buckets = Vec::new();
enumerate_buckets(&root, &mut buckets);
assert_eq!(buckets.len(), 1);
}
#[test]
fn test_count_buckets() {
let local = make_local_node();
let bucket = Bucket::new(&local);
let root = BucketTreeNode::new_leaf(bucket);
assert_eq!(count_buckets(&root), 1);
}
}