Struct PrefixMap 

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

Prefix map implemented as a TreeBitMap.

Implementations

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

where P: Prefix,

pub fn new() -> Self

Create an empty prefix map.

pub fn len(&self) -> usize

Returns the number of entries stored in the map.

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

pub fn is_empty(&self) -> bool

Returns true if the map contains no entries.

pub fn mem_size(&self) -> usize

Returns the amount of memory used by this datastructure in bytes.

Warning: This number does not include any heap allocations of T!

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

Count the number of unique addresses covered by all prefixes in the map. 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::PrefixMap;

let mut pm: PrefixMap<ipnet::Ipv4Net, u32> = PrefixMap::new();
pm.insert("192.0.2.0/24".parse()?, 1);
pm.insert("192.0.2.128/25".parse()?, 2); // overlaps, counted once
pm.insert("198.51.100.0/24".parse()?, 3);
assert_eq!(pm.address_count(), Some(512));

pm.insert("0.0.0.0/0".parse()?, 1);
assert_eq!(pm.address_count(), None);

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

Get the value stored at exactly prefix.

let mut pm: PrefixMap<ipnet::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<'a>(&'a mut self, prefix: &P) -> Option<&'a mut T>

Get a mutable reference to the value stored at exactly prefix.

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

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

Get the value stored at exactly prefix, together with the canonical matched prefix.

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

let mut pm: PrefixMap<ipnet::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)));

Warning The table does not store the prefix, but it is reconstructed. This means, that any bits in the host part will be truncated:

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

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

Get the longest prefix in the map that contains prefix, together with its value.

let mut pm: PrefixMap<ipnet::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);

Warning The table does not store the prefix, but it is reconstructed. This means, that any bits in the host part will be truncated:

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

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

Get a mutable reference to the value of the longest prefix in the map that contains prefix.

let mut pm: PrefixMap<ipnet::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_mut(&"192.168.1.1/32".parse()?), Some(("192.168.1.0/24".parse()?, &mut 1)));
*pm.get_lpm_mut(&"192.168.1.64/26".parse()?).unwrap().1 += 1;
assert_eq!(pm.get_lpm_mut(&"192.168.1.1/32".parse()?), Some(("192.168.1.0/24".parse()?, &mut 2)));

Warning The table does not store the prefix, but it is reconstructed. This means, that any bits in the host part will be truncated.

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

Get the longest prefix in the map that contains prefix.

let mut pm: PrefixMap<ipnet::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);

Warning The table does not store the prefix, but it is reconstructed. This means, that any bits in the host part will be truncated:

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

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

Check whether prefix is present in the map.

let mut pm: PrefixMap<ipnet::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_spm<'a>(&'a self, prefix: &P) -> Option<(P, &'a T)>

Get the shortest prefix in the map that contains prefix, together with its value.

let mut pm: PrefixMap<ipnet::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_spm(&"192.168.1.1/32".parse()?), Some(("192.168.0.0/23".parse()?, &2)));
assert_eq!(pm.get_spm(&"192.168.1.0/24".parse()?), Some(("192.168.0.0/23".parse()?, &2)));
assert_eq!(pm.get_spm(&"192.168.0.0/23".parse()?), Some(("192.168.0.0/23".parse()?, &2)));
assert_eq!(pm.get_spm(&"192.168.2.0/24".parse()?), None);

Warning The table does not store the prefix, but it is reconstructed. This means, that any bits in the host part will be truncated.

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

Get the shortest prefix in the map that contains prefix.

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

Warning The table does not store the prefix, but it is reconstructed. This means, that any bits in the host part will be truncated.

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

Check whether prefix is covered by the map, i.e., whether the map contains an entry at 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 entries themselves.

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

let mut pm: PrefixMap<ipnet::Ipv4Net, _> = PrefixMap::new();
pm.insert("10.0.0.0/8".parse()?, 1);
assert!(pm.is_covered(&"10.0.0.0/8".parse()?));  // exact member
assert!(pm.is_covered(&"10.1.2.0/24".parse()?)); // covered by 10.0.0.0/8
assert!(!pm.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 map, i.e., whether prefix’s entire range is tiled by entries in the map, even if no single entry covers prefix on its own.

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

let mut pm: PrefixMap<ipnet::Ipv4Net, _> = PrefixMap::new();
pm.insert("10.0.0.0/9".parse()?, 1);
pm.insert("10.128.0.0/9".parse()?, 2);
assert!(!pm.is_covered(&"10.0.0.0/8".parse()?));              // no single covering entry
assert!(pm.is_covered_in_aggregate(&"10.0.0.0/8".parse()?));  // the two /9s tile the /8

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

Warning: You cannot store additional information in the host-part of the prefix. Prefixes are reconstructed from the trie position, so host bits are not preserved.

let mut pm: PrefixMap<ipnet::Ipv4Net, _> = PrefixMap::new();

pm.insert("192.168.0.1/24".parse()?, 1);
assert_eq!(
    pm.get_key_value(&"192.168.0.0/24".parse()?),
    Some(("192.168.0.0/24".parse()?, &1)) // notice that the host part is zero.
);

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

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

Prefixes are not stored verbatim. They are reconstructed from the trie position, so host bits masked out by the prefix length are not preserved. See the documentation of Entry, OccupiedEntry, and VacantEntry.

let mut pm: PrefixMap<ipnet::Ipv4Net, Vec<i32>> = PrefixMap::new();
pm.insert("192.168.0.0/23".parse()?, vec![1]);
pm.entry("192.168.0.1/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 may prune empty trie nodes, reducing the memory footprint.

let mut pm: PrefixMap<ipnet::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, this operation only removes the stored value and may leave empty trie nodes in place.

let mut pm: PrefixMap<ipnet::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);

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. Like Self::remove, this prunes trie nodes that become empty.

let mut pm: PrefixMap<ipnet::Ipv4Net, _> = PrefixMap::new();
pm.insert("192.168.0.0/21".parse()?, 1);
pm.insert("192.168.0.0/22".parse()?, 2);
pm.insert("192.168.0.0/23".parse()?, 3);
pm.insert("192.168.0.0/24".parse()?, 4);
pm.insert("192.168.4.0/22".parse()?, 5);
pm.insert("192.168.4.0/23".parse()?, 6);

assert_eq!(pm.len(), 6);
pm.remove_children(&"192.168.0.0/22".parse()?);
assert_eq!(pm.len(), 3);

assert_eq!(pm.get(&"192.168.0.0/22".parse()?), None);
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.4.0/22".parse()?), Some(&5));
assert_eq!(pm.get(&"192.168.4.0/23".parse()?), Some(&6));

pub fn clear(&mut self)

Clear the map but keep the allocated memory.

let mut pm: PrefixMap<ipnet::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<ipnet::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));

You can also use the prefix for filtering

let mut pm: PrefixMap<ipnet::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(|p, _| p.prefix_len() > 24);
assert_eq!(pm.get(&"192.168.0.0/24".parse()?), None);
assert_eq!(pm.get(&"192.168.1.0/24".parse()?), None);
assert_eq!(pm.get(&"192.168.2.0/24".parse()?), None);
assert_eq!(pm.get(&"192.168.2.0/25".parse()?), Some(&4));

pub fn aggregate_consistent(&mut self)

where T: Clone + Eq,

Removes every entry whose nearest covering ancestor (a less specific prefix) maps to the same value, without merging adjacent prefixes.

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

use prefix_trie::PrefixMap;

let mut pm: PrefixMap<ipnet::Ipv4Net, u32> = PrefixMap::new();
pm.insert("10.0.0.0/16".parse()?, 1);
pm.insert("10.0.0.0/24".parse()?, 2);    // exception under 10.0.0.0/16
pm.insert("10.0.1.0/24".parse()?, 2);    // sibling of the above, same value
pm.insert("10.0.2.0/24".parse()?, 1);    // same value as 10.0.0.0/16 -> redundant
pm.insert("192.168.0.0/16".parse()?, 1); // a separate branch, same value
pm.aggregate_consistent();
// Only the redundant 10.0.2.0/24 is dropped; nothing is merged.
assert_eq!(pm.iter().collect::<Vec<_>>(), vec![
    ("10.0.0.0/16".parse()?, &1),
    ("10.0.0.0/24".parse()?, &2),
    ("10.0.1.0/24".parse()?, &2),
    ("192.168.0.0/16".parse()?, &1),
]);

pub fn aggregate(&mut self)

where T: Clone + Ord,

Reduce the map to the fewest entries that keep every lookup unchanged.

For any address a (a host prefix, i.e. one of maximum length), self.get_lpm(&a) resolves to the same value as before (only the matched prefix may differ). Holes remain uncovered. Among all maps with that property this keeps the fewest entries. For prefixes, this may not be the case; When two siblings with the same value get merged, the the parent prefix holds a value after aggregation.

The guarantee is per address, not per prefix: entries may be merged or moved. Use aggregate_consistent instead to keep every prefix matching the same entry.

use prefix_trie::PrefixMap;

let mut pm: PrefixMap<ipnet::Ipv4Net, u32> = PrefixMap::new();
pm.insert("10.0.0.0/16".parse()?, 1);
pm.insert("10.0.0.0/24".parse()?, 2);
pm.insert("10.0.1.0/24".parse()?, 2);
pm.insert("10.0.2.0/24".parse()?, 1);
pm.insert("192.168.0.0/16".parse()?, 1);
pm.aggregate();
// The siblings merge into a /23 and the redundant /24 is dropped, but the two /16 branches
// cannot merge across the uncovered space between them.
assert_eq!(pm.iter().collect::<Vec<_>>(), vec![
    ("10.0.0.0/16".parse()?, &1),
    ("10.0.0.0/23".parse()?, &2),
    ("192.168.0.0/16".parse()?, &1),
]);

pub fn aggregate_fill<F>(&mut self, default: F)

where T: Clone + Ord, F: Fn() -> T + Copy,

Reduce the map to the fewest entries, inserting otherwise-uncovered addresses to default.

For any address a (a host prefix, i.e. one of maximum length), self.get_lpm(&a) under .unwrap_or_else(default) remains unchanged: covered addresses keep their value, and uncovered addresses now resolve to default(). Among all maps with that property this keeps the fewest entries.

Because no address is left uncovered, the result is always total: the root of the tree (e.g., 0.0.0.0/0) will contain a value, so get_lpm always returns Some.

The guarantee is per address, not per prefix: entries may be merged or moved. Use aggregate_consistent instead to keep every prefix matching the same entry.

use prefix_trie::PrefixMap;

let mut pm: PrefixMap<ipnet::Ipv4Net, u32> = PrefixMap::new();
pm.insert("10.0.0.0/16".parse()?, 1);
pm.insert("10.0.0.0/24".parse()?, 2);
pm.insert("10.0.1.0/24".parse()?, 2);
pm.insert("10.0.2.0/24".parse()?, 1);
pm.insert("192.168.0.0/16".parse()?, 1);
pm.aggregate_fill(|| 1);
// Filling the gaps with 1 lets both /16 branches and all uncovered space collapse into one
// default route; only the 10.0.0.0/23 = 2 exception survives.
assert_eq!(pm.iter().collect::<Vec<_>>(), vec![
    ("0.0.0.0/0".parse()?, &1),
    ("10.0.0.0/23".parse()?, &2),
]);

pub fn aggregate_fill_default(&mut self)

where T: Clone + Ord + Default,

aggregate_fill with T::default as the fill value.

pub fn cover<'a>(&'a self, prefix: &P) -> Cover<'a, P, T>

Iterate over all entries in the map that cover prefix, including prefix itself if it is present. The returned iterator yields (P, &'a T), with reconstructed prefixes P.

The iterator will always yield elements ordered by their prefix length, i.e., their depth in the tree.

let mut pm: PrefixMap<ipnet::Ipv4Net, _> = PrefixMap::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()?;
pm.insert(p0, 0);
pm.insert(p1, 1);
pm.insert(p2, 2);
pm.insert("10.1.2.0/24".parse()?, 3); // disjoint prefixes are not covered
pm.insert("10.1.1.0/25".parse()?, 4); // more specific prefixes are not covered
pm.insert("11.0.0.0/8".parse()?, 5);  // Branch points that don't contain values are skipped
assert_eq!(
    pm.cover(&p2).collect::<Vec<_>>(),
    vec![(p0, &0), (p1, &1), (p2, &2)]
);

This function also yields the root node if it is part of the map:

let mut pm: PrefixMap<ipnet::Ipv4Net, _> = PrefixMap::new();
let root = "0.0.0.0/0".parse()?;
pm.insert(root, 0);
assert_eq!(pm.cover(&"10.0.0.0/8".parse()?).collect::<Vec<_>>(), vec![(root, &0)]);

pub fn cover_keys<'a>(&'a self, prefix: &P) -> CoverKeys<'a, P, T>

Iterate over all prefixes in the map that cover prefix, including prefix itself if it is present. The returned iterator yields reconstructed prefixes P.

The iterator will always yield elements ordered by their prefix length, i.e., their depth in the tree.

let mut pm: PrefixMap<ipnet::Ipv4Net, _> = PrefixMap::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()?;
pm.insert(p0, 0);
pm.insert(p1, 1);
pm.insert(p2, 2);
pm.insert("10.1.2.0/24".parse()?, 3); // disjoint prefixes are not covered
pm.insert("10.1.1.0/25".parse()?, 4); // more specific prefixes are not covered
pm.insert("11.0.0.0/8".parse()?, 5);  // Branch points that don't contain values are skipped
assert_eq!(pm.cover_keys(&p2).collect::<Vec<_>>(), vec![p0, p1, p2]);

pub fn cover_values<'a>(&'a self, prefix: &P) -> CoverValues<'a, P, T>

Iterate over the values of all prefixes in the map that cover prefix, including prefix itself if it is present. The returned iterator yields &'a T.

The iterator will always yield elements ordered by their prefix length, i.e., their depth in the tree.

let mut pm: PrefixMap<ipnet::Ipv4Net, _> = PrefixMap::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()?;
pm.insert(p0, 0);
pm.insert(p1, 1);
pm.insert(p2, 2);
pm.insert("10.1.2.0/24".parse()?, 3); // disjoint prefixes are not covered
pm.insert("10.1.1.0/25".parse()?, 4); // more specific prefixes are not covered
pm.insert("11.0.0.0/8".parse()?, 5);  // Branch points that don't contain values are skipped
assert_eq!(pm.cover_values(&p2).collect::<Vec<_>>(), vec![&0, &1, &2]);

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

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

let mut pm: PrefixMap<ipnet::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 lexicographic.

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

Iterate over all entries 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 the entry at prefix (if present).
• If inclusive is false, the iterator starts after prefix. Entries more specific than prefix (its children) are still yielded.

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

let mut pm: PrefixMap<ipnet::Ipv4Net, _> = PrefixMap::new();
pm.insert("10.0.0.0/8".parse()?, 1);
pm.insert("10.1.0.0/16".parse()?, 2);
pm.insert("10.2.0.0/16".parse()?, 3);
pm.insert("10.2.0.0/24".parse()?, 4);
pm.insert("10.3.0.0/16".parse()?, 5);
pm.insert("10.4.0.0/16".parse()?, 6);

// Inclusive: start at 10.2.0.0/16 and take the next 2 entries
let page: Vec<_> = pm.iter_from(&"10.2.0.0/16".parse()?, true).take(3).collect();
assert_eq!(page, vec![
    ("10.2.0.0/16".parse()?, &3),
    ("10.2.0.0/24".parse()?, &4),
    ("10.3.0.0/16".parse()?, &5),
]);

// Exclusive: cursor pagination — skip last seen, fetch next page
let last_seen: ipnet::Ipv4Net = "10.2.0.0/16".parse()?;
let next_page: Vec<_> = pm.iter_from(&last_seen, false).take(3).collect();
assert_eq!(next_page, vec![
    ("10.2.0.0/24".parse()?, &4),
    ("10.3.0.0/16".parse()?, &5),
    ("10.4.0.0/16".parse()?, &6)
]);

pub fn iter_from_mut<'a>( &'a mut self, prefix: &P, inclusive: bool, ) -> IterMut<'a, P, T>

Return a mutable iterator starting at the given prefix in lexicographic order.

If inclusive is true, the iterator includes the entry at prefix (if present). If inclusive is false, the iterator starts after prefix.

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

let mut pm: PrefixMap<ipnet::Ipv4Net, _> = PrefixMap::new();
pm.insert("10.0.0.0/8".parse()?, 1);
pm.insert("10.1.0.0/16".parse()?, 2);
pm.insert("10.2.0.0/16".parse()?, 3);

// Mutate all entries starting from 10.1.0.0/16 (inclusive)
pm.iter_from_mut(&"10.1.0.0/16".parse()?, true).for_each(|(_, v)| *v *= 10);
assert_eq!(pm.get(&"10.0.0.0/8".parse()?), Some(&1));
assert_eq!(pm.get(&"10.1.0.0/16".parse()?), Some(&20));
assert_eq!(pm.get(&"10.2.0.0/16".parse()?), Some(&30));

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

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

let mut pm: PrefixMap<ipnet::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 reconstructed prefixes P.

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

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

let mut pm: PrefixMap<ipnet::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 T.

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

Get a mutable iterator over all values. The order of this iterator is lexicographic.

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

where P: Prefix,

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

Iterate over prefix and all more-specific entries contained within it, including prefix itself if it is present. The iterator yields (P, &'a T), with reconstructed prefixes P, in lexicographic order.

Note: Consider using crate::AsView::view_at as an alternative.

let mut pm: PrefixMap<ipnet::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 children_mut<'a>(&'a mut self, prefix: &P) -> IterMut<'a, P, T>

Iterate with mutable references over prefix and all more-specific entries contained within it, including prefix itself if it is present. The iterator yields (P, &'a mut T), with reconstructed prefixes P, in lexicographic order.

Note: Consider using crate::AsView::view_at on a mutable map reference as an alternative.

let mut pm: PrefixMap<ipnet::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.children_mut(&"192.168.0.0/23".parse()?).for_each(|(_, x)| *x *= 10);
assert_eq!(
    pm.into_iter().collect::<Vec<_>>(),
    vec![
        ("192.168.0.0/22".parse()?, 1),
        ("192.168.0.0/23".parse()?, 20),
        ("192.168.0.0/24".parse()?, 30),
        ("192.168.2.0/23".parse()?, 4),
        ("192.168.2.0/24".parse()?, 5),
    ]
);

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

Consume the map and iterate over prefix and all more-specific entries contained within it, including prefix itself if it is present. This returns an iterator over the owned entries.

let mut pm: PrefixMap<ipnet::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),
    ]
);

Trait Implementations

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

Available on crate feature rkyv only.

type Archived = ArchivedPrefixMap<P, T>

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, T> AsView<'a> for &'a PrefixMap<P, T>

type P = P

The prefix type.

type View = TrieRef<'a, P, T>

The concrete view type returned by view.

fn view(self) -> TrieRef<'a, P, T>

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, T> AsView<'a> for &'a mut PrefixMap<P, T>

type P = P

The prefix type.

type View = TrieRefMut<'a, P, T>

The concrete view type returned by view.

fn view(self) -> TrieRefMut<'a, P, T>

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, T: Clone> Clone for PrefixMap<P, T>

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

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<P: Prefix + 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>

fn default() -> Self

Returns the “default value” for a type.

impl<'de, P: Prefix + Deserialize<'de>, T: Deserialize<'de>> Deserialize<'de> for PrefixMap<P, T>

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, T, D> Deserialize<PrefixMap<P, T>, D> for ArchivedPrefixMap<P, T>

where P: Prefix, T: Archive, T::Archived: Deserialize<T, D>, D: Fallible + ?Sized, D::Error: Source,

Available on crate feature rkyv only.

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

Deserializes using the given deserializer

impl<P: Prefix + Eq, T: Eq> Eq for PrefixMap<P, T>

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

type Item = (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 + PartialEq, T: PartialEq> PartialEq for PrefixMap<P, T>

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

Equality operator ==.

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

Inequality operator !=.

impl<P: Prefix + Serialize, T: Serialize> Serialize for PrefixMap<P, T>

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, T, S> Serialize<S> for PrefixMap<P, T>

where P: Prefix, T: Serialize<S>, 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.