Struct JointPrefixSet 

pub struct JointPrefixSet<P: JointPrefix> {
    pub t1: PrefixSet<P::P1>,
    pub t2: PrefixSet<P::P2>,
}

Set of prefixes, organized in a tree. This strucutre gives efficient access to the longest prefix in the set that contains another prefix.

Access the individual sets self.t1 and self.t2 to perform set operations (using crate::AsView).

Fields

t1: PrefixSet<P::P1>

PrefixSet that corresponds to the first prefix type

t2: PrefixSet<P::P2>

PrefixSet that corresponds to the second prefix type

Implementations

impl<P: JointPrefix> JointPrefixSet<P>

pub fn new() -> Self

Create a new, empty prefixset.

pub fn len(&self) -> usize

Returns the number of elements stored in self.

let mut set: JointPrefixSet<ipnet::IpNet> = JointPrefixSet::default();
set.insert("192.168.1.0/24".parse()?);
set.insert("192.168.1.0/25".parse()?);
set.insert("2001::1:0:0/96".parse()?);
assert_eq!(set.len(), 3);

pub fn is_empty(&self) -> bool

Returns true if the set contains no elements.

let mut set: JointPrefixSet<ipnet::IpNet> = JointPrefixSet::new();
assert!(set.is_empty());
set.insert("2001::1:0:0/96".parse()?);
assert!(!set.is_empty());

pub fn contains(&self, prefix: &P) -> bool

Check wether some prefix is present in the set, without using longest prefix match.

let mut set: JointPrefixSet<ipnet::IpNet> = JointPrefixSet::new();
set.insert("192.168.1.0/24".parse()?);
assert!(set.contains(&"192.168.1.0/24".parse()?));
assert!(!set.contains(&"192.168.2.0/24".parse()?));
assert!(!set.contains(&"192.168.0.0/23".parse()?));
assert!(!set.contains(&"192.168.1.128/25".parse()?));
assert!(!set.contains(&"c0a8:1::/24".parse()?));

pub fn get(&self, prefix: &P) -> Option<P>

Get a reference to the stored prefix. This function allows you to retrieve the host part of the prefix. The returned prefix will always have the same network address and prefix length.

let mut set: JointPrefixSet<ipnet::IpNet> = JointPrefixSet::new();
set.insert("192.168.0.254/24".parse()?);
assert_eq!(set.get(&"192.168.0.0/24".parse()?), Some("192.168.0.254/24".parse()?));

pub fn get_lpm(&self, prefix: &P) -> Option<P>

Get the longest prefix in the set that contains the given preifx.

let mut set: JointPrefixSet<ipnet::IpNet> = JointPrefixSet::new();
set.insert("192.168.1.0/24".parse()?);
set.insert("192.168.0.0/23".parse()?);
assert_eq!(set.get_lpm(&"192.168.1.1/32".parse()?), Some("192.168.1.0/24".parse()?));
assert_eq!(set.get_lpm(&"192.168.1.0/24".parse()?), Some("192.168.1.0/24".parse()?));
assert_eq!(set.get_lpm(&"192.168.0.0/24".parse()?), Some("192.168.0.0/23".parse()?));
assert_eq!(set.get_lpm(&"192.168.2.0/24".parse()?), None);

pub fn get_spm(&self, prefix: &P) -> Option<P>

Get the shortest prefix in the set that contains the given preifx.

let mut set: JointPrefixSet<ipnet::IpNet> = JointPrefixSet::new();
set.insert("192.168.1.0/24".parse()?);
set.insert("192.168.0.0/23".parse()?);
assert_eq!(set.get_spm(&"192.168.1.1/32".parse()?), Some("192.168.0.0/23".parse()?));
assert_eq!(set.get_spm(&"192.168.1.0/24".parse()?), Some("192.168.0.0/23".parse()?));
assert_eq!(set.get_spm(&"192.168.0.0/23".parse()?), Some("192.168.0.0/23".parse()?));
assert_eq!(set.get_spm(&"192.168.2.0/24".parse()?), None);

pub fn insert(&mut self, prefix: P) -> bool

Adds a value to the set.

Returns whether the value was newly inserted. That is:

• If the set did not previously contain this value, true is returned.
• If the set already contained this value, false is returned.

This operation will always replace the currently stored prefix. This allows you to store additional information in the host aprt of the prefix.

let mut set: JointPrefixSet<ipnet::IpNet> = JointPrefixSet::new();
assert!(set.insert("192.168.0.0/23".parse()?));
assert!(set.insert("192.168.1.0/24".parse()?));
assert!(!set.insert("192.168.1.0/24".parse()?));

pub fn remove(&mut self, prefix: &P) -> bool

Removes a value from the set. Returns whether the value was present in the set.

let mut set: JointPrefixSet<ipnet::IpNet> = JointPrefixSet::new();
let prefix = "192.168.1.0/24".parse()?;
set.insert(prefix);
assert!(set.contains(&prefix));
assert!(set.remove(&prefix));
assert!(!set.contains(&prefix));

pub fn remove_keep_tree(&mut self, prefix: &P) -> bool

Removes a prefix from the set, returning wether the prefix was present or not. In contrast to Self::remove, his operation will keep the tree structure as is, but only remove the element from it. This allows any future insert on the same prefix to be faster. However future reads from the tree might be a bit slower because they need to traverse more nodes.

let mut set: JointPrefixSet<ipnet::IpNet> = JointPrefixSet::new();
let prefix = "192.168.1.0/24".parse()?;
set.insert(prefix);
assert!(set.contains(&prefix));
assert!(set.remove_keep_tree(&prefix));
assert!(!set.contains(&prefix));

// future inserts of the same key are now faster!
set.insert(prefix);

pub fn remove_children(&mut self, prefix: &P)

Remove all elements that are contained within prefix. This will change the tree structure. This operation is O(n), as the entries must be freed up one-by-one.

let mut set: JointPrefixSet<ipnet::IpNet> = JointPrefixSet::new();
set.insert("192.168.0.0/22".parse()?);
set.insert("192.168.0.0/23".parse()?);
set.insert("192.168.0.0/24".parse()?);
set.insert("192.168.2.0/23".parse()?);
set.insert("192.168.2.0/24".parse()?);
set.insert("c0a8::/24".parse()?);
set.remove_children(&"192.168.0.0/23".parse()?);
assert!(!set.contains(&"192.168.0.0/23".parse()?));
assert!(!set.contains(&"192.168.0.0/24".parse()?));
assert!(set.contains(&"192.168.2.0/23".parse()?));
assert!(set.contains(&"192.168.2.0/24".parse()?));
assert!(set.contains(&"c0a8::/24".parse()?));

pub fn clear(&mut self)

Clear the set but keep the allocated memory.

let mut set: JointPrefixSet<ipnet::IpNet> = JointPrefixSet::new();
set.insert("192.168.0.0/24".parse()?);
set.insert("192.168.1.0/24".parse()?);
set.insert("2001::1:0:0/96".parse()?);
set.clear();
assert!(!set.contains(&"192.168.0.0/24".parse()?));
assert!(!set.contains(&"192.168.1.0/24".parse()?));
assert!(!set.contains(&"2001::1:0:0/96".parse()?));

pub fn iter(&self) -> Iter<'_, P>

Iterate over all prefixes in the set. It iterates over the first, and then over the second set.

let mut set: JointPrefixSet<ipnet::IpNet> = JointPrefixSet::new();
set.insert("192.168.1.0/24".parse()?);
set.insert("192.168.0.0/24".parse()?);
set.insert("2001::1:0:0/96".parse()?);
assert_eq!(
    set.iter().collect::<Vec<_>>(),
    vec![
        "192.168.0.0/24".parse()?,
        "192.168.1.0/24".parse()?,
        "2001::1:0:0/96".parse()?
    ],
);

pub fn retain<F>(&mut self, f: F)

where F: FnMut(P) -> bool,

Keep only the elements in the map that satisfy the given condition f.

let mut set: JointPrefixSet<ipnet::IpNet> = JointPrefixSet::new();
set.insert("192.168.0.0/24".parse()?);
set.insert("192.168.1.0/24".parse()?);
set.insert("192.168.2.0/24".parse()?);
set.insert("192.168.2.0/25".parse()?);
set.insert("2001::/24".parse()?);
set.insert("2001::/25".parse()?);
set.retain(|p| p.prefix_len() == 24);
assert!(set.contains(&"192.168.0.0/24".parse()?));
assert!(set.contains(&"192.168.1.0/24".parse()?));
assert!(set.contains(&"192.168.2.0/24".parse()?));
assert!(!set.contains(&"192.168.2.0/25".parse()?));
assert!(set.contains(&"2001::/24".parse()?));
assert!(!set.contains(&"2001::/25".parse()?));

pub fn children<'a>(&'a self, prefix: &P) -> Iter<'a, P>

Get an iterator over the node itself and all children. All elements returned have a prefix that is contained within prefix itself (or are the same). The iterator yields elements in lexicographic order.

Info: Use the crate::trieview::TrieView abstraction that provides more flexibility.

let mut set: JointPrefixSet<ipnet::IpNet> = JointPrefixSet::new();
set.insert("192.168.0.0/22".parse()?);
set.insert("192.168.0.0/23".parse()?);
set.insert("192.168.2.0/23".parse()?);
set.insert("192.168.0.0/24".parse()?);
set.insert("192.168.2.0/24".parse()?);
assert_eq!(
    set.children(&"192.168.0.0/23".parse()?).collect::<Vec<_>>(),
    vec![
        "192.168.0.0/23".parse()?,
        "192.168.0.0/24".parse()?,
    ]
);

pub fn cover<'a, 'p>(&'a self, prefix: &'p P) -> CoverKeys<'a, 'p, P, ()>

Iterate over all prefixes in the set that covers the given prefix (including prefix itself if that is present in the set). The returned iterator yields &'a P.

The iterator will always yield elements ordered by their prefix length, i.e., their depth in the tree.

let mut set: JointPrefixSet<ipnet::IpNet> = JointPrefixSet::new();
let p0 = "10.0.0.0/8".parse()?;
let p1 = "10.1.0.0/16".parse()?;
let p2 = "10.1.1.0/24".parse()?;
set.insert(p0);
set.insert(p1);
set.insert(p2);
set.insert("10.1.2.0/24".parse()?); // disjoint prefixes are not covered
set.insert("10.1.1.0/25".parse()?); // more specific prefixes are not covered
set.insert("11.0.0.0/8".parse()?);  // Branch points that don't contain values are skipped
assert_eq!(set.cover(&p2).collect::<Vec<_>>(), vec![p0, p1, p2]);

pub fn union<'a>(&'a self, other: &'a JointPrefixSet<P>) -> Union<'a, P>

Iterate over the union of two joint prefix sets. This is roughly equivalent to calling self.t1.view().union(&other.t1).chain(self.t2.view().union(&other.t2)).

If a prefix is present in both trees, the iterator will yield both elements. Otherwise, the iterator will yield the element of one map together with the longest prefix match in the other map. Elements are of type P.

macro_rules! net { ($x:literal) => {$x.parse::<ipnet::IpNet>().unwrap()}; }

let mut set_a: JointPrefixSet<ipnet::IpNet> = JointPrefixSet::from_iter([
    net!("2001::1:0:0/96"),
    net!("192.168.0.0/22"),
    net!("192.168.0.0/24"),
]);
let mut set_b: JointPrefixSet<ipnet::IpNet> = JointPrefixSet::from_iter([
    net!("192.168.0.0/22"),
    net!("192.168.0.0/23"),
]);
assert_eq!(
    set_a.union(&set_b).collect::<Vec<_>>(),
    vec![
        net!("192.168.0.0/22"),
        net!("192.168.0.0/23"),
        net!("192.168.0.0/24"),
        net!("2001::1:0:0/96"),
    ]
);

pub fn intersection<'a>( &'a self, other: &'a JointPrefixSet<P>, ) -> Intersection<'a, P>

Iterate over the intersection of two joint prefix sets. This is roughly equivalent to calling self.t1.view().intersection(&other.t1).chain(self.t2.view().intersection(&other.t2)).

macro_rules! net { ($x:literal) => {$x.parse::<ipnet::IpNet>().unwrap()}; }

let mut set_a: JointPrefixSet<ipnet::IpNet> = JointPrefixSet::from_iter([
    net!("192.168.0.0/20"),
    net!("192.168.0.0/22"),
    net!("192.168.0.0/24"),
    net!("192.168.2.0/23"),
    net!("2001::1:0:0/96"),
    net!("2001::1:0:0/97"),
]);
let mut set_b: JointPrefixSet<ipnet::IpNet> = JointPrefixSet::from_iter([
    net!("192.168.0.0/20"),
    net!("192.168.0.0/22"),
    net!("192.168.0.0/23"),
    net!("192.168.0.0/24"),
    net!("192.168.2.0/24"),
    net!("2001::1:0:0/96"),
    net!("2001::0:0:0/97"),
]);
assert_eq!(
    set_a.intersection(&set_b).collect::<Vec<_>>(),
    vec![
        net!("192.168.0.0/20"),
        net!("192.168.0.0/22"),
        net!("192.168.0.0/24"),
        net!("2001::1:0:0/96"),
    ]
);

pub fn difference<'a>( &'a self, other: &'a JointPrefixSet<P>, ) -> Difference<'a, P>

Iterate over the all elements in self that are not present in other. Each item will return a reference to the prefix and value in self, as well as the longest prefix match of other.

macro_rules! net { ($x:literal) => {$x.parse::<ipnet::IpNet>().unwrap()}; }

let mut set_a: JointPrefixSet<ipnet::IpNet> = JointPrefixSet::from_iter([
    net!("192.168.0.0/20"),
    net!("192.168.0.0/22"),
    net!("192.168.0.0/24"),
    net!("192.168.2.0/23"),
    net!("2001::1:0:0/96"),
    net!("2001::1:0:0/97"),
]);
let mut set_b: JointPrefixSet<ipnet::IpNet> = JointPrefixSet::from_iter([
    net!("192.168.0.0/20"),
    net!("192.168.0.0/22"),
    net!("192.168.0.0/23"),
    net!("192.168.2.0/24"),
    net!("2001::1:0:0/96"),
]);
assert_eq!(
    set_a.difference(&set_b).collect::<Vec<_>>(),
    vec![
        (net!("192.168.0.0/24"), Some(net!("192.168.0.0/23"))),
        (net!("192.168.2.0/23"), Some(net!("192.168.0.0/22"))),
        (net!("2001::1:0:0/97"), Some(net!("2001::1:0:0/96"))),
    ]
);

pub fn covering_difference<'a>( &'a self, other: &'a JointPrefixSet<P>, ) -> CoveringDifference<'a, P>

Iterate over the all elements in self that are not covered by other.

macro_rules! net { ($x:literal) => {$x.parse::<ipnet::IpNet>().unwrap()}; }

let mut set_a: JointPrefixSet<ipnet::IpNet> = JointPrefixSet::from_iter([
    net!("192.168.0.0/20"),
    net!("192.168.0.0/22"),
    net!("192.168.0.0/24"),
    net!("192.168.2.0/23"),
    net!("2001::0:0:0/95"),
    net!("2001::1:0:0/96"),
    net!("2001::1:0:0/97"),
]);
let mut set_b: JointPrefixSet<ipnet::IpNet> = JointPrefixSet::from_iter([
    net!("192.168.0.0/21"),
    net!("192.168.0.0/22"),
    net!("192.168.0.0/23"),
    net!("192.168.2.0/24"),
    net!("2001::1:0:0/96"),
]);
assert_eq!(
    set_a.covering_difference(&set_b).collect::<Vec<_>>(),
    vec![net!("192.168.0.0/20"), net!("2001::0:0:0/95")]
);

Trait Implementations

impl<P: Clone + JointPrefix> Clone for JointPrefixSet<P>

where P::P1: Clone, P::P2: Clone,

fn clone(&self) -> JointPrefixSet<P>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<P: Debug + JointPrefix> Debug for JointPrefixSet<P>

where P::P1: Debug, P::P2: Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<P: JointPrefix> Default for JointPrefixSet<P>

fn default() -> Self

Returns the “default value” for a type.

impl<P: JointPrefix> FromIterator<P> for JointPrefixSet<P>

fn from_iter<I: IntoIterator<Item = P>>(iter: I) -> Self

Creates a value from an iterator.

impl<'a, P: JointPrefix> IntoIterator for &'a JointPrefixSet<P>

type Item = P

The type of the elements being iterated over.

type IntoIter = Iter<'a, P>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<P: JointPrefix> IntoIterator for JointPrefixSet<P>

type Item = P

The type of the elements being iterated over.

type IntoIter = IntoIter<P>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<P> PartialEq for JointPrefixSet<P>

where P: JointPrefix + PartialEq,

fn eq(&self, other: &Self) -> bool

Compare two prefix sets to contain the same prefixes. This also compares the host-part of the prefix:

let mut set1: JointPrefixSet<ipnet::IpNet> = ["10.0.0.0/8".parse()?].into_iter().collect();
let mut set2: JointPrefixSet<ipnet::IpNet> = ["10.0.0.1/8".parse()?].into_iter().collect();
assert_ne!(set1, set2);

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<P> Eq for JointPrefixSet<P>

where P: JointPrefix + Eq,