Struct iptrie::RTrieMap

source ·

pub struct RTrieMap<K, V>(_);

Expand description

A map of Ip prefixes based on a radix binary trie

Implementations§

source §

impl<K: IpPrefix, V: Default> RTrieMap<K, V>

source

pub fn new() -> Self

Create a new map.

The root prefix is associated with the default value of V.

source

pub fn with_capacity(capacity: usize) -> Self

Create a new map with a initial capacity.

The root prefix is associated with the default value of V.

source §

impl<K: IpPrefix, V> RTrieMap<K, V>

source

pub fn len(&self) -> NonZeroUsize

Returns the size of the map.

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

Example

use std::net::Ipv4Addr;
let trie = Ipv4RTrieMap::with_root(42);

assert_eq!(trie.len().get(), 1);

source

pub fn with_root(root: V) -> Self

Creates a new trie map with the specified value associated to the root prefix.

source

pub fn with_root_and_capacity(root: V, capacity: usize) -> Self

Creates a new trie map with a initial capacity.

source

pub fn compress(self) -> LCTrieMap<K, V>

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

source

pub fn insert(&mut self, k: K, v: V) -> Option<V>

Inserts a new entry in the map.

If the specified key already exists in the map, then the previous associated value is replaced by the new one and is returned.

Example

use std::net::Ipv4Addr;

let mut trie = RTrieMap::with_root(42);
let addr = Ipv4Addr::new(1,1,1,1);
let ip = Ipv4Prefix::new(addr, 20).unwrap();

assert_eq!( trie.insert(ip, 45), None);
assert_eq!( trie.insert(ip, 50), Some(45));

assert_eq!( trie.insert(Ipv4Prefix::default(), 12), Some(42));

source

pub fn get<Q>(&self, k: &Q) -> Option<&V>where Q: IpPrefix<Addr = K::Addr>, K: 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;
let mut trie = RTrieMap::with_root(42);

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(ip24, 24);
trie.insert(ip20, 20);

assert_eq!( trie.get(&ip24), Some(&24));
assert_eq!( trie.get(&ip22), None);
assert_eq!( trie.get(&ip20), Some(&20));

source

pub fn get_mut<Q>(&mut self, k: &Q) -> Option<&mut V>where Q: IpPrefix<Addr = K::Addr>, K: IpPrefixCovering<Q>,

Gets a mutable access to the value associated with an exact match of the key.

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

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

Example

use std::net::Ipv4Addr;
let mut trie = RTrieMap::with_root(42);

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

trie.insert(ip20, 20);
assert_eq!( trie.get(&ip20), Some(&20));

assert_eq!( trie.get_mut(&ip22), None);
*trie.get_mut(&ip20).unwrap() = 42;
assert_eq!( trie.get(&ip20), Some(&42));

source

pub fn remove<Q>(&mut self, k: &Q) -> Option<V>where Q: IpPrefix<Addr = K::Addr>, K: IpPrefixCovering<Q>,

Removes a previously inserted prefix (exact match).

Panic

Panics if trying to remove the root prefix.

Example

use std::net::Ipv4Addr;
let mut trie = RTrieMap::with_root(42);

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

trie.insert(ip22, 22);
trie.insert(ip20, 20);
assert_eq!( trie.get(&ip22), Some(&22));

trie.remove(&ip22);
assert_eq!( trie.get(&ip22), None);

source

pub fn lookup<Q>(&self, k: &Q) -> (&K, &V)where Q: IpPrefix<Addr = K::Addr>, K: IpPrefixCovering<Q>,

Gets the entry associated with the longest prefix match of the key.

As the top prefix always matches, it never fails.

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

To get a mutable access to a value, use Self::lookup_mut.

Example

use std::net::Ipv4Addr;
let mut trie = RTrieMap::with_root(42);

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, 20);
trie.insert(ip24, 24);

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

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

source

pub fn lookup_mut<Q>(&mut self, k: &Q) -> (&K, &mut V)where Q: IpPrefix<Addr = K::Addr>, K: IpPrefixCovering<Q>,

Gets a mutable access to the value associated with a longest prefix match of the key.

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

Example

let mut trie = RTrieMap::with_root(42);

let ip20 = "1.1.1.1/20".parse::<Ipv4Prefix>().unwrap();
let ip22 = "1.1.1.1/22".parse::<Ipv4Prefix>().unwrap();

trie.insert(ip20, 20);
assert_eq!( trie.get(&ip20), Some(&20));

*trie.lookup_mut(&ip22).1 = 42;
assert_eq!( trie.get(&ip20), Some(&42));