Struct prefix_trie::set::PrefixSet

pub struct PrefixSet<P>(/* private fields */);

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

Implementations

impl<P: Prefix> PrefixSet<P>

pub fn new() -> Self

Create a new, empty prefixset.

pub fn len(&self) -> usize

Returns the number of elements stored in self.

pub fn is_empty(&self) -> bool

Returns true if the set contains no elements.

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

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

let mut set: PrefixSet<ipnet::Ipv4Net> = PrefixSet::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()?));

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

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

let mut set: PrefixSet<ipnet::Ipv4Net> = PrefixSet::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<'a>(&'a self, prefix: &P) -> Option<&'a P>

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

let mut set: PrefixSet<ipnet::Ipv4Net> = PrefixSet::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.

let mut set: PrefixSet<ipnet::Ipv4Net> = PrefixSet::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: PrefixSet<ipnet::Ipv4Net> = PrefixSet::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: PrefixSet<ipnet::Ipv4Net> = PrefixSet::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: PrefixSet<ipnet::Ipv4Net> = PrefixSet::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.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()?));

pub fn clear(&mut self)

Clear the set but keep the allocated memory.

let mut set: PrefixSet<ipnet::Ipv4Net> = PrefixSet::new();
set.insert("192.168.0.0/24".parse()?);
set.insert("192.168.1.0/24".parse()?);
set.clear();
assert!(!set.contains(&"192.168.0.0/24".parse()?));
assert!(!set.contains(&"192.168.1.0/24".parse()?));

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

Iterate over all prefixes in the set

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: PrefixSet<ipnet::Ipv4Net> = PrefixSet::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.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()?));

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

Return an iterator that traverses both trees simultaneously and yields the union of both sets in lexicographic order.

let mut set_a: PrefixSet<ipnet::Ipv4Net> = PrefixSet::from_iter([
    "192.168.0.0/22".parse()?,
    "192.168.0.0/24".parse()?,
    "192.168.2.0/23".parse()?,
]);
let mut set_b: PrefixSet<ipnet::Ipv4Net> = PrefixSet::from_iter([
    "192.168.0.0/22".parse()?,
    "192.168.0.0/23".parse()?,
    "192.168.2.0/24".parse()?,
]);
assert_eq!(
    set_a.union(&set_b).copied().collect::<Vec<_>>(),
    vec![
        "192.168.0.0/22".parse()?,
        "192.168.0.0/23".parse()?,
        "192.168.0.0/24".parse()?,
        "192.168.2.0/23".parse()?,
        "192.168.2.0/24".parse()?,
    ]
);

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

Return an iterator that traverses both trees simultaneously and yields the intersection of both sets in lexicographic order.

let mut set_a: PrefixSet<ipnet::Ipv4Net> = PrefixSet::from_iter([
    "192.168.0.0/22".parse()?,
    "192.168.0.0/24".parse()?,
    "192.168.2.0/23".parse()?,
]);
let mut set_b: PrefixSet<ipnet::Ipv4Net> = PrefixSet::from_iter([
    "192.168.0.0/22".parse()?,
    "192.168.0.0/24".parse()?,
    "192.168.2.0/24".parse()?,
]);
assert_eq!(
    set_a.intersection(&set_b).copied().collect::<Vec<_>>(),
    vec!["192.168.0.0/22".parse()?, "192.168.0.0/24".parse()?]
);

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

Return an iterator that traverses both trees simultaneously and yields the difference of both sets in lexicographic order.

let mut set_a: PrefixSet<ipnet::Ipv4Net> = PrefixSet::from_iter([
    "192.168.0.0/22".parse()?,
    "192.168.0.0/24".parse()?,
    "192.168.2.0/23".parse()?,
]);
let mut set_b: PrefixSet<ipnet::Ipv4Net> = PrefixSet::from_iter([
    "192.168.0.0/22".parse()?,
    "192.168.0.0/24".parse()?,
    "192.168.2.0/24".parse()?,
]);
assert_eq!(
    set_a.difference(&set_b).copied().collect::<Vec<_>>(),
    vec!["192.168.2.0/23".parse()?]
);

pub fn cover<'a>(&'a self, prefix: &'a P) -> CoverKeys<'a, 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: PrefixSet<ipnet::Ipv4Net> = PrefixSet::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]);

Trait Implementations

impl<P: Clone> Clone for PrefixSet<P>

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<P: Debug> Debug for PrefixSet<P>

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

Formats the value using the given formatter.

impl<P: Prefix> Default for PrefixSet<P>

fn default() -> Self

Returns the “default value” for a type.

impl<P: Prefix> FromIterator<P> for PrefixSet<P>

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

Creates a value from an iterator.

impl<'a, P: Prefix> IntoIterator for &'a PrefixSet<P>

type Item = &'a 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: Prefix> IntoIterator for PrefixSet<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 PrefixSet<P>

where P: Prefix + PartialEq,

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

This method tests for self and other values to be equal, and is used by ==.

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

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

impl<P> Eq for PrefixSet<P>

where P: Prefix + Eq,