iptrie/
lib.rs

1#[cfg(feature = "graphviz")]
2pub mod graphviz;
3pub mod map;
4mod prefix;
5pub mod set;
6mod trie;
7
8use ipnet::{IpNet, Ipv4Net, Ipv6Net};
9use map::*;
10use set::*;
11use std::num::NonZeroUsize;
12
13pub use prefix::*;
14
15/// Convenient alias for radix trie set of Ipv4 prefixes
16pub type Ipv4RTrieSet = RTrieSet<Ipv4Prefix>;
17/// Convenient alias for radix trie set of Ipv6 prefixes
18pub type Ipv6RTrieSet = RTrieSet<Ipv6Prefix>;
19
20/// Convenient alias for LC-Trie set of Ipv4 prefixes
21pub type Ipv4LCTrieSet = LCTrieSet<Ipv4Prefix>;
22/// Convenient alias for LC-Trie set of Ipv6 prefixes
23pub type Ipv6LCTrieSet = LCTrieSet<Ipv6Prefix>;
24
25/// A radix trie set that mix both Ipv4 and Ipv6 prefixes
26#[derive(Clone, Default)]
27pub struct IpRTrieSet {
28    pub ipv4: Ipv4RTrieSet,
29    pub ipv6: Ipv6RTrieSet,
30}
31
32/// A LC-trie set that mix both Ipv4 and Ipv6 prefixes
33pub struct IpLCTrieSet {
34    pub ipv4: Ipv4LCTrieSet,
35    pub ipv6: Ipv6LCTrieSet,
36}
37
38impl IpRTrieSet {
39    pub fn new() -> Self {
40        Self {
41            ipv4: Ipv4RTrieSet::new(),
42            ipv6: Ipv6RTrieSet::new(),
43        }
44    }
45    pub fn compress(self) -> IpLCTrieSet {
46        IpLCTrieSet {
47            ipv4: self.ipv4.compress(),
48            ipv6: self.ipv6.compress(),
49        }
50    }
51    pub fn shrink_to_fit(&mut self) {
52        self.ipv4.shrink_to_fit();
53        self.ipv6.shrink_to_fit();
54    }
55
56    /// Returns the size of the set.
57    ///
58    /// Notice that it always greater or equals two since two top prefixes are
59    /// always present in the map (one for Ipv4 and the other for Ipv6)
60    pub fn len(&self) -> NonZeroUsize {
61        self.ipv4.len().saturating_add(self.ipv6.len().get())
62    }
63
64    /// Checks if an element is present (exact match).
65    pub fn contains(&self, ipnet: &IpNet) -> bool {
66        match ipnet {
67            IpNet::V4(net) => self.ipv4.contains(net),
68            IpNet::V6(net) => self.ipv6.contains(net),
69        }
70    }
71
72    /// Gets the value associated with an exact match of the key.
73    ///
74    /// To access to the longest prefix match, use [`Self::lookup`].
75    pub fn get(&self, ipnet: &IpNet) -> Option<IpNet> {
76        match ipnet {
77            IpNet::V4(net) => self.ipv4.get(net).map(|ip| (*ip).into()),
78            IpNet::V6(net) => self.ipv6.get(net).map(|ip| (*ip).into()),
79        }
80    }
81    /// Gets the longest prefix which matches the given key.
82    ///
83    /// As the top prefix always matches, it never fails.
84    ///
85    /// To access to the exact prefix match, use [`Self::get`].
86    pub fn lookup(&self, ipnet: &IpNet) -> IpNet {
87        match ipnet {
88            IpNet::V4(net) => (*self.ipv4.lookup(net)).into(),
89            IpNet::V6(net) => (*self.ipv6.lookup(net)).into(),
90        }
91    }
92
93    /// Inserts a new element in the set.
94    ///
95    /// If the specified element already exists in the set, `false` is returned.
96    pub fn insert(&mut self, ipnet: IpNet) -> bool {
97        match ipnet {
98            IpNet::V4(net) => self.ipv4.insert(net.into()),
99            IpNet::V6(net) => self.ipv6.insert(net.into()),
100        }
101    }
102    /// Removes a previously inserted prefix (exact match).
103    ///
104    /// Returns `false` is the element was not present in the set
105    /// and `true` if the removal is effective.
106    pub fn remove(&mut self, ipnet: &IpNet) -> bool {
107        match ipnet {
108            IpNet::V4(net) => self.ipv4.remove(net),
109            IpNet::V6(net) => self.ipv6.remove(net),
110        }
111    }
112    /// Replace an existing prefix.
113    ///
114    /// Adds a prefix to the set, replacing the existing one, if any (exact match performed).
115    /// Returns the replaced value.
116    pub fn replace(&mut self, ipnet: IpNet) -> Option<IpNet> {
117        match ipnet {
118            IpNet::V4(net) => self.ipv4.replace(net.into()).map(IpNet::from),
119            IpNet::V6(net) => self.ipv6.replace(net.into()).map(IpNet::from),
120        }
121    }
122
123    /// Iterates over all the prefixes of this set.
124    pub fn iter(&self) -> impl Iterator<Item = IpNet> + '_ {
125        self.ipv4
126            .iter()
127            .map(|i| (*i).into())
128            .chain(self.ipv6.iter().map(|i| (*i).into()))
129    }
130}
131
132impl Extend<Ipv4Net> for IpRTrieSet {
133    fn extend<I: IntoIterator<Item = Ipv4Net>>(&mut self, iter: I) {
134        self.ipv4.extend(iter.into_iter().map(|i| i.into()))
135    }
136}
137impl Extend<Ipv6Net> for IpRTrieSet {
138    fn extend<I: IntoIterator<Item = Ipv6Net>>(&mut self, iter: I) {
139        self.ipv6.extend(iter.into_iter().map(|i| i.into()))
140    }
141}
142
143impl Extend<IpNet> for IpRTrieSet {
144    fn extend<I: IntoIterator<Item = IpNet>>(&mut self, iter: I) {
145        iter.into_iter().for_each(|item| {
146            self.insert(item);
147        })
148    }
149}
150
151impl FromIterator<IpNet> for IpRTrieSet {
152    fn from_iter<I: IntoIterator<Item = IpNet>>(iter: I) -> Self {
153        let mut trieset = Self::default();
154        trieset.extend(iter);
155        trieset
156    }
157}
158
159impl FromIterator<Ipv4Net> for IpRTrieSet {
160    fn from_iter<I: IntoIterator<Item = Ipv4Net>>(iter: I) -> Self {
161        let mut trieset = Self::default();
162        trieset.extend(iter);
163        trieset
164    }
165}
166
167impl FromIterator<Ipv6Net> for IpRTrieSet {
168    fn from_iter<I: IntoIterator<Item = Ipv6Net>>(iter: I) -> Self {
169        let mut trieset = Self::default();
170        trieset.extend(iter);
171        trieset
172    }
173}
174
175impl IpLCTrieSet {
176    /// Returns the size of the set.
177    ///
178    /// Notice that it always greater or equals two since two top prefixes are
179    /// always present in the map (one for Ipv4 and the other for Ipv6)
180    pub fn len(&self) -> NonZeroUsize {
181        self.ipv4.len().saturating_add(self.ipv6.len().get())
182    }
183
184    /// Checks if an element is present (exact match).
185    pub fn contains(&self, ipnet: &IpNet) -> bool {
186        match ipnet {
187            IpNet::V4(net) => self.ipv4.contains(net),
188            IpNet::V6(net) => self.ipv6.contains(net),
189        }
190    }
191
192    /// Gets the value associated with an exact match of the key.
193    ///
194    /// To access to the longest prefix match, use [`Self::lookup`].
195    pub fn get(&self, ipnet: &IpNet) -> Option<IpNet> {
196        match ipnet {
197            IpNet::V4(net) => self.ipv4.get(net).map(|ip| (*ip).into()),
198            IpNet::V6(net) => self.ipv6.get(net).map(|ip| (*ip).into()),
199        }
200    }
201    /// Gets the longest prefix which matches the given key.
202    ///
203    /// As the top prefix always matches, it never fails.
204    ///
205    /// To access to the exact prefix match, use [`Self::get`].
206    pub fn lookup(&self, ipnet: &IpNet) -> IpNet {
207        match ipnet {
208            IpNet::V4(net) => (*self.ipv4.lookup(net)).into(),
209            IpNet::V6(net) => (*self.ipv6.lookup(net)).into(),
210        }
211    }
212
213    /// Iterates over all the prefixes of this set.
214    pub fn iter(&self) -> impl Iterator<Item = IpNet> + '_ {
215        self.ipv4
216            .iter()
217            .map(|i| (*i).into())
218            .chain(self.ipv6.iter().map(|i| (*i).into()))
219    }
220}
221
222impl FromIterator<IpNet> for IpLCTrieSet {
223    fn from_iter<I: IntoIterator<Item = IpNet>>(iter: I) -> Self {
224        IpRTrieSet::from_iter(iter).compress()
225    }
226}
227
228/// Convenient alias for radix trie map of Ipv4 prefixes
229pub type Ipv4RTrieMap<V> = RTrieMap<Ipv4Prefix, V>;
230/// Convenient alias for radix trie map of Ipv6 prefixes
231pub type Ipv6RTrieMap<V> = RTrieMap<Ipv6Prefix, V>;
232
233/// Convenient alias for LC-Trie map of Ipv4 prefixes
234pub type Ipv4LCTrieMap<V> = LCTrieMap<Ipv4Prefix, V>;
235/// Convenient alias for LC-Trie map of Ipv6 prefixes
236pub type Ipv6LCTrieMap<V> = LCTrieMap<Ipv6Prefix, V>;
237
238/// A radix trie map that mix both Ipv4 and Ipv6 prefixes
239#[derive(Clone, Default)]
240pub struct IpRTrieMap<V> {
241    pub ipv4: Ipv4RTrieMap<V>,
242    pub ipv6: Ipv6RTrieMap<V>,
243}
244
245/// A LC-trie map that mix both Ipv4 and Ipv6 prefixes
246pub struct IpLCTrieMap<V> {
247    pub ipv4: Ipv4LCTrieMap<V>,
248    pub ipv6: Ipv6LCTrieMap<V>,
249}
250
251impl<V: Default> IpRTrieMap<V> {
252    pub fn new() -> Self {
253        Self {
254            ipv4: Ipv4RTrieMap::new(),
255            ipv6: Ipv6RTrieMap::new(),
256        }
257    }
258}
259
260impl<V> IpRTrieMap<V> {
261    pub fn with_roots(ipv4: V, ipv6: V) -> Self {
262        Self {
263            ipv4: RTrieMap::with_root(ipv4),
264            ipv6: RTrieMap::with_root(ipv6),
265        }
266    }
267}
268
269impl<V> IpRTrieMap<V> {
270    /// Returns the size of the map.
271    ///
272    /// Notice that it always greater or equals two since two top prefixes are
273    /// always present in the map (one for Ipv4 and the other for Ipv6)
274    pub fn len(&self) -> NonZeroUsize {
275        self.ipv4.len().saturating_add(self.ipv6.len().get())
276    }
277
278    /// Compress this Patricia trie in a LC-Trie.
279    ///
280    /// For lookup algorithms, a Patricia trie performs unit bit checking and LC-Trie
281    /// performs multi bits checking. So the last one is more performant but it
282    /// cannot be modified (no insertion or removal operations are provided).
283    pub fn compress(self) -> IpLCTrieMap<V> {
284        IpLCTrieMap {
285            ipv4: self.ipv4.compress(),
286            ipv6: self.ipv6.compress(),
287        }
288    }
289
290    pub fn shrink_to_fit(&mut self) {
291        self.ipv4.shrink_to_fit();
292        self.ipv6.shrink_to_fit();
293    }
294
295    /// Gets the value associated with an exact match of the key.
296    ///
297    /// To access to the longest prefix match, use [`Self::lookup`].
298    ///
299    /// To get a mutable access to a value, use [`Self::get_mut`].
300    ///
301    pub fn get(&self, ipnet: &IpNet) -> Option<&V> {
302        match ipnet {
303            IpNet::V4(net) => self.ipv4.get(net),
304            IpNet::V6(net) => self.ipv6.get(net),
305        }
306    }
307    /// Gets a mutable access to the value associated with an exact match of the key.
308    ///
309    /// To access to the longest prefix match, use [`Self::lookup_mut`].
310    ///
311    /// To get a mutable access to a value, use [`Self::get_mut`].
312    pub fn get_mut(&mut self, ipnet: &IpNet) -> Option<&mut V> {
313        match ipnet {
314            IpNet::V4(net) => self.ipv4.get_mut(net),
315            IpNet::V6(net) => self.ipv6.get_mut(net),
316        }
317    }
318    /// Gets the value associated with the longest prefix match of the key.
319    ///
320    /// As the top prefix always matches, the lookup never fails.
321    ///
322    /// To access to the exact prefix match, use [`Self::get`].
323    ///
324    /// To get a mutable access to a value, use [`Self::lookup_mut`].
325    pub fn lookup(&self, ipnet: &IpNet) -> (IpNet, &V) {
326        match ipnet {
327            IpNet::V4(net) => {
328                let (&k, v) = self.ipv4.lookup(net);
329                (k.into(), v)
330            }
331            IpNet::V6(net) => {
332                let (&k, v) = self.ipv6.lookup(net);
333                (k.into(), v)
334            }
335        }
336    }
337    /// Gets a mutable access to the value associated with a longest prefix match of the key.
338    ///
339    /// To access to the exact prefix match, use [`Self::get_mut`].
340    pub fn lookup_mut(&mut self, ipnet: &IpNet) -> (IpNet, &mut V) {
341        match ipnet {
342            IpNet::V4(net) => {
343                let (&k, v) = self.ipv4.lookup_mut(net);
344                (k.into(), v)
345            }
346            IpNet::V6(net) => {
347                let (&k, v) = self.ipv6.lookup_mut(net);
348                (k.into(), v)
349            }
350        }
351    }
352    /// Inserts a new entry in the map.
353    ///
354    /// If the specified key already exists in the map, then the previous associated
355    /// value is replaced by the new one and is returned.
356    pub fn insert(&mut self, ipnet: IpNet, v: V) -> Option<V> {
357        match ipnet {
358            IpNet::V4(net) => self.ipv4.insert(net.into(), v),
359            IpNet::V6(net) => self.ipv6.insert(net.into(), v),
360        }
361    }
362    /// Removes a previously inserted prefix (exact match).
363    /// # Panic
364    /// Panics if trying to remove the root prefix.
365    pub fn remove(&mut self, ipnet: &IpNet) -> Option<V> {
366        match ipnet {
367            IpNet::V4(net) => self.ipv4.remove(net),
368            IpNet::V6(net) => self.ipv6.remove(net),
369        }
370    }
371    /// Iterates over all the entries.
372    ///
373    /// For a mutable access of values, use [`Self::iter_mut`]
374    pub fn iter(&self) -> impl Iterator<Item = (IpNet, &V)> + '_ {
375        self.ipv4
376            .iter()
377            .map(|(k, v)| ((*k).into(), v))
378            .chain(self.ipv6.iter().map(|(k, v)| ((*k).into(), v)))
379    }
380    /// Iterates over all the entries with a mutable access to values.
381    pub fn iter_mut(&mut self) -> impl Iterator<Item = (IpNet, &mut V)> + '_ {
382        self.ipv4
383            .iter_mut()
384            .map(|(k, v)| ((*k).into(), v))
385            .chain(self.ipv6.iter_mut().map(|(k, v)| ((*k).into(), v)))
386    }
387
388    /// Gets a set of copy of all the keys in a trie set.
389    pub fn prefixes(&self) -> IpRTrieSet {
390        IpRTrieSet {
391            ipv4: self.ipv4.prefixes(),
392            ipv6: self.ipv6.prefixes(),
393        }
394    }
395}
396
397impl<V> Extend<(Ipv4Net, V)> for IpRTrieMap<V> {
398    fn extend<I: IntoIterator<Item = (Ipv4Net, V)>>(&mut self, iter: I) {
399        self.ipv4
400            .extend(iter.into_iter().map(|(i, v)| (i.into(), v)))
401    }
402}
403impl<V> Extend<(Ipv6Net, V)> for IpRTrieMap<V> {
404    fn extend<I: IntoIterator<Item = (Ipv6Net, V)>>(&mut self, iter: I) {
405        self.ipv6
406            .extend(iter.into_iter().map(|(i, v)| (i.into(), v)))
407    }
408}
409impl<V> Extend<(IpNet, V)> for IpRTrieMap<V> {
410    fn extend<I: IntoIterator<Item = (IpNet, V)>>(&mut self, iter: I) {
411        iter.into_iter().for_each(|(k, v)| {
412            self.insert(k, v);
413        })
414    }
415}
416
417impl<V: Default> FromIterator<(IpNet, V)> for IpRTrieMap<V> {
418    fn from_iter<I: IntoIterator<Item = (IpNet, V)>>(iter: I) -> Self {
419        let mut triemap = Self::default();
420        triemap.extend(iter);
421        triemap
422    }
423}
424
425impl<V: Default> FromIterator<(Ipv4Net, V)> for IpRTrieMap<V> {
426    fn from_iter<I: IntoIterator<Item = (Ipv4Net, V)>>(iter: I) -> Self {
427        let mut triemap = Self::default();
428        triemap.extend(iter);
429        triemap
430    }
431}
432
433impl<V: Default> FromIterator<(Ipv6Net, V)> for IpRTrieMap<V> {
434    fn from_iter<I: IntoIterator<Item = (Ipv6Net, V)>>(iter: I) -> Self {
435        let mut triemap = Self::default();
436        triemap.extend(iter);
437        triemap
438    }
439}
440
441impl<V> IpLCTrieMap<V> {
442    /// Returns the size of the map.
443    ///
444    /// Notice that it always greater or equals two since two top prefixes are
445    /// always present in the map (one for Ipv4 and the other for Ipv6)
446    pub fn len(&self) -> NonZeroUsize {
447        self.ipv4.len().saturating_add(self.ipv6.len().get())
448    }
449
450    /// Gets the value associated with an exact match of the key.
451    ///
452    /// To access to the longest prefix match, use [`Self::lookup`].
453    ///
454    /// To get a mutable access to a value, use [`Self::get_mut`].
455    ///
456    pub fn get(&self, ipnet: &IpNet) -> Option<&V> {
457        match ipnet {
458            IpNet::V4(net) => self.ipv4.get(net),
459            IpNet::V6(net) => self.ipv6.get(net),
460        }
461    }
462    /// Gets a mutable access to the value associated with an exact match of the key.
463    ///
464    /// To access to the longest prefix match, use [`Self::lookup_mut`].
465    ///
466    /// To get a mutable access to a value, use [`Self::get_mut`].
467    pub fn get_mut(&mut self, ipnet: &IpNet) -> Option<&mut V> {
468        match ipnet {
469            IpNet::V4(net) => self.ipv4.get_mut(net),
470            IpNet::V6(net) => self.ipv6.get_mut(net),
471        }
472    }
473    /// Gets the value associated with the longest prefix match of the key.
474    ///
475    /// As the top prefix always matches, the lookup never fails.
476    ///
477    /// To access to the exact prefix match, use [`Self::get`].
478    ///
479    /// To get a mutable access to a value, use [`Self::lookup_mut`].
480    pub fn lookup(&self, ipnet: &IpNet) -> (IpNet, &V) {
481        match ipnet {
482            IpNet::V4(net) => {
483                let (&k, v) = self.ipv4.lookup(net);
484                (k.into(), v)
485            }
486            IpNet::V6(net) => {
487                let (&k, v) = self.ipv6.lookup(net);
488                (k.into(), v)
489            }
490        }
491    }
492    /// Gets a mutable access to the value associated with a longest prefix match of the key.
493    ///
494    /// To access to the exact prefix match, use [`Self::get_mut`].
495    pub fn lookup_mut(&mut self, ipnet: &IpNet) -> (IpNet, &mut V) {
496        match ipnet {
497            IpNet::V4(net) => {
498                let (&k, v) = self.ipv4.lookup_mut(net);
499                (k.into(), v)
500            }
501            IpNet::V6(net) => {
502                let (&k, v) = self.ipv6.lookup_mut(net);
503                (k.into(), v)
504            }
505        }
506    }
507
508    /// Iterates over all the entries.
509    ///
510    /// For a mutable access of values, use [`Self::iter_mut`]
511    pub fn iter(&self) -> impl Iterator<Item = (IpNet, &V)> + '_ {
512        self.ipv4
513            .iter()
514            .map(|(k, v)| ((*k).into(), v))
515            .chain(self.ipv6.iter().map(|(k, v)| ((*k).into(), v)))
516    }
517    /// Iterates over all the entries with a mutable access to values.
518    pub fn iter_mut(&mut self) -> impl Iterator<Item = (IpNet, &mut V)> + '_ {
519        self.ipv4
520            .iter_mut()
521            .map(|(k, v)| ((*k).into(), v))
522            .chain(self.ipv6.iter_mut().map(|(k, v)| ((*k).into(), v)))
523    }
524
525    /// Gets a set of copy of all the keys in a trie set.
526    pub fn prefixes(&self) -> IpLCTrieSet {
527        IpLCTrieSet {
528            ipv4: self.ipv4.prefixes(),
529            ipv6: self.ipv6.prefixes(),
530        }
531    }
532}
533
534impl<V: Default> FromIterator<(IpNet, V)> for IpLCTrieMap<V> {
535    fn from_iter<I: IntoIterator<Item = (IpNet, V)>>(iter: I) -> Self {
536        IpRTrieMap::from_iter(iter).compress()
537    }
538}
iptrie/lib.rs

iptrie/
lib.rs
