use std::collections::VecDeque;
use std::net::SocketAddr;
use std::time::{Duration, Instant};
use crate::dht::{distance, NodeId};
const K: usize = 8;
#[derive(Debug, Clone)]
pub struct NodeEntry {
pub id: NodeId,
pub addr: SocketAddr,
pub last_seen: Instant,
}
impl NodeEntry {
pub fn new(id: NodeId, addr: SocketAddr) -> Self {
Self {
id,
addr,
last_seen: Instant::now(),
}
}
pub fn touch(&mut self) {
self.last_seen = Instant::now();
}
}
#[derive(Debug)]
struct KBucket {
live: Vec<NodeEntry>,
replacements: VecDeque<NodeEntry>,
last_changed: Instant,
}
impl KBucket {
fn new() -> Self {
Self {
live: Vec::new(),
replacements: VecDeque::new(),
last_changed: Instant::now(),
}
}
fn touch_bucket(&mut self) {
self.last_changed = Instant::now();
}
}
#[derive(Debug)]
pub struct RoutingTable {
local_id: NodeId,
buckets: Vec<KBucket>,
}
impl RoutingTable {
pub fn new(local_id: NodeId) -> Self {
Self {
local_id,
buckets: (0..160).map(|_| KBucket::new()).collect(),
}
}
pub fn local_id(&self) -> NodeId {
self.local_id
}
pub fn upsert(&mut self, entry: NodeEntry) {
let bucket_idx = bucket_index(&self.local_id, &entry.id);
let bucket = &mut self.buckets[bucket_idx];
if let Some(existing) = bucket.live.iter_mut().find(|node| node.id == entry.id) {
existing.addr = entry.addr;
existing.touch();
bucket.touch_bucket();
return;
}
if let Some(existing) = bucket
.replacements
.iter_mut()
.find(|node| node.id == entry.id)
{
existing.addr = entry.addr;
existing.touch();
return;
}
if bucket.live.len() < K {
bucket.live.push(entry);
bucket.touch_bucket();
return;
}
bucket.replacements.retain(|node| node.id != entry.id);
bucket.replacements.push_back(entry);
while bucket.replacements.len() > K {
bucket.replacements.pop_front();
}
}
pub fn all_entries(&self) -> Vec<NodeEntry> {
self.buckets
.iter()
.flat_map(|bucket| bucket.live.iter().cloned())
.collect()
}
pub fn live_node_count(&self) -> usize {
self.buckets.iter().map(|bucket| bucket.live.len()).sum()
}
pub fn stale_contacts(&self, older_than: Duration, limit: usize) -> Vec<NodeEntry> {
let mut nodes: Vec<_> = self
.buckets
.iter()
.flat_map(|bucket| bucket.live.iter())
.filter(|node| node.last_seen.elapsed() > older_than)
.cloned()
.collect();
nodes.sort_by_key(|node| node.last_seen);
nodes.truncate(limit);
nodes
}
pub fn remove_id(&mut self, id: &NodeId) {
let bucket_idx = bucket_index(&self.local_id, id);
let bucket = &mut self.buckets[bucket_idx];
let before = bucket.live.len();
bucket.live.retain(|node| node.id != *id);
bucket.replacements.retain(|node| node.id != *id);
if bucket.live.len() < before {
if let Some(promoted) = bucket.replacements.pop_back() {
bucket.live.push(promoted);
}
bucket.touch_bucket();
}
}
pub fn buckets_needing_refresh(&self, idle_for: Duration, limit: usize) -> Vec<usize> {
let mut idxs: Vec<_> = self
.buckets
.iter()
.enumerate()
.filter(|(_, bucket)| bucket.last_changed.elapsed() > idle_for)
.map(|(idx, bucket)| (idx, bucket.last_changed, bucket.live.len()))
.collect();
idxs.sort_by(|a, b| a.1.cmp(&b.1).then(a.2.cmp(&b.2)));
idxs.into_iter().map(|(idx, _, _)| idx).take(limit).collect()
}
pub fn refresh_target(&self, bucket_idx: usize) -> NodeId {
random_id_in_bucket(&self.local_id, bucket_idx.min(159))
}
#[cfg(test)]
pub fn replacement_count(&self, bucket_idx: usize) -> usize {
self.buckets[bucket_idx].replacements.len()
}
#[cfg(test)]
pub fn live_count(&self, bucket_idx: usize) -> usize {
self.buckets[bucket_idx].live.len()
}
pub fn closest(&self, target: &NodeId, count: usize) -> Vec<NodeEntry> {
let mut nodes = self.all_entries();
nodes.sort_by(|a, b| {
distance(&a.id, target)
.cmp(&distance(&b.id, target))
.then_with(|| a.id.cmp(&b.id))
});
nodes.truncate(count);
nodes
}
}
fn bucket_index(local: &NodeId, node: &NodeId) -> usize {
let xor = distance(local, node);
leading_zero_bits(&xor).min(159)
}
fn leading_zero_bits(x: &[u8; 20]) -> usize {
let mut zeros = 0usize;
for byte in x {
if *byte == 0 {
zeros += 8;
} else {
zeros += byte.leading_zeros() as usize;
break;
}
}
zeros
}
fn random_id_in_bucket(local: &NodeId, bucket_idx: usize) -> NodeId {
let mut id = *local.as_bytes();
let byte_idx = bucket_idx / 8;
let bit_in_byte = 7 - (bucket_idx % 8);
id[byte_idx] ^= 1 << bit_in_byte;
if let Ok(rand) = crate::net::random_bytes::<20>() {
for (idx, byte) in id.iter_mut().enumerate().skip(byte_idx) {
if idx == byte_idx {
let keep_mask = !((1u8 << bit_in_byte) - 1);
*byte = (*byte & keep_mask) | (rand[idx] & !keep_mask);
} else {
*byte = rand[idx];
}
}
}
NodeId::from_bytes(id)
}
#[cfg(test)]
mod tests {
use super::*;
use std::net::{Ipv4Addr, SocketAddrV4};
fn addr() -> SocketAddr {
SocketAddr::V4(SocketAddrV4::new(Ipv4Addr::LOCALHOST, 6881))
}
#[test]
fn keeps_closest_nodes() {
let local = NodeId::from_bytes([0; 20]);
let mut table = RoutingTable::new(local);
for idx in 1..=4u8 {
let mut id = [0u8; 20];
id[19] = idx;
table.upsert(NodeEntry::new(NodeId::from_bytes(id), addr()));
}
let target = NodeId::from_bytes([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]);
let closest = table.closest(&target, 2);
assert_eq!(closest.len(), 2);
}
#[test]
fn full_bucket_keeps_replacements_and_promotes() {
let local = NodeId::from_bytes([0; 20]);
let mut table = RoutingTable::new(local);
let mut ids = Vec::new();
for i in 0..(K + 3) {
let mut id = [0u8; 20];
id[0] = 0x80; id[19] = i as u8;
ids.push(NodeId::from_bytes(id));
table.upsert(NodeEntry::new(NodeId::from_bytes(id), addr()));
}
assert_eq!(table.live_count(0), K);
assert_eq!(table.replacement_count(0), 3);
let evict = ids[0];
table.remove_id(&evict);
assert_eq!(table.live_count(0), K);
assert_eq!(table.replacement_count(0), 2);
assert!(!table.all_entries().iter().any(|e| e.id == evict));
}
#[test]
fn refresh_target_lands_in_bucket() {
let local = NodeId::from_bytes([0; 20]);
let table = RoutingTable::new(local);
for bucket in [0usize, 7, 40, 159] {
let target = table.refresh_target(bucket);
assert_eq!(bucket_index(&local, &target), bucket);
}
}
}