use super::bucket::Bucket;
use super::node::DhtNode;
use std::collections::BinaryHeap;
const K: usize = 8;
pub(super) enum BucketTreeNode {
Internal {
left: Box<BucketTreeNode>,
right: Box<BucketTreeNode>,
min_id: [u8; 20],
max_id: [u8; 20],
},
Leaf { bucket: Bucket },
}
impl BucketTreeNode {
pub(super) 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,
}
}
fn min_id(&self) -> [u8; 20] {
match self {
Self::Internal { min_id, .. } => *min_id,
Self::Leaf { bucket } => *bucket.min_id(),
}
}
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,
}
}
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(super) 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);
let (left_prefix, right_prefix) = match self {
Self::Internal { left, right, .. } => {
let prefix = |node: &BucketTreeNode| match node {
Self::Leaf { bucket } => bucket.prefix_length(),
Self::Internal { .. } => 0,
};
(prefix(left), prefix(right))
}
Self::Leaf { .. } => unreachable!("a split produces two child buckets"),
};
tracing::debug!(left_prefix, right_prefix, "Bucket split");
}
Self::Internal { .. } => {
panic!("split() called on non-leaf node");
}
}
}
pub(super) fn for_each_bucket_mut(&mut self, f: &mut impl FnMut(&mut Bucket)) {
match self {
Self::Leaf { bucket } => f(bucket),
Self::Internal { left, right, .. } => {
left.for_each_bucket_mut(f);
right.for_each_bucket_mut(f);
}
}
}
}
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(super) 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(super) 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(super) 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(super) fn find_closest_k_nodes(root: &BucketTreeNode, key: &[u8; 20]) -> Vec<DhtNode> {
let mut nodes = BinaryHeap::with_capacity(K);
collect_closest_from_tree(root, key, &mut nodes);
let mut result: Vec<DhtNode> = nodes.into_iter().map(|candidate| candidate.node).collect();
result.sort_by(|a, b| {
a.distance_to(key)
.cmp(&b.distance_to(key))
.then_with(|| a.id.cmp(&b.id))
});
result
}
struct ClosestCandidate {
distance: usize,
node: DhtNode,
}
impl PartialEq for ClosestCandidate {
fn eq(&self, other: &Self) -> bool {
self.distance == other.distance && self.node.id == other.node.id
}
}
impl Eq for ClosestCandidate {}
impl PartialOrd for ClosestCandidate {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
Some(self.cmp(other))
}
}
impl Ord for ClosestCandidate {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
self.distance
.cmp(&other.distance)
.then_with(|| self.node.id.cmp(&other.node.id))
}
}
fn collect_closest_from_tree(
root: &BucketTreeNode,
key: &[u8; 20],
nodes: &mut BinaryHeap<ClosestCandidate>,
) {
match root {
BucketTreeNode::Leaf { bucket } => {
for node in bucket.nodes() {
if node.is_bad() {
continue;
}
let candidate = ClosestCandidate {
distance: node.distance_to(key),
node: node.clone(),
};
if nodes.len() < K {
nodes.push(candidate);
} else if nodes.peek().is_some_and(|farthest| candidate < *farthest) {
nodes.pop();
nodes.push(candidate);
}
}
}
BucketTreeNode::Internal { left, right, .. } => {
collect_closest_from_tree(left, key, nodes);
collect_closest_from_tree(right, key, nodes);
}
}
}
pub(super) 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);
}
}
}
#[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!(matches!(node, BucketTreeNode::Leaf { .. }));
}
#[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!(matches!(found, BucketTreeNode::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);
}
}