rings_core/dht/
finger.rs

1//! FingerTable
2
3#![warn(missing_docs)]
4
5use derivative::Derivative;
6use serde::Deserialize;
7use serde::Serialize;
8
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(Derivative, Clone, Debug, Serialize, Deserialize)]
17#[derivative(PartialEq)]
18pub struct FingerTable {
19    did: Did,
20    size: usize,
21    finger: Vec<Option<Did>>,
22    #[derivative(PartialEq = "ignore")]
23    pub(super) fix_finger_index: usize,
24}
25
26impl FingerTable {
27    /// builder
28    ///
29    /// `Did` is represented by H160, so finger slots above 160 would wrap the
30    /// `2^index` lookup target back into the same 160-bit space. Values above
31    /// [`DEFAULT_FINGER_TABLE_SIZE`] are clamped; zero is allowed for tests that
32    /// intentionally disable finger maintenance.
33    pub fn new(did: Did, size: usize) -> Self {
34        let size = size.min(DEFAULT_FINGER_TABLE_SIZE);
35        Self {
36            did,
37            size,
38            finger: vec![None; size],
39            fix_finger_index: 0,
40        }
41    }
42
43    /// is empty
44    pub fn is_empty(&self) -> bool {
45        self.len() == 0
46    }
47
48    /// Get first element from Finger Table
49    pub fn first(&self) -> Option<Did> {
50        self.finger.iter().flatten().next().copied()
51    }
52
53    /// getter
54    pub fn get(&self, index: usize) -> Option<Did> {
55        self.finger.get(index).copied().flatten()
56    }
57
58    fn write_slot(&mut self, index: usize, did: Option<Did>) {
59        if let Some(slot) = self.finger.get_mut(index) {
60            *slot = did;
61        }
62    }
63
64    /// setter
65    pub fn set(&mut self, index: usize, did: Did) {
66        tracing::debug!("set finger table index: {} did: {}", index, did);
67        if index >= self.finger.len() {
68            tracing::error!("set finger index out of range, index: {}", index);
69            return;
70        }
71        if did == self.did {
72            tracing::trace!("set finger table with self did, ignore it");
73            return;
74        }
75        self.write_slot(index, Some(did));
76    }
77
78    /// setter for fix_finger_index
79    pub fn set_fix(&mut self, did: Did) {
80        let index = self.fix_finger_index;
81        self.set(index, did)
82    }
83
84    /// remove a node from dht finger table
85    pub fn remove(&mut self, did: Did) {
86        let indexes: Vec<usize> = self
87            .finger
88            .iter()
89            .enumerate()
90            .filter(|(_, &x)| x == Some(did))
91            .map(|(id, _)| id)
92            .collect();
93
94        if let (Some(first_idx), Some(last_idx)) =
95            (indexes.first().copied(), indexes.last().copied())
96        {
97            let end_idx = last_idx + 1;
98
99            // Update to the next did of last equaled did in finger table.
100            // If cannot get that, use None.
101            let fix_id = self.finger.get(end_idx).copied().flatten();
102
103            for idx in first_idx..end_idx {
104                self.write_slot(idx, fix_id);
105            }
106        }
107    }
108
109    /// Join FingerTable
110    pub fn join(&mut self, did: Did) {
111        let bias = did.bias(self.did);
112
113        for k in 0..self.size {
114            let pos = Did::power_of_two(k);
115
116            if bias.pos() < pos {
117                continue;
118            }
119
120            if let Some(v) = self.finger.get(k).copied().flatten() {
121                if bias > v.bias(self.did) {
122                    continue;
123                }
124            }
125
126            self.write_slot(k, Some(did));
127        }
128    }
129
130    /// Check finger is contains some node
131    pub fn contains(&self, v: Option<Did>) -> bool {
132        self.finger.contains(&v)
133    }
134
135    /// get closest predecessor
136    pub fn closest_predecessor(&self, did: Did) -> Did {
137        let bias = did.bias(self.did);
138
139        for i in (0..self.size).rev() {
140            if let Some(v) = self.finger.get(i).copied().flatten() {
141                if v.bias(self.did) < bias {
142                    return v;
143                }
144            }
145        }
146
147        self.did
148    }
149
150    /// get length of finger
151    pub fn len(&self) -> usize {
152        self.finger.iter().flatten().count()
153    }
154
155    /// Get the number of slots in this finger table.
156    pub fn slot_count(&self) -> usize {
157        self.size
158    }
159
160    /// Get the next finger index maintained by the periodic fixer.
161    pub fn fix_finger_index(&self) -> usize {
162        self.fix_finger_index
163    }
164
165    /// get finger list
166    pub fn list(&self) -> &Vec<Option<Did>> {
167        &self.finger
168    }
169
170    /// Replace the full finger state with a value produced by the pure topology transition.
171    ///
172    /// Post: the table keeps its fixed slot count; entries beyond that count
173    /// are ignored, missing entries become `None`, and the fix cursor is
174    /// clamped to a valid slot when the table is non-empty.
175    pub(crate) fn replace_state(&mut self, fingers: &[Option<Did>], fix_finger_index: usize) {
176        self.finger = fingers.iter().copied().take(self.size).collect();
177        self.finger.resize(self.size, None);
178        self.fix_finger_index = if self.size == 0 {
179            0
180        } else {
181            fix_finger_index % self.size
182        };
183    }
184
185    /// Reset finger table to empty vector
186    #[cfg(test)]
187    pub fn reset_finger(&mut self) {
188        self.finger = vec![None; self.size]
189    }
190
191    /// Clone a finger table
192    #[cfg(test)]
193    pub fn clone_finger(self) -> Vec<Option<Did>> {
194        self.finger
195    }
196}
197
198#[cfg(test)]
199mod test {
200    use super::*;
201    use crate::dht::tests::gen_ordered_dids;
202
203    #[test]
204    fn test_finger_table_size_bounds() {
205        let did = gen_ordered_dids(1)[0];
206
207        assert_eq!(
208            FingerTable::new(did, DEFAULT_FINGER_TABLE_SIZE + 1).slot_count(),
209            DEFAULT_FINGER_TABLE_SIZE
210        );
211        assert_eq!(FingerTable::new(did, 0).slot_count(), 0);
212    }
213
214    #[test]
215    fn test_finger_table_get_set_remove() {
216        let dids = gen_ordered_dids(5);
217
218        let mut table = FingerTable::new(dids[0], 3);
219        println!("check finger len");
220        assert_eq!(table.len(), 0);
221        assert_eq!(table.finger.len(), 3);
222        println!("check finger all items is none");
223        assert!(table.get(0).is_none(), "index 0 should be None");
224        assert!(table.get(1).is_none(), "index 1 should be None");
225        assert!(table.get(2).is_none(), "index 2 should be None");
226        assert!(table.get(3).is_none(), "index 3 should be None");
227
228        println!("set finger item");
229        let (id1, id2, id3, id4) = (dids[1], dids[2], dids[3], dids[4]);
230
231        table.set(0, id1);
232        assert_eq!(table.len(), 1);
233        assert_eq!(table.finger.len(), 3);
234
235        table.set(2, id3);
236        assert_eq!(table.len(), 2);
237        assert_eq!(table.finger.len(), 3);
238
239        assert!(
240            table.get(0) == Some(id1),
241            "expect value at index 0 is {:?}, got {:?}",
242            Some(id1),
243            table.get(0)
244        );
245        assert!(
246            table.get(1).is_none(),
247            "expect value at index 1 is None, got {:?}",
248            table.get(1)
249        );
250        assert!(
251            table.get(2) == Some(id3),
252            "expect value at index 2 is {:?}, got {:?}",
253            Some(id3),
254            table.get(2)
255        );
256
257        println!("set value out of index");
258        table.set(4, id4);
259        assert_eq!(table.len(), 2);
260        assert_eq!(table.finger.len(), 3);
261
262        println!("remove node from finger");
263        table.remove(id1);
264        assert_eq!(table.len(), 1);
265        assert_eq!(table.finger.len(), 3);
266        assert!(
267            table.get(0).is_none(),
268            "expect value at index 1 is None, got {:?}",
269            table.get(0)
270        );
271        assert!(
272            table.get(2) == Some(id3),
273            "expect value at index 2 is {:?}, got {:?}",
274            Some(id3),
275            table.get(2)
276        );
277
278        println!("remove node with auto fill");
279        table.set(0, id1);
280        table.set(1, id2);
281        assert!(
282            table.get(0) == Some(id1),
283            "expect value at index 0 is {:?}, got {:?}",
284            Some(id1),
285            table.get(0)
286        );
287        assert!(
288            table.get(1) == Some(id2),
289            "expect value at index 1 is {:?}, got {:?}",
290            Some(id2),
291            table.get(1)
292        );
293        assert!(
294            table.get(2) == Some(id3),
295            "expect value at index 2 is {:?}, got {:?}",
296            Some(id3),
297            table.get(2)
298        );
299
300        table.remove(id1);
301        assert_eq!(table.len(), 3);
302        assert_eq!(table.finger.len(), 3);
303        assert!(
304            table.get(0) == Some(id2),
305            "expect value at index 0 is {:?}, got {:?}",
306            id2,
307            table.get(0)
308        );
309        assert!(
310            table.get(1) == Some(id2),
311            "expect value at index 1 is {:?}, got {:?}",
312            Some(id2),
313            table.get(1),
314        );
315
316        println!("remove item not in fingers");
317        table.remove(id4);
318
319        println!("remove all items in fingers");
320        table.remove(id1);
321        assert_eq!(table.first(), Some(id2));
322
323        println!("check first item");
324        table.remove(id3);
325        assert_eq!(table.first(), Some(id2));
326
327        table.remove(id2);
328        assert_eq!(table.first(), None);
329        assert_eq!(table.len(), 0);
330        assert_eq!(table.finger.len(), 3);
331    }
332
333    #[test]
334    fn test_finger_table_remove_then_fill() {
335        let dids = gen_ordered_dids(6);
336        let (did1, did2, did3, did4, did5) = (dids[1], dids[2], dids[3], dids[4], dids[5]);
337
338        let mut table = FingerTable::new(dids[0], 5);
339
340        // [did1, did2, did3, did4, did5] - did1 = [did2, did2, did3, did4, did5]
341        table.reset_finger();
342        table.set(0, did1);
343        table.set(1, did2);
344        table.set(2, did3);
345        table.set(3, did4);
346        table.set(4, did5);
347        table.remove(did1);
348        assert_eq!(table.finger, [
349            Some(did2),
350            Some(did2),
351            Some(did3),
352            Some(did4),
353            Some(did5),
354        ]);
355
356        // [did1, did2, did3, did4, did5] - did2 = [did1, did3, did3, did4, did5]
357        table.reset_finger();
358        table.set(0, did1);
359        table.set(1, did2);
360        table.set(2, did3);
361        table.set(3, did4);
362        table.set(4, did5);
363        table.remove(did2);
364        assert_eq!(table.finger, [
365            Some(did1),
366            Some(did3),
367            Some(did3),
368            Some(did4),
369            Some(did5),
370        ]);
371
372        // [did1, None, did3, did4, did5] - did1 = [None, None, did3, did4, did5]
373        table.reset_finger();
374        table.set(0, did1);
375        table.set(2, did3);
376        table.set(3, did4);
377        table.set(4, did5);
378        table.remove(did1);
379        assert_eq!(table.finger, [
380            None,
381            None,
382            Some(did3),
383            Some(did4),
384            Some(did5),
385        ]);
386
387        // [did1, None, did3, did4, did5] - did3 = [did1, None, did4, did4, did5]
388        table.reset_finger();
389        table.set(0, did1);
390        table.set(2, did3);
391        table.set(3, did4);
392        table.set(4, did5);
393        table.remove(did3);
394        assert_eq!(table.finger, [
395            Some(did1),
396            None,
397            Some(did4),
398            Some(did4),
399            Some(did5),
400        ]);
401
402        // [did1, did2, did3, did4, did5] - did5 = [did1, did2, did4, did4, None]
403        table.reset_finger();
404        table.set(0, did1);
405        table.set(1, did2);
406        table.set(2, did3);
407        table.set(3, did4);
408        table.set(4, did5);
409        table.remove(did5);
410        assert_eq!(table.finger, [
411            Some(did1),
412            Some(did2),
413            Some(did3),
414            Some(did4),
415            None
416        ]);
417    }
418}
rings_core/dht/finger.rs

rings_core/dht/
finger.rs
