1use std::collections::HashMap;
6
7use serde::Serialize;
8use zigbee_primitives::NodeId;
9
10#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize)]
12#[serde(rename_all = "snake_case")]
13pub enum LinkSource {
14 LastHop,
16 RouteRecord,
18 NeighborTable,
20}
21
22#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
25pub struct Link {
26 pub from: NodeId,
28 pub to: NodeId,
30 pub lqi: Option<u8>,
32 pub rssi: Option<i8>,
34 pub source: LinkSource,
36 pub seen_unix: u64,
38}
39
40pub const MAX_AGE_S: u64 = 24 * 3600;
42pub const MAX_LINKS: usize = 8192;
44
45#[derive(Debug, Default, Clone)]
47pub struct Topology {
48 links: HashMap<(NodeId, NodeId), Link>,
49 routes: HashMap<NodeId, Vec<NodeId>>,
51}
52
53impl Topology {
54 fn put(&mut self, link: Link) {
55 if self.links.len() >= MAX_LINKS && !self.links.contains_key(&(link.from, link.to)) {
56 self.expire(link.seen_unix);
57 if self.links.len() >= MAX_LINKS {
58 if let Some(oldest) = self
59 .links
60 .values()
61 .min_by_key(|l| l.seen_unix)
62 .map(|l| (l.from, l.to))
63 {
64 self.links.remove(&oldest);
65 }
66 }
67 }
68 let key = (link.from, link.to);
69 match self.links.get_mut(&key) {
70 Some(old) if link.lqi.is_none() => {
73 old.seen_unix = link.seen_unix;
74 }
75 _ => {
76 self.links.insert(key, link);
77 }
78 }
79 }
80
81 pub fn last_hop(
85 &mut self,
86 source: NodeId,
87 coordinator: NodeId,
88 lqi: u8,
89 rssi: Option<i8>,
90 now: u64,
91 ) {
92 let from = self
93 .routes
94 .get(&source)
95 .and_then(|r| r.last().copied())
96 .unwrap_or(source);
97 self.put(Link {
98 from,
99 to: coordinator,
100 lqi: Some(lqi),
101 rssi,
102 source: LinkSource::LastHop,
103 seen_unix: now,
104 });
105 }
106
107 pub fn route_record(
109 &mut self,
110 source: NodeId,
111 relays: &[NodeId],
112 coordinator: NodeId,
113 lqi: Option<u8>,
114 rssi: Option<i8>,
115 now: u64,
116 ) {
117 let mut path = Vec::with_capacity(relays.len() + 2);
118 path.push(source);
119 path.extend_from_slice(relays);
120 path.push(coordinator);
121 for (i, pair) in path.windows(2).enumerate() {
122 if let [from, to] = pair {
123 let last = i + 2 == path.len();
124 self.put(Link {
125 from: *from,
126 to: *to,
127 lqi: lqi.filter(|_| last),
128 rssi: rssi.filter(|_| last),
129 source: LinkSource::RouteRecord,
130 seen_unix: now,
131 });
132 }
133 }
134 self.routes.insert(source, relays.to_vec());
135 }
136
137 pub fn neighbor(&mut self, router: NodeId, neighbor: NodeId, lqi: u8, now: u64) {
139 self.put(Link {
140 from: neighbor,
141 to: router,
142 lqi: Some(lqi),
143 rssi: None,
144 source: LinkSource::NeighborTable,
145 seen_unix: now,
146 });
147 }
148
149 pub fn remove_node(&mut self, node: NodeId) {
151 self.links
152 .retain(|(from, to), _| *from != node && *to != node);
153 self.routes.remove(&node);
154 }
155
156 pub fn expire(&mut self, now: u64) {
158 self.links
159 .retain(|_, l| now.saturating_sub(l.seen_unix) <= MAX_AGE_S);
160 }
161
162 pub fn links(&self) -> Vec<Link> {
164 let mut out: Vec<Link> = self.links.values().cloned().collect();
165 out.sort_by_key(|l| (l.from, l.to));
166 out
167 }
168
169 pub fn route(&self, source: NodeId) -> Option<&[NodeId]> {
171 self.routes.get(&source).map(Vec::as_slice)
172 }
173}
174
175#[cfg(test)]
176mod tests {
177 use super::*;
178
179 #[test]
180 fn last_hop_follows_the_route_record() {
181 let mut t = Topology::default();
182 t.last_hop(0x1111, 0, 200, Some(-40), 10);
183 t.route_record(0x2222, &[0x3333, 0x1111], 0, Some(150), Some(-60), 11);
184 t.last_hop(0x2222, 0, 140, Some(-62), 12);
185 let links = t.links();
186 let hop = links
187 .iter()
188 .find(|l| l.from == 0x1111 && l.to == 0)
189 .unwrap();
190 assert_eq!(hop.lqi, Some(140));
191 assert!(links
192 .iter()
193 .any(|l| l.from == 0x2222 && l.to == 0x3333 && l.source == LinkSource::RouteRecord));
194 assert!(links.iter().any(|l| l.from == 0x3333 && l.to == 0x1111));
195 t.expire(11 + MAX_AGE_S + 1);
196 assert_eq!(t.links().len(), 1);
197 t.remove_node(0x1111);
198 assert!(t.links().is_empty());
199 }
200
201 #[test]
202 fn table_is_bounded() {
203 let mut t = Topology::default();
204 for i in 0..(MAX_LINKS as u32 + 100) {
205 t.neighbor((i % 65000) as u16 + 1, 0, 1, u64::from(i));
206 }
207 assert!(t.links().len() <= MAX_LINKS);
208 }
209}