rings_core/dht/finger/
mod.rs

1//! FingerTable
2
3#![deny(missing_docs)]
4
5use serde::Deserialize;
6use serde::Serialize;
7
8use crate::dht::did::BiasId;
9use crate::dht::Did;
10
11/// Default number of Chord finger slots for a 160-bit `Did`.
12pub const DEFAULT_FINGER_TABLE_SIZE: usize = 160;
13
14/// Finger table of Chord DHT
15/// Ring's finger table is implemented with BiasRing
16#[derive(Clone, Debug, Serialize, Deserialize)]
17pub struct FingerTable {
18    did: Did,
19    size: usize,
20    finger: Vec<Option<Did>>,
21    pub(super) fix_finger_index: usize,
22}
23
24impl PartialEq for FingerTable {
25    fn eq(&self, other: &Self) -> bool {
26        self.did == other.did && self.size == other.size && self.finger == other.finger
27    }
28}
29
30impl Eq for FingerTable {}
31
32impl FingerTable {
33    /// builder
34    ///
35    /// `Did` is represented by H160, so finger slots above 160 would wrap the
36    /// `2^index` lookup target back into the same 160-bit space. Values above
37    /// [`DEFAULT_FINGER_TABLE_SIZE`] are clamped; zero is allowed for tests that
38    /// intentionally disable finger maintenance.
39    pub fn new(did: Did, size: usize) -> Self {
40        let size = size.min(DEFAULT_FINGER_TABLE_SIZE);
41        Self {
42            did,
43            size,
44            finger: vec![None; size],
45            fix_finger_index: 0,
46        }
47    }
48
49    /// is empty
50    pub fn is_empty(&self) -> bool {
51        self.len() == 0
52    }
53
54    /// Get first element from Finger Table
55    pub fn first(&self) -> Option<Did> {
56        self.finger.iter().flatten().next().copied()
57    }
58
59    /// getter
60    pub fn get(&self, index: usize) -> Option<Did> {
61        self.finger.get(index).copied().flatten()
62    }
63
64    fn write_slot(&mut self, index: usize, did: Option<Did>) {
65        if let Some(slot) = self.finger.get_mut(index) {
66            *slot = did;
67        }
68    }
69
70    /// setter
71    pub fn set(&mut self, index: usize, did: Did) {
72        tracing::debug!("set finger table index: {} did: {}", index, did);
73        if index >= self.finger.len() {
74            tracing::error!("set finger index out of range, index: {}", index);
75            return;
76        }
77        if did == self.did {
78            tracing::trace!("set finger table with self did, ignore it");
79            return;
80        }
81        self.write_slot(index, Some(did));
82    }
83
84    /// setter for fix_finger_index
85    pub fn set_fix(&mut self, did: Did) {
86        let index = self.fix_finger_index;
87        self.set(index, did)
88    }
89
90    /// remove a node from dht finger table
91    pub fn remove(&mut self, did: Did) {
92        self.finger = crate::dht::topology::remove_finger_peer(&self.finger, did);
93    }
94
95    /// Join FingerTable
96    pub fn join(&mut self, did: Did) {
97        let observer = self.did;
98        let bias = did.bias(observer);
99
100        for k in 0..self.size {
101            let pos = Did::power_of_two(k);
102
103            if bias.pos() < pos {
104                continue;
105            }
106
107            if let Some(v) = self.finger.get(k).copied().flatten() {
108                if BiasId::cmp_from_observer(observer, did, v) == std::cmp::Ordering::Greater {
109                    continue;
110                }
111            }
112
113            self.write_slot(k, Some(did));
114        }
115    }
116
117    /// Check finger is contains some node
118    pub fn contains(&self, v: Option<Did>) -> bool {
119        self.finger.contains(&v)
120    }
121
122    /// get closest predecessor
123    pub fn closest_predecessor(&self, did: Did) -> Did {
124        let observer = self.did;
125
126        for i in (0..self.size).rev() {
127            if let Some(v) = self.finger.get(i).copied().flatten() {
128                if BiasId::cmp_from_observer(observer, v, did) == std::cmp::Ordering::Less {
129                    return v;
130                }
131            }
132        }
133
134        self.did
135    }
136
137    /// get length of finger
138    pub fn len(&self) -> usize {
139        self.finger.iter().flatten().count()
140    }
141
142    /// Get the number of slots in this finger table.
143    pub fn slot_count(&self) -> usize {
144        self.size
145    }
146
147    /// Get the next finger index maintained by the periodic fixer.
148    pub fn fix_finger_index(&self) -> usize {
149        self.fix_finger_index
150    }
151
152    /// get finger list
153    pub fn list(&self) -> &Vec<Option<Did>> {
154        &self.finger
155    }
156
157    /// Replace the full finger state with a value produced by the pure topology transition.
158    ///
159    /// Post: the table keeps its fixed slot count; entries beyond that count
160    /// are ignored, missing entries become `None`, and the fix cursor is
161    /// clamped to a valid slot when the table is non-empty.
162    pub(crate) fn replace_state(&mut self, fingers: &[Option<Did>], fix_finger_index: usize) {
163        self.finger = fingers.iter().copied().take(self.size).collect();
164        self.finger.resize(self.size, None);
165        self.fix_finger_index = if self.size == 0 {
166            0
167        } else {
168            fix_finger_index % self.size
169        };
170    }
171
172    /// Reset finger table to empty vector
173    #[cfg(test)]
174    pub fn reset_finger(&mut self) {
175        self.finger = vec![None; self.size]
176    }
177
178    /// Clone a finger table
179    #[cfg(test)]
180    pub fn clone_finger(self) -> Vec<Option<Did>> {
181        self.finger
182    }
183}
184
185#[cfg(test)]
186mod test_finger;
rings_core/dht/finger/mod.rs

rings_core/dht/finger/
mod.rs
