prefix_trie/joint/map/mod.rs
1//! Module that defines the JointPrefixMap
2
3use super::JointPrefix;
4use crate::{AsView, PrefixMap};
5#[cfg(test)]
6#[cfg(feature = "ipnet")]
7mod test;
8
9use either::{Left, Right};
10
11/// A Joint prefix map, implemented as two separate prefix trees.
12#[derive(Clone, Debug)]
13#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
14#[cfg_attr(
15 feature = "serde",
16 serde(bound(
17 serialize = "P::P1: serde::Serialize, P::P2: serde::Serialize, T: serde::Serialize",
18 deserialize = "P::P1: serde::Deserialize<'de>, P::P2: serde::Deserialize<'de>, T: serde::Deserialize<'de>",
19 ))
20)]
21pub struct JointPrefixMap<P, T>
22where
23 P: JointPrefix,
24{
25 /// PrefixMap that corresponds to the first prefix type
26 pub t1: PrefixMap<P::P1, T>,
27 /// PrefixMap that corresponds to the second prefix type
28 pub t2: PrefixMap<P::P2, T>,
29}
30
31impl<P, T> Default for JointPrefixMap<P, T>
32where
33 P: JointPrefix,
34{
35 fn default() -> Self {
36 Self {
37 t1: Default::default(),
38 t2: Default::default(),
39 }
40 }
41}
42
43impl<P: JointPrefix, T> JointPrefixMap<P, T> {
44 /// Create an empty prefix map
45 pub fn new() -> Self {
46 Self {
47 t1: PrefixMap::new(),
48 t2: PrefixMap::new(),
49 }
50 }
51
52 /// Returns the number of elements stored in `self`.
53 ///
54 /// ```
55 /// # use prefix_trie::joint::*;
56 /// # #[cfg(feature = "ipnet")]
57 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
58 /// let mut map: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::default();
59 /// map.insert("192.168.1.0/24".parse()?, 1u32);
60 /// map.insert("192.168.1.0/25".parse()?, 2u32);
61 /// map.insert("2001::1:0:0/96".parse()?, 3u32);
62 /// # let map = map.clone();
63 /// assert_eq!(map.len(), 3);
64 /// # Ok(())
65 /// # }
66 /// # #[cfg(not(feature = "ipnet"))]
67 /// # fn main() {}
68 /// ```
69 #[inline(always)]
70 pub fn len(&self) -> usize {
71 self.t1.len() + self.t2.len()
72 }
73
74 /// Returns `true` if the map contains no elements.
75 ///
76 /// ```
77 /// # use prefix_trie::joint::*;
78 /// # #[cfg(feature = "ipnet")]
79 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
80 /// let mut map: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
81 /// assert!(map.is_empty());
82 /// map.insert("2001::1:0:0/96".parse()?, 1u32);
83 /// assert!(!map.is_empty());
84 /// # Ok(())
85 /// # }
86 /// # #[cfg(not(feature = "ipnet"))]
87 /// # fn main() {}
88 /// ```
89 #[inline(always)]
90 pub fn is_empty(&self) -> bool {
91 self.len() == 0
92 }
93
94 /// Get the value of an element by matching exactly on the prefix.
95 ///
96 /// ```
97 /// # use prefix_trie::joint::*;
98 /// # #[cfg(feature = "ipnet")]
99 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
100 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
101 /// pm.insert("192.168.1.0/24".parse()?, 1);
102 /// pm.insert("2001::1:0:0/96".parse()?, 2);
103 /// assert_eq!(pm.get(&"192.168.1.0/24".parse()?), Some(&1));
104 /// assert_eq!(pm.get(&"192.168.2.0/24".parse()?), None);
105 /// assert_eq!(pm.get(&"192.168.0.0/23".parse()?), None);
106 /// assert_eq!(pm.get(&"192.168.1.128/25".parse()?), None);
107 /// assert_eq!(pm.get(&"2001::1:0:0/96".parse()?), Some(&2));
108 /// assert_eq!(pm.get(&"0ca8:1::/24".parse()?), None);
109 /// # Ok(())
110 /// # }
111 /// # #[cfg(not(feature = "ipnet"))]
112 /// # fn main() {}
113 /// ```
114 pub fn get<'a>(&'a self, prefix: &P) -> Option<&'a T> {
115 fork_ref!(self, prefix, get)
116 }
117
118 /// Get a mutable reference to a value of an element by matching exactly on the prefix.
119 ///
120 /// ```
121 /// # use prefix_trie::joint::*;
122 /// # #[cfg(feature = "ipnet")]
123 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
124 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
125 /// let prefix = "2001::/32".parse()?;
126 /// pm.insert(prefix, 1);
127 /// assert_eq!(pm.get(&prefix), Some(&1));
128 /// *pm.get_mut(&prefix).unwrap() += 1;
129 /// assert_eq!(pm.get(&prefix), Some(&2));
130 /// # Ok(())
131 /// # }
132 /// # #[cfg(not(feature = "ipnet"))]
133 /// # fn main() {}
134 /// ```
135 pub fn get_mut<'a>(&'a mut self, prefix: &P) -> Option<&'a mut T> {
136 fork_ref!(self, prefix, get_mut)
137 }
138
139 /// Get the value of an element by matching exactly on the prefix. Notice, that the returned
140 /// prefix may differ from the one provided in the host-part of the address.
141 ///
142 /// ```
143 /// # use prefix_trie::joint::*;
144 /// # #[cfg(feature = "ipnet")]
145 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
146 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
147 /// let prefix = "2001::/32".parse()?;
148 /// pm.insert(prefix, 1);
149 /// assert_eq!(pm.get_key_value(&prefix), Some((prefix, &1)));
150 /// # Ok(())
151 /// # }
152 /// # #[cfg(not(feature = "ipnet"))]
153 /// # fn main() {}
154 /// ```
155 pub fn get_key_value<'a>(&'a self, prefix: &P) -> Option<(P, &'a T)> {
156 fork_ref!(self, prefix as (P, T), get_key_value)
157 }
158
159 /// Get a value of an element by using longest prefix matching
160 ///
161 /// ```
162 /// # use prefix_trie::joint::*;
163 /// # #[cfg(feature = "ipnet")]
164 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
165 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
166 /// pm.insert("192.168.1.0/24".parse()?, 1);
167 /// pm.insert("192.168.0.0/23".parse()?, 2);
168 /// assert_eq!(pm.get_lpm(&"192.168.1.1/32".parse()?), Some(("192.168.1.0/24".parse()?, &1)));
169 /// assert_eq!(pm.get_lpm(&"192.168.1.0/24".parse()?), Some(("192.168.1.0/24".parse()?, &1)));
170 /// assert_eq!(pm.get_lpm(&"192.168.0.0/24".parse()?), Some(("192.168.0.0/23".parse()?, &2)));
171 /// assert_eq!(pm.get_lpm(&"192.168.2.0/24".parse()?), None);
172 /// # Ok(())
173 /// # }
174 /// # #[cfg(not(feature = "ipnet"))]
175 /// # fn main() {}
176 /// ```
177 pub fn get_lpm<'a>(&'a self, prefix: &P) -> Option<(P, &'a T)> {
178 fork_ref!(self, prefix as (P, T), get_lpm)
179 }
180
181 /// Get a mutable reference to a value of an element by using longest prefix matching
182 ///
183 /// ```
184 /// # use prefix_trie::joint::*;
185 /// # #[cfg(feature = "ipnet")]
186 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
187 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
188 /// pm.insert("192.168.1.0/24".parse()?, 1);
189 /// pm.insert("192.168.0.0/23".parse()?, 2);
190 /// assert_eq!(pm.get_lpm(&"192.168.1.1/32".parse()?), Some(("192.168.1.0/24".parse()?, &1)));
191 /// *pm.get_lpm_mut(&"192.168.1.64/26".parse()?).unwrap().1 += 1;
192 /// assert_eq!(pm.get_lpm(&"192.168.1.1/32".parse()?), Some(("192.168.1.0/24".parse()?, &2)));
193 /// # Ok(())
194 /// # }
195 /// # #[cfg(not(feature = "ipnet"))]
196 /// # fn main() {}
197 /// ```
198 pub fn get_lpm_mut<'a>(&'a mut self, prefix: &P) -> Option<(P, &'a mut T)> {
199 fork_ref!(self, prefix as (P, T), get_lpm_mut)
200 }
201
202 /// Check if a key is present in the datastructure.
203 ///
204 /// ```
205 /// # use prefix_trie::joint::*;
206 /// # #[cfg(feature = "ipnet")]
207 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
208 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
209 /// pm.insert("192.168.1.0/24".parse()?, 1);
210 /// assert!(pm.contains_key(&"192.168.1.0/24".parse()?));
211 /// assert!(!pm.contains_key(&"192.168.2.0/24".parse()?));
212 /// assert!(!pm.contains_key(&"192.168.0.0/23".parse()?));
213 /// assert!(!pm.contains_key(&"192.168.1.128/25".parse()?));
214 /// # Ok(())
215 /// # }
216 /// # #[cfg(not(feature = "ipnet"))]
217 /// # fn main() {}
218 /// ```
219 pub fn contains_key(&self, prefix: &P) -> bool {
220 fork_ref!(self, prefix, contains_key)
221 }
222
223 /// Get the longest prefix in the datastructure that matches the given `prefix`.
224 ///
225 /// ```
226 /// # use prefix_trie::joint::*;
227 /// # #[cfg(feature = "ipnet")]
228 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
229 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
230 /// pm.insert("192.168.1.0/24".parse()?, 1);
231 /// pm.insert("192.168.0.0/23".parse()?, 2);
232 /// assert_eq!(pm.get_lpm_prefix(&"192.168.1.1/32".parse()?), Some("192.168.1.0/24".parse()?));
233 /// assert_eq!(pm.get_lpm_prefix(&"192.168.1.0/24".parse()?), Some("192.168.1.0/24".parse()?));
234 /// assert_eq!(pm.get_lpm_prefix(&"192.168.0.0/24".parse()?), Some("192.168.0.0/23".parse()?));
235 /// assert_eq!(pm.get_lpm_prefix(&"192.168.2.0/24".parse()?), None);
236 /// # Ok(())
237 /// # }
238 /// # #[cfg(not(feature = "ipnet"))]
239 /// # fn main() {}
240 /// ```
241 pub fn get_lpm_prefix(&self, prefix: &P) -> Option<P> {
242 fork_ref!(self, prefix as P, get_lpm_prefix)
243 }
244
245 /// Get a value of an element by using shortest prefix matching.
246 ///
247 /// ```
248 /// # use prefix_trie::joint::*;
249 /// # #[cfg(feature = "ipnet")]
250 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
251 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
252 /// pm.insert("192.168.1.0/24".parse()?, 1);
253 /// pm.insert("192.168.0.0/23".parse()?, 2);
254 /// assert_eq!(pm.get_spm(&"192.168.1.1/32".parse()?), Some(("192.168.0.0/23".parse()?, &2)));
255 /// assert_eq!(pm.get_spm(&"192.168.1.0/24".parse()?), Some(("192.168.0.0/23".parse()?, &2)));
256 /// assert_eq!(pm.get_spm(&"192.168.0.0/23".parse()?), Some(("192.168.0.0/23".parse()?, &2)));
257 /// assert_eq!(pm.get_spm(&"192.168.2.0/24".parse()?), None);
258 /// # Ok(())
259 /// # }
260 /// # #[cfg(not(feature = "ipnet"))]
261 /// # fn main() {}
262 pub fn get_spm<'a>(&'a self, prefix: &P) -> Option<(P, &'a T)> {
263 fork_ref!(self, prefix as (P, T), get_spm)
264 }
265
266 /// Get the shortest prefix in the datastructure that contains the given `prefix`.
267 ///
268 /// ```
269 /// # use prefix_trie::joint::*;
270 /// # #[cfg(feature = "ipnet")]
271 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
272 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
273 /// pm.insert("192.168.1.1/24".parse()?, 1);
274 /// pm.insert("192.168.0.0/23".parse()?, 2);
275 /// assert_eq!(pm.get_spm_prefix(&"192.168.1.1/32".parse()?), Some("192.168.0.0/23".parse()?));
276 /// assert_eq!(pm.get_spm_prefix(&"192.168.1.0/24".parse()?), Some("192.168.0.0/23".parse()?));
277 /// assert_eq!(pm.get_spm_prefix(&"192.168.0.0/23".parse()?), Some("192.168.0.0/23".parse()?));
278 /// assert_eq!(pm.get_spm_prefix(&"192.168.2.0/24".parse()?), None);
279 /// # Ok(())
280 /// # }
281 /// # #[cfg(not(feature = "ipnet"))]
282 /// # fn main() {}
283 pub fn get_spm_prefix(&self, prefix: &P) -> Option<P> {
284 fork_ref!(self, prefix as P, get_spm_prefix)
285 }
286
287 /// Insert a new item into the prefix-map. This function may return any value that existed
288 /// before.
289 ///
290 /// In case the node already exists in the tree, its prefix will be replaced by the provided
291 /// argument. This allows you to store additional information in the host part of the prefix.
292 ///
293 /// ```
294 /// # use prefix_trie::joint::*;
295 /// # #[cfg(feature = "ipnet")]
296 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
297 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
298 /// assert_eq!(pm.insert("192.168.0.0/23".parse()?, 1), None);
299 /// assert_eq!(pm.insert("192.168.1.0/24".parse()?, 2), None);
300 /// assert_eq!(pm.insert("192.168.1.0/24".parse()?, 3), Some(2));
301 /// assert_eq!(pm.insert("2001::1:0:0/96".parse()?, 4), None);
302 /// assert_eq!(pm.insert("2001::1:0:0/97".parse()?, 5), None);
303 /// assert_eq!(pm.insert("2001::1:0:0/97".parse()?, 6), Some(5));
304 /// # Ok(())
305 /// # }
306 /// # #[cfg(not(feature = "ipnet"))]
307 /// # fn main() {}
308 /// ```
309 pub fn insert(&mut self, prefix: P, value: T) -> Option<T> {
310 fork!(self, prefix, insert, value)
311 }
312
313 /// Gets the given key’s corresponding entry in the map for in-place manipulation. In case you
314 /// eventually insert an element into the map, this operation will also replace the prefix in
315 /// the node with the existing one. That is if you store additional information in the host part
316 /// of the address (the one that is masked out).
317 ///
318 /// ```
319 /// # use prefix_trie::joint::*;
320 /// # #[cfg(feature = "ipnet")]
321 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
322 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
323 /// pm.insert("192.168.1.0/24".parse()?, vec![1]);
324 /// pm.entry("192.168.1.0/24".parse()?).or_default().push(2);
325 /// pm.entry("192.168.1.0/25".parse()?).or_default().push(3);
326 /// pm.entry("c0a8:1::/24".parse()?).or_default().push(4);
327 /// assert_eq!(pm.get(&"192.168.1.0/24".parse()?), Some(&vec![1, 2]));
328 /// assert_eq!(pm.get(&"192.168.1.0/25".parse()?), Some(&vec![3]));
329 /// assert_eq!(pm.get(&"c0a8:1::/24".parse()?), Some(&vec![4]));
330 /// # Ok(())
331 /// # }
332 /// # #[cfg(not(feature = "ipnet"))]
333 /// # fn main() {}
334 /// ```
335 pub fn entry(&mut self, prefix: P) -> Entry<'_, P, T> {
336 match prefix.p1_or_p2() {
337 Left(p1) => match self.t1.entry(p1) {
338 crate::map::Entry::Vacant(e) => Entry::Vacant(VacantEntry::P1(e)),
339 crate::map::Entry::Occupied(e) => Entry::Occupied(OccupiedEntry::P1(e)),
340 },
341 Right(p2) => match self.t2.entry(p2) {
342 crate::map::Entry::Vacant(e) => Entry::Vacant(VacantEntry::P2(e)),
343 crate::map::Entry::Occupied(e) => Entry::Occupied(OccupiedEntry::P2(e)),
344 },
345 }
346 }
347
348 /// Removes a key from the map, returning the value at the key if the key was previously in the
349 /// map. In contrast to [`Self::remove_keep_tree`], this operation will modify the tree
350 /// structure. As a result, this operation takes longer than `remove_keep_tree`, as does
351 /// inserting the same element again. However, future reads may be faster as less nodes need to
352 /// be traversed. Further, it reduces the memory footprint to its minimum.
353 ///
354 /// ```
355 /// # use prefix_trie::joint::*;
356 /// # #[cfg(feature = "ipnet")]
357 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
358 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
359 /// let prefix = "192.168.1.0/24".parse()?;
360 /// pm.insert(prefix, 1);
361 /// assert_eq!(pm.get(&prefix), Some(&1));
362 /// assert_eq!(pm.remove(&prefix), Some(1));
363 /// assert_eq!(pm.get(&prefix), None);
364 /// # Ok(())
365 /// # }
366 /// # #[cfg(not(feature = "ipnet"))]
367 /// # fn main() {}
368 /// ```
369 pub fn remove(&mut self, prefix: &P) -> Option<T> {
370 fork_ref!(self, prefix, remove)
371 }
372
373 /// Removes a key from the map, returning the value at the key if the key was previously in the
374 /// map. In contrast to [`Self::remove`], his operation will keep the tree structure as is, but
375 /// only remove the element from it. This allows any future `insert` on the same prefix to be
376 /// faster. However future reads from the tree might be a bit slower because they need to
377 /// traverse more nodes.
378 ///
379 /// ```
380 /// # use prefix_trie::joint::*;
381 /// # #[cfg(feature = "ipnet")]
382 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
383 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
384 /// let prefix = "192.168.1.0/24".parse()?;
385 /// pm.insert(prefix, 1);
386 /// assert_eq!(pm.get(&prefix), Some(&1));
387 /// assert_eq!(pm.remove_keep_tree(&prefix), Some(1));
388 /// assert_eq!(pm.get(&prefix), None);
389 ///
390 /// // future inserts of the same key are now faster!
391 /// pm.insert(prefix, 1);
392 /// # Ok(())
393 /// # }
394 /// # #[cfg(not(feature = "ipnet"))]
395 /// # fn main() {}
396 /// ```
397 pub fn remove_keep_tree(&mut self, prefix: &P) -> Option<T> {
398 fork_ref!(self, prefix, remove_keep_tree)
399 }
400
401 /// Remove all entries that are contained within `prefix`. This will change the tree
402 /// structure. This operation is `O(n)`, as the entries must be freed up one-by-one.
403 ///
404 /// ```
405 /// # use prefix_trie::joint::*;
406 /// # #[cfg(feature = "ipnet")]
407 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
408 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
409 /// pm.insert("192.168.0.0/22".parse()?, 1);
410 /// pm.insert("192.168.0.0/23".parse()?, 2);
411 /// pm.insert("192.168.0.0/24".parse()?, 3);
412 /// pm.insert("192.168.2.0/23".parse()?, 4);
413 /// pm.insert("192.168.2.0/24".parse()?, 5);
414 /// pm.remove_children(&"192.168.0.0/23".parse()?);
415 /// assert_eq!(pm.get(&"192.168.0.0/23".parse()?), None);
416 /// assert_eq!(pm.get(&"192.168.0.0/24".parse()?), None);
417 /// assert_eq!(pm.get(&"192.168.2.0/23".parse()?), Some(&4));
418 /// assert_eq!(pm.get(&"192.168.2.0/24".parse()?), Some(&5));
419 /// # Ok(())
420 /// # }
421 /// # #[cfg(not(feature = "ipnet"))]
422 /// # fn main() {}
423 /// ```
424 pub fn remove_children(&mut self, prefix: &P) {
425 fork_ref!(self, prefix, remove_children)
426 }
427
428 /// Clear the map but keep the allocated memory.
429 ///
430 /// ```
431 /// # use prefix_trie::joint::*;
432 /// # #[cfg(feature = "ipnet")]
433 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
434 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
435 /// pm.insert("192.168.0.0/24".parse()?, 1);
436 /// pm.insert("192.168.1.0/24".parse()?, 2);
437 /// pm.insert("2001::1:0:0/96".parse()?, 3);
438 /// pm.clear();
439 /// assert_eq!(pm.get(&"192.168.0.0/24".parse()?), None);
440 /// assert_eq!(pm.get(&"192.168.1.0/24".parse()?), None);
441 /// assert_eq!(pm.get(&"2001::1:0:0/96".parse()?), None);
442 /// # Ok(())
443 /// # }
444 /// # #[cfg(not(feature = "ipnet"))]
445 /// # fn main() {}
446 /// ```
447 pub fn clear(&mut self) {
448 self.t1.clear();
449 self.t2.clear();
450 }
451
452 /// Keep only the elements in the map that satisfy the given condition `f`.
453 ///
454 /// ```
455 /// # use prefix_trie::joint::*;
456 /// # #[cfg(feature = "ipnet")]
457 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
458 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
459 /// pm.insert("192.168.0.0/24".parse()?, 1);
460 /// pm.insert("192.168.1.0/24".parse()?, 2);
461 /// pm.insert("192.168.2.0/24".parse()?, 3);
462 /// pm.insert("192.168.2.0/25".parse()?, 4);
463 /// pm.insert("2001::1:0:0/24".parse()?, 5);
464 /// pm.insert("2001::1:0:0/25".parse()?, 6);
465 /// pm.retain(|_, t| *t % 2 == 0); // only keep the even values.
466 /// assert_eq!(pm.get(&"192.168.0.0/24".parse()?), None);
467 /// assert_eq!(pm.get(&"192.168.1.0/24".parse()?), Some(&2));
468 /// assert_eq!(pm.get(&"192.168.2.0/24".parse()?), None);
469 /// assert_eq!(pm.get(&"192.168.2.0/25".parse()?), Some(&4));
470 /// assert_eq!(pm.get(&"2001::1:0:0/24".parse()?), None);
471 /// assert_eq!(pm.get(&"2001::1:0:0/25".parse()?), Some(&6));
472 /// # Ok(())
473 /// # }
474 /// # #[cfg(not(feature = "ipnet"))]
475 /// # fn main() {}
476 /// ```
477 pub fn retain<F>(&mut self, mut f: F)
478 where
479 F: FnMut(P, &T) -> bool,
480 {
481 self.t1.retain(|p, t| f(P::from_p1(p), t));
482 self.t2.retain(|p, t| f(P::from_p2(p), t));
483 }
484
485 /// Iterate over all entries in the map that covers the given `prefix` (including `prefix`
486 /// itself if that is present in the map). The returned iterator yields `(&'a P, &'a T)`.
487 ///
488 /// The iterator will always yield elements ordered by their prefix length, i.e., their depth in
489 /// the tree.
490 ///
491 /// ```
492 /// # use prefix_trie::joint::*;
493 /// # #[cfg(feature = "ipnet")]
494 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
495 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
496 /// let p0 = "10.0.0.0/8".parse()?;
497 /// let p1 = "10.1.0.0/16".parse()?;
498 /// let p2 = "10.1.1.0/24".parse()?;
499 /// pm.insert(p0, 0);
500 /// pm.insert(p1, 1);
501 /// pm.insert(p2, 2);
502 /// pm.insert("10.1.2.0/24".parse()?, 3); // disjoint prefixes are not covered
503 /// pm.insert("10.1.1.0/25".parse()?, 4); // more specific prefixes are not covered
504 /// pm.insert("11.0.0.0/8".parse()?, 5); // Branch points that don't contain values are skipped
505 /// assert_eq!(
506 /// pm.cover(&p2).collect::<Vec<_>>(),
507 /// vec![(p0, &0), (p1, &1), (p2, &2)]
508 /// );
509 /// # Ok(())
510 /// # }
511 /// # #[cfg(not(feature = "ipnet"))]
512 /// # fn main() {}
513 /// ```
514 ///
515 /// This function also yields the root note *if* it is part of the map:
516 ///
517 /// ```
518 /// # use prefix_trie::joint::*;
519 /// # #[cfg(feature = "ipnet")]
520 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
521 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
522 /// let root = "0.0.0.0/0".parse()?;
523 /// pm.insert(root, 0);
524 /// assert_eq!(pm.cover(&"10.0.0.0/8".parse()?).collect::<Vec<_>>(), vec![(root, &0)]);
525 /// # Ok(())
526 /// # }
527 /// # #[cfg(not(feature = "ipnet"))]
528 /// # fn main() {}
529 /// ```
530 pub fn cover<'a, 'p>(&'a self, prefix: &'p P) -> Cover<'a, 'p, P, T> {
531 match prefix.p1_or_p2_ref() {
532 Left(p1) => Cover::P1(self.t1.cover(p1)),
533 Right(p2) => Cover::P2(self.t2.cover(p2)),
534 }
535 }
536
537 /// Iterate over all keys (prefixes) in the map that covers the given `prefix` (including
538 /// `prefix` itself if that is present in the map). The returned iterator yields `&'a P`.
539 ///
540 /// The iterator will always yield elements ordered by their prefix length, i.e., their depth in
541 /// the tree.
542 ///
543 /// ```
544 /// # use prefix_trie::joint::*;
545 /// # #[cfg(feature = "ipnet")]
546 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
547 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
548 /// let p0 = "10.0.0.0/8".parse()?;
549 /// let p1 = "10.1.0.0/16".parse()?;
550 /// let p2 = "10.1.1.0/24".parse()?;
551 /// pm.insert(p0, 0);
552 /// pm.insert(p1, 1);
553 /// pm.insert(p2, 2);
554 /// pm.insert("10.1.2.0/24".parse()?, 3); // disjoint prefixes are not covered
555 /// pm.insert("10.1.1.0/25".parse()?, 4); // more specific prefixes are not covered
556 /// pm.insert("11.0.0.0/8".parse()?, 5); // Branch points that don't contain values are skipped
557 /// assert_eq!(pm.cover_keys(&p2).collect::<Vec<_>>(), vec![p0, p1, p2]);
558 /// # Ok(())
559 /// # }
560 /// # #[cfg(not(feature = "ipnet"))]
561 /// # fn main() {}
562 /// ```
563 pub fn cover_keys<'a, 'p>(&'a self, prefix: &'p P) -> CoverKeys<'a, 'p, P, T> {
564 CoverKeys(self.cover(prefix))
565 }
566
567 /// Iterate over all values in the map that covers the given `prefix` (including `prefix`
568 /// itself if that is present in the map). The returned iterator yields `&'a T`.
569 ///
570 /// The iterator will always yield elements ordered by their prefix length, i.e., their depth in
571 /// the tree.
572 ///
573 /// ```
574 /// # use prefix_trie::joint::*;
575 /// # #[cfg(feature = "ipnet")]
576 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
577 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
578 /// let p0 = "10.0.0.0/8".parse()?;
579 /// let p1 = "10.1.0.0/16".parse()?;
580 /// let p2 = "10.1.1.0/24".parse()?;
581 /// pm.insert(p0, 0);
582 /// pm.insert(p1, 1);
583 /// pm.insert(p2, 2);
584 /// pm.insert("10.1.2.0/24".parse()?, 3); // disjoint prefixes are not covered
585 /// pm.insert("10.1.1.0/25".parse()?, 4); // more specific prefixes are not covered
586 /// pm.insert("11.0.0.0/8".parse()?, 5); // Branch points that don't contain values are skipped
587 /// assert_eq!(pm.cover_values(&p2).collect::<Vec<_>>(), vec![&0, &1, &2]);
588 /// # Ok(())
589 /// # }
590 /// # #[cfg(not(feature = "ipnet"))]
591 /// # fn main() {}
592 /// ```
593 pub fn cover_values<'a, 'p>(&'a self, prefix: &'p P) -> CoverValues<'a, 'p, P, T> {
594 CoverValues(self.cover(prefix))
595 }
596}
597
598impl<P: JointPrefix, T> JointPrefixMap<P, T> {
599 /// An iterator visiting all key-value pairs in lexicographic order. The iterator element type
600 /// is `(&P, &T)`. Elements of the first prefix are yielded before those of the second prefix.
601 ///
602 /// ```
603 /// # use prefix_trie::joint::*;
604 /// # #[cfg(feature = "ipnet")]
605 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
606 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
607 /// pm.insert("2001::1:0:0/97".parse()?, 6);
608 /// pm.insert("2001::1:0:0/96".parse()?, 7);
609 /// pm.insert("192.168.0.0/22".parse()?, 1);
610 /// pm.insert("192.168.0.0/23".parse()?, 2);
611 /// pm.insert("192.168.2.0/23".parse()?, 3);
612 /// pm.insert("192.168.0.0/24".parse()?, 4);
613 /// pm.insert("192.168.2.0/24".parse()?, 5);
614 /// assert_eq!(
615 /// pm.iter().collect::<Vec<_>>(),
616 /// vec![
617 /// ("192.168.0.0/22".parse()?, &1),
618 /// ("192.168.0.0/23".parse()?, &2),
619 /// ("192.168.0.0/24".parse()?, &4),
620 /// ("192.168.2.0/23".parse()?, &3),
621 /// ("192.168.2.0/24".parse()?, &5),
622 /// ("2001::1:0:0/96".parse()?, &7),
623 /// ("2001::1:0:0/97".parse()?, &6),
624 /// ]
625 /// );
626 /// # Ok(())
627 /// # }
628 /// # #[cfg(not(feature = "ipnet"))]
629 /// # fn main() {}
630 /// ```
631 #[inline(always)]
632 pub fn iter(&self) -> Iter<'_, P, T> {
633 self.into_iter()
634 }
635
636 /// Get a mutable iterator over all key-value pairs. The order of this iterator is lexicographic.
637 /// ```
638 /// # use prefix_trie::joint::*;
639 /// # #[cfg(feature = "ipnet")]
640 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
641 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
642 /// pm.insert("2001::1:0:0/97".parse()?, 6);
643 /// pm.insert("2001::1:0:0/96".parse()?, 7);
644 /// pm.insert("192.168.0.0/22".parse()?, 1);
645 /// pm.insert("192.168.0.0/23".parse()?, 2);
646 /// pm.insert("192.168.2.0/23".parse()?, 3);
647 /// pm.insert("192.168.0.0/24".parse()?, 4);
648 /// pm.insert("192.168.2.0/24".parse()?, 5);
649 /// pm.iter_mut().for_each(|(_, v)| *v += 1);
650 /// assert_eq!(
651 /// pm.iter().collect::<Vec<_>>(),
652 /// vec![
653 /// ("192.168.0.0/22".parse()?, &2),
654 /// ("192.168.0.0/23".parse()?, &3),
655 /// ("192.168.0.0/24".parse()?, &5),
656 /// ("192.168.2.0/23".parse()?, &4),
657 /// ("192.168.2.0/24".parse()?, &6),
658 /// ("2001::1:0:0/96".parse()?, &8),
659 /// ("2001::1:0:0/97".parse()?, &7),
660 /// ]
661 /// );
662 /// # Ok(())
663 /// # }
664 /// # #[cfg(not(feature = "ipnet"))]
665 /// # fn main() {}
666 /// ```
667 pub fn iter_mut(&mut self) -> IterMut<'_, P, T> {
668 IterMut {
669 i1: Some(self.t1.iter_mut()),
670 i2: Some(self.t2.iter_mut()),
671 }
672 }
673
674 /// An iterator visiting all keys in lexicographic order. The iterator element type is
675 /// `&P`. Elements of the first prefix are yielded before those of the second one.
676 ///
677 /// ```
678 /// # use prefix_trie::joint::*;
679 /// # #[cfg(feature = "ipnet")]
680 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
681 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
682 /// pm.insert("2001::1:0:0/97".parse()?, 6);
683 /// pm.insert("2001::1:0:0/96".parse()?, 7);
684 /// pm.insert("192.168.0.0/22".parse()?, 1);
685 /// pm.insert("192.168.0.0/23".parse()?, 2);
686 /// pm.insert("192.168.2.0/23".parse()?, 3);
687 /// pm.insert("192.168.0.0/24".parse()?, 4);
688 /// pm.insert("192.168.2.0/24".parse()?, 5);
689 /// assert_eq!(
690 /// pm.keys().collect::<Vec<_>>(),
691 /// vec![
692 /// "192.168.0.0/22".parse()?,
693 /// "192.168.0.0/23".parse()?,
694 /// "192.168.0.0/24".parse()?,
695 /// "192.168.2.0/23".parse()?,
696 /// "192.168.2.0/24".parse()?,
697 /// "2001::1:0:0/96".parse()?,
698 /// "2001::1:0:0/97".parse()?,
699 /// ]
700 /// );
701 /// # Ok(())
702 /// # }
703 /// # #[cfg(not(feature = "ipnet"))]
704 /// # fn main() {}
705 /// ```
706 #[inline(always)]
707 pub fn keys(&self) -> Keys<'_, P, T> {
708 Keys { inner: self.iter() }
709 }
710
711 /// Creates a consuming iterator visiting all keys in lexicographic order. The iterator element
712 /// type is `P`.
713 ///
714 /// ```
715 /// # use prefix_trie::joint::*;
716 /// # #[cfg(feature = "ipnet")]
717 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
718 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
719 /// pm.insert("2001::1:0:0/97".parse()?, 6);
720 /// pm.insert("2001::1:0:0/96".parse()?, 7);
721 /// pm.insert("192.168.0.0/22".parse()?, 1);
722 /// pm.insert("192.168.0.0/23".parse()?, 2);
723 /// pm.insert("192.168.2.0/23".parse()?, 3);
724 /// pm.insert("192.168.0.0/24".parse()?, 4);
725 /// pm.insert("192.168.2.0/24".parse()?, 5);
726 /// assert_eq!(
727 /// pm.into_keys().collect::<Vec<_>>(),
728 /// vec![
729 /// "192.168.0.0/22".parse()?,
730 /// "192.168.0.0/23".parse()?,
731 /// "192.168.0.0/24".parse()?,
732 /// "192.168.2.0/23".parse()?,
733 /// "192.168.2.0/24".parse()?,
734 /// "2001::1:0:0/96".parse()?,
735 /// "2001::1:0:0/97".parse()?,
736 /// ]
737 /// );
738 /// # Ok(())
739 /// # }
740 /// # #[cfg(not(feature = "ipnet"))]
741 /// # fn main() {}
742 /// ```
743 #[inline(always)]
744 pub fn into_keys(self) -> IntoKeys<P, T> {
745 IntoKeys {
746 inner: self.into_iter(),
747 }
748 }
749
750 /// An iterator visiting all values in lexicographic order. The iterator element type is
751 /// `&P`. Elements of the first prefix are yielded before those of the second one.
752 ///
753 /// ```
754 /// # use prefix_trie::joint::*;
755 /// # #[cfg(feature = "ipnet")]
756 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
757 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
758 /// pm.insert("2001::1:0:0/97".parse()?, 6);
759 /// pm.insert("2001::1:0:0/96".parse()?, 7);
760 /// pm.insert("192.168.0.0/22".parse()?, 1);
761 /// pm.insert("192.168.0.0/23".parse()?, 2);
762 /// pm.insert("192.168.2.0/23".parse()?, 3);
763 /// pm.insert("192.168.0.0/24".parse()?, 4);
764 /// pm.insert("192.168.2.0/24".parse()?, 5);
765 /// assert_eq!(pm.values().collect::<Vec<_>>(), vec![&1, &2, &4, &3, &5, &7, &6]);
766 /// # Ok(())
767 /// # }
768 /// # #[cfg(not(feature = "ipnet"))]
769 /// # fn main() {}
770 /// ```
771 #[inline(always)]
772 pub fn values(&self) -> Values<'_, P, T> {
773 Values { inner: self.iter() }
774 }
775
776 /// Creates a consuming iterator visiting all values in lexicographic order. The iterator
777 /// element type is `P`.
778 ///
779 /// ```
780 /// # use prefix_trie::joint::*;
781 /// # #[cfg(feature = "ipnet")]
782 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
783 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
784 /// pm.insert("2001::1:0:0/97".parse()?, 6);
785 /// pm.insert("2001::1:0:0/96".parse()?, 7);
786 /// pm.insert("192.168.0.0/22".parse()?, 1);
787 /// pm.insert("192.168.0.0/23".parse()?, 2);
788 /// pm.insert("192.168.2.0/23".parse()?, 3);
789 /// pm.insert("192.168.0.0/24".parse()?, 4);
790 /// pm.insert("192.168.2.0/24".parse()?, 5);
791 /// assert_eq!(pm.into_values().collect::<Vec<_>>(), vec![1, 2, 4, 3, 5, 7, 6]);
792 /// # Ok(())
793 /// # }
794 /// # #[cfg(not(feature = "ipnet"))]
795 /// # fn main() {}
796 /// ```
797 #[inline(always)]
798 pub fn into_values(self) -> IntoValues<P, T> {
799 IntoValues {
800 inner: self.into_iter(),
801 }
802 }
803
804 /// Get a mutable iterator over all values. The order of this iterator is lexicographic.
805 /// ```
806 /// # use prefix_trie::joint::*;
807 /// # #[cfg(feature = "ipnet")]
808 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
809 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
810 /// pm.insert("2001::1:0:0/97".parse()?, 6);
811 /// pm.insert("2001::1:0:0/96".parse()?, 7);
812 /// pm.insert("192.168.0.0/22".parse()?, 1);
813 /// pm.insert("192.168.0.0/23".parse()?, 2);
814 /// pm.insert("192.168.2.0/23".parse()?, 3);
815 /// pm.insert("192.168.0.0/24".parse()?, 4);
816 /// pm.insert("192.168.2.0/24".parse()?, 5);
817 ///
818 /// pm.values_mut().for_each(|v| *v += 1);
819 /// assert_eq!(pm.values().collect::<Vec<_>>(), vec![&2, &3, &5, &4, &6, &8, &7]);
820 /// # Ok(())
821 /// # }
822 /// # #[cfg(not(feature = "ipnet"))]
823 /// # fn main() {}
824 /// ```
825 pub fn values_mut(&mut self) -> ValuesMut<'_, P, T> {
826 ValuesMut {
827 inner: self.iter_mut(),
828 }
829 }
830
831 /// Get an iterator over the node itself and all children. All elements returned have a prefix
832 /// that is contained within `prefix` itself (or are the same). The iterator yields references
833 /// to both keys and values, i.e., type `(&'a P, &'a T)`. The iterator yields elements in
834 /// lexicographic order.
835 ///
836 /// **Note**: Consider using [`crate::AsView::view_at`] as an alternative.
837 ///
838 /// ```
839 /// # use prefix_trie::joint::*;
840 /// # #[cfg(feature = "ipnet")]
841 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
842 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
843 /// pm.insert("192.168.0.0/22".parse()?, 1);
844 /// pm.insert("192.168.0.0/23".parse()?, 2);
845 /// pm.insert("192.168.2.0/23".parse()?, 3);
846 /// pm.insert("192.168.0.0/24".parse()?, 4);
847 /// pm.insert("192.168.2.0/24".parse()?, 5);
848 /// assert_eq!(
849 /// pm.children(&"192.168.0.0/23".parse()?).collect::<Vec<_>>(),
850 /// vec![
851 /// ("192.168.0.0/23".parse()?, &2),
852 /// ("192.168.0.0/24".parse()?, &4),
853 /// ]
854 /// );
855 /// # Ok(())
856 /// # }
857 /// # #[cfg(not(feature = "ipnet"))]
858 /// # fn main() {}
859 /// ```
860 ///
861 /// If the prefix is not present in the tree, and there are no children, the iterator will be
862 /// empty:
863 ///
864 /// ```
865 /// # use prefix_trie::joint::*;
866 /// # #[cfg(feature = "ipnet")]
867 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
868 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
869 /// pm.insert("2001::/32".parse()?, 1);
870 /// pm.insert("2001::/48".parse()?, 2);
871 /// assert_eq!(
872 /// pm.children(&"2001::/24".parse()?).collect::<Vec<_>>(),
873 /// vec![
874 /// ("2001::/32".parse()?, &1),
875 /// ("2001::/48".parse()?, &2),
876 /// ]
877 /// );
878 /// assert_eq!(pm.children(&"2001::/96".parse()?).collect::<Vec<_>>(), vec![]);
879 /// assert_eq!(pm.children(&"1111::/24".parse()?).collect::<Vec<_>>(), vec![]);
880 /// # Ok(())
881 /// # }
882 /// # #[cfg(not(feature = "ipnet"))]
883 /// # fn main() {}
884 /// ```
885 pub fn children<'a>(&'a self, prefix: &P) -> Iter<'a, P, T> {
886 match prefix.p1_or_p2_ref() {
887 Left(p1) => Iter {
888 i1: Some(self.t1.children(p1)),
889 i2: None,
890 },
891 Right(p2) => Iter {
892 i1: None,
893 i2: Some(self.t2.children(p2)),
894 },
895 }
896 }
897
898 /// Get an iterator of mutable references of the node itself and all its children. All elements
899 /// returned have a prefix that is contained within `prefix` itself (or are the same). The
900 /// iterator yields references to the keys, and mutable references to the values, i.e., type
901 /// `(&'a P, &'a mut T)`. The iterator yields elements in lexicographic order.
902 ///
903 /// **Note**: Consider using [`crate::AsViewMut::view_mut_at`] as an alternative.
904 ///
905 /// ```
906 /// # use prefix_trie::joint::*;
907 /// # #[cfg(feature = "ipnet")]
908 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
909 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
910 /// pm.insert("192.168.0.0/22".parse()?, 1);
911 /// pm.insert("192.168.0.0/23".parse()?, 2);
912 /// pm.insert("192.168.0.0/24".parse()?, 3);
913 /// pm.insert("192.168.2.0/23".parse()?, 4);
914 /// pm.insert("192.168.2.0/24".parse()?, 5);
915 /// pm.children_mut(&"192.168.0.0/23".parse()?).for_each(|(_, x)| *x *= 10);
916 /// assert_eq!(
917 /// pm.into_iter().collect::<Vec<_>>(),
918 /// vec![
919 /// ("192.168.0.0/22".parse()?, 1),
920 /// ("192.168.0.0/23".parse()?, 20),
921 /// ("192.168.0.0/24".parse()?, 30),
922 /// ("192.168.2.0/23".parse()?, 4),
923 /// ("192.168.2.0/24".parse()?, 5),
924 /// ]
925 /// );
926 /// # Ok(())
927 /// # }
928 /// # #[cfg(not(feature = "ipnet"))]
929 /// # fn main() {}
930 /// ```
931 ///
932 /// If the prefix is not present in the tree, and there are no children, the iterator will be
933 /// empty:
934 ///
935 /// ```
936 /// # use prefix_trie::joint::*;
937 /// # #[cfg(feature = "ipnet")]
938 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
939 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
940 /// pm.insert("2001::/32".parse()?, 1);
941 /// pm.insert("2001::/48".parse()?, 2);
942 /// assert_eq!(pm.children_mut(&"2001::/96".parse()?).collect::<Vec<_>>(), vec![]);
943 /// assert_eq!(pm.children_mut(&"1111::/24".parse()?).collect::<Vec<_>>(), vec![]);
944 /// # Ok(())
945 /// # }
946 /// # #[cfg(not(feature = "ipnet"))]
947 /// # fn main() {}
948 /// ```
949 pub fn children_mut<'a>(&'a mut self, prefix: &P) -> IterMut<'a, P, T> {
950 match prefix.p1_or_p2_ref() {
951 Left(p1) => IterMut {
952 i1: Some(self.t1.children_mut(p1)),
953 i2: None,
954 },
955 Right(p2) => IterMut {
956 i1: None,
957 i2: Some(self.t2.children_mut(p2)),
958 },
959 }
960 }
961
962 /// Get an iterator over the node itself and all children with a value. All elements returned
963 /// have a prefix that is contained within `prefix` itself (or are the same). This function will
964 /// consume `self`, returning an iterator over all owned children.
965 ///
966 /// ```
967 /// # use prefix_trie::joint::*;
968 /// # #[cfg(feature = "ipnet")]
969 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
970 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
971 /// pm.insert("192.168.0.0/22".parse()?, 1);
972 /// pm.insert("192.168.0.0/23".parse()?, 2);
973 /// pm.insert("192.168.2.0/23".parse()?, 3);
974 /// pm.insert("192.168.0.0/24".parse()?, 4);
975 /// pm.insert("192.168.2.0/24".parse()?, 5);
976 /// assert_eq!(
977 /// pm.into_children(&"192.168.0.0/23".parse()?).collect::<Vec<_>>(),
978 /// vec![
979 /// ("192.168.0.0/23".parse()?, 2),
980 /// ("192.168.0.0/24".parse()?, 4),
981 /// ]
982 /// );
983 /// # Ok(())
984 /// # }
985 /// # #[cfg(not(feature = "ipnet"))]
986 /// # fn main() {}
987 /// ```
988 ///
989 /// If the prefix is not present in the tree, and there are no children, the iterator will be
990 /// empty:
991 ///
992 /// ```
993 /// # use prefix_trie::joint::*;
994 /// # #[cfg(feature = "ipnet")]
995 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
996 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
997 /// pm.insert("2001::/32".parse()?, 1);
998 /// pm.insert("2001::/48".parse()?, 2);
999 /// assert_eq!(
1000 /// pm.clone().into_children(&"2001::/24".parse()?).collect::<Vec<_>>(),
1001 /// vec![
1002 /// ("2001::/32".parse()?, 1),
1003 /// ("2001::/48".parse()?, 2),
1004 /// ]
1005 /// );
1006 /// assert_eq!(pm.clone().into_children(&"2001::/96".parse()?).collect::<Vec<_>>(), vec![]);
1007 /// assert_eq!(pm.clone().into_children(&"1111::/24".parse()?).collect::<Vec<_>>(), vec![]);
1008 /// # Ok(())
1009 /// # }
1010 /// # #[cfg(not(feature = "ipnet"))]
1011 /// # fn main() {}
1012 /// ```
1013 pub fn into_children(self, prefix: &P) -> IntoIter<P, T> {
1014 match prefix.p1_or_p2_ref() {
1015 Left(p1) => IntoIter {
1016 i1: Some(self.t1.into_children(p1)),
1017 i2: None,
1018 },
1019 Right(p2) => IntoIter {
1020 i1: None,
1021 i2: Some(self.t2.into_children(p2)),
1022 },
1023 }
1024 }
1025
1026 /// Iterate over the union of two joint prefix maps. This is roughly equivalent to calling
1027 /// `self.t1.view().union(&other.t1).chain(self.t2.view().union(&other.t2))`.
1028 ///
1029 /// If a prefix is present in both trees, the iterator will yield both elements. Otherwise, the
1030 /// iterator will yield the element of one map together with the longest prefix match in
1031 /// the other map. Elements are of type [`UnionItem`].
1032 ///
1033 /// ```
1034 /// # use prefix_trie::joint::*;
1035 /// # use prefix_trie::joint::map::UnionItem;
1036 /// # #[cfg(feature = "ipnet")]
1037 /// macro_rules! net { ($x:literal) => {$x.parse::<ipnet::IpNet>().unwrap()}; }
1038 ///
1039 /// # #[cfg(feature = "ipnet")]
1040 /// # {
1041 /// let mut map_a: JointPrefixMap<ipnet::IpNet, usize> = JointPrefixMap::from_iter([
1042 /// (net!("2001::1:0:0/96"), 1),
1043 /// (net!("192.168.0.0/22"), 2),
1044 /// (net!("192.168.0.0/24"), 3),
1045 /// ]);
1046 /// let mut map_b: JointPrefixMap<ipnet::IpNet, &'static str> = JointPrefixMap::from_iter([
1047 /// (net!("192.168.0.0/22"), "a"),
1048 /// (net!("192.168.0.0/23"), "b"),
1049 /// ]);
1050 /// assert_eq!(
1051 /// map_a.union(&map_b).collect::<Vec<_>>(),
1052 /// vec![
1053 /// UnionItem::Both{
1054 /// prefix: net!("192.168.0.0/22"),
1055 /// left: &2,
1056 /// right: &"a",
1057 /// },
1058 /// UnionItem::Right{
1059 /// prefix: net!("192.168.0.0/23"),
1060 /// left: Some((net!("192.168.0.0/22"), &2)),
1061 /// right: &"b",
1062 /// },
1063 /// UnionItem::Left{
1064 /// prefix: net!("192.168.0.0/24"),
1065 /// left: &3,
1066 /// right: Some((net!("192.168.0.0/23"), &"b")),
1067 /// },
1068 /// UnionItem::Left{
1069 /// prefix: net!("2001::1:0:0/96"),
1070 /// left: &1,
1071 /// right: None,
1072 /// },
1073 /// ]
1074 /// );
1075 /// # }
1076 /// ```
1077 pub fn union<'a, R>(&'a self, other: &'a JointPrefixMap<P, R>) -> Union<'a, P, T, R> {
1078 Union {
1079 i1: Some(self.t1.view().union(&other.t1)),
1080 i2: Some(self.t2.view().union(&other.t2)),
1081 }
1082 }
1083
1084 /// Iterate over the intersection of two joint prefix maps. This is roughly equivalent to
1085 /// calling `self.t1.view().intersection(&other.t1).chain(self.t2.view().intersection(&other.t2))`.
1086 ///
1087 /// ```
1088 /// # use prefix_trie::joint::*;
1089 /// # #[cfg(feature = "ipnet")]
1090 /// macro_rules! net { ($x:literal) => {$x.parse::<ipnet::IpNet>().unwrap()}; }
1091 ///
1092 /// # #[cfg(feature = "ipnet")]
1093 /// # {
1094 /// let mut map_a: JointPrefixMap<ipnet::IpNet, usize> = JointPrefixMap::from_iter([
1095 /// (net!("192.168.0.0/20"), 1),
1096 /// (net!("192.168.0.0/22"), 2),
1097 /// (net!("192.168.0.0/24"), 3),
1098 /// (net!("192.168.2.0/23"), 4),
1099 /// (net!("2001::1:0:0/96"), 5),
1100 /// (net!("2001::1:0:0/97"), 6),
1101 /// ]);
1102 /// let mut map_b: JointPrefixMap<ipnet::IpNet, &'static str> = JointPrefixMap::from_iter([
1103 /// (net!("192.168.0.0/20"), "a"),
1104 /// (net!("192.168.0.0/22"), "b"),
1105 /// (net!("192.168.0.0/23"), "c"),
1106 /// (net!("192.168.0.0/24"), "d"),
1107 /// (net!("192.168.2.0/24"), "e"),
1108 /// (net!("2001::1:0:0/96"), "f"),
1109 /// (net!("2001::0:0:0/97"), "g"),
1110 /// ]);
1111 /// assert_eq!(
1112 /// map_a.intersection(&map_b).collect::<Vec<_>>(),
1113 /// vec![
1114 /// (net!("192.168.0.0/20"), &1, &"a"),
1115 /// (net!("192.168.0.0/22"), &2, &"b"),
1116 /// (net!("192.168.0.0/24"), &3, &"d"),
1117 /// (net!("2001::1:0:0/96"), &5, &"f"),
1118 /// ]
1119 /// );
1120 /// # }
1121 /// ```
1122 pub fn intersection<'a, R>(
1123 &'a self,
1124 other: &'a JointPrefixMap<P, R>,
1125 ) -> Intersection<'a, P, T, R> {
1126 Intersection {
1127 i1: Some(self.t1.view().intersection(&other.t1)),
1128 i2: Some(self.t2.view().intersection(&other.t2)),
1129 }
1130 }
1131
1132 /// Iterate over the all elements in `self` that are not present in `other`. Each item will
1133 /// return a reference to the prefix and value in `self`, as well as the longest prefix match of
1134 /// `other`.
1135 ///
1136 /// ```
1137 /// # use prefix_trie::joint::*;
1138 /// # use prefix_trie::joint::map::DifferenceItem;
1139 /// # #[cfg(feature = "ipnet")]
1140 /// macro_rules! net { ($x:literal) => {$x.parse::<ipnet::IpNet>().unwrap()}; }
1141 ///
1142 /// # #[cfg(feature = "ipnet")]
1143 /// # {
1144 /// let mut map_a: JointPrefixMap<ipnet::IpNet, usize> = JointPrefixMap::from_iter([
1145 /// (net!("192.168.0.0/20"), 1),
1146 /// (net!("192.168.0.0/22"), 2),
1147 /// (net!("192.168.0.0/24"), 3),
1148 /// (net!("192.168.2.0/23"), 4),
1149 /// (net!("2001::1:0:0/96"), 5),
1150 /// (net!("2001::1:0:0/97"), 6),
1151 /// ]);
1152 /// let mut map_b: JointPrefixMap<ipnet::IpNet, &'static str> = JointPrefixMap::from_iter([
1153 /// (net!("192.168.0.0/20"), "a"),
1154 /// (net!("192.168.0.0/22"), "b"),
1155 /// (net!("192.168.0.0/23"), "c"),
1156 /// (net!("192.168.2.0/24"), "d"),
1157 /// (net!("2001::1:0:0/96"), "e"),
1158 /// ]);
1159 /// assert_eq!(
1160 /// map_a.difference(&map_b).collect::<Vec<_>>(),
1161 /// vec![
1162 /// DifferenceItem { prefix: net!("192.168.0.0/24"), value: &3, right: Some((net!("192.168.0.0/23"), &"c"))},
1163 /// DifferenceItem { prefix: net!("192.168.2.0/23"), value: &4, right: Some((net!("192.168.0.0/22"), &"b"))},
1164 /// DifferenceItem { prefix: net!("2001::1:0:0/97"), value: &6, right: Some((net!("2001::1:0:0/96"), &"e"))},
1165 /// ]
1166 /// );
1167 /// # }
1168 /// ```
1169 pub fn difference<'a, R>(&'a self, other: &'a JointPrefixMap<P, R>) -> Difference<'a, P, T, R> {
1170 Difference {
1171 i1: Some(self.t1.view().difference(&other.t1)),
1172 i2: Some(self.t2.view().difference(&other.t2)),
1173 }
1174 }
1175
1176 /// Iterate over the all elements in `self` that are not covered by `other`.
1177 ///
1178 /// ```
1179 /// # use prefix_trie::joint::*;
1180 /// # use prefix_trie::joint::map::DifferenceItem;
1181 /// # #[cfg(feature = "ipnet")]
1182 /// macro_rules! net { ($x:literal) => {$x.parse::<ipnet::IpNet>().unwrap()}; }
1183 ///
1184 /// # #[cfg(feature = "ipnet")]
1185 /// # {
1186 /// let mut map_a: JointPrefixMap<ipnet::IpNet, usize> = JointPrefixMap::from_iter([
1187 /// (net!("192.168.0.0/20"), 1),
1188 /// (net!("192.168.0.0/22"), 2),
1189 /// (net!("192.168.0.0/24"), 3),
1190 /// (net!("192.168.2.0/23"), 4),
1191 /// (net!("2001::0:0:0/95"), 5),
1192 /// (net!("2001::1:0:0/96"), 6),
1193 /// (net!("2001::1:0:0/97"), 7),
1194 /// ]);
1195 /// let mut map_b: JointPrefixMap<ipnet::IpNet, &'static str> = JointPrefixMap::from_iter([
1196 /// (net!("192.168.0.0/21"), "a"),
1197 /// (net!("192.168.0.0/22"), "b"),
1198 /// (net!("192.168.0.0/23"), "c"),
1199 /// (net!("192.168.2.0/24"), "d"),
1200 /// (net!("2001::1:0:0/96"), "e"),
1201 /// ]);
1202 /// assert_eq!(
1203 /// map_a.covering_difference(&map_b).collect::<Vec<_>>(),
1204 /// vec![(net!("192.168.0.0/20"), &1), (net!("2001::0:0:0/95"), &5)]
1205 /// );
1206 /// # }
1207 /// ```
1208 pub fn covering_difference<'a, R>(
1209 &'a self,
1210 other: &'a JointPrefixMap<P, R>,
1211 ) -> CoveringDifference<'a, P, T, R> {
1212 CoveringDifference {
1213 i1: Some(self.t1.view().covering_difference(&other.t1)),
1214 i2: Some(self.t2.view().covering_difference(&other.t2)),
1215 }
1216 }
1217}
1218
1219impl<P, L, R> PartialEq<JointPrefixMap<P, R>> for JointPrefixMap<P, L>
1220where
1221 P: JointPrefix + PartialEq,
1222 L: PartialEq<R>,
1223{
1224 fn eq(&self, other: &JointPrefixMap<P, R>) -> bool {
1225 self.iter()
1226 .zip(other.iter())
1227 .all(|((lp, lt), (rp, rt))| lt == rt && lp == rp)
1228 }
1229}
1230
1231impl<P, T> Eq for JointPrefixMap<P, T>
1232where
1233 P: JointPrefix + Eq,
1234 T: Eq,
1235{
1236}
1237
1238mod entry;
1239mod iter;
1240
1241pub use entry::*;
1242pub use iter::*;