ndn_store/
fib.rs

1use std::sync::Arc;
2
3use ndn_packet::Name;
4
5use crate::NameTrie;
6
7/// A nexthop in the FIB.
8///
9/// Uses `u32` for `face_id` (consistent with PIT records). The engine layer
10/// maps this to a typed `FaceId` from `ndn-transport`; keeping them as `u32`
11/// here avoids a same-layer dependency between `ndn-store` and `ndn-transport`.
12#[derive(Clone, Debug, PartialEq, Eq)]
13pub struct FibNexthop {
14    pub face_id: u32,
15    pub cost: u32,
16}
17
18/// A FIB entry — the set of nexthops for one name prefix.
19#[derive(Clone, Debug)]
20pub struct FibEntry {
21    pub nexthops: Vec<FibNexthop>,
22}
23
24impl FibEntry {
25    pub fn new(nexthops: Vec<FibNexthop>) -> Self {
26        Self { nexthops }
27    }
28}
29
30/// The Forwarding Information Base.
31///
32/// Wraps a `NameTrie<Arc<FibEntry>>`. Lookup uses longest-prefix match, so
33/// the most specific registered prefix wins. All methods are `&self` — the
34/// trie's per-node `RwLock` provides the necessary interior mutability.
35pub struct Fib(NameTrie<Arc<FibEntry>>);
36
37impl Fib {
38    pub fn new() -> Self {
39        Self(NameTrie::new())
40    }
41
42    /// Longest-prefix match for `name`.
43    pub fn lpm(&self, name: &Name) -> Option<Arc<FibEntry>> {
44        self.0.lpm(name)
45    }
46
47    /// Exact lookup — returns `Some` only if `prefix` is registered exactly.
48    pub fn get(&self, prefix: &Name) -> Option<Arc<FibEntry>> {
49        self.0.get(prefix)
50    }
51
52    /// Register or replace the entry for `prefix`.
53    pub fn insert(&self, prefix: &Name, entry: FibEntry) {
54        self.0.insert(prefix, Arc::new(entry));
55    }
56
57    /// Add one nexthop to `prefix`, creating the entry if it does not exist.
58    pub fn add_nexthop(&self, prefix: &Name, nexthop: FibNexthop) {
59        let nexthops = match self.0.get(prefix) {
60            Some(existing) => {
61                let mut v = existing.nexthops.clone();
62                v.push(nexthop);
63                v
64            }
65            None => vec![nexthop],
66        };
67        self.0.insert(prefix, Arc::new(FibEntry { nexthops }));
68    }
69
70    /// Remove the entry for `prefix` entirely.
71    pub fn remove(&self, prefix: &Name) {
72        self.0.remove(prefix);
73    }
74}
75
76impl Default for Fib {
77    fn default() -> Self {
78        Self::new()
79    }
80}
81
82#[cfg(test)]
83mod tests {
84    use super::*;
85    use bytes::Bytes;
86    use ndn_packet::NameComponent;
87
88    fn name(components: &[&str]) -> Name {
89        Name::from_components(
90            components
91                .iter()
92                .map(|s| NameComponent::generic(Bytes::copy_from_slice(s.as_bytes()))),
93        )
94    }
95
96    fn nexthop(face_id: u32, cost: u32) -> FibNexthop {
97        FibNexthop { face_id, cost }
98    }
99
100    // ── lpm ──────────────────────────────────────────────────────────────────
101
102    #[test]
103    fn lpm_empty_returns_none() {
104        let fib = Fib::new();
105        assert!(fib.lpm(&name(&["edu", "ucla"])).is_none());
106    }
107
108    #[test]
109    fn lpm_exact_match() {
110        let fib = Fib::new();
111        fib.insert(&name(&["edu", "ucla"]), FibEntry::new(vec![nexthop(1, 0)]));
112        let entry = fib.lpm(&name(&["edu", "ucla"])).unwrap();
113        assert_eq!(entry.nexthops[0].face_id, 1);
114    }
115
116    #[test]
117    fn lpm_most_specific_wins() {
118        let fib = Fib::new();
119        fib.insert(&name(&["edu"]), FibEntry::new(vec![nexthop(1, 10)]));
120        fib.insert(&name(&["edu", "ucla"]), FibEntry::new(vec![nexthop(2, 0)]));
121        let entry = fib.lpm(&name(&["edu", "ucla", "data"])).unwrap();
122        assert_eq!(entry.nexthops[0].face_id, 2);
123    }
124
125    #[test]
126    fn lpm_falls_back_to_shorter_prefix() {
127        let fib = Fib::new();
128        fib.insert(&name(&["edu"]), FibEntry::new(vec![nexthop(3, 5)]));
129        let entry = fib.lpm(&name(&["edu", "mit"])).unwrap();
130        assert_eq!(entry.nexthops[0].face_id, 3);
131    }
132
133    // ── add_nexthop ───────────────────────────────────────────────────────────
134
135    #[test]
136    fn add_nexthop_creates_entry() {
137        let fib = Fib::new();
138        fib.add_nexthop(&name(&["a"]), nexthop(7, 1));
139        let entry = fib.get(&name(&["a"])).unwrap();
140        assert_eq!(entry.nexthops.len(), 1);
141        assert_eq!(entry.nexthops[0].face_id, 7);
142    }
143
144    #[test]
145    fn add_nexthop_appends_to_existing() {
146        let fib = Fib::new();
147        fib.add_nexthop(&name(&["a"]), nexthop(1, 0));
148        fib.add_nexthop(&name(&["a"]), nexthop(2, 10));
149        let entry = fib.get(&name(&["a"])).unwrap();
150        assert_eq!(entry.nexthops.len(), 2);
151        assert!(entry.nexthops.iter().any(|n| n.face_id == 1));
152        assert!(entry.nexthops.iter().any(|n| n.face_id == 2));
153    }
154
155    // ── remove ────────────────────────────────────────────────────────────────
156
157    #[test]
158    fn remove_clears_prefix() {
159        let fib = Fib::new();
160        fib.insert(&name(&["a", "b"]), FibEntry::new(vec![nexthop(5, 0)]));
161        fib.remove(&name(&["a", "b"]));
162        assert!(fib.get(&name(&["a", "b"])).is_none());
163    }
164
165    #[test]
166    fn remove_does_not_affect_parent() {
167        let fib = Fib::new();
168        fib.insert(&name(&["a"]), FibEntry::new(vec![nexthop(1, 0)]));
169        fib.insert(&name(&["a", "b"]), FibEntry::new(vec![nexthop(2, 0)]));
170        fib.remove(&name(&["a", "b"]));
171        assert!(fib.get(&name(&["a"])).is_some());
172    }
173}
ndn_store/fib.rs

ndn_store/
fib.rs
