Struct PrefixSet 

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

Set of prefixes, organized in a dense prefix trie.

This structure gives efficient access to the longest prefix in the set that contains another prefix. Prefixes returned from this set are reconstructed from the trie and are therefore returned by value. Host bits outside the prefix length are not preserved.

You can perform union, intersection, and difference operations by creating a view with AsView.

Implementations

impl<P: Prefix> PrefixSet<P>

pub fn new() -> Self

Create a new, empty prefix set.

use prefix_trie::PrefixSet;

let set: PrefixSet<ipnet::Ipv4Net> = PrefixSet::new();
assert!(set.is_empty());

pub fn len(&self) -> usize

Returns the number of prefixes stored in the set.

This is the number of stored prefixes, not the number of addresses they cover (see address_count).

use prefix_trie::PrefixSet;

let mut set: PrefixSet<ipnet::Ipv4Net> = PrefixSet::new();
assert_eq!(set.len(), 0);
set.insert("192.168.0.0/24".parse()?);
set.insert("192.168.1.0/24".parse()?);
assert_eq!(set.len(), 2);

pub fn is_empty(&self) -> bool

Returns true if the set contains no prefixes.

use prefix_trie::PrefixSet;

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

pub fn mem_size(&self) -> usize

Returns the amount of memory used by this data structure in bytes.

use prefix_trie::PrefixSet;

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

pub fn address_count(&self) -> Option<P::R>

Count the number of unique addresses covered by all prefixes in the set. If the entire trie is covered, the function returns None (as it contains P::R::MAX + 1 addresses). Overlapping prefixes are not double-counted.

To avoid double-counting, the function traverses the (partial) tree once, skipping nodes that are already covered.

use prefix_trie::PrefixSet;

let mut set: PrefixSet<ipnet::Ipv4Net> = PrefixSet::new();
set.insert("192.0.2.0/24".parse()?);
set.insert("198.51.100.0/24".parse()?);
assert_eq!(set.address_count(), Some(512));

// Full address spaces cannot be represented in their address type.
set.insert("0.0.0.0/0".parse()?);
assert_eq!(set.address_count(), None);

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

Check whether prefix is present in the set.

use prefix_trie::PrefixSet;

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(&self, prefix: &P) -> Option<P>

Get the canonical (reconstructed) prefix that matches prefix exactly.

Prefixes are not stored verbatim. They are reconstructed from the trie position, so host bits masked out by the prefix length are not preserved.

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

Get the longest prefix in the set that contains prefix.

use prefix_trie::PrefixSet;

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(&self, prefix: &P) -> Option<P>

Get the shortest prefix in the set that contains prefix.

use prefix_trie::PrefixSet;

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 is_covered(&self, prefix: &P) -> bool

Check whether prefix is covered by the set, i.e., whether the set contains prefix itself or any less-specific prefix that contains it.

This is equivalent to self.cover(prefix).next().is_some(), but stops at the first (shortest) covering prefix. See cover to iterate over the covering prefixes themselves.

This function does not perform aggregation. That means that, even if both the left and right children of p are present in the set, is_covered(p) may still return false. See is_covered_in_aggregate for that case.

use prefix_trie::PrefixSet;

let mut set: PrefixSet<ipnet::Ipv4Net> = PrefixSet::new();
set.insert("10.0.0.0/8".parse()?);
assert!(set.is_covered(&"10.0.0.0/8".parse()?));  // exact member
assert!(set.is_covered(&"10.1.2.0/24".parse()?)); // covered by 10.0.0.0/8
assert!(!set.is_covered(&"11.0.0.0/8".parse()?)); // not covered

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

Check whether every address in prefix is covered by the set, i.e., whether prefix’s entire range is tiled by members of the set, even if no single member covers prefix on its own.

This is equivalent to { let mut s = self.clone(); s.aggregate(); s.is_covered(prefix) }, but read-only and without cloning. See is_covered for the (cheaper, stricter) single-member check.

use prefix_trie::PrefixSet;

let mut set: PrefixSet<ipnet::Ipv4Net> = PrefixSet::new();
set.insert("10.0.0.0/9".parse()?);
set.insert("10.128.0.0/9".parse()?);
assert!(!set.is_covered(&"10.0.0.0/8".parse()?));             // no single covering member
assert!(set.is_covered_in_aggregate(&"10.0.0.0/8".parse()?)); // the two /9s tile the /8

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

Adds a prefix to the set.

Returns whether the prefix was newly inserted.

use prefix_trie::PrefixSet;

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 prefix from the set and returns whether it was present.

use prefix_trie::PrefixSet;

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 prefix from the set and may leave empty trie nodes in place.

use prefix_trie::PrefixSet;

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));

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

Remove all prefixes that are contained within prefix.

use prefix_trie::PrefixSet;

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 while keeping allocated memory for reuse.

use prefix_trie::PrefixSet;

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.is_empty());
assert!(!set.contains(&"192.168.0.0/24".parse()?));

pub fn aggregate_consistent(&mut self)

Modifies the prefix set by removing entries that are already covered by another one with a shorter prefix length, without merging adjacent prefixes.

Invariant: for any prefix p, before.is_covered(p) and after.is_covered(p) yield the same value (while the matched prefix may become less specific).

use prefix_trie::PrefixSet;

let mut set: PrefixSet<ipnet::Ipv4Net> = PrefixSet::new();
set.insert("10.0.0.0/24".parse()?);
set.insert("10.0.1.0/24".parse()?);   // adjacent sibling of 10.0.0.0/24
set.insert("10.0.0.128/25".parse()?); // covered by 10.0.0.0/24
set.aggregate_consistent();
// Only the covered /25 is dropped; the two /24 siblings are *not* merged.
assert_eq!(
    set.iter().collect::<Vec<_>>(),
    vec![
        "10.0.0.0/24".parse()?,
        "10.0.1.0/24".parse()?,
    ]
);

pub fn aggregate(&mut self)

Modifies the prefix set by removing entries that are already covered by another one with a shorter prefix length, and by (recursively) merging adjacent prefixes.

Invariant: for any address a (a host prefix of maximal length), before.is_covered(a) == after.is_covered(a). That is, the covered address space is preserved exactly. This does not extend to shorter prefixes: merging siblings can make get_lpm return Some for a prefix that previously matched nothing. For example, two /24s merge into a /23, so get_lpm of that /23 flips from None to Some. If you need the invariant to hold for every prefix, use PrefixSet::aggregate_consistent, which only drops redundant entries and never merges.

use prefix_trie::PrefixSet;

let mut set: PrefixSet<ipnet::Ipv4Net> = PrefixSet::new();
set.insert("10.0.0.0/24".parse()?);
set.insert("10.0.1.0/24".parse()?);   // adjacent sibling of 10.0.0.0/24
set.insert("10.0.0.128/25".parse()?); // covered by 10.0.0.0/24
set.aggregate();
// The two /24 siblings are merged into a single /23.
assert_eq!(
    set.iter().collect::<Vec<_>>(),
    vec![
        "10.0.0.0/23".parse()?,
    ]
);

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

Iterate over all prefixes in lexicographic order.

The iterator yields canonical owned prefixes.

use prefix_trie::PrefixSet;

let mut set: PrefixSet<ipnet::Ipv4Net> = PrefixSet::new();
set.insert("192.168.0.0/23".parse()?);
set.insert("192.168.0.0/24".parse()?);
set.insert("192.168.2.0/23".parse()?);
assert_eq!(
    set.iter().collect::<Vec<_>>(),
    vec![
        "192.168.0.0/23".parse()?,
        "192.168.0.0/24".parse()?,
        "192.168.2.0/23".parse()?,
    ]
);

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

Iterate over all prefixes starting at prefix, in lexicographic order.

This enables stateless, cursor-based pagination: pass the last-seen prefix to resume.

• If inclusive is true, the iterator includes prefix (if present).
• If inclusive is false, the iterator starts after prefix. Prefixes more specific than prefix (its children) are still yielded.

If prefix is not present in the set, the iterator starts at the first prefix that would come after prefix in lexicographic order, regardless of inclusive.

use prefix_trie::PrefixSet;

let mut set: PrefixSet<ipnet::Ipv4Net> = PrefixSet::new();
set.insert("10.0.0.0/8".parse()?);
set.insert("10.1.0.0/16".parse()?);
set.insert("10.2.0.0/16".parse()?);
set.insert("10.3.0.0/16".parse()?);

// Cursor pagination: skip last seen, fetch next page
let page: Vec<_> = set.iter_from(&"10.1.0.0/16".parse()?, false).take(2).collect();
assert_eq!(page, vec!["10.2.0.0/16".parse()?, "10.3.0.0/16".parse()?]);

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

where F: FnMut(&P) -> bool,

Keep only prefixes that satisfy the predicate f.

use prefix_trie::{Prefix, PrefixSet};

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>

Iterate over prefix and all more-specific prefixes contained within it, including prefix itself if it is present.

The iterator yields canonical owned prefixes in lexicographic order.

use prefix_trie::PrefixSet;

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>(&'a self, prefix: &P) -> CoverKeys<'a, P, ()>

Iterate over all prefixes in the set that cover prefix.

This includes prefix itself if it is present in the set. The iterator yields canonical owned prefixes ordered by prefix length.

use prefix_trie::PrefixSet;

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()?);
set.insert("10.1.1.0/25".parse()?);
set.insert("11.0.0.0/8".parse()?);
assert_eq!(set.cover(&p2).collect::<Vec<_>>(), vec![p0, p1, p2]);

Trait Implementations

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

Available on crate feature rkyv only.

type Archived = ArchivedPrefixSet<P>

The archived representation of this type.

type Resolver = PrefixMapResolver

The resolver for this type. It must contain all the additional information from serializing needed to make the archived type from the normal type.

fn resolve(&self, resolver: Self::Resolver, out: Place<Self::Archived>)

Creates the archived version of this value at the given position and writes it to the given output.

const COPY_OPTIMIZATION: CopyOptimization<Self> = _

An optimization flag that allows the bytes of this type to be copied directly to a writer instead of calling serialize.

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

type P = P

The prefix type.

type View = TrieRef<'a, P, ()>

The concrete view type returned by view.

fn view(self) -> Self::View

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

fn view_at(self, prefix: &Self::P) -> Option<Self::View>

where Self: Sized,

Get a view rooted at prefix, or None if the sub-trie is empty.

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

type P = P

The prefix type.

type View = TrieRefMut<'a, P, ()>

The concrete view type returned by view.

fn view(self) -> Self::View

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

fn view_at(self, prefix: &Self::P) -> Option<Self::View>

where Self: Sized,

Get a view rooted at prefix, or None if the sub-trie is empty.

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

where P: Prefix + Debug,

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

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<'de, P: Prefix + Deserialize<'de>> Deserialize<'de> for PrefixSet<P>

Available on crate feature serde only.

fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>

where D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<P, D> Deserialize<PrefixSet<P>, D> for ArchivedPrefixSet<P>

where P: Prefix, D: Fallible + ?Sized, D::Error: Source,

Available on crate feature rkyv only.

fn deserialize(&self, d: &mut D) -> Result<PrefixSet<P>, D::Error>

Deserializes using the given deserializer

impl<P> Eq for PrefixSet<P>

where P: Prefix,

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<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<'a, P: Prefix> IntoIterator for &'a PrefixSet<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> PartialEq for PrefixSet<P>

where P: Prefix,

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

Equality operator ==.

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

Inequality operator !=.

impl<P: Prefix + Serialize> Serialize for PrefixSet<P>

Available on crate feature serde only.

fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>

where S: Serializer,

Serialize this value into the given Serde serializer.

impl<P, S> Serialize<S> for PrefixSet<P>

where P: Prefix, S: Fallible + Writer + Allocator + ?Sized,

Available on crate feature rkyv only.

fn serialize(&self, s: &mut S) -> Result<PrefixMapResolver, S::Error>

Writes the dependencies for the object and returns a resolver that can create the archived type.