use std::time::Instant;
use super::node::DhtNode;
pub const K: usize = 8;
pub const CACHE_SIZE: usize = 2;
const ID_LENGTH: usize = 20;
const BUCKET_REFRESH_INTERVAL_SECS: u64 = 15 * 60;
fn flip_bit(id: &mut [u8; 20], bit_index: usize) {
let byte_index = bit_index / 8;
let bit_offset = 7 - (bit_index % 8);
if byte_index < 20 {
id[byte_index] ^= 1 << bit_offset;
}
}
#[derive(Debug)]
pub struct Bucket {
prefix_length: usize,
min_id: [u8; 20],
max_id: [u8; 20],
local_id: [u8; 20],
nodes: Vec<DhtNode>,
cached_nodes: Vec<DhtNode>,
last_updated: Instant,
}
impl Bucket {
pub fn new(local_node: &DhtNode) -> Self {
Self {
prefix_length: 0,
min_id: [0u8; 20],
max_id: [0xFFu8; 20],
local_id: local_node.id,
nodes: Vec::with_capacity(K),
cached_nodes: Vec::with_capacity(CACHE_SIZE),
last_updated: Instant::now(),
}
}
pub fn new_for_range(
prefix_length: usize,
min_id: [u8; 20],
max_id: [u8; 20],
local_id: [u8; 20],
) -> Self {
Self {
prefix_length,
min_id,
max_id,
local_id,
nodes: Vec::with_capacity(K),
cached_nodes: Vec::with_capacity(CACHE_SIZE),
last_updated: Instant::now(),
}
}
pub fn prefix_length(&self) -> usize {
self.prefix_length
}
pub fn min_id(&self) -> &[u8; 20] {
&self.min_id
}
pub fn max_id(&self) -> &[u8; 20] {
&self.max_id
}
pub fn count_node(&self) -> usize {
self.nodes.len()
}
pub fn is_full(&self) -> bool {
self.nodes.len() >= K
}
pub fn is_empty(&self) -> bool {
self.nodes.is_empty()
}
pub fn nodes(&self) -> &[DhtNode] {
&self.nodes
}
pub fn cached_nodes(&self) -> &[DhtNode] {
&self.cached_nodes
}
pub fn good_node_count(&self) -> usize {
self.nodes.iter().filter(|n| n.is_good()).count()
}
pub fn is_in_range(&self, node_id: &[u8; 20]) -> bool {
node_id.as_slice() >= self.min_id.as_slice() && node_id.as_slice() <= self.max_id.as_slice()
}
pub fn add_node(&mut self, node: DhtNode) -> bool {
self.try_add_node(node).is_ok()
}
pub(super) fn try_add_node(&mut self, node: DhtNode) -> Result<(), DhtNode> {
if let Some(pos) = self.nodes.iter().position(|n| n.id == node.id) {
if self.nodes[pos].verified && !node.verified {
return Ok(());
}
self.notify_update();
self.nodes.remove(pos);
self.nodes.push(node);
return Ok(());
}
if self.nodes.len() < K {
self.notify_update();
self.nodes.push(node);
return Ok(());
}
if let Some(front) = self.nodes.first()
&& front.is_bad()
&& node.is_good()
{
self.notify_update();
self.nodes.remove(0);
self.nodes.push(node);
return Ok(());
}
Err(node)
}
pub fn cache_node(&mut self, node: DhtNode) {
if self.nodes.iter().any(|existing| existing.id == node.id) {
return;
}
if let Some(position) = self
.cached_nodes
.iter()
.position(|cached| cached.id == node.id)
{
self.cached_nodes.remove(position);
}
self.cached_nodes.insert(0, node);
if self.cached_nodes.len() > CACHE_SIZE {
self.cached_nodes.truncate(CACHE_SIZE);
}
}
pub fn drop_node(&mut self, node_id: &[u8; 20]) -> bool {
if let Some(pos) = self.nodes.iter().position(|n| &n.id == node_id) {
self.nodes.remove(pos);
if !self.cached_nodes.is_empty() {
let replacement = self.cached_nodes.remove(0);
self.nodes.push(replacement);
}
true
} else {
false
}
}
pub fn remove_node(&mut self, node_id: &[u8; 20]) -> bool {
if let Some(pos) = self.nodes.iter().position(|n| &n.id == node_id) {
self.nodes.remove(pos);
true
} else {
false
}
}
pub fn replace_node(&mut self, node_id: &[u8; 20], replacement: DhtNode) -> bool {
if replacement.id != *node_id && self.nodes.iter().any(|node| node.id == replacement.id) {
return false;
}
if let Some(pos) = self.nodes.iter().position(|n| &n.id == node_id) {
self.nodes.remove(pos);
self.nodes.push(replacement);
true
} else {
false
}
}
pub fn remove_cached_node(&mut self, node_id: &[u8; 20]) -> bool {
if let Some(pos) = self
.cached_nodes
.iter()
.position(|node| &node.id == node_id)
{
self.cached_nodes.remove(pos);
true
} else {
false
}
}
pub fn move_to_head(&mut self, node_id: &[u8; 20]) {
if let Some(pos) = self.nodes.iter().position(|n| &n.id == node_id) {
let node = self.nodes.remove(pos);
self.nodes.insert(0, node);
}
}
pub fn move_to_tail(&mut self, node_id: &[u8; 20]) {
if let Some(pos) = self.nodes.iter().position(|n| &n.id == node_id) {
let node = self.nodes.remove(pos);
self.nodes.push(node);
}
}
pub fn split_allowed(&self) -> bool {
self.prefix_length < ID_LENGTH * 8 - 1 && self.is_in_range(&self.local_id)
}
pub fn split(&mut self) -> Bucket {
assert!(
self.split_allowed(),
"split() called on non-splittable bucket"
);
let r_max = self.max_id;
let mut r_min = self.min_id;
flip_bit(&mut r_min, self.prefix_length);
flip_bit(&mut self.max_id, self.prefix_length);
self.prefix_length += 1;
let new_prefix_length = self.prefix_length;
let mut right_bucket =
Bucket::new_for_range(new_prefix_length, r_min, r_max, self.local_id);
let mut remaining = Vec::with_capacity(K);
for node in self.nodes.drain(..) {
if right_bucket.is_in_range(&node.id) {
right_bucket.nodes.push(node);
} else {
remaining.push(node);
}
}
self.nodes = remaining;
tracing::debug!(
"Bucket split: left prefix={} range={}-{}, right prefix={} range={}-{}",
self.prefix_length,
hex::encode(self.min_id),
hex::encode(self.max_id),
right_bucket.prefix_length,
hex::encode(right_bucket.min_id),
hex::encode(right_bucket.max_id),
);
right_bucket
}
pub fn needs_refresh(&self) -> bool {
self.nodes.len() < K
|| self.last_updated.elapsed().as_secs() >= BUCKET_REFRESH_INTERVAL_SECS
}
pub fn contains_questionable_node(&self) -> bool {
self.nodes.iter().any(|n| n.is_questionable())
}
pub fn get_lru_questionable_node(&self) -> Option<&DhtNode> {
self.nodes.iter().find(|n| n.is_questionable())
}
pub fn get_node(&self, node_id: &[u8; 20], ip_addr: &str, port: u16) -> Option<&DhtNode> {
self.nodes.iter().find(|n| {
&n.id == node_id && n.addr.ip().to_string() == ip_addr && n.addr.port() == port
})
}
pub fn get_random_node_id(&self) -> [u8; 20] {
use rand::RngExt;
let mut id = [0u8; 20];
let mut rng = rand::rng();
rng.fill(&mut id);
self.apply_fixed_prefix(&mut id);
id
}
fn apply_fixed_prefix(&self, id: &mut [u8; 20]) {
let full_bytes = self.prefix_length / 8;
id[..full_bytes].copy_from_slice(&self.min_id[..full_bytes]);
let remaining_bits = self.prefix_length % 8;
if remaining_bits > 0 {
let mask = u8::MAX << (8 - remaining_bits);
id[full_bytes] = (id[full_bytes] & !mask) | (self.min_id[full_bytes] & mask);
}
}
pub fn mark_good(&mut self, node_id: &[u8; 20]) -> bool {
if let Some(node) = self.nodes.iter_mut().find(|n| &n.id == node_id) {
node.touch();
true
} else {
false
}
}
pub fn mark_bad(&mut self, node_id: &[u8; 20]) -> bool {
if let Some(node) = self.nodes.iter_mut().find(|n| &n.id == node_id) {
node.record_failure();
true
} else {
false
}
}
pub fn evict_bad(&mut self) -> usize {
let bad_node_ids = self
.nodes
.iter()
.filter(|node| node.is_bad())
.map(|node| node.id)
.collect::<Vec<_>>();
for node_id in &bad_node_ids {
self.drop_node(node_id);
}
bad_node_ids.len()
}
fn notify_update(&mut self) {
self.last_updated = Instant::now();
}
pub fn get_good_nodes(&self) -> Vec<DhtNode> {
self.nodes.iter().filter(|n| n.is_good()).cloned().collect()
}
pub fn questionable_count(&self) -> usize {
self.nodes.iter().filter(|n| n.is_questionable()).count()
}
pub fn bad_count(&self) -> usize {
self.nodes.iter().filter(|n| n.is_bad()).count()
}
}
impl Clone for Bucket {
fn clone(&self) -> Self {
Self {
prefix_length: self.prefix_length,
min_id: self.min_id,
max_id: self.max_id,
local_id: self.local_id,
nodes: self.nodes.clone(),
cached_nodes: self.cached_nodes.clone(),
last_updated: self.last_updated,
}
}
}
#[cfg(test)]
mod tests;