prefix_trie/joint/map/mod.rs
1//! Module that defines the JointPrefixMap
2
3use super::JointPrefix;
4use crate::{AsView, PrefixMap, TrieView};
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.
140 ///
141 /// Prefixes are not stored verbatim. They are reconstructed from the trie position, so host
142 /// bits masked out by the prefix length are not preserved.
143 ///
144 /// ```
145 /// # use prefix_trie::joint::*;
146 /// # #[cfg(feature = "ipnet")]
147 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
148 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
149 /// let prefix = "2001::/32".parse()?;
150 /// pm.insert(prefix, 1);
151 /// assert_eq!(pm.get_key_value(&prefix), Some((prefix, &1)));
152 /// # Ok(())
153 /// # }
154 /// # #[cfg(not(feature = "ipnet"))]
155 /// # fn main() {}
156 /// ```
157 pub fn get_key_value<'a>(&'a self, prefix: &P) -> Option<(P, &'a T)> {
158 fork_ref!(self, prefix as (P, T), get_key_value)
159 }
160
161 /// Get a value of an element by using longest prefix matching
162 ///
163 /// ```
164 /// # use prefix_trie::joint::*;
165 /// # #[cfg(feature = "ipnet")]
166 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
167 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
168 /// pm.insert("192.168.1.0/24".parse()?, 1);
169 /// pm.insert("192.168.0.0/23".parse()?, 2);
170 /// assert_eq!(pm.get_lpm(&"192.168.1.1/32".parse()?), Some(("192.168.1.0/24".parse()?, &1)));
171 /// assert_eq!(pm.get_lpm(&"192.168.1.0/24".parse()?), Some(("192.168.1.0/24".parse()?, &1)));
172 /// assert_eq!(pm.get_lpm(&"192.168.0.0/24".parse()?), Some(("192.168.0.0/23".parse()?, &2)));
173 /// assert_eq!(pm.get_lpm(&"192.168.2.0/24".parse()?), None);
174 /// # Ok(())
175 /// # }
176 /// # #[cfg(not(feature = "ipnet"))]
177 /// # fn main() {}
178 /// ```
179 pub fn get_lpm<'a>(&'a self, prefix: &P) -> Option<(P, &'a T)> {
180 fork_ref!(self, prefix as (P, T), get_lpm)
181 }
182
183 /// Get a mutable reference to a value of an element by using longest prefix matching
184 ///
185 /// ```
186 /// # use prefix_trie::joint::*;
187 /// # #[cfg(feature = "ipnet")]
188 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
189 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
190 /// pm.insert("192.168.1.0/24".parse()?, 1);
191 /// pm.insert("192.168.0.0/23".parse()?, 2);
192 /// assert_eq!(pm.get_lpm(&"192.168.1.1/32".parse()?), Some(("192.168.1.0/24".parse()?, &1)));
193 /// *pm.get_lpm_mut(&"192.168.1.64/26".parse()?).unwrap().1 += 1;
194 /// assert_eq!(pm.get_lpm(&"192.168.1.1/32".parse()?), Some(("192.168.1.0/24".parse()?, &2)));
195 /// # Ok(())
196 /// # }
197 /// # #[cfg(not(feature = "ipnet"))]
198 /// # fn main() {}
199 /// ```
200 pub fn get_lpm_mut<'a>(&'a mut self, prefix: &P) -> Option<(P, &'a mut T)> {
201 fork_ref!(self, prefix as (P, T), get_lpm_mut)
202 }
203
204 /// Check if a key is present in the datastructure.
205 ///
206 /// ```
207 /// # use prefix_trie::joint::*;
208 /// # #[cfg(feature = "ipnet")]
209 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
210 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
211 /// pm.insert("192.168.1.0/24".parse()?, 1);
212 /// assert!(pm.contains_key(&"192.168.1.0/24".parse()?));
213 /// assert!(!pm.contains_key(&"192.168.2.0/24".parse()?));
214 /// assert!(!pm.contains_key(&"192.168.0.0/23".parse()?));
215 /// assert!(!pm.contains_key(&"192.168.1.128/25".parse()?));
216 /// # Ok(())
217 /// # }
218 /// # #[cfg(not(feature = "ipnet"))]
219 /// # fn main() {}
220 /// ```
221 pub fn contains_key(&self, prefix: &P) -> bool {
222 fork_ref!(self, prefix, contains_key)
223 }
224
225 /// Get the longest prefix in the datastructure that matches the given `prefix`.
226 ///
227 /// ```
228 /// # use prefix_trie::joint::*;
229 /// # #[cfg(feature = "ipnet")]
230 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
231 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
232 /// pm.insert("192.168.1.0/24".parse()?, 1);
233 /// pm.insert("192.168.0.0/23".parse()?, 2);
234 /// assert_eq!(pm.get_lpm_prefix(&"192.168.1.1/32".parse()?), Some("192.168.1.0/24".parse()?));
235 /// assert_eq!(pm.get_lpm_prefix(&"192.168.1.0/24".parse()?), Some("192.168.1.0/24".parse()?));
236 /// assert_eq!(pm.get_lpm_prefix(&"192.168.0.0/24".parse()?), Some("192.168.0.0/23".parse()?));
237 /// assert_eq!(pm.get_lpm_prefix(&"192.168.2.0/24".parse()?), None);
238 /// # Ok(())
239 /// # }
240 /// # #[cfg(not(feature = "ipnet"))]
241 /// # fn main() {}
242 /// ```
243 pub fn get_lpm_prefix(&self, prefix: &P) -> Option<P> {
244 fork_ref!(self, prefix as P, get_lpm_prefix)
245 }
246
247 /// Get a value of an element by using shortest prefix matching.
248 ///
249 /// ```
250 /// # use prefix_trie::joint::*;
251 /// # #[cfg(feature = "ipnet")]
252 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
253 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
254 /// pm.insert("192.168.1.0/24".parse()?, 1);
255 /// pm.insert("192.168.0.0/23".parse()?, 2);
256 /// assert_eq!(pm.get_spm(&"192.168.1.1/32".parse()?), Some(("192.168.0.0/23".parse()?, &2)));
257 /// assert_eq!(pm.get_spm(&"192.168.1.0/24".parse()?), Some(("192.168.0.0/23".parse()?, &2)));
258 /// assert_eq!(pm.get_spm(&"192.168.0.0/23".parse()?), Some(("192.168.0.0/23".parse()?, &2)));
259 /// assert_eq!(pm.get_spm(&"192.168.2.0/24".parse()?), None);
260 /// # Ok(())
261 /// # }
262 /// # #[cfg(not(feature = "ipnet"))]
263 /// # fn main() {}
264 /// ```
265 pub fn get_spm<'a>(&'a self, prefix: &P) -> Option<(P, &'a T)> {
266 fork_ref!(self, prefix as (P, T), get_spm)
267 }
268
269 /// Get the shortest prefix in the datastructure that contains the given `prefix`.
270 ///
271 /// ```
272 /// # use prefix_trie::joint::*;
273 /// # #[cfg(feature = "ipnet")]
274 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
275 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
276 /// pm.insert("192.168.1.1/24".parse()?, 1);
277 /// pm.insert("192.168.0.0/23".parse()?, 2);
278 /// assert_eq!(pm.get_spm_prefix(&"192.168.1.1/32".parse()?), Some("192.168.0.0/23".parse()?));
279 /// assert_eq!(pm.get_spm_prefix(&"192.168.1.0/24".parse()?), Some("192.168.0.0/23".parse()?));
280 /// assert_eq!(pm.get_spm_prefix(&"192.168.0.0/23".parse()?), Some("192.168.0.0/23".parse()?));
281 /// assert_eq!(pm.get_spm_prefix(&"192.168.2.0/24".parse()?), None);
282 /// # Ok(())
283 /// # }
284 /// # #[cfg(not(feature = "ipnet"))]
285 /// # fn main() {}
286 /// ```
287 pub fn get_spm_prefix(&self, prefix: &P) -> Option<P> {
288 fork_ref!(self, prefix as P, get_spm_prefix)
289 }
290
291 /// Insert a new item into the prefix-map. This function may return any value that existed
292 /// before.
293 ///
294 /// Prefixes are not stored verbatim. They are reconstructed from the trie position, so host
295 /// bits masked out by the prefix length are not preserved.
296 ///
297 /// ```
298 /// # use prefix_trie::joint::*;
299 /// # #[cfg(feature = "ipnet")]
300 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
301 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
302 /// assert_eq!(pm.insert("192.168.0.0/23".parse()?, 1), None);
303 /// assert_eq!(pm.insert("192.168.1.0/24".parse()?, 2), None);
304 /// assert_eq!(pm.insert("192.168.1.0/24".parse()?, 3), Some(2));
305 /// assert_eq!(pm.insert("2001::1:0:0/96".parse()?, 4), None);
306 /// assert_eq!(pm.insert("2001::1:0:0/97".parse()?, 5), None);
307 /// assert_eq!(pm.insert("2001::1:0:0/97".parse()?, 6), Some(5));
308 /// # Ok(())
309 /// # }
310 /// # #[cfg(not(feature = "ipnet"))]
311 /// # fn main() {}
312 /// ```
313 pub fn insert(&mut self, prefix: P, value: T) -> Option<T> {
314 fork!(self, prefix, insert, value)
315 }
316
317 /// Gets the given key’s corresponding entry in the map for in-place manipulation.
318 ///
319 /// Prefixes are not stored verbatim. They are reconstructed from the trie position, so host
320 /// bits masked out by the prefix length are not preserved.
321 ///
322 /// ```
323 /// # use prefix_trie::joint::*;
324 /// # #[cfg(feature = "ipnet")]
325 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
326 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
327 /// pm.insert("192.168.1.0/24".parse()?, vec![1]);
328 /// pm.entry("192.168.1.0/24".parse()?).or_default().push(2);
329 /// pm.entry("192.168.1.0/25".parse()?).or_default().push(3);
330 /// pm.entry("c0a8:1::/24".parse()?).or_default().push(4);
331 /// assert_eq!(pm.get(&"192.168.1.0/24".parse()?), Some(&vec![1, 2]));
332 /// assert_eq!(pm.get(&"192.168.1.0/25".parse()?), Some(&vec![3]));
333 /// assert_eq!(pm.get(&"c0a8:1::/24".parse()?), Some(&vec![4]));
334 /// # Ok(())
335 /// # }
336 /// # #[cfg(not(feature = "ipnet"))]
337 /// # fn main() {}
338 /// ```
339 pub fn entry(&mut self, prefix: P) -> Entry<'_, P, T> {
340 match prefix.p1_or_p2() {
341 Left(p1) => match self.t1.entry(p1) {
342 crate::map::Entry::Vacant(e) => Entry::Vacant(VacantEntry::P1(e)),
343 crate::map::Entry::Occupied(e) => Entry::Occupied(OccupiedEntry::P1(e)),
344 },
345 Right(p2) => match self.t2.entry(p2) {
346 crate::map::Entry::Vacant(e) => Entry::Vacant(VacantEntry::P2(e)),
347 crate::map::Entry::Occupied(e) => Entry::Occupied(OccupiedEntry::P2(e)),
348 },
349 }
350 }
351
352 /// Removes a key from the map, returning the value at the key if the key was previously in the
353 /// map. In contrast to [`Self::remove_keep_tree`], this operation may prune empty trie nodes,
354 /// reducing the memory footprint.
355 ///
356 /// ```
357 /// # use prefix_trie::joint::*;
358 /// # #[cfg(feature = "ipnet")]
359 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
360 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
361 /// let prefix = "192.168.1.0/24".parse()?;
362 /// pm.insert(prefix, 1);
363 /// assert_eq!(pm.get(&prefix), Some(&1));
364 /// assert_eq!(pm.remove(&prefix), Some(1));
365 /// assert_eq!(pm.get(&prefix), None);
366 /// # Ok(())
367 /// # }
368 /// # #[cfg(not(feature = "ipnet"))]
369 /// # fn main() {}
370 /// ```
371 pub fn remove(&mut self, prefix: &P) -> Option<T> {
372 fork_ref!(self, prefix, remove)
373 }
374
375 /// Removes a key from the map, returning the value at the key if the key was previously in the
376 /// map. In contrast to [`Self::remove`], this operation only removes the stored value and may
377 /// leave empty trie nodes in place.
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 /// # Ok(())
390 /// # }
391 /// # #[cfg(not(feature = "ipnet"))]
392 /// # fn main() {}
393 /// ```
394 pub fn remove_keep_tree(&mut self, prefix: &P) -> Option<T> {
395 fork_ref!(self, prefix, remove_keep_tree)
396 }
397
398 /// Remove all entries that are contained within `prefix`. This will change the tree
399 /// structure. This operation is `O(n)`, as the entries must be freed up one-by-one.
400 ///
401 /// ```
402 /// # use prefix_trie::joint::*;
403 /// # #[cfg(feature = "ipnet")]
404 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
405 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
406 /// pm.insert("192.168.0.0/22".parse()?, 1);
407 /// pm.insert("192.168.0.0/23".parse()?, 2);
408 /// pm.insert("192.168.0.0/24".parse()?, 3);
409 /// pm.insert("192.168.2.0/23".parse()?, 4);
410 /// pm.insert("192.168.2.0/24".parse()?, 5);
411 /// pm.remove_children(&"192.168.0.0/23".parse()?);
412 /// assert_eq!(pm.get(&"192.168.0.0/23".parse()?), None);
413 /// assert_eq!(pm.get(&"192.168.0.0/24".parse()?), None);
414 /// assert_eq!(pm.get(&"192.168.2.0/23".parse()?), Some(&4));
415 /// assert_eq!(pm.get(&"192.168.2.0/24".parse()?), Some(&5));
416 /// # Ok(())
417 /// # }
418 /// # #[cfg(not(feature = "ipnet"))]
419 /// # fn main() {}
420 /// ```
421 pub fn remove_children(&mut self, prefix: &P) {
422 fork_ref!(self, prefix, remove_children)
423 }
424
425 /// Clear the map but keep the allocated memory.
426 ///
427 /// ```
428 /// # use prefix_trie::joint::*;
429 /// # #[cfg(feature = "ipnet")]
430 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
431 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
432 /// pm.insert("192.168.0.0/24".parse()?, 1);
433 /// pm.insert("192.168.1.0/24".parse()?, 2);
434 /// pm.insert("2001::1:0:0/96".parse()?, 3);
435 /// pm.clear();
436 /// assert_eq!(pm.get(&"192.168.0.0/24".parse()?), None);
437 /// assert_eq!(pm.get(&"192.168.1.0/24".parse()?), None);
438 /// assert_eq!(pm.get(&"2001::1:0:0/96".parse()?), None);
439 /// # Ok(())
440 /// # }
441 /// # #[cfg(not(feature = "ipnet"))]
442 /// # fn main() {}
443 /// ```
444 pub fn clear(&mut self) {
445 self.t1.clear();
446 self.t2.clear();
447 }
448
449 /// Keep only the elements in the map that satisfy the given condition `f`.
450 ///
451 /// ```
452 /// # use prefix_trie::joint::*;
453 /// # #[cfg(feature = "ipnet")]
454 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
455 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
456 /// pm.insert("192.168.0.0/24".parse()?, 1);
457 /// pm.insert("192.168.1.0/24".parse()?, 2);
458 /// pm.insert("192.168.2.0/24".parse()?, 3);
459 /// pm.insert("192.168.2.0/25".parse()?, 4);
460 /// pm.insert("2001::1:0:0/24".parse()?, 5);
461 /// pm.insert("2001::1:0:0/25".parse()?, 6);
462 /// pm.retain(|_, t| *t % 2 == 0); // only keep the even values.
463 /// assert_eq!(pm.get(&"192.168.0.0/24".parse()?), None);
464 /// assert_eq!(pm.get(&"192.168.1.0/24".parse()?), Some(&2));
465 /// assert_eq!(pm.get(&"192.168.2.0/24".parse()?), None);
466 /// assert_eq!(pm.get(&"192.168.2.0/25".parse()?), Some(&4));
467 /// assert_eq!(pm.get(&"2001::1:0:0/24".parse()?), None);
468 /// assert_eq!(pm.get(&"2001::1:0:0/25".parse()?), Some(&6));
469 /// # Ok(())
470 /// # }
471 /// # #[cfg(not(feature = "ipnet"))]
472 /// # fn main() {}
473 /// ```
474 pub fn retain<F>(&mut self, mut f: F)
475 where
476 F: FnMut(P, &T) -> bool,
477 {
478 self.t1.retain(|p, t| f(P::from_p1(p), t));
479 self.t2.retain(|p, t| f(P::from_p2(p), t));
480 }
481
482 /// Iterate over all entries in the map that covers the given `prefix` (including `prefix`
483 /// itself if that is present in the map). The returned iterator yields `(P, &'a T)`, with
484 /// reconstructed prefixes `P`.
485 ///
486 /// The iterator will always yield elements ordered by their prefix length, i.e., their depth in
487 /// the tree.
488 ///
489 /// ```
490 /// # use prefix_trie::joint::*;
491 /// # #[cfg(feature = "ipnet")]
492 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
493 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
494 /// let p0 = "10.0.0.0/8".parse()?;
495 /// let p1 = "10.1.0.0/16".parse()?;
496 /// let p2 = "10.1.1.0/24".parse()?;
497 /// pm.insert(p0, 0);
498 /// pm.insert(p1, 1);
499 /// pm.insert(p2, 2);
500 /// pm.insert("10.1.2.0/24".parse()?, 3); // disjoint prefixes are not covered
501 /// pm.insert("10.1.1.0/25".parse()?, 4); // more specific prefixes are not covered
502 /// pm.insert("11.0.0.0/8".parse()?, 5); // Branch points that don't contain values are skipped
503 /// assert_eq!(
504 /// pm.cover(&p2).collect::<Vec<_>>(),
505 /// vec![(p0, &0), (p1, &1), (p2, &2)]
506 /// );
507 /// # Ok(())
508 /// # }
509 /// # #[cfg(not(feature = "ipnet"))]
510 /// # fn main() {}
511 /// ```
512 ///
513 /// This function also yields the root node *if* it is part of the map:
514 ///
515 /// ```
516 /// # use prefix_trie::joint::*;
517 /// # #[cfg(feature = "ipnet")]
518 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
519 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
520 /// let root = "0.0.0.0/0".parse()?;
521 /// pm.insert(root, 0);
522 /// assert_eq!(pm.cover(&"10.0.0.0/8".parse()?).collect::<Vec<_>>(), vec![(root, &0)]);
523 /// # Ok(())
524 /// # }
525 /// # #[cfg(not(feature = "ipnet"))]
526 /// # fn main() {}
527 /// ```
528 pub fn cover<'a>(&'a self, prefix: &P) -> Cover<'a, P, T> {
529 match prefix.p1_or_p2_ref() {
530 Left(p1) => Cover::P1(self.t1.cover(p1)),
531 Right(p2) => Cover::P2(self.t2.cover(p2)),
532 }
533 }
534
535 /// Iterate over all keys (prefixes) in the map that covers the given `prefix` (including
536 /// `prefix` itself if that is present in the map). The returned iterator yields reconstructed
537 /// prefixes `P`.
538 ///
539 /// The iterator will always yield elements ordered by their prefix length, i.e., their depth in
540 /// the tree.
541 ///
542 /// ```
543 /// # use prefix_trie::joint::*;
544 /// # #[cfg(feature = "ipnet")]
545 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
546 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
547 /// let p0 = "10.0.0.0/8".parse()?;
548 /// let p1 = "10.1.0.0/16".parse()?;
549 /// let p2 = "10.1.1.0/24".parse()?;
550 /// pm.insert(p0, 0);
551 /// pm.insert(p1, 1);
552 /// pm.insert(p2, 2);
553 /// pm.insert("10.1.2.0/24".parse()?, 3); // disjoint prefixes are not covered
554 /// pm.insert("10.1.1.0/25".parse()?, 4); // more specific prefixes are not covered
555 /// pm.insert("11.0.0.0/8".parse()?, 5); // Branch points that don't contain values are skipped
556 /// assert_eq!(pm.cover_keys(&p2).collect::<Vec<_>>(), vec![p0, p1, p2]);
557 /// # Ok(())
558 /// # }
559 /// # #[cfg(not(feature = "ipnet"))]
560 /// # fn main() {}
561 /// ```
562 pub fn cover_keys<'a>(&'a self, prefix: &P) -> CoverKeys<'a, P, T> {
563 CoverKeys(self.cover(prefix))
564 }
565
566 /// Iterate over all values in the map that covers the given `prefix` (including `prefix`
567 /// itself if that is present in the map). The returned iterator yields `&'a T`.
568 ///
569 /// The iterator will always yield elements ordered by their prefix length, i.e., their depth in
570 /// the tree.
571 ///
572 /// ```
573 /// # use prefix_trie::joint::*;
574 /// # #[cfg(feature = "ipnet")]
575 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
576 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
577 /// let p0 = "10.0.0.0/8".parse()?;
578 /// let p1 = "10.1.0.0/16".parse()?;
579 /// let p2 = "10.1.1.0/24".parse()?;
580 /// pm.insert(p0, 0);
581 /// pm.insert(p1, 1);
582 /// pm.insert(p2, 2);
583 /// pm.insert("10.1.2.0/24".parse()?, 3); // disjoint prefixes are not covered
584 /// pm.insert("10.1.1.0/25".parse()?, 4); // more specific prefixes are not covered
585 /// pm.insert("11.0.0.0/8".parse()?, 5); // Branch points that don't contain values are skipped
586 /// assert_eq!(pm.cover_values(&p2).collect::<Vec<_>>(), vec![&0, &1, &2]);
587 /// # Ok(())
588 /// # }
589 /// # #[cfg(not(feature = "ipnet"))]
590 /// # fn main() {}
591 /// ```
592 pub fn cover_values<'a>(&'a self, prefix: &P) -> CoverValues<'a, P, T> {
593 CoverValues(self.cover(prefix))
594 }
595}
596
597impl<P: JointPrefix, T> JointPrefixMap<P, T> {
598 /// An iterator visiting all key-value pairs in lexicographic order. The iterator element type
599 /// is `(P, &T)`, with reconstructed prefixes `P`. Elements of the first prefix are yielded
600 /// 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 /// Return an iterator starting at the given prefix in lexicographic order.
637 ///
638 /// If `inclusive` is `true`, the iterator includes the entry at `prefix` (if present).
639 /// If `inclusive` is `false`, the iterator starts after `prefix`.
640 ///
641 /// If `prefix` is not present in the map, the iterator starts at the first entry that
642 /// would come after `prefix` in lexicographic order, regardless of `inclusive`.
643 ///
644 /// ```
645 /// # use prefix_trie::joint::*;
646 /// # #[cfg(feature = "ipnet")]
647 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
648 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
649 /// pm.insert("192.168.0.0/22".parse()?, 1);
650 /// pm.insert("192.168.0.0/24".parse()?, 2);
651 /// pm.insert("2001::1:0:0/96".parse()?, 3);
652 /// pm.insert("2001::1:0:0/97".parse()?, 4);
653 ///
654 /// // Cursor pagination starting from an IPv4 prefix
655 /// let page: Vec<_> = pm.iter_from(&"192.168.0.0/24".parse()?, false).take(2).collect();
656 /// assert_eq!(page, vec![("2001::1:0:0/96".parse()?, &3), ("2001::1:0:0/97".parse()?, &4)]);
657 ///
658 /// // Starting from an IPv6 prefix
659 /// let page: Vec<_> = pm.iter_from(&"2001::1:0:0/96".parse()?, true).take(1).collect();
660 /// assert_eq!(page, vec![("2001::1:0:0/96".parse()?, &3)]);
661 /// # Ok(())
662 /// # }
663 /// # #[cfg(not(feature = "ipnet"))]
664 /// # fn main() {}
665 /// ```
666 pub fn iter_from<'a>(&'a self, prefix: &P, inclusive: bool) -> Iter<'a, P, T> {
667 match prefix.p1_or_p2_ref() {
668 Left(p1) => Iter {
669 i1: Some(self.t1.iter_from(p1, inclusive)),
670 i2: Some(self.t2.iter()),
671 },
672 Right(p2) => Iter {
673 i1: None,
674 i2: Some(self.t2.iter_from(p2, inclusive)),
675 },
676 }
677 }
678
679 /// Return a mutable iterator starting at the given prefix in lexicographic order.
680 ///
681 /// If `inclusive` is `true`, the iterator includes the entry at `prefix` (if present).
682 /// If `inclusive` is `false`, the iterator starts after `prefix`.
683 ///
684 /// If `prefix` is not present in the map, the iterator starts at the first entry that
685 /// would come after `prefix` in lexicographic order, regardless of `inclusive`.
686 ///
687 /// ```
688 /// # use prefix_trie::joint::*;
689 /// # #[cfg(feature = "ipnet")]
690 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
691 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
692 /// pm.insert("192.168.0.0/22".parse()?, 1);
693 /// pm.insert("192.168.0.0/24".parse()?, 2);
694 /// pm.insert("2001::1:0:0/96".parse()?, 3);
695 ///
696 /// // Mutate entries from 192.168.0.0/24 onwards (inclusive)
697 /// pm.iter_from_mut(&"192.168.0.0/24".parse()?, true).for_each(|(_, v)| *v *= 10);
698 /// assert_eq!(pm.get(&"192.168.0.0/22".parse()?), Some(&1));
699 /// assert_eq!(pm.get(&"192.168.0.0/24".parse()?), Some(&20));
700 /// assert_eq!(pm.get(&"2001::1:0:0/96".parse()?), Some(&30));
701 /// # Ok(())
702 /// # }
703 /// # #[cfg(not(feature = "ipnet"))]
704 /// # fn main() {}
705 /// ```
706 pub fn iter_from_mut<'a>(&'a mut self, prefix: &P, inclusive: bool) -> IterMut<'a, P, T> {
707 match prefix.p1_or_p2_ref() {
708 Left(p1) => IterMut {
709 i1: Some(self.t1.iter_from_mut(p1, inclusive)),
710 i2: Some(self.t2.iter_mut()),
711 },
712 Right(p2) => IterMut {
713 i1: None,
714 i2: Some(self.t2.iter_from_mut(p2, inclusive)),
715 },
716 }
717 }
718
719 /// Get a mutable iterator over all key-value pairs. The order of this iterator is lexicographic.
720 /// ```
721 /// # use prefix_trie::joint::*;
722 /// # #[cfg(feature = "ipnet")]
723 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
724 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
725 /// pm.insert("2001::1:0:0/97".parse()?, 6);
726 /// pm.insert("2001::1:0:0/96".parse()?, 7);
727 /// pm.insert("192.168.0.0/22".parse()?, 1);
728 /// pm.insert("192.168.0.0/23".parse()?, 2);
729 /// pm.insert("192.168.2.0/23".parse()?, 3);
730 /// pm.insert("192.168.0.0/24".parse()?, 4);
731 /// pm.insert("192.168.2.0/24".parse()?, 5);
732 /// pm.iter_mut().for_each(|(_, v)| *v += 1);
733 /// assert_eq!(
734 /// pm.iter().collect::<Vec<_>>(),
735 /// vec![
736 /// ("192.168.0.0/22".parse()?, &2),
737 /// ("192.168.0.0/23".parse()?, &3),
738 /// ("192.168.0.0/24".parse()?, &5),
739 /// ("192.168.2.0/23".parse()?, &4),
740 /// ("192.168.2.0/24".parse()?, &6),
741 /// ("2001::1:0:0/96".parse()?, &8),
742 /// ("2001::1:0:0/97".parse()?, &7),
743 /// ]
744 /// );
745 /// # Ok(())
746 /// # }
747 /// # #[cfg(not(feature = "ipnet"))]
748 /// # fn main() {}
749 /// ```
750 pub fn iter_mut(&mut self) -> IterMut<'_, P, T> {
751 IterMut {
752 i1: Some(self.t1.iter_mut()),
753 i2: Some(self.t2.iter_mut()),
754 }
755 }
756
757 /// An iterator visiting all keys in lexicographic order. The iterator element type is
758 /// reconstructed prefixes `P`. Elements of the first prefix are yielded before those of the
759 /// second one.
760 ///
761 /// ```
762 /// # use prefix_trie::joint::*;
763 /// # #[cfg(feature = "ipnet")]
764 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
765 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
766 /// pm.insert("2001::1:0:0/97".parse()?, 6);
767 /// pm.insert("2001::1:0:0/96".parse()?, 7);
768 /// pm.insert("192.168.0.0/22".parse()?, 1);
769 /// pm.insert("192.168.0.0/23".parse()?, 2);
770 /// pm.insert("192.168.2.0/23".parse()?, 3);
771 /// pm.insert("192.168.0.0/24".parse()?, 4);
772 /// pm.insert("192.168.2.0/24".parse()?, 5);
773 /// assert_eq!(
774 /// pm.keys().collect::<Vec<_>>(),
775 /// vec![
776 /// "192.168.0.0/22".parse()?,
777 /// "192.168.0.0/23".parse()?,
778 /// "192.168.0.0/24".parse()?,
779 /// "192.168.2.0/23".parse()?,
780 /// "192.168.2.0/24".parse()?,
781 /// "2001::1:0:0/96".parse()?,
782 /// "2001::1:0:0/97".parse()?,
783 /// ]
784 /// );
785 /// # Ok(())
786 /// # }
787 /// # #[cfg(not(feature = "ipnet"))]
788 /// # fn main() {}
789 /// ```
790 #[inline(always)]
791 pub fn keys(&self) -> Keys<'_, P, T> {
792 Keys { inner: self.iter() }
793 }
794
795 /// Creates a consuming iterator visiting all keys in lexicographic order. The iterator element
796 /// type is `P`.
797 ///
798 /// ```
799 /// # use prefix_trie::joint::*;
800 /// # #[cfg(feature = "ipnet")]
801 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
802 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
803 /// pm.insert("2001::1:0:0/97".parse()?, 6);
804 /// pm.insert("2001::1:0:0/96".parse()?, 7);
805 /// pm.insert("192.168.0.0/22".parse()?, 1);
806 /// pm.insert("192.168.0.0/23".parse()?, 2);
807 /// pm.insert("192.168.2.0/23".parse()?, 3);
808 /// pm.insert("192.168.0.0/24".parse()?, 4);
809 /// pm.insert("192.168.2.0/24".parse()?, 5);
810 /// assert_eq!(
811 /// pm.into_keys().collect::<Vec<_>>(),
812 /// vec![
813 /// "192.168.0.0/22".parse()?,
814 /// "192.168.0.0/23".parse()?,
815 /// "192.168.0.0/24".parse()?,
816 /// "192.168.2.0/23".parse()?,
817 /// "192.168.2.0/24".parse()?,
818 /// "2001::1:0:0/96".parse()?,
819 /// "2001::1:0:0/97".parse()?,
820 /// ]
821 /// );
822 /// # Ok(())
823 /// # }
824 /// # #[cfg(not(feature = "ipnet"))]
825 /// # fn main() {}
826 /// ```
827 #[inline(always)]
828 pub fn into_keys(self) -> IntoKeys<P, T> {
829 IntoKeys {
830 inner: self.into_iter(),
831 }
832 }
833
834 /// An iterator visiting all values in lexicographic order. The iterator element type is
835 /// `&T`. Elements of the first prefix are yielded before those of the second one.
836 ///
837 /// ```
838 /// # use prefix_trie::joint::*;
839 /// # #[cfg(feature = "ipnet")]
840 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
841 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
842 /// pm.insert("2001::1:0:0/97".parse()?, 6);
843 /// pm.insert("2001::1:0:0/96".parse()?, 7);
844 /// pm.insert("192.168.0.0/22".parse()?, 1);
845 /// pm.insert("192.168.0.0/23".parse()?, 2);
846 /// pm.insert("192.168.2.0/23".parse()?, 3);
847 /// pm.insert("192.168.0.0/24".parse()?, 4);
848 /// pm.insert("192.168.2.0/24".parse()?, 5);
849 /// assert_eq!(pm.values().collect::<Vec<_>>(), vec![&1, &2, &4, &3, &5, &7, &6]);
850 /// # Ok(())
851 /// # }
852 /// # #[cfg(not(feature = "ipnet"))]
853 /// # fn main() {}
854 /// ```
855 #[inline(always)]
856 pub fn values(&self) -> Values<'_, P, T> {
857 Values { inner: self.iter() }
858 }
859
860 /// Creates a consuming iterator visiting all values in lexicographic order. The iterator
861 /// element type is `T`.
862 ///
863 /// ```
864 /// # use prefix_trie::joint::*;
865 /// # #[cfg(feature = "ipnet")]
866 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
867 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
868 /// pm.insert("2001::1:0:0/97".parse()?, 6);
869 /// pm.insert("2001::1:0:0/96".parse()?, 7);
870 /// pm.insert("192.168.0.0/22".parse()?, 1);
871 /// pm.insert("192.168.0.0/23".parse()?, 2);
872 /// pm.insert("192.168.2.0/23".parse()?, 3);
873 /// pm.insert("192.168.0.0/24".parse()?, 4);
874 /// pm.insert("192.168.2.0/24".parse()?, 5);
875 /// assert_eq!(pm.into_values().collect::<Vec<_>>(), vec![1, 2, 4, 3, 5, 7, 6]);
876 /// # Ok(())
877 /// # }
878 /// # #[cfg(not(feature = "ipnet"))]
879 /// # fn main() {}
880 /// ```
881 #[inline(always)]
882 pub fn into_values(self) -> IntoValues<P, T> {
883 IntoValues {
884 inner: self.into_iter(),
885 }
886 }
887
888 /// Get a mutable iterator over all values. The order of this iterator is lexicographic.
889 /// ```
890 /// # use prefix_trie::joint::*;
891 /// # #[cfg(feature = "ipnet")]
892 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
893 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
894 /// pm.insert("2001::1:0:0/97".parse()?, 6);
895 /// pm.insert("2001::1:0:0/96".parse()?, 7);
896 /// pm.insert("192.168.0.0/22".parse()?, 1);
897 /// pm.insert("192.168.0.0/23".parse()?, 2);
898 /// pm.insert("192.168.2.0/23".parse()?, 3);
899 /// pm.insert("192.168.0.0/24".parse()?, 4);
900 /// pm.insert("192.168.2.0/24".parse()?, 5);
901 ///
902 /// pm.values_mut().for_each(|v| *v += 1);
903 /// assert_eq!(pm.values().collect::<Vec<_>>(), vec![&2, &3, &5, &4, &6, &8, &7]);
904 /// # Ok(())
905 /// # }
906 /// # #[cfg(not(feature = "ipnet"))]
907 /// # fn main() {}
908 /// ```
909 pub fn values_mut(&mut self) -> ValuesMut<'_, P, T> {
910 ValuesMut {
911 inner: self.iter_mut(),
912 }
913 }
914
915 /// Get an iterator over the node itself and all children. All elements returned have a prefix
916 /// that is contained within `prefix` itself (or are the same). The iterator yields
917 /// `(P, &'a T)`, with reconstructed prefixes `P`. The iterator yields elements in
918 /// lexicographic order.
919 ///
920 /// **Note**: Consider using [`crate::AsView::view_at`] as an alternative.
921 ///
922 /// ```
923 /// # use prefix_trie::joint::*;
924 /// # #[cfg(feature = "ipnet")]
925 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
926 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
927 /// pm.insert("192.168.0.0/22".parse()?, 1);
928 /// pm.insert("192.168.0.0/23".parse()?, 2);
929 /// pm.insert("192.168.2.0/23".parse()?, 3);
930 /// pm.insert("192.168.0.0/24".parse()?, 4);
931 /// pm.insert("192.168.2.0/24".parse()?, 5);
932 /// assert_eq!(
933 /// pm.children(&"192.168.0.0/23".parse()?).collect::<Vec<_>>(),
934 /// vec![
935 /// ("192.168.0.0/23".parse()?, &2),
936 /// ("192.168.0.0/24".parse()?, &4),
937 /// ]
938 /// );
939 /// # Ok(())
940 /// # }
941 /// # #[cfg(not(feature = "ipnet"))]
942 /// # fn main() {}
943 /// ```
944 ///
945 /// If the prefix is not present in the tree, and there are no children, the iterator will be
946 /// empty:
947 ///
948 /// ```
949 /// # use prefix_trie::joint::*;
950 /// # #[cfg(feature = "ipnet")]
951 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
952 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
953 /// pm.insert("2001::/32".parse()?, 1);
954 /// pm.insert("2001::/48".parse()?, 2);
955 /// assert_eq!(
956 /// pm.children(&"2001::/24".parse()?).collect::<Vec<_>>(),
957 /// vec![
958 /// ("2001::/32".parse()?, &1),
959 /// ("2001::/48".parse()?, &2),
960 /// ]
961 /// );
962 /// assert_eq!(pm.children(&"2001::/96".parse()?).collect::<Vec<_>>(), vec![]);
963 /// assert_eq!(pm.children(&"1111::/24".parse()?).collect::<Vec<_>>(), vec![]);
964 /// # Ok(())
965 /// # }
966 /// # #[cfg(not(feature = "ipnet"))]
967 /// # fn main() {}
968 /// ```
969 pub fn children<'a>(&'a self, prefix: &P) -> Iter<'a, P, T> {
970 match prefix.p1_or_p2_ref() {
971 Left(p1) => Iter {
972 i1: Some(self.t1.children(p1)),
973 i2: None,
974 },
975 Right(p2) => Iter {
976 i1: None,
977 i2: Some(self.t2.children(p2)),
978 },
979 }
980 }
981
982 /// Get an iterator of mutable references of the node itself and all its children. All elements
983 /// returned have a prefix that is contained within `prefix` itself (or are the same). The
984 /// iterator yields `(P, &'a mut T)`, with reconstructed prefixes `P`. The iterator yields
985 /// elements in lexicographic order.
986 ///
987 /// **Note**: Consider using [`crate::AsView::view_at`] on a mutable map reference as an
988 /// alternative.
989 ///
990 /// ```
991 /// # use prefix_trie::joint::*;
992 /// # #[cfg(feature = "ipnet")]
993 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
994 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
995 /// pm.insert("192.168.0.0/22".parse()?, 1);
996 /// pm.insert("192.168.0.0/23".parse()?, 2);
997 /// pm.insert("192.168.0.0/24".parse()?, 3);
998 /// pm.insert("192.168.2.0/23".parse()?, 4);
999 /// pm.insert("192.168.2.0/24".parse()?, 5);
1000 /// pm.children_mut(&"192.168.0.0/23".parse()?).for_each(|(_, x)| *x *= 10);
1001 /// assert_eq!(
1002 /// pm.into_iter().collect::<Vec<_>>(),
1003 /// vec![
1004 /// ("192.168.0.0/22".parse()?, 1),
1005 /// ("192.168.0.0/23".parse()?, 20),
1006 /// ("192.168.0.0/24".parse()?, 30),
1007 /// ("192.168.2.0/23".parse()?, 4),
1008 /// ("192.168.2.0/24".parse()?, 5),
1009 /// ]
1010 /// );
1011 /// # Ok(())
1012 /// # }
1013 /// # #[cfg(not(feature = "ipnet"))]
1014 /// # fn main() {}
1015 /// ```
1016 ///
1017 /// If the prefix is not present in the tree, and there are no children, the iterator will be
1018 /// empty:
1019 ///
1020 /// ```
1021 /// # use prefix_trie::joint::*;
1022 /// # #[cfg(feature = "ipnet")]
1023 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
1024 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
1025 /// pm.insert("2001::/32".parse()?, 1);
1026 /// pm.insert("2001::/48".parse()?, 2);
1027 /// assert_eq!(pm.children_mut(&"2001::/96".parse()?).collect::<Vec<_>>(), vec![]);
1028 /// assert_eq!(pm.children_mut(&"1111::/24".parse()?).collect::<Vec<_>>(), vec![]);
1029 /// # Ok(())
1030 /// # }
1031 /// # #[cfg(not(feature = "ipnet"))]
1032 /// # fn main() {}
1033 /// ```
1034 pub fn children_mut<'a>(&'a mut self, prefix: &P) -> IterMut<'a, P, T> {
1035 match prefix.p1_or_p2_ref() {
1036 Left(p1) => IterMut {
1037 i1: Some(self.t1.children_mut(p1)),
1038 i2: None,
1039 },
1040 Right(p2) => IterMut {
1041 i1: None,
1042 i2: Some(self.t2.children_mut(p2)),
1043 },
1044 }
1045 }
1046
1047 /// Get an iterator over the node itself and all children with a value. All elements returned
1048 /// have a prefix that is contained within `prefix` itself (or are the same). This function will
1049 /// consume `self`, returning an iterator over all owned children.
1050 ///
1051 /// ```
1052 /// # use prefix_trie::joint::*;
1053 /// # #[cfg(feature = "ipnet")]
1054 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
1055 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
1056 /// pm.insert("192.168.0.0/22".parse()?, 1);
1057 /// pm.insert("192.168.0.0/23".parse()?, 2);
1058 /// pm.insert("192.168.2.0/23".parse()?, 3);
1059 /// pm.insert("192.168.0.0/24".parse()?, 4);
1060 /// pm.insert("192.168.2.0/24".parse()?, 5);
1061 /// assert_eq!(
1062 /// pm.into_children(&"192.168.0.0/23".parse()?).collect::<Vec<_>>(),
1063 /// vec![
1064 /// ("192.168.0.0/23".parse()?, 2),
1065 /// ("192.168.0.0/24".parse()?, 4),
1066 /// ]
1067 /// );
1068 /// # Ok(())
1069 /// # }
1070 /// # #[cfg(not(feature = "ipnet"))]
1071 /// # fn main() {}
1072 /// ```
1073 ///
1074 /// If the prefix is not present in the tree, and there are no children, the iterator will be
1075 /// empty:
1076 ///
1077 /// ```
1078 /// # use prefix_trie::joint::*;
1079 /// # #[cfg(feature = "ipnet")]
1080 /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
1081 /// let mut pm: JointPrefixMap<ipnet::IpNet, _> = JointPrefixMap::new();
1082 /// pm.insert("2001::/32".parse()?, 1);
1083 /// pm.insert("2001::/48".parse()?, 2);
1084 /// assert_eq!(
1085 /// pm.clone().into_children(&"2001::/24".parse()?).collect::<Vec<_>>(),
1086 /// vec![
1087 /// ("2001::/32".parse()?, 1),
1088 /// ("2001::/48".parse()?, 2),
1089 /// ]
1090 /// );
1091 /// assert_eq!(pm.clone().into_children(&"2001::/96".parse()?).collect::<Vec<_>>(), vec![]);
1092 /// assert_eq!(pm.clone().into_children(&"1111::/24".parse()?).collect::<Vec<_>>(), vec![]);
1093 /// # Ok(())
1094 /// # }
1095 /// # #[cfg(not(feature = "ipnet"))]
1096 /// # fn main() {}
1097 /// ```
1098 pub fn into_children(self, prefix: &P) -> IntoIter<P, T> {
1099 match prefix.p1_or_p2_ref() {
1100 Left(p1) => IntoIter {
1101 i1: Some(self.t1.into_children(p1)),
1102 i2: None,
1103 },
1104 Right(p2) => IntoIter {
1105 i1: None,
1106 i2: Some(self.t2.into_children(p2)),
1107 },
1108 }
1109 }
1110
1111 /// Iterate over the union of two joint prefix maps. This is roughly equivalent to calling
1112 /// `self.t1.view().union(&other.t1).chain(self.t2.view().union(&other.t2))`.
1113 ///
1114 /// If a prefix is present in both trees, the iterator will yield both elements. Otherwise, the
1115 /// iterator will yield the element from the side where it is present. Elements are of type
1116 /// [`UnionItem`].
1117 ///
1118 /// ```
1119 /// # use prefix_trie::joint::*;
1120 /// # use prefix_trie::joint::map::UnionItem;
1121 /// # #[cfg(feature = "ipnet")]
1122 /// macro_rules! net { ($x:literal) => {$x.parse::<ipnet::IpNet>().unwrap()}; }
1123 ///
1124 /// # #[cfg(feature = "ipnet")]
1125 /// # {
1126 /// let mut map_a: JointPrefixMap<ipnet::IpNet, usize> = JointPrefixMap::from_iter([
1127 /// (net!("2001::1:0:0/96"), 1),
1128 /// (net!("192.168.0.0/22"), 2),
1129 /// (net!("192.168.0.0/24"), 3),
1130 /// ]);
1131 /// let mut map_b: JointPrefixMap<ipnet::IpNet, &'static str> = JointPrefixMap::from_iter([
1132 /// (net!("192.168.0.0/22"), "a"),
1133 /// (net!("192.168.0.0/23"), "b"),
1134 /// ]);
1135 /// assert_eq!(
1136 /// map_a.union(&map_b).collect::<Vec<_>>(),
1137 /// vec![
1138 /// UnionItem::Both{
1139 /// prefix: net!("192.168.0.0/22"),
1140 /// left: &2,
1141 /// right: &"a",
1142 /// },
1143 /// UnionItem::Right{
1144 /// prefix: net!("192.168.0.0/23"),
1145 /// left: None,
1146 /// right: &"b",
1147 /// },
1148 /// UnionItem::Left{
1149 /// prefix: net!("192.168.0.0/24"),
1150 /// left: &3,
1151 /// right: None,
1152 /// },
1153 /// UnionItem::Left{
1154 /// prefix: net!("2001::1:0:0/96"),
1155 /// left: &1,
1156 /// right: None,
1157 /// },
1158 /// ]
1159 /// );
1160 /// # }
1161 /// ```
1162 pub fn union<'a, R>(&'a self, other: &'a JointPrefixMap<P, R>) -> Union<'a, P, T, R> {
1163 Union {
1164 i1: Some(self.t1.view().union(&other.t1).into_iter()),
1165 i2: Some(self.t2.view().union(&other.t2).into_iter()),
1166 }
1167 }
1168
1169 /// Iterate over the intersection of two joint prefix maps. This is roughly equivalent to
1170 /// calling `self.t1.view().intersection(&other.t1).chain(self.t2.view().intersection(&other.t2))`.
1171 ///
1172 /// ```
1173 /// # use prefix_trie::joint::*;
1174 /// # #[cfg(feature = "ipnet")]
1175 /// macro_rules! net { ($x:literal) => {$x.parse::<ipnet::IpNet>().unwrap()}; }
1176 ///
1177 /// # #[cfg(feature = "ipnet")]
1178 /// # {
1179 /// let mut map_a: JointPrefixMap<ipnet::IpNet, usize> = JointPrefixMap::from_iter([
1180 /// (net!("192.168.0.0/20"), 1),
1181 /// (net!("192.168.0.0/22"), 2),
1182 /// (net!("192.168.0.0/24"), 3),
1183 /// (net!("192.168.2.0/23"), 4),
1184 /// (net!("2001::1:0:0/96"), 5),
1185 /// (net!("2001::1:0:0/97"), 6),
1186 /// ]);
1187 /// let mut map_b: JointPrefixMap<ipnet::IpNet, &'static str> = JointPrefixMap::from_iter([
1188 /// (net!("192.168.0.0/20"), "a"),
1189 /// (net!("192.168.0.0/22"), "b"),
1190 /// (net!("192.168.0.0/23"), "c"),
1191 /// (net!("192.168.0.0/24"), "d"),
1192 /// (net!("192.168.2.0/24"), "e"),
1193 /// (net!("2001::1:0:0/96"), "f"),
1194 /// (net!("2001::0:0:0/97"), "g"),
1195 /// ]);
1196 /// assert_eq!(
1197 /// map_a.intersection(&map_b).collect::<Vec<_>>(),
1198 /// vec![
1199 /// (net!("192.168.0.0/20"), &1, &"a"),
1200 /// (net!("192.168.0.0/22"), &2, &"b"),
1201 /// (net!("192.168.0.0/24"), &3, &"d"),
1202 /// (net!("2001::1:0:0/96"), &5, &"f"),
1203 /// ]
1204 /// );
1205 /// # }
1206 /// ```
1207 pub fn intersection<'a, R>(
1208 &'a self,
1209 other: &'a JointPrefixMap<P, R>,
1210 ) -> Intersection<'a, P, T, R> {
1211 Intersection {
1212 i1: self
1213 .t1
1214 .view()
1215 .intersection(&other.t1)
1216 .map(IntoIterator::into_iter),
1217 i2: self
1218 .t2
1219 .view()
1220 .intersection(&other.t2)
1221 .map(IntoIterator::into_iter),
1222 }
1223 }
1224
1225 /// Iterate over the all elements in `self` that are not present in `other`.
1226 ///
1227 /// ```
1228 /// # use prefix_trie::joint::*;
1229 /// # use prefix_trie::joint::map::DifferenceItem;
1230 /// # #[cfg(feature = "ipnet")]
1231 /// macro_rules! net { ($x:literal) => {$x.parse::<ipnet::IpNet>().unwrap()}; }
1232 ///
1233 /// # #[cfg(feature = "ipnet")]
1234 /// # {
1235 /// let mut map_a: JointPrefixMap<ipnet::IpNet, usize> = JointPrefixMap::from_iter([
1236 /// (net!("192.168.0.0/20"), 1),
1237 /// (net!("192.168.0.0/22"), 2),
1238 /// (net!("192.168.0.0/24"), 3),
1239 /// (net!("192.168.2.0/23"), 4),
1240 /// (net!("2001::1:0:0/96"), 5),
1241 /// (net!("2001::1:0:0/97"), 6),
1242 /// ]);
1243 /// let mut map_b: JointPrefixMap<ipnet::IpNet, &'static str> = JointPrefixMap::from_iter([
1244 /// (net!("192.168.0.0/20"), "a"),
1245 /// (net!("192.168.0.0/22"), "b"),
1246 /// (net!("192.168.0.0/23"), "c"),
1247 /// (net!("192.168.2.0/24"), "d"),
1248 /// (net!("2001::1:0:0/96"), "e"),
1249 /// ]);
1250 /// assert_eq!(
1251 /// map_a.difference(&map_b).collect::<Vec<_>>(),
1252 /// vec![
1253 /// DifferenceItem { prefix: net!("192.168.0.0/24"), value: &3, right: None },
1254 /// DifferenceItem { prefix: net!("192.168.2.0/23"), value: &4, right: None },
1255 /// DifferenceItem { prefix: net!("2001::1:0:0/97"), value: &6, right: None },
1256 /// ]
1257 /// );
1258 /// # }
1259 /// ```
1260 pub fn difference<'a, R>(&'a self, other: &'a JointPrefixMap<P, R>) -> Difference<'a, P, T, R> {
1261 Difference {
1262 i1: Some(self.t1.view().difference(&other.t1).into_iter()),
1263 i2: Some(self.t2.view().difference(&other.t2).into_iter()),
1264 }
1265 }
1266
1267 /// Iterate over the all elements in `self` that are not covered by `other`.
1268 ///
1269 /// ```
1270 /// # use prefix_trie::joint::*;
1271 /// # use prefix_trie::joint::map::DifferenceItem;
1272 /// # #[cfg(feature = "ipnet")]
1273 /// macro_rules! net { ($x:literal) => {$x.parse::<ipnet::IpNet>().unwrap()}; }
1274 ///
1275 /// # #[cfg(feature = "ipnet")]
1276 /// # {
1277 /// let mut map_a: JointPrefixMap<ipnet::IpNet, usize> = JointPrefixMap::from_iter([
1278 /// (net!("192.168.0.0/20"), 1),
1279 /// (net!("192.168.0.0/22"), 2),
1280 /// (net!("192.168.0.0/24"), 3),
1281 /// (net!("192.168.2.0/23"), 4),
1282 /// (net!("2001::0:0:0/95"), 5),
1283 /// (net!("2001::1:0:0/96"), 6),
1284 /// (net!("2001::1:0:0/97"), 7),
1285 /// ]);
1286 /// let mut map_b: JointPrefixMap<ipnet::IpNet, &'static str> = JointPrefixMap::from_iter([
1287 /// (net!("192.168.0.0/21"), "a"),
1288 /// (net!("192.168.0.0/22"), "b"),
1289 /// (net!("192.168.0.0/23"), "c"),
1290 /// (net!("192.168.2.0/24"), "d"),
1291 /// (net!("2001::1:0:0/96"), "e"),
1292 /// ]);
1293 /// assert_eq!(
1294 /// map_a.covering_difference(&map_b).collect::<Vec<_>>(),
1295 /// vec![(net!("192.168.0.0/20"), &1), (net!("2001::0:0:0/95"), &5)]
1296 /// );
1297 /// # }
1298 /// ```
1299 pub fn covering_difference<'a, R>(
1300 &'a self,
1301 other: &'a JointPrefixMap<P, R>,
1302 ) -> CoveringDifference<'a, P, T, R> {
1303 CoveringDifference {
1304 i1: Some(self.t1.view().covering_difference(&other.t1).into_iter()),
1305 i2: Some(self.t2.view().covering_difference(&other.t2).into_iter()),
1306 }
1307 }
1308}
1309
1310impl<P, L, R> PartialEq<JointPrefixMap<P, R>> for JointPrefixMap<P, L>
1311where
1312 P: JointPrefix + PartialEq,
1313 L: PartialEq<R>,
1314{
1315 fn eq(&self, other: &JointPrefixMap<P, R>) -> bool {
1316 self.len() == other.len()
1317 && self
1318 .iter()
1319 .zip(other.iter())
1320 .all(|((lp, lt), (rp, rt))| lp == rp && lt == rt)
1321 }
1322}
1323
1324impl<P, T> Eq for JointPrefixMap<P, T>
1325where
1326 P: JointPrefix + Eq,
1327 T: Eq,
1328{
1329}
1330
1331mod entry;
1332mod iter;
1333
1334pub use entry::*;
1335pub use iter::*;