Struct RTrieSet

pub struct RTrieSet<P: IpPrefix>(/* private fields */);

A set of Ip prefixes based on a radix binary trie

Implementations

impl<P: IpRootPrefix> RTrieSet<P>

pub fn new() -> Self

Creates a new set which contains the root prefix.

pub fn with_capacity(capacity: usize) -> Self

Creates a new set with an initial capacity.

The returned set already contains the root prefix.

impl<P: IpPrefix> RTrieSet<P>

pub fn len(&self) -> NonZeroUsize

Returns the size of the set.

Notice that it never equals zero since the top prefix is always present in the set.

pub fn compress(self) -> LCTrieSet<P>

Compress this Patricia trie in a LC-Trie.

For lookup algorithms, a Patricia trie performs unit bit checking and LC-Trie performs multi bits checking. So the last one is more performant but it cannot be modified (no insertion or removal operations are provided).

pub fn shrink_to_fit(&mut self)

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

Inserts a new element in the set.

If the specified element already exists in the set, false is returned.

Example

use std::net::Ipv4Addr;

let addr = Ipv4Addr::new(1,1,1,1);
let mut trie = Ipv4RTrieSet::new();

let ip20 = Ipv4Prefix::new(addr, 20).unwrap();
let ip22 = Ipv4Prefix::new(addr, 22).unwrap();

assert_eq!( trie.insert(ip20), true);
assert_eq!( trie.insert(ip22), true);
assert_eq!( trie.insert(ip20), false);

pub fn contains<Q>(&self, k: &Q) -> bool

where Q: IpPrefix<Addr = P::Addr>, P: IpPrefixCovering<Q>,

Checks if an element is present (exact match).

Example

use std::net::Ipv4Addr;

let addr = Ipv4Addr::new(1,1,1,1);

let ip20 = Ipv4Prefix::new(addr, 20).unwrap();
let ip22 = Ipv4Prefix::new(addr, 22).unwrap();
let ip24 = Ipv4Prefix::new(addr, 24).unwrap();

let trie = Ipv4RTrieSet::from_iter([ip20,ip24]);

assert_eq!( trie.contains(&ip20), true);
assert_eq!( trie.contains(&ip22), false);
assert_eq!( trie.contains(&ip24), true);

pub fn remove<Q>(&mut self, k: &Q) -> bool

where Q: IpPrefix<Addr = P::Addr>, P: IpPrefixCovering<Q>,

Removes a previously inserted prefix (exact match).

Returns false is the element was not present in the set and true if the removal is effective.

Example

use std::net::Ipv4Addr;

let addr = Ipv4Addr::new(1,1,1,1);

let ip20 = Ipv4Prefix::new(addr, 20).unwrap();
let ip22 = Ipv4Prefix::new(addr, 22).unwrap();

let mut trie = Ipv4RTrieSet::from_iter([ip20,ip22]);

assert_eq!( trie.contains(&ip20), true);
assert_eq!(trie.remove(&ip20), true);
assert_eq!(trie.remove(&ip20), false);

assert_eq!( trie.contains(&ip22), true);
assert_eq!( trie.contains(&ip20), false);

pub fn replace(&mut self, k: P) -> Option<P>

Adds a prefix to the set, replacing the existing one, if any (exact match performed). Returns the replaced value.

Example

use std::net::Ipv4Addr;
use ipnet::Ipv4Net;
let mut trie = RTrieSet::new();

let addr1 = Ipv4Addr::new(1,1,1,1);
let addr2 = Ipv4Addr::new(1,1,1,2);
let ip20 = Ipv4Net::new(addr1, 20).unwrap();
let ip20b = Ipv4Net::new(addr2, 20).unwrap();

trie.insert(ip20);
assert_eq!(trie.get(&ip20).unwrap().to_string(), "1.1.1.1/20".to_string());

assert_eq!(trie.insert(ip20b), false);
assert_eq!(trie.get(&ip20).unwrap().to_string(), "1.1.1.1/20".to_string());

assert_eq!(trie.replace(ip20b), Some(ip20));
assert_eq!(trie.get(&ip20).unwrap().to_string(), "1.1.1.2/20".to_string());

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

where Q: IpPrefix<Addr = P::Addr>, P: IpPrefixCovering<Q>,

Gets the value associated with an exact match of the key.

To access to the longest prefix match, use Self::lookup.

To get a mutable access to a value, use [Self::get_mut].

Example

use std::net::Ipv4Addr;
use ipnet::Ipv4Net;
let mut trie = RTrieSet::new();

let addr1 = Ipv4Addr::new(1,1,1,1);
let addr2 = Ipv4Addr::new(1,1,1,2);
let ip20 = Ipv4Net::new(addr1, 20).unwrap();
let ip20b = Ipv4Net::new(addr2, 20).unwrap();

trie.insert(ip20);
assert_eq!(trie.get(&ip20).unwrap().to_string(), "1.1.1.1/20".to_string());

trie.insert(ip20b);
assert_eq!(trie.get(&ip20).unwrap().to_string(), "1.1.1.1/20".to_string());

pub fn lookup<Q>(&self, k: &Q) -> &P

where Q: IpPrefix<Addr = P::Addr>, P: IpPrefixCovering<Q>,

Gets the longest prefix which matches the given key.

As the top prefix always matches, it never fails.

To access to the exact prefix match, use Self::get.

Example

use std::net::Ipv4Addr;
let mut trie = Ipv4RTrieSet::new();

let addr = Ipv4Addr::new(1,1,1,1);
let ip20 = Ipv4Prefix::new(addr, 20).unwrap();
let ip22 = Ipv4Prefix::new(addr, 22).unwrap();
let ip24 = Ipv4Prefix::new(addr, 24).unwrap();

trie.insert(ip20);
trie.insert(ip24);

assert_eq!( trie.lookup(&ip20), &ip20);
assert_eq!( trie.lookup(&ip22), &ip20);
assert_eq!( trie.lookup(&ip24), &ip24);

assert_eq!( trie.lookup(&addr), &ip24);

pub fn iter(&self) -> impl Iterator<Item = &P> + '_

Iterates over all the prefixes of this set.

pub fn info(&self)

Trait Implementations

impl<P: Clone + IpPrefix> Clone for RTrieSet<P>

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<P: IpRootPrefix> Default for RTrieSet<P>

fn default() -> Self

Returns the “default value” for a type.

impl<P: IpPrefix> Extend<P> for RTrieSet<P>

fn extend<I: IntoIterator<Item = P>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<P: IpRootPrefix> FromIterator<P> for RTrieSet<P>

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

Creates a value from an iterator.