use tracing::trace;
use super::BucketTreeNode;
use super::bucket::DhtBucket;
use super::bucket_tree::{
find_bucket_for, find_bucket_for_mut, find_closest_k_nodes, find_tree_node_for_mut,
};
use super::constants::K;
use super::node::DhtNode;
use super::node_id::NodeId;
pub struct RoutingTable {
local_node_id: NodeId,
root: BucketTreeNode,
num_buckets: usize,
}
impl RoutingTable {
pub fn new(local_node_id: NodeId) -> Self {
let bucket = DhtBucket::new(local_node_id);
let root = BucketTreeNode::leaf(bucket);
RoutingTable {
local_node_id,
root,
num_buckets: 1,
}
}
pub fn add_node(&mut self, node: DhtNode) -> bool {
self.add_node_inner(node, false)
}
pub fn add_good_node(&mut self, node: DhtNode) -> bool {
self.add_node_inner(node, true)
}
fn add_node_inner(&mut self, node: DhtNode, good: bool) -> bool {
let node_id = *node.id();
if node_id == self.local_node_id {
trace!("Rejected node with same ID as local node");
return false;
}
trace!(node_id = %node_id, "Trying to add node to routing table");
let tree_node = find_tree_node_for_mut(&mut self.root, &node_id);
{
let (can_add, should_split) = {
let bucket = tree_node.bucket().expect("leaf must have bucket");
let already_exists = bucket.nodes().iter().any(|n| n.id() == &node_id);
let has_room = bucket.count() < K;
let has_bad_front = bucket.nodes().front().is_some_and(|n| n.is_bad());
let can = already_exists || has_room || has_bad_front;
let should = !can && bucket.split_allowed();
(can, should)
};
if can_add {
let bucket = tree_node.bucket_mut().expect("leaf must have bucket");
let added = bucket.add_node(node);
if added {
trace!(node_id = %node_id, "Added node to bucket");
}
return added;
}
if should_split {
trace!("Splitting bucket tree node");
tree_node.split();
self.num_buckets += 1;
let go_left = tree_node.left().unwrap().is_in_range(&node_id);
if go_left {
let left = tree_node.left_mut().unwrap();
let left_bucket = left.bucket_mut().expect("left child must be leaf");
return left_bucket.add_node(node);
} else {
let right = tree_node.right_mut().unwrap();
let right_bucket = right.bucket_mut().expect("right child must be leaf");
return right_bucket.add_node(node);
}
}
if good {
let bucket = tree_node.bucket_mut().expect("leaf must have bucket");
bucket.cache_node(node);
trace!(node_id = %node_id, "Cached node in full bucket");
}
false
}
}
pub fn get_closest_k_nodes(&self, key: &NodeId) -> Vec<&DhtNode> {
find_closest_k_nodes(&self.root, key)
}
pub fn get_bucket_for(&self, node_id: &NodeId) -> &DhtBucket {
find_bucket_for(&self.root, node_id)
}
pub fn drop_node(&mut self, node_id: &NodeId) {
let bucket = find_bucket_for_mut(&mut self.root, node_id);
bucket.drop_node(node_id);
}
pub fn move_bucket_tail(&mut self, node_id: &NodeId) {
let bucket = find_bucket_for_mut(&mut self.root, node_id);
bucket.move_to_tail(node_id);
}
pub fn get_node(
&self,
node_id: &NodeId,
addr_check: impl Fn(&DhtNode) -> bool,
) -> Option<&DhtNode> {
let bucket = self.get_bucket_for(node_id);
bucket.get_node(node_id, addr_check)
}
pub fn get_node_mut(&mut self, node_id: &NodeId) -> Option<&mut DhtNode> {
let bucket = find_bucket_for_mut(&mut self.root, node_id);
bucket.get_node_mut(node_id)
}
pub fn get_buckets(&self) -> Vec<&DhtBucket> {
super::bucket_tree::enumerate_buckets(&self.root)
}
pub fn num_buckets(&self) -> usize {
self.num_buckets
}
pub fn local_node_id(&self) -> &NodeId {
&self.local_node_id
}
}
impl std::fmt::Debug for RoutingTable {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("RoutingTable")
.field("local_node_id", &self.local_node_id)
.field("num_buckets", &self.num_buckets)
.finish()
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::dht::constants::ID_LENGTH;
use std::net::{IpAddr, Ipv4Addr, SocketAddr};
fn test_addr() -> SocketAddr {
SocketAddr::new(IpAddr::V4(Ipv4Addr::new(127, 0, 0, 1)), 6881)
}
fn make_node(id_byte: u8) -> DhtNode {
let id = NodeId::from_slice(&[id_byte; ID_LENGTH]);
DhtNode::new(id, test_addr())
}
#[test]
fn new_routing_table_has_one_bucket() {
let rt = RoutingTable::new(NodeId::from_slice(&[0x80u8; ID_LENGTH]));
assert_eq!(rt.num_buckets(), 1);
}
#[test]
fn reject_node_with_local_id() {
let local_id = NodeId::from_slice(&[0x80u8; ID_LENGTH]);
let mut rt = RoutingTable::new(local_id);
let node = make_node(0x80);
assert!(!rt.add_node(node));
}
#[test]
fn add_node_to_empty_table() {
let local_id = NodeId::from_slice(&[0x80u8; ID_LENGTH]);
let mut rt = RoutingTable::new(local_id);
let node = make_node(0x01);
assert!(rt.add_node(node));
}
#[test]
fn add_nodes_trigger_split() {
let local_id = NodeId::from_slice(&[0x80u8; ID_LENGTH]);
let mut rt = RoutingTable::new(local_id);
for i in 0u8..9 {
let node = make_node(i);
rt.add_node(node);
}
assert!(rt.num_buckets() > 1);
}
#[test]
fn get_closest_k_nodes() {
let local_id = NodeId::from_slice(&[0x80u8; ID_LENGTH]);
let mut rt = RoutingTable::new(local_id);
for i in 0u8..5 {
let mut node = make_node(i);
node.mark_good();
node.update_last_contact();
rt.add_node(node);
}
let key = NodeId::from_slice(&[0x02u8; ID_LENGTH]);
let nodes = rt.get_closest_k_nodes(&key);
assert!(nodes.len() <= 8);
assert!(!nodes.is_empty());
}
#[test]
fn get_bucket_for_key() {
let local_id = NodeId::from_slice(&[0x80u8; ID_LENGTH]);
let rt = RoutingTable::new(local_id);
let key = NodeId::from_slice(&[0x42u8; ID_LENGTH]);
let bucket = rt.get_bucket_for(&key);
assert!(key.is_in_range(bucket.min_id(), bucket.max_id()));
}
#[test]
fn drop_node_from_table() {
let local_id = NodeId::from_slice(&[0x80u8; ID_LENGTH]);
let mut rt = RoutingTable::new(local_id);
let mut node = make_node(0x01);
node.mark_good();
node.update_last_contact();
rt.add_node(node);
let cached = make_node(0x02);
rt.add_good_node(cached);
let node_id = NodeId::from_slice(&[0x01u8; ID_LENGTH]);
rt.drop_node(&node_id);
}
#[test]
fn get_all_buckets() {
let local_id = NodeId::from_slice(&[0x80u8; ID_LENGTH]);
let mut rt = RoutingTable::new(local_id);
for i in 0u8..10 {
let node = make_node(i);
rt.add_node(node);
}
let buckets = rt.get_buckets();
assert!(buckets.len() > 1);
}
#[test]
fn add_good_node_caches_when_full() {
let local_id = NodeId::from_slice(&[0x80u8; ID_LENGTH]);
let mut rt = RoutingTable::new(local_id);
for i in 0u8..12 {
let node = make_node(i);
rt.add_good_node(node);
}
}
}