Struct prefix_trie::map::PrefixMap

pub struct PrefixMap<P, T> { /* private fields */ }

Prefix map implemented as a prefix tree.

Implementations

impl<P, T> PrefixMap<P, T>

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

An iterator visiting all key-value pairs in lexicographic order. The iterator element type is (&P, &T).

let mut pm: PrefixMap<Ipv4Net, _> = PrefixMap::new();
pm.insert("192.168.0.0/22".parse()?, 1);
pm.insert("192.168.0.0/23".parse()?, 2);
pm.insert("192.168.2.0/23".parse()?, 3);
pm.insert("192.168.0.0/24".parse()?, 4);
pm.insert("192.168.2.0/24".parse()?, 5);
assert_eq!(
    pm.iter().collect::<Vec<_>>(),
    vec![
        (&"192.168.0.0/22".parse()?, &1),
        (&"192.168.0.0/23".parse()?, &2),
        (&"192.168.0.0/24".parse()?, &4),
        (&"192.168.2.0/23".parse()?, &3),
        (&"192.168.2.0/24".parse()?, &5),
    ]
);

pub fn iter_mut(&mut self) -> IterMut<'_, P, T>

Get a mutable iterator over all key-value pairs. The order of this iterator is arbitrary (and not in lexicographic order).

pub fn keys(&self) -> Keys<'_, P, T>

An iterator visiting all keys in lexicographic order. The iterator element type is &P.

let mut pm: PrefixMap<Ipv4Net, _> = PrefixMap::new();
pm.insert("192.168.0.0/22".parse()?, 1);
pm.insert("192.168.0.0/23".parse()?, 2);
pm.insert("192.168.2.0/23".parse()?, 3);
pm.insert("192.168.0.0/24".parse()?, 4);
pm.insert("192.168.2.0/24".parse()?, 5);
assert_eq!(
    pm.keys().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 into_keys(self) -> IntoKeys<P, T>

Creates a consuming iterator visiting all keys in lexicographic order. The iterator element type is P.

pub fn values(&self) -> Values<'_, P, T>

An iterator visiting all values in lexicographic order. The iterator element type is &P.

let mut pm: PrefixMap<Ipv4Net, _> = PrefixMap::new();
pm.insert("192.168.0.0/22".parse()?, 1);
pm.insert("192.168.0.0/23".parse()?, 2);
pm.insert("192.168.2.0/23".parse()?, 3);
pm.insert("192.168.0.0/24".parse()?, 4);
pm.insert("192.168.2.0/24".parse()?, 5);
assert_eq!(pm.values().collect::<Vec<_>>(), vec![&1, &2, &4, &3, &5]);

pub fn into_values(self) -> IntoValues<P, T>

Creates a consuming iterator visiting all values in lexicographic order. The iterator element type is P.

pub fn values_mut(&mut self) -> ValuesMut<'_, P, T>

Get a mutable iterator over all values. The order of this iterator is arbitrary (and not in lexicographic order).

impl<P, T> PrefixMap<P, T>where
    P: Prefix,

pub fn children(&self, prefix: &P) -> Iter<'_, P, T>

Get an iterator over the node itself and all children with a value. All elements returned have a prefix that is contained within prefix itself (or are the same).

let mut pm: PrefixMap<Ipv4Net, _> = PrefixMap::new();
pm.insert("192.168.0.0/22".parse()?, 1);
pm.insert("192.168.0.0/23".parse()?, 2);
pm.insert("192.168.2.0/23".parse()?, 3);
pm.insert("192.168.0.0/24".parse()?, 4);
pm.insert("192.168.2.0/24".parse()?, 5);
assert_eq!(
    pm.children(&"192.168.0.0/23".parse()?).collect::<Vec<_>>(),
    vec![
        (&"192.168.0.0/23".parse()?, &2),
        (&"192.168.0.0/24".parse()?, &4),
    ]
);

pub fn into_children(self, prefix: &P) -> IntoIter<P, T>

Get an iterator over the node itself and all children with a value. All elements returned have a prefix that is contained within prefix itself (or are the same). This function will consume self, returning an iterator over all owned children.

let mut pm: PrefixMap<Ipv4Net, _> = PrefixMap::new();
pm.insert("192.168.0.0/22".parse()?, 1);
pm.insert("192.168.0.0/23".parse()?, 2);
pm.insert("192.168.2.0/23".parse()?, 3);
pm.insert("192.168.0.0/24".parse()?, 4);
pm.insert("192.168.2.0/24".parse()?, 5);
assert_eq!(
    pm.into_children(&"192.168.0.0/23".parse()?).collect::<Vec<_>>(),
    vec![
        ("192.168.0.0/23".parse()?, 2),
        ("192.168.0.0/24".parse()?, 4),
    ]
);

impl<P, T> PrefixMap<P, T>where
    P: Prefix,

pub fn new() -> Self

Create an empty prefix map.

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

Get the value of an element by matching exactly on the prefix.

let mut pm: PrefixMap<Ipv4Net, _> = PrefixMap::new();
pm.insert("192.168.1.0/24".parse()?, 1);
assert_eq!(pm.get(&"192.168.1.0/24".parse()?), Some(&1));
assert_eq!(pm.get(&"192.168.2.0/24".parse()?), None);
assert_eq!(pm.get(&"192.168.0.0/23".parse()?), None);
assert_eq!(pm.get(&"192.168.1.128/25".parse()?), None);

pub fn get_mut(&mut self, prefix: &P) -> Option<&mut T>

Get a mutable reference to a value of an element by matching exactly on the prefix.

let mut pm: PrefixMap<Ipv4Net, _> = PrefixMap::new();
let prefix = "192.168.1.0/24".parse()?;
pm.insert(prefix, 1);
assert_eq!(pm.get(&prefix), Some(&1));
*pm.get_mut(&prefix).unwrap() += 1;
assert_eq!(pm.get(&prefix), Some(&2));

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

Get the value of an element by matching exactly on the prefix.

let mut pm: PrefixMap<Ipv4Net, _> = PrefixMap::new();
let prefix = "192.168.1.0/24".parse()?;
pm.insert(prefix, 1);
assert_eq!(pm.get_key_value(&prefix), Some((&prefix, &1)));

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

Get a value of an element by using longest prefix matching

let mut pm: PrefixMap<Ipv4Net, _> = PrefixMap::new();
pm.insert("192.168.1.0/24".parse()?, 1);
pm.insert("192.168.0.0/23".parse()?, 2);
assert_eq!(pm.get_lpm(&"192.168.1.1/32".parse()?), Some((&"192.168.1.0/24".parse()?, &1)));
assert_eq!(pm.get_lpm(&"192.168.1.0/24".parse()?), Some((&"192.168.1.0/24".parse()?, &1)));
assert_eq!(pm.get_lpm(&"192.168.0.0/24".parse()?), Some((&"192.168.0.0/23".parse()?, &2)));
assert_eq!(pm.get_lpm(&"192.168.2.0/24".parse()?), None);

pub fn get_lpm_mut(&mut self, prefix: &P) -> Option<(&P, &mut T)>

Get a mutable reference to a value of an element by using longest prefix matching

let mut pm: PrefixMap<Ipv4Net, _> = PrefixMap::new();
pm.insert("192.168.1.0/24".parse()?, 1);
pm.insert("192.168.0.0/23".parse()?, 2);
assert_eq!(pm.get_lpm(&"192.168.1.1/32".parse()?), Some((&"192.168.1.0/24".parse()?, &1)));
*pm.get_lpm_mut(&"192.168.1.64/26".parse()?).unwrap().1 += 1;
assert_eq!(pm.get_lpm(&"192.168.1.1/32".parse()?), Some((&"192.168.1.0/24".parse()?, &2)));

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

Check if a key is present in the datastructure.

let mut pm: PrefixMap<Ipv4Net, _> = PrefixMap::new();
pm.insert("192.168.1.0/24".parse()?, 1);
assert!(pm.contains_key(&"192.168.1.0/24".parse()?));
assert!(!pm.contains_key(&"192.168.2.0/24".parse()?));
assert!(!pm.contains_key(&"192.168.0.0/23".parse()?));
assert!(!pm.contains_key(&"192.168.1.128/25".parse()?));

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

Get the longest prefix in the datastructure that matches the given prefix.

let mut pm: PrefixMap<Ipv4Net, _> = PrefixMap::new();
pm.insert("192.168.1.0/24".parse()?, 1);
pm.insert("192.168.0.0/23".parse()?, 2);
assert_eq!(pm.get_lpm_prefix(&"192.168.1.1/32".parse()?), Some(&"192.168.1.0/24".parse()?));
assert_eq!(pm.get_lpm_prefix(&"192.168.1.0/24".parse()?), Some(&"192.168.1.0/24".parse()?));
assert_eq!(pm.get_lpm_prefix(&"192.168.0.0/24".parse()?), Some(&"192.168.0.0/23".parse()?));
assert_eq!(pm.get_lpm_prefix(&"192.168.2.0/24".parse()?), None);

pub fn insert(&mut self, prefix: P, value: T) -> Option<T>

Insert a new item into the prefix-map. This function may return any value that existed before.

let mut pm: PrefixMap<Ipv4Net, _> = PrefixMap::new();
assert_eq!(pm.insert("192.168.0.0/23".parse()?, 1), None);
assert_eq!(pm.insert("192.168.1.0/24".parse()?, 2), None);
assert_eq!(pm.insert("192.168.1.0/24".parse()?, 3), Some(2));

pub fn entry(&mut self, prefix: P) -> Entry<'_, P, T>

Gets the given key’s corresponding entry in the map for in-place manipulation.

let mut pm: PrefixMap<Ipv4Net, _> = PrefixMap::new();
pm.insert("192.168.0.0/23".parse()?, vec![1]);
pm.entry("192.168.0.0/23".parse()?).or_default().push(2);
pm.entry("192.168.0.0/24".parse()?).or_default().push(3);
assert_eq!(pm.get(&"192.168.0.0/23".parse()?), Some(&vec![1, 2]));
assert_eq!(pm.get(&"192.168.0.0/24".parse()?), Some(&vec![3]));

pub fn remove(&mut self, prefix: &P) -> Option<T>

Removes a key from the map, returning the value at the key if the key was previously in the map. In contrast to Self::remove_keep_tree, this operation will modify the tree structure. As a result, this operation takes longer than remove_keep_tree, as does inserting the same element again. However, future reads may be faster as less nodes need to be traversed. Further, it reduces the memory footprint to its minimum.

let mut pm: PrefixMap<Ipv4Net, _> = PrefixMap::new();
let prefix = "192.168.1.0/24".parse()?;
pm.insert(prefix, 1);
assert_eq!(pm.get(&prefix), Some(&1));
assert_eq!(pm.remove(&prefix), Some(1));
assert_eq!(pm.get(&prefix), None);

pub fn remove_keep_tree(&mut self, prefix: &P) -> Option<T>

Removes a key from the map, returning the value at the key if the key was previously in the map. 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 pm: PrefixMap<Ipv4Net, _> = PrefixMap::new();
let prefix = "192.168.1.0/24".parse()?;
pm.insert(prefix, 1);
assert_eq!(pm.get(&prefix), Some(&1));
assert_eq!(pm.remove_keep_tree(&prefix), Some(1));
assert_eq!(pm.get(&prefix), None);

// future inserts of the same key are now faster!
pm.insert(prefix, 1);

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

Remove all entries 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 pm: PrefixMap<Ipv4Net, _> = PrefixMap::new();
pm.insert("192.168.0.0/22".parse()?, 1);
pm.insert("192.168.0.0/23".parse()?, 2);
pm.insert("192.168.0.0/24".parse()?, 3);
pm.insert("192.168.2.0/23".parse()?, 4);
pm.insert("192.168.2.0/24".parse()?, 5);
pm.remove_children(&"192.168.0.0/23".parse()?);
assert_eq!(pm.get(&"192.168.0.0/23".parse()?), None);
assert_eq!(pm.get(&"192.168.0.0/24".parse()?), None);
assert_eq!(pm.get(&"192.168.2.0/23".parse()?), Some(&4));
assert_eq!(pm.get(&"192.168.2.0/24".parse()?), Some(&5));

pub fn clear(&mut self)

Clear the map but keep the allocated memory.

let mut pm: PrefixMap<Ipv4Net, _> = PrefixMap::new();
pm.insert("192.168.0.0/24".parse()?, 1);
pm.insert("192.168.1.0/24".parse()?, 2);
pm.clear();
assert_eq!(pm.get(&"192.168.0.0/24".parse()?), None);
assert_eq!(pm.get(&"192.168.1.0/24".parse()?), None);

pub fn retain<F>(&mut self, f: F)where
    F: FnMut(&P, &T) -> bool,

Keep only the elements in the map that satisfy the given condition f.

let mut pm: PrefixMap<Ipv4Net, _> = PrefixMap::new();
pm.insert("192.168.0.0/24".parse()?, 1);
pm.insert("192.168.1.0/24".parse()?, 2);
pm.insert("192.168.2.0/24".parse()?, 3);
pm.insert("192.168.2.0/25".parse()?, 4);
pm.retain(|_, t| *t % 2 == 0);
assert_eq!(pm.get(&"192.168.0.0/24".parse()?), None);
assert_eq!(pm.get(&"192.168.1.0/24".parse()?), Some(&2));
assert_eq!(pm.get(&"192.168.2.0/24".parse()?), None);
assert_eq!(pm.get(&"192.168.2.0/25".parse()?), Some(&4));

Trait Implementations

impl<P: Clone, T: Clone> Clone for PrefixMap<P, T>

fn clone(&self) -> PrefixMap<P, T>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<P: Debug, T: Debug> Debug for PrefixMap<P, T>

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

Formats the value using the given formatter.

impl<P, T> Default for PrefixMap<P, T>where
    P: Prefix,

fn default() -> Self

Returns the “default value” for a type.

impl<P, T> FromIterator<(P, T)> for PrefixMap<P, T>where
    P: Prefix,

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

Creates a value from an iterator.

impl<'a, P, T> IntoIterator for &'a PrefixMap<P, T>

type Item = (&'a P, &'a T)

The type of the elements being iterated over.

type IntoIter = Iter<'a, P, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<P: Prefix, T> IntoIterator for PrefixMap<P, T>

type Item = (P, T)

The type of the elements being iterated over.

type IntoIter = IntoIter<P, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<P, T> PartialEq<PrefixMap<P, T>> for PrefixMap<P, T>where
    P: Prefix + PartialEq,
    T: 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, T> Eq for PrefixMap<P, T>where
    P: Prefix + Eq,
    T: Eq,