1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

use crate::Node;

/// Finger table entry
#[derive(Debug, Clone)]
pub struct Finger {
    pub(crate) _start: u64,
    pub node: Node,
}

impl Finger {
    /// Finger table size
    pub const FINGER_TABLE_SIZE: u8 = 64;

    /// Generate a finger id for a given node id and finger index.
    /// The finger id is calculated using the following formula:
    /// ```text
    /// (node_id + 2^(index - 1)) % 2^m
    /// ```
    ///
    /// Ref: https://pdos.csail.mit.edu/papers/ton:chord/paper-ton.pdf
    /// Ref: https://en.wikipedia.org/wiki/Chord_(peer-to-peer)#Finger_table
    ///
    /// # Arguments
    ///
    /// * `node_id` - The id of the node
    /// * `index` - The index of the finger
    pub(crate) fn finger_id(node_id: u64, index: u8) -> u64 {
        Self::sized_finger_id(Self::FINGER_TABLE_SIZE, node_id, index)
    }

    pub(crate) fn sized_finger_id(size: u8, node_id: u64, index: u8) -> u64 {
        if index == 0 {
            return node_id;
        }

        let offset: u128 = 2_u128.pow((index - 1) as u32);
        let power: u128 = 2_u128.pow(size as u32);

        let id = (node_id as u128 + offset) % power;

        id as u64
    }

    /// Initialize a new finger table for a node.
    /// All the fingers in the table will point to the same node.
    ///
    /// # Arguments
    ///
    /// * `node` - The node which will fill the finger table.
    ///            Usually it's the immediate successor of the node for which the finger table is being generated.
    pub(crate) fn init_finger_table(node: Node) -> Vec<Self> {
        Self::sized_finger_table(64, node)
    }

    fn sized_finger_table(size: u8, node: Node) -> Vec<Self> {
        let mut fingers = Vec::with_capacity(size as usize);

        // We start at 1 because the calculation of the finger id is based on the index
        // of the finger. The calculation assumes that the index starts at 1.
        for i in 1..(size + 1) {
            let finger_id = Self::sized_finger_id(size, node.id.0, i);
            fingers.push(Finger {
                _start: finger_id,
                node: node.clone(),
            });
        }

        fingers
    }
}

#[cfg(test)]
mod tests {
    use crate::NodeId;

    use super::*;
    use std::net::SocketAddr;

    #[test]
    fn it_should_generate_finger_id() {
        let node_id: u64 = 1;

        assert_eq!(Finger::finger_id(node_id, 0), 1);
        assert_eq!(Finger::finger_id(node_id, 1), 2);
        assert_eq!(Finger::finger_id(node_id, 2), 3);
        assert_eq!(Finger::finger_id(node_id, 3), 5);
        assert_eq!(Finger::finger_id(node_id, 4), 9);
        assert_eq!(Finger::finger_id(node_id, 5), 17);
        assert_eq!(Finger::finger_id(node_id, 6), 33);
        assert_eq!(Finger::finger_id(node_id, 7), 65);
        assert_eq!(Finger::finger_id(node_id, 8), 129);
        assert_eq!(Finger::finger_id(node_id, 9), 257);
        assert_eq!(Finger::finger_id(node_id, 10), 513);
        assert_eq!(Finger::finger_id(node_id, 11), 1025);
        assert_eq!(Finger::finger_id(node_id, 12), 2049);
        assert_eq!(Finger::finger_id(node_id, 13), 4097);
        assert_eq!(Finger::finger_id(node_id, 14), 8193);
        assert_eq!(Finger::finger_id(node_id, 15), 16385);
        assert_eq!(Finger::finger_id(node_id, 32), 2147483649);
        assert_eq!(Finger::finger_id(node_id, 64), 9223372036854775809);
        assert_eq!(Finger::finger_id(node_id, 65), 1);

        const M: u8 = 6;
        assert_eq!(Finger::sized_finger_id(M, node_id, 0), 1);
        assert_eq!(Finger::sized_finger_id(M, node_id, 1), 2);
        assert_eq!(Finger::sized_finger_id(M, node_id, 2), 3);
        assert_eq!(Finger::sized_finger_id(M, node_id, 3), 5);
        assert_eq!(Finger::sized_finger_id(M, node_id, 4), 9);
        assert_eq!(Finger::sized_finger_id(M, node_id, 5), 17);
        assert_eq!(Finger::sized_finger_id(M, node_id, 6), 33);
        assert_eq!(Finger::sized_finger_id(M, node_id, 7), 1);
    }

    #[test]
    fn it_should_generate_finger_table() {
        let node = Node::with_id(NodeId(1), SocketAddr::from(([127, 0, 0, 1], 42001)));

        let fingers = Finger::init_finger_table(node.clone());

        assert_eq!(fingers.len(), 64);
        assert_eq!(fingers[0]._start, 2);
        assert_eq!(fingers[1]._start, 3);
        assert_eq!(fingers[2]._start, 5);
        assert_eq!(fingers[3]._start, 9);
        assert_eq!(fingers[4]._start, 17);
        assert_eq!(fingers[5]._start, 33);
        assert_eq!(fingers[15]._start, 32769);
        assert_eq!(fingers[63]._start, 9223372036854775809);

        let node = Node::with_id(NodeId(5), SocketAddr::from(([127, 0, 0, 1], 42001)));
        let fingers = Finger::sized_finger_table(6, node);

        assert_eq!(fingers.len(), 6);
        assert_eq!(fingers[0]._start, 6);
        assert_eq!(fingers[1]._start, 7);
        assert_eq!(fingers[2]._start, 9);
        assert_eq!(fingers[3]._start, 13);
        assert_eq!(fingers[4]._start, 21);
        assert_eq!(fingers[5]._start, 37);
    }
}