Struct 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.

You can perform union, intersection, and (covering) difference operations by first creating a view over the map using crate::AsView or crate::AsViewMut.

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

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: 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 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: 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.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: 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: Prefix> AsView for PrefixSet<P>

type P = P

The prefix type of the returned view

type T = ()

The value type of the returned view

fn view(&self) -> TrieView<'_, P, ()>

Get a TrieView rooted at the origin (referencing the entire trie).

fn view_at(&self, prefix: Self::P) -> Option<TrieView<'_, Self::P, Self::T>>

Get a TrieView rooted at the given prefix. If that prefix is not part of the trie, None is returned. Calling this function is identical to self.view().find(prefix).

impl<'a, P: Prefix> AsViewMut<'a, P, ()> for &'a mut PrefixSet<P>

fn view_mut(self) -> TrieViewMut<'a, P, ()>

Get a mutable view rooted at the origin (referencing the entire trie).

fn view_mut_at(self, prefix: P) -> Option<TrieViewMut<'a, P, T>>

Get a mutable view rooted at the given prefix. If that prefix is not part of the trie, None is returned. Calling this function is identical to self.view().find(prefix).

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

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

Returns a duplicate 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

Tests for self and other values to be equal, and is used by ==.

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 PrefixSet<P>

where P: Prefix + Eq,