Oregami
Repositories/oxedyne/fe2o3

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

4.8 KiB, 58 runs

created by r1870400018:11190, 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//! A single Kademlia k-map -- one bucket of the routing table.
2//!
3//! Each [`KMap`] stores up to `k` contacts ordered from most- to
4//! least-recently-seen. On touch a contact moves to the front; on overflow the
5//! LRU at the tail becomes the eviction candidate. Replacement is
6//! LRU-biased: a live LRU is retained (the incoming contact is discarded) and
7//! only a confirmed-dead LRU is evicted. The bias reduces churn and raises
8//! the cost of eclipse attacks.
9//!
10//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
11//! Anthropic Claude
12
13use super::{
14 contact::Contact,
15 id::NodeId,
16};
17
18use oxedyne_fe2o3_core::prelude::*;
19
20use std::collections::VecDeque;
21
22
23#[derive(Clone, Debug)]
24pub enum InsertOutcome {
25 Inserted, // placed at the front
26 // The existing entry moved to the front, and its last_seen, rtt,
27 // capabilities and addresses were overwritten from the incoming copy.
28 Refreshed,
29 // The k-map is full, and candidate is the current LRU standing in the way.
30 // Probe it: call KMap::keep_lru if it answers, KMap::evict_and_insert with
31 // pending if it does not.
32 Full {
33 candidate: Contact,
34 pending: Contact,
35 },
36}
37
38
39/// A single Kademlia k-map holding up to `k` contacts.
40///
41/// The front of the internal deque is the most-recently-seen contact; the
42/// back is the least-recently-seen (the eviction candidate). Iteration order
43/// is MRU first.
44#[derive(Clone, Debug)]
45pub struct KMap {
46 k: usize,
47 entries: VecDeque<Contact>, // MRU at the front, LRU at the back
48}
49
50impl KMap {
51 pub fn new(k: usize) -> Outcome<Self> {
52 if k == 0 {
53 return Err(err!(
54 "KMap capacity k must be greater than zero.";
55 Invalid, Input));
56 }
57 Ok(Self {
58 k,
59 entries: VecDeque::with_capacity(k),
60 })
61 }
62
63 pub fn capacity(&self) -> usize {
64 self.k
65 }
66
67 pub fn len(&self) -> usize {
68 self.entries.len()
69 }
70
71 pub fn is_empty(&self) -> bool {
72 self.entries.is_empty()
73 }
74
75 pub fn is_full(&self) -> bool {
76 self.entries.len() >= self.k
77 }
78
79 /// MRU-first order.
80 pub fn iter(&self) -> impl Iterator<Item = &Contact> {
81 self.entries.iter()
82 }
83
84 /// Behaviour by case:
85 ///
86 /// - Not present, bucket has room: inserted at the front, returns
87 /// [`InsertOutcome::Inserted`].
88 /// - Already present: existing entry refreshed and moved to the front,
89 /// returns [`InsertOutcome::Refreshed`].
90 /// - Not present, bucket full: returns
91 /// [`InsertOutcome::Full`] with the current LRU as the eviction
92 /// candidate and the incoming contact to re-apply once liveness of the
93 /// LRU is known.
94 pub fn insert(&mut self, contact: Contact) -> InsertOutcome {
95 if let Some(pos) = self.position(&contact.node_id) {
96 // Refresh: overwrite metadata and move to front.
97 if let Some(mut existing) = self.entries.remove(pos) {
98 existing.addresses = contact.addresses;
99 existing.last_seen = contact.last_seen;
100 existing.rtt = contact.rtt;
101 existing.capabilities = contact.capabilities;
102 self.entries.push_front(existing);
103 }
104 return InsertOutcome::Refreshed;
105 }
106 if self.is_full() {
107 // Copy the LRU out as the eviction candidate without mutating.
108 let candidate = match self.entries.back() {
109 Some(c) => c.clone(),
110 None => {
111 // Unreachable: is_full implies non-empty.
112 self.entries.push_front(contact);
113 return InsertOutcome::Inserted;
114 },
115 };
116 return InsertOutcome::Full { candidate, pending: contact };
117 }
118 self.entries.push_front(contact);
119 InsertOutcome::Inserted
120 }
121
122 /// Call this once an external probe has confirmed the LRU is still live.
123 /// The tail contact moves to the front and its `last_seen` is updated; any
124 /// pending contact the caller was holding is discarded. No-op on an empty
125 /// bucket.
126 pub fn keep_lru(&mut self, now: u64) {
127 if let Some(mut lru) = self.entries.pop_back() {
128 lru.touch(now);
129 self.entries.push_front(lru);
130 }
131 }
132
133 /// Call this once an external probe has confirmed the LRU is dead. The
134 /// dead contact is dropped and returned; `new` goes to the front.
135 pub fn evict_and_insert(&mut self, new: Contact) -> Option<Contact> {
136 let evicted = self.entries.pop_back();
137 self.entries.push_front(new);
138 evicted
139 }
140
141 pub fn remove(&mut self, id: &NodeId) -> Option<Contact> {
142 let pos = ok!(self.position(id));
143 self.entries.remove(pos)
144 }
145
146 pub fn get(&self, id: &NodeId) -> Option<&Contact> {
147 self.entries.iter().find(|c| c.node_id == *id)
148 }
149
150 /// Records a liveness observation by moving an existing contact to the
151 /// front. False if the contact was not there.
152 pub fn touch(&mut self, id: &NodeId, now: u64) -> bool {
153 let Some(pos) = self.position(id) else { return false; };
154 if let Some(mut c) = self.entries.remove(pos) {
155 c.touch(now);
156 self.entries.push_front(c);
157 return true;
158 }
159 false
160 }
161
162 fn position(&self, id: &NodeId) -> Option<usize> {
163 self.entries.iter().position(|c| c.node_id == *id)
164 }
165}