Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_o3db_sync/src/kademlia/table.rs

5.4 KiB, 46 runs

created by r1870400018:11194, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! The full Kademlia routing table.
2//!
3//! A [`RoutingTable`] owns 256 [`KMap`]s, one per bit of XOR distance from the
4//! local node. Peer placement is deterministic -- the most-significant set bit
5//! of the XOR distance between the local id and the remote id selects the
6//! k-map. The table exposes insertion (with overflow handled by the caller
7//! via LRU probe), removal, lookup and a `k_closest` query used by both
8//! `FIND_NODE` and `FIND_CLOSEST` message-layer flows.
9//!
10//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
11//! Anthropic Claude
12
13use super::{
14 contact::Contact,
15 id::{
16 ID_BITS,
17 NodeId,
18 },
19 kmap::{
20 InsertOutcome,
21 KMap,
22 },
23};
24
25use oxedyne_fe2o3_core::prelude::*;
26
27
28/// A Kademlia routing table for a single local node.
29#[derive(Clone, Debug)]
30pub struct RoutingTable {
31 local_id: NodeId,
32 k: usize, // shared by every k-map
33 maps: Vec<KMap>, // 256, indexed by XOR-distance bit position
34}
35
36impl RoutingTable {
37 /// Every k-map gets capacity `k`.
38 pub fn new(local_id: NodeId, k: usize) -> Outcome<Self> {
39 if k == 0 {
40 return Err(err!(
41 "Routing table k must be greater than zero.";
42 Invalid, Input));
43 }
44 let mut maps = Vec::with_capacity(ID_BITS);
45 for _ in 0..ID_BITS {
46 maps.push(res!(KMap::new(k)));
47 }
48 Ok(Self { local_id, k, maps })
49 }
50
51 pub fn local_id(&self) -> &NodeId {
52 &self.local_id
53 }
54
55 pub fn k(&self) -> usize {
56 self.k
57 }
58
59 /// `None` where no caller follow-up is required: a new insertion, a refresh
60 /// of an existing entry, or a contact that is the local node itself, which
61 /// is never routed through. [`InsertOutcome::Full`] means the target k-map
62 /// is full and the caller must probe the returned candidate, then call
63 /// [`RoutingTable::keep_lru`] or [`RoutingTable::evict_and_insert`].
64 pub fn insert(&mut self, contact: Contact) -> Outcome<Option<InsertOutcome>> {
65 let Some(idx) = self.local_id.bucket_index(&contact.node_id) else {
66 // Distance zero -- the contact is the local node. Silently
67 // refuse; this is a caller-side guarantee the table protects.
68 return Ok(None);
69 };
70 let map = res!(self.map_mut(idx));
71 Ok(match map.insert(contact) {
72 InsertOutcome::Inserted | InsertOutcome::Refreshed => None,
73 full @ InsertOutcome::Full { .. } => Some(full),
74 })
75 }
76
77 /// Call this after an external liveness probe on a candidate returned by
78 /// [`InsertOutcome::Full`] succeeded. `now` becomes the refreshed
79 /// `last_seen` tick.
80 pub fn keep_lru(&mut self, probed: &NodeId, now: u64) -> Outcome<()> {
81 let Some(idx) = self.local_id.bucket_index(probed) else {
82 return Err(err!(
83 "Cannot keep_lru for the local node itself.";
84 Invalid, Input));
85 };
86 res!(self.map_mut(idx)).keep_lru(now);
87 Ok(())
88 }
89
90 /// Call this after an external liveness probe on a candidate returned by
91 /// [`InsertOutcome::Full`] failed. `new` is the contact that was pending.
92 pub fn evict_and_insert(&mut self, new: Contact) -> Outcome<Option<Contact>> {
93 let Some(idx) = self.local_id.bucket_index(&new.node_id) else {
94 return Err(err!(
95 "Cannot evict_and_insert for the local node itself.";
96 Invalid, Input));
97 };
98 Ok(res!(self.map_mut(idx)).evict_and_insert(new))
99 }
100
101 pub fn remove(&mut self, id: &NodeId) -> Outcome<Option<Contact>> {
102 let Some(idx) = self.local_id.bucket_index(id) else {
103 return Ok(None);
104 };
105 Ok(res!(self.map_mut(idx)).remove(id))
106 }
107
108 pub fn get(&self, id: &NodeId) -> Outcome<Option<&Contact>> {
109 let Some(idx) = self.local_id.bucket_index(id) else {
110 return Ok(None);
111 };
112 Ok(res!(self.map(idx)).get(id))
113 }
114
115 /// Refreshes the `last_seen` of an existing contact and nothing else. False
116 /// if the contact was not there.
117 pub fn touch(&mut self, id: &NodeId, now: u64) -> Outcome<bool> {
118 let Some(idx) = self.local_id.bucket_index(id) else {
119 return Ok(false);
120 };
121 Ok(res!(self.map_mut(idx)).touch(id, now))
122 }
123
124 /// Across all k-maps.
125 pub fn len(&self) -> usize {
126 self.maps.iter().map(|m| m.len()).sum()
127 }
128
129 pub fn is_empty(&self) -> bool {
130 self.maps.iter().all(|m| m.is_empty())
131 }
132
133 /// Up to `want` contacts, in ascending XOR distance from `target`.
134 ///
135 /// Serves both `FIND_NODE(target)` and `FIND_CLOSEST(region)` at the
136 /// message layer. The underlying algorithm is the same -- only the caller
137 /// context differs. Ties on distance break by MRU: contacts in the same
138 /// bucket appear in MRU-first order, which is the natural iteration order
139 /// of a [`KMap`].
140 pub fn k_closest(&self, target: &NodeId, want: usize) -> Vec<Contact> {
141 let mut out: Vec<Contact> = Vec::with_capacity(want.min(self.k));
142 if want == 0 {
143 return out;
144 }
145 // Gather every contact, tagged with its distance to the target.
146 let mut tagged: Vec<(super::id::Distance, Contact)> =
147 Vec::with_capacity(self.len());
148 for map in &self.maps {
149 for c in map.iter() {
150 let d = c.node_id.distance(target);
151 tagged.push((d, c.clone()));
152 }
153 }
154 // Sort by distance ascending; stable to preserve MRU tiebreak.
155 tagged.sort_by(|a, b| a.0.cmp(&b.0));
156 for (_, c) in tagged.into_iter().take(want) {
157 out.push(c);
158 }
159 out
160 }
161
162 fn map(&self, idx: usize) -> Outcome<&KMap> {
163 self.maps.get(idx).ok_or_else(|| err!(
164 "Bucket index {} out of range (0..{}).", idx, ID_BITS;
165 Invalid, Input, Bug))
166 }
167
168 fn map_mut(&mut self, idx: usize) -> Outcome<&mut KMap> {
169 if idx >= self.maps.len() {
170 return Err(err!(
171 "Bucket index {} out of range (0..{}).", idx, ID_BITS;
172 Invalid, Input, Bug));
173 }
174 Ok(&mut self.maps[idx])
175 }
176}