/rust/registry/src/index.crates.io-1949cf8c6b5b557f/prefix-trie-0.6.0/src/map/iter.rs

Source
//! Module that contains the implementation for the iterators

use map::Table;

use crate::*;

use super::Node;

/// An iterator over all entries of a [`PrefixMap`] in lexicographic order.
#[derive(Clone)]
pub struct Iter<'a, P, T> {
    table: Option<&'a Table<P, T>>,
    nodes: Vec<usize>,
}

impl<P, T> Default for Iter<'_, P, T> {
    fn default() -> Self {
        Self {
            table: None,
            nodes: Vec::new(),
        }
    }
}

impl<'a, P, T> Iter<'a, P, T> {
    pub(crate) fn new(table: &'a Table<P, T>, nodes: Vec<usize>) -> Self {
        Self {
            table: Some(table),
            nodes,
        }
    }
}

impl<'a, P, T> Iterator for Iter<'a, P, T> {
    type Item = (&'a P, &'a T);

    fn next(&mut self) -> Option<(&'a P, &'a T)> {
        while let Some(cur) = self.nodes.pop() {
            let node = &self.table.as_ref()?[cur];
            if let Some(right) = node.right {
                self.nodes.push(right);
            }
            if let Some(left) = node.left {
                self.nodes.push(left);
            }
            if let Some(v) = &node.value {
                return Some((&node.prefix, v));
            }
        }
        None
    }
}

/// An iterator over all prefixes of a [`PrefixMap`] in lexicographic order.
#[derive(Clone, Default)]
pub struct Keys<'a, P, T> {
    pub(crate) inner: Iter<'a, P, T>,
}

impl<'a, P, T> Iterator for Keys<'a, P, T> {
    type Item = &'a P;

    fn next(&mut self) -> Option<&'a P> {
        self.inner.next().map(|(k, _)| k)
    }
}

/// An iterator over all values of a [`PrefixMap`] in lexicographic order of their associated
/// prefixes.
#[derive(Clone, Default)]
pub struct Values<'a, P, T> {
    pub(crate) inner: Iter<'a, P, T>,
}

impl<'a, P, T> Iterator for Values<'a, P, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<&'a T> {
        self.inner.next().map(|(_, v)| v)
    }
}

/// An iterator over all owned entries of a [`PrefixMap`] in lexicographic order.
#[derive(Clone)]
pub struct IntoIter<P, T> {
    table: Vec<Node<P, T>>,
    nodes: Vec<usize>,
}

impl<P: Prefix, T> Iterator for IntoIter<P, T> {
    type Item = (P, T);

    fn next(&mut self) -> Option<(P, T)> {
        while let Some(cur) = self.nodes.pop() {
            let node = &mut self.table[cur];
            if let Some(right) = node.right {
                self.nodes.push(right);
            }
            if let Some(left) = node.left {
                self.nodes.push(left);
            }
            if let Some(v) = node.value.take() {
                return Some((std::mem::replace(&mut node.prefix, P::zero()), v));
            }
        }
        None
    }
}

/// An iterator over all prefixes of a [`PrefixMap`] in lexicographic order.
#[derive(Clone)]
pub struct IntoKeys<P, T> {
    inner: IntoIter<P, T>,
}

impl<P: Prefix, T> Iterator for IntoKeys<P, T> {
    type Item = P;

    fn next(&mut self) -> Option<P> {
        self.inner.next().map(|(k, _)| k)
    }
}

/// An iterator over all values of a [`PrefixMap`] in lexicographic order of their associated
/// prefix.
#[derive(Clone)]
pub struct IntoValues<P, T> {
    inner: IntoIter<P, T>,
}

impl<P: Prefix, T> Iterator for IntoValues<P, T> {
    type Item = T;

    fn next(&mut self) -> Option<T> {
        self.inner.next().map(|(_, v)| v)
    }
}

impl<P: Prefix, T> IntoIterator for PrefixMap<P, T> {
    type Item = (P, T);

    type IntoIter = IntoIter<P, T>;

    fn into_iter(self) -> Self::IntoIter {
        IntoIter {
            table: self.table.into_inner(),
            nodes: vec![0],
        }
    }
}

impl<'a, P, T> IntoIterator for &'a PrefixMap<P, T> {
    type Item = (&'a P, &'a T);

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

    fn into_iter(self) -> Self::IntoIter {
        // Safety: we own an immutable reference, and `Iter` will only ever read the table.
        Iter::new(&self.table, vec![0])
    }
}

/// A mutable iterator over a [`PrefixMap`]. This iterator yields elements in lexicographic order of
/// their associated prefix.
pub struct IterMut<'a, P, T> {
    table: Option<&'a Table<P, T>>,
    nodes: Vec<usize>,
}

impl<P, T> Default for IterMut<'_, P, T> {
    fn default() -> Self {
        Self {
            table: None,
            nodes: Vec::new(),
        }
    }
}

impl<'a, P, T> IterMut<'a, P, T> {
    /// # Safety
    /// - First, you must ensure that 'a is tied to a mutable reference of the original table.
    /// - Second, you are allowed to create mutiple such `IterMut`s, as long as none of the root
    ///   nodes is the parent of another root node (of any of the iterators). This also applies if
    ///   you only create a single iterator with multiple root nodes.
    ///
    /// The iterator will only ever access its roots or its children.
    pub(crate) unsafe fn new(table: &'a Table<P, T>, nodes: Vec<usize>) -> Self {
        Self {
            table: Some(table),
            nodes,
        }
    }
}

impl<'a, P, T> Iterator for IterMut<'a, P, T> {
    type Item = (&'a P, &'a mut T);

    fn next(&mut self) -> Option<Self::Item> {
        while let Some(cur) = self.nodes.pop() {
            // Safety:
            // In the following, we assume that there are no two iterators that may reach the same
            // sub-tree (see the safety comment above).
            //
            // The iterator borrows from &'a mut PrefixMap, see `PrefixMap::iter_mut` where 'a is
            // linked to a mutable reference. Then, we must ensure that we only ever construct a
            // mutable reference to each element exactly once. We ensure this by the fact that we
            // iterate over a tree. Thus, each node is visited exactly once.
            let node: &'a mut Node<P, T> = unsafe { self.table.as_ref()?.get_mut(cur) };

            if let Some(right) = node.right {
                self.nodes.push(right);
            }
            if let Some(left) = node.left {
                self.nodes.push(left);
            }
            if node.value.is_some() {
                let v = node.value.as_mut().unwrap();
                return Some((&node.prefix, v));
            }
        }
        None
    }
}

/// A mutable iterator over values of [`PrefixMap`]. This iterator yields elements in lexicographic
/// order.
#[derive(Default)]
pub struct ValuesMut<'a, P, T> {
    // # Safety
    // You must ensure that there only ever exists one such iterator for each tree. You may create
    // multiple such iterators for the same tree if you start with distinct starting nodes! This
    // ensures that any one iteration will never yield elements of the other iterator.
    pub(crate) inner: IterMut<'a, P, T>,
}

impl<'a, P, T> Iterator for ValuesMut<'a, P, T> {
    type Item = &'a mut T;

    fn next(&mut self) -> Option<Self::Item> {
        self.inner.next().map(|(_, v)| v)
    }
}

impl<P, T> PrefixMap<P, T> {
    /// An iterator visiting all key-value pairs in lexicographic order. The iterator element type
    /// is `(&P, &T)`.
    ///
    /// ```
    /// # use prefix_trie::*;
    /// # #[cfg(feature = "ipnet")]
    /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
    /// 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),
    ///     ]
    /// );
    /// # Ok(())
    /// # }
    /// # #[cfg(not(feature = "ipnet"))]
    /// # fn main() {}
    /// ```
    #[inline(always)]
    pub fn iter(&self) -> Iter<'_, P, T> {
        self.into_iter()
    }

    /// Get a mutable iterator over all key-value pairs. The order of this iterator is lexicographic.
    pub fn iter_mut(&mut self) -> IterMut<'_, P, T> {
        // Safety: We get the pointer to the table by and construct the `IterMut`. Its lifetime is
        // now tied to the mutable borrow of `self`, so we are allowed to access elements of that
        // table mutably.
        unsafe { IterMut::new(&self.table, vec![0]) }
    }

    /// An iterator visiting all keys in lexicographic order. The iterator element type is `&P`.
    ///
    /// ```
    /// # use prefix_trie::*;
    /// # #[cfg(feature = "ipnet")]
    /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
    /// 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()?,
    ///     ]
    /// );
    /// # Ok(())
    /// # }
    /// # #[cfg(not(feature = "ipnet"))]
    /// # fn main() {}
    /// ```
    #[inline(always)]
    pub fn keys(&self) -> Keys<'_, P, T> {
        Keys { inner: self.iter() }
    }

    /// Creates a consuming iterator visiting all keys in lexicographic order. The iterator element
    /// type is `P`.
    #[inline(always)]
    pub fn into_keys(self) -> IntoKeys<P, T> {
        IntoKeys {
            inner: IntoIter {
                table: self.table.into_inner(),
                nodes: vec![0],
            },
        }
    }

    /// An iterator visiting all values in lexicographic order. The iterator element type is `&P`.
    ///
    /// ```
    /// # use prefix_trie::*;
    /// # #[cfg(feature = "ipnet")]
    /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
    /// 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]);
    /// # Ok(())
    /// # }
    /// # #[cfg(not(feature = "ipnet"))]
    /// # fn main() {}
    /// ```
    #[inline(always)]
    pub fn values(&self) -> Values<'_, P, T> {
        Values { inner: self.iter() }
    }

    /// Creates a consuming iterator visiting all values in lexicographic order. The iterator
    /// element type is `P`.
    #[inline(always)]
    pub fn into_values(self) -> IntoValues<P, T> {
        IntoValues {
            inner: IntoIter {
                table: self.table.into_inner(),
                nodes: vec![0],
            },
        }
    }

    /// Get a mutable iterator over all values. The order of this iterator is lexicographic.
    pub fn values_mut(&mut self) -> ValuesMut<'_, P, T> {
        ValuesMut {
            inner: self.iter_mut(),
        }
    }
}

impl<P, T> PrefixMap<P, T>
where
    P: Prefix,
{
    /// Get an iterator over the node itself and all children. All elements returned have a prefix
    /// that is contained within `prefix` itself (or are the same). The iterator yields references
    /// to both keys and values, i.e., type `(&'a P, &'a T)`. The iterator yields elements in
    /// lexicographic order.
    ///
    /// **Note**: Consider using [`AsView::view_at`] as an alternative.
    ///
    /// ```
    /// # use prefix_trie::*;
    /// # #[cfg(feature = "ipnet")]
    /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
    /// 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),
    ///     ]
    /// );
    /// # Ok(())
    /// # }
    /// # #[cfg(not(feature = "ipnet"))]
    /// # fn main() {}
    /// ```
    pub fn children(&self, prefix: P) -> Iter<'_, P, T> {
        self.view_at(prefix)
            .map(|x| x.into_iter())
            .unwrap_or_default()
    }

    /// Get an iterator of mutable references of the node itself and all its children. All elements
    /// returned have a prefix that is contained within `prefix` itself (or are the same). The
    /// iterator yields references to the keys, and mutable references to the values, i.e., type
    /// `(&'a P, &'a mut T)`. The iterator yields elements in lexicographic order.
    ///
    /// **Note**: Consider using [`AsViewMut::view_mut_at`] as an alternative.
    ///
    /// ```
    /// # use prefix_trie::*;
    /// # #[cfg(feature = "ipnet")]
    /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
    /// 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),
    ///     ]
    /// );
    /// # Ok(())
    /// # }
    /// # #[cfg(not(feature = "ipnet"))]
    /// # fn main() {}
    /// ```
    pub fn children_mut(&mut self, prefix: P) -> IterMut<'_, P, T> {
        self.view_mut_at(prefix)
            .map(|x| x.into_iter())
            .unwrap_or_default()
    }

    /// 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.
    ///
    /// ```
    /// # use prefix_trie::*;
    /// # #[cfg(feature = "ipnet")]
    /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
    /// 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),
    ///     ]
    /// );
    /// # Ok(())
    /// # }
    /// # #[cfg(not(feature = "ipnet"))]
    /// # fn main() {}
    /// ```
    pub fn into_children(self, prefix: &P) -> IntoIter<P, T> {
        let nodes = lpm_children_iter_start(&self.table, prefix);
        IntoIter {
            table: self.table.into_inner(),
            nodes,
        }
    }
}

fn lpm_children_iter_start<P: Prefix, T>(table: &Table<P, T>, prefix: &P) -> Vec<usize> {
    let mut idx = 0;
    let mut cur_p = &table[idx].prefix;

    loop {
        if cur_p.eq(prefix) {
            break vec![idx];
        }
        let right = to_right(cur_p, prefix);
        match table.get_child(idx, right) {
            Some(c) => {
                cur_p = &table[c].prefix;
                if cur_p.contains(prefix) {
                    // continue traversal
                    idx = c;
                } else if prefix.contains(cur_p) {
                    break vec![c];
                } else {
                    break vec![];
                }
            }
            None => break vec![],
        }
    }
}

impl<P, T> FromIterator<(P, T)> for PrefixMap<P, T>
where
    P: Prefix,
{
    fn from_iter<I: IntoIterator<Item = (P, T)>>(iter: I) -> Self {
        let mut map = Self::new();
        iter.into_iter().for_each(|(p, v)| {
            map.insert(p, v);
        });
        map
    }
}

/// An iterator that yields all items in a `PrefixMap` that covers a given prefix (including the
/// prefix itself if preseint). See [`PrefixMap::cover`] for how to create this iterator.
pub struct Cover<'a, P, T> {
    pub(super) table: &'a Table<P, T>,
    pub(super) idx: Option<usize>,
    pub(super) prefix: &'a P,
}

impl<'a, P, T> Iterator for Cover<'a, P, T>
where
    P: Prefix,
{
    type Item = (&'a P, &'a T);

    fn next(&mut self) -> Option<Self::Item> {
        // check if self.idx is None. If so, then check if the first branch is present in the map
        if self.idx.is_none() {
            self.idx = Some(0);
            let entry = &self.table[0];
            if let Some(value) = entry.value.as_ref() {
                return Some((&entry.prefix, value));
            }
        }

        // if we reach here, then self.idx is not None!

        loop {
            let map::Direction::Enter { next, .. } =
                self.table.get_direction(self.idx.unwrap(), self.prefix)
            else {
                return None;
            };
            self.idx = Some(next);
            let entry = &self.table[next];
            if let Some(value) = entry.value.as_ref() {
                return Some((&entry.prefix, value));
            }
        }
    }
}

/// An iterator that yields all keys (prefixes) in a `PrefixMap` that covers a given prefix
/// (including the prefix itself if preseint). See [`PrefixMap::cover_keys`] for how to create this
/// iterator.
pub struct CoverKeys<'a, P, T>(pub(super) Cover<'a, P, T>);

impl<'a, P, T> Iterator for CoverKeys<'a, P, T>
where
    P: Prefix,
{
    type Item = &'a P;

    fn next(&mut self) -> Option<Self::Item> {
        self.0.next().map(|(p, _)| p)
    }
}

/// An iterator that yields all values in a `PrefixMap` that covers a given prefix (including the
/// prefix itself if preseint). See [`PrefixMap::cover_values`] for how to create this iterator.
pub struct CoverValues<'a, P, T>(pub(super) Cover<'a, P, T>);

impl<'a, P, T> Iterator for CoverValues<'a, P, T>
where
    P: Prefix,
{
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        self.0.next().map(|(_, t)| t)
    }
}

Coverage Report

Created: 2026-02-14 06:16

Line	Count	Source
1		//! Module that contains the implementation for the iterators
2
3		use map::Table;
4
5		use crate::*;
6
7		use super::Node;
8
9		/// An iterator over all entries of a [`PrefixMap`] in lexicographic order.
10		#[derive(Clone)]
11		pub struct Iter<'a, P, T> {
12		table: Option<&'a Table<P, T>>,
13		nodes: Vec<usize>,
14		}
15
16		impl<P, T> Default for Iter<'_, P, T> {
17	0	fn default() -> Self {
18	0	Self {
19	0	table: None,
20	0	nodes: Vec::new(),
21	0	}
22	0	}
23		}
24
25		impl<'a, P, T> Iter<'a, P, T> {
26	0	pub(crate) fn new(table: &'a Table<P, T>, nodes: Vec<usize>) -> Self {
27	0	Self {
28	0	table: Some(table),
29	0	nodes,
30	0	}
31	0	} Unexecuted instantiation: <prefix_trie::map::iter::Iter<ipnet::ipnet::Ipv4Net, ()>>::new Unexecuted instantiation: <prefix_trie::map::iter::Iter<ipnet::ipnet::Ipv6Net, ()>>::new Unexecuted instantiation: <prefix_trie::map::iter::Iter<_, _>>::new
32		}
33
34		impl<'a, P, T> Iterator for Iter<'a, P, T> {
35		type Item = (&'a P, &'a T);
36
37	0	fn next(&mut self) -> Option<(&'a P, &'a T)> {
38	0	while let Some(cur) = self.nodes.pop() {
39	0	let node = &self.table.as_ref()?[cur];
40	0	if let Some(right) = node.right {
41	0	self.nodes.push(right);
42	0	}
43	0	if let Some(left) = node.left {
44	0	self.nodes.push(left);
45	0	}
46	0	if let Some(v) = &node.value {
47	0	return Some((&node.prefix, v));
48	0	}
49		}
50	0	None
51	0	} Unexecuted instantiation: <prefix_trie::map::iter::Iter<ipnet::ipnet::Ipv4Net, ()> as core::iter::traits::iterator::Iterator>::next Unexecuted instantiation: <prefix_trie::map::iter::Iter<ipnet::ipnet::Ipv6Net, ()> as core::iter::traits::iterator::Iterator>::next Unexecuted instantiation: <prefix_trie::map::iter::Iter<_, _> as core::iter::traits::iterator::Iterator>::next
52		}
53
54		/// An iterator over all prefixes of a [`PrefixMap`] in lexicographic order.
55		#[derive(Clone, Default)]
56		pub struct Keys<'a, P, T> {
57		pub(crate) inner: Iter<'a, P, T>,
58		}
59
60		impl<'a, P, T> Iterator for Keys<'a, P, T> {
61		type Item = &'a P;
62
63	0	fn next(&mut self) -> Option<&'a P> {
64	0	self.inner.next().map(\|(k, _)\| k)
65	0	}
66		}
67
68		/// An iterator over all values of a [`PrefixMap`] in lexicographic order of their associated
69		/// prefixes.
70		#[derive(Clone, Default)]
71		pub struct Values<'a, P, T> {
72		pub(crate) inner: Iter<'a, P, T>,
73		}
74
75		impl<'a, P, T> Iterator for Values<'a, P, T> {
76		type Item = &'a T;
77
78	0	fn next(&mut self) -> Option<&'a T> {
79	0	self.inner.next().map(\|(_, v)\| v)
80	0	}
81		}
82
83		/// An iterator over all owned entries of a [`PrefixMap`] in lexicographic order.
84		#[derive(Clone)]
85		pub struct IntoIter<P, T> {
86		table: Vec<Node<P, T>>,
87		nodes: Vec<usize>,
88		}
89
90		impl<P: Prefix, T> Iterator for IntoIter<P, T> {
91		type Item = (P, T);
92
93	0	fn next(&mut self) -> Option<(P, T)> {
94	0	while let Some(cur) = self.nodes.pop() {
95	0	let node = &mut self.table[cur];
96	0	if let Some(right) = node.right {
97	0	self.nodes.push(right);
98	0	}
99	0	if let Some(left) = node.left {
100	0	self.nodes.push(left);
101	0	}
102	0	if let Some(v) = node.value.take() {
103	0	return Some((std::mem::replace(&mut node.prefix, P::zero()), v));
104	0	}
105		}
106	0	None
107	0	}
108		}
109
110		/// An iterator over all prefixes of a [`PrefixMap`] in lexicographic order.
111		#[derive(Clone)]
112		pub struct IntoKeys<P, T> {
113		inner: IntoIter<P, T>,
114		}
115
116		impl<P: Prefix, T> Iterator for IntoKeys<P, T> {
117		type Item = P;
118
119	0	fn next(&mut self) -> Option<P> {
120	0	self.inner.next().map(\|(k, _)\| k)
121	0	}
122		}
123
124		/// An iterator over all values of a [`PrefixMap`] in lexicographic order of their associated
125		/// prefix.
126		#[derive(Clone)]
127		pub struct IntoValues<P, T> {
128		inner: IntoIter<P, T>,
129		}
130
131		impl<P: Prefix, T> Iterator for IntoValues<P, T> {
132		type Item = T;
133
134	0	fn next(&mut self) -> Option<T> {
135	0	self.inner.next().map(\|(_, v)\| v)
136	0	}
137		}
138
139		impl<P: Prefix, T> IntoIterator for PrefixMap<P, T> {
140		type Item = (P, T);
141
142		type IntoIter = IntoIter<P, T>;
143
144	0	fn into_iter(self) -> Self::IntoIter {
145	0	IntoIter {
146	0	table: self.table.into_inner(),
147	0	nodes: vec![0],
148	0	}
149	0	}
150		}
151
152		impl<'a, P, T> IntoIterator for &'a PrefixMap<P, T> {
153		type Item = (&'a P, &'a T);
154
155		type IntoIter = Iter<'a, P, T>;
156
157	0	fn into_iter(self) -> Self::IntoIter {
158		// Safety: we own an immutable reference, and `Iter` will only ever read the table.
159	0	Iter::new(&self.table, vec![0])
160	0	} Unexecuted instantiation: <&prefix_trie::map::PrefixMap<ipnet::ipnet::Ipv4Net, ()> as core::iter::traits::collect::IntoIterator>::into_iter Unexecuted instantiation: <&prefix_trie::map::PrefixMap<ipnet::ipnet::Ipv6Net, ()> as core::iter::traits::collect::IntoIterator>::into_iter Unexecuted instantiation: <&prefix_trie::map::PrefixMap<_, _> as core::iter::traits::collect::IntoIterator>::into_iter
161		}
162
163		/// A mutable iterator over a [`PrefixMap`]. This iterator yields elements in lexicographic order of
164		/// their associated prefix.
165		pub struct IterMut<'a, P, T> {
166		table: Option<&'a Table<P, T>>,
167		nodes: Vec<usize>,
168		}
169
170		impl<P, T> Default for IterMut<'_, P, T> {
171	0	fn default() -> Self {
172	0	Self {
173	0	table: None,
174	0	nodes: Vec::new(),
175	0	}
176	0	}
177		}
178
179		impl<'a, P, T> IterMut<'a, P, T> {
180		/// # Safety
181		/// - First, you must ensure that 'a is tied to a mutable reference of the original table.
182		/// - Second, you are allowed to create mutiple such `IterMut`s, as long as none of the root
183		/// nodes is the parent of another root node (of any of the iterators). This also applies if
184		/// you only create a single iterator with multiple root nodes.
185		///
186		/// The iterator will only ever access its roots or its children.
187	0	pub(crate) unsafe fn new(table: &'a Table<P, T>, nodes: Vec<usize>) -> Self {
188	0	Self {
189	0	table: Some(table),
190	0	nodes,
191	0	}
192	0	}
193		}
194
195		impl<'a, P, T> Iterator for IterMut<'a, P, T> {
196		type Item = (&'a P, &'a mut T);
197
198	0	fn next(&mut self) -> Option<Self::Item> {
199	0	while let Some(cur) = self.nodes.pop() {
200		// Safety:
201		// In the following, we assume that there are no two iterators that may reach the same
202		// sub-tree (see the safety comment above).
203		//
204		// The iterator borrows from &'a mut PrefixMap, see `PrefixMap::iter_mut` where 'a is
205		// linked to a mutable reference. Then, we must ensure that we only ever construct a
206		// mutable reference to each element exactly once. We ensure this by the fact that we
207		// iterate over a tree. Thus, each node is visited exactly once.
208	0	let node: &'a mut Node<P, T> = unsafe { self.table.as_ref()?.get_mut(cur) };
209
210	0	if let Some(right) = node.right {
211	0	self.nodes.push(right);
212	0	}
213	0	if let Some(left) = node.left {
214	0	self.nodes.push(left);
215	0	}
216	0	if node.value.is_some() {
217	0	let v = node.value.as_mut().unwrap();
218	0	return Some((&node.prefix, v));
219	0	}
220		}
221	0	None
222	0	}
223		}
224
225		/// A mutable iterator over values of [`PrefixMap`]. This iterator yields elements in lexicographic
226		/// order.
227		#[derive(Default)]
228		pub struct ValuesMut<'a, P, T> {
229		// # Safety
230		// You must ensure that there only ever exists one such iterator for each tree. You may create
231		// multiple such iterators for the same tree if you start with distinct starting nodes! This
232		// ensures that any one iteration will never yield elements of the other iterator.
233		pub(crate) inner: IterMut<'a, P, T>,
234		}
235
236		impl<'a, P, T> Iterator for ValuesMut<'a, P, T> {
237		type Item = &'a mut T;
238
239	0	fn next(&mut self) -> Option<Self::Item> {
240	0	self.inner.next().map(\|(_, v)\| v)
241	0	}
242		}
243
244		impl<P, T> PrefixMap<P, T> {
245		/// An iterator visiting all key-value pairs in lexicographic order. The iterator element type
246		/// is `(&P, &T)`.
247		///
248		/// ```
249		/// # use prefix_trie::*;
250		/// # #[cfg(feature = "ipnet")]
251		/// # fn main() -> Result<(), Box<dyn std::error::Error>> {
252		/// let mut pm: PrefixMap<ipnet::Ipv4Net, _> = PrefixMap::new();
253		/// pm.insert("192.168.0.0/22".parse()?, 1);
254		/// pm.insert("192.168.0.0/23".parse()?, 2);
255		/// pm.insert("192.168.2.0/23".parse()?, 3);
256		/// pm.insert("192.168.0.0/24".parse()?, 4);
257		/// pm.insert("192.168.2.0/24".parse()?, 5);
258		/// assert_eq!(
259		/// pm.iter().collect::<Vec<_>>(),
260		/// vec![
261		/// (&"192.168.0.0/22".parse()?, &1),
262		/// (&"192.168.0.0/23".parse()?, &2),
263		/// (&"192.168.0.0/24".parse()?, &4),
264		/// (&"192.168.2.0/23".parse()?, &3),
265		/// (&"192.168.2.0/24".parse()?, &5),
266		/// ]
267		/// );
268		/// # Ok(())
269		/// # }
270		/// # #[cfg(not(feature = "ipnet"))]
271		/// # fn main() {}
272		/// ```
273		#[inline(always)]
274	0	pub fn iter(&self) -> Iter<'_, P, T> {
275	0	self.into_iter()
276	0	} Unexecuted instantiation: <prefix_trie::map::PrefixMap<ipnet::ipnet::Ipv4Net, ()>>::iter Unexecuted instantiation: <prefix_trie::map::PrefixMap<ipnet::ipnet::Ipv6Net, ()>>::iter Unexecuted instantiation: <prefix_trie::map::PrefixMap<_, _>>::iter
277
278		/// Get a mutable iterator over all key-value pairs. The order of this iterator is lexicographic.
279	0	pub fn iter_mut(&mut self) -> IterMut<'_, P, T> {
280		// Safety: We get the pointer to the table by and construct the `IterMut`. Its lifetime is
281		// now tied to the mutable borrow of `self`, so we are allowed to access elements of that
282		// table mutably.
283	0	unsafe { IterMut::new(&self.table, vec![0]) }
284	0	}
285
286		/// An iterator visiting all keys in lexicographic order. The iterator element type is `&P`.
287		///
288		/// ```
289		/// # use prefix_trie::*;
290		/// # #[cfg(feature = "ipnet")]
291		/// # fn main() -> Result<(), Box<dyn std::error::Error>> {
292		/// let mut pm: PrefixMap<ipnet::Ipv4Net, _> = PrefixMap::new();
293		/// pm.insert("192.168.0.0/22".parse()?, 1);
294		/// pm.insert("192.168.0.0/23".parse()?, 2);
295		/// pm.insert("192.168.2.0/23".parse()?, 3);
296		/// pm.insert("192.168.0.0/24".parse()?, 4);
297		/// pm.insert("192.168.2.0/24".parse()?, 5);
298		/// assert_eq!(
299		/// pm.keys().collect::<Vec<_>>(),
300		/// vec![
301		/// &"192.168.0.0/22".parse()?,
302		/// &"192.168.0.0/23".parse()?,
303		/// &"192.168.0.0/24".parse()?,
304		/// &"192.168.2.0/23".parse()?,
305		/// &"192.168.2.0/24".parse()?,
306		/// ]
307		/// );
308		/// # Ok(())
309		/// # }
310		/// # #[cfg(not(feature = "ipnet"))]
311		/// # fn main() {}
312		/// ```
313		#[inline(always)]
314	0	pub fn keys(&self) -> Keys<'_, P, T> {
315	0	Keys { inner: self.iter() }
316	0	}
317
318		/// Creates a consuming iterator visiting all keys in lexicographic order. The iterator element
319		/// type is `P`.
320		#[inline(always)]
321	0	pub fn into_keys(self) -> IntoKeys<P, T> {
322	0	IntoKeys {
323	0	inner: IntoIter {
324	0	table: self.table.into_inner(),
325	0	nodes: vec![0],
326	0	},
327	0	}
328	0	}
329
330		/// An iterator visiting all values in lexicographic order. The iterator element type is `&P`.
331		///
332		/// ```
333		/// # use prefix_trie::*;
334		/// # #[cfg(feature = "ipnet")]
335		/// # fn main() -> Result<(), Box<dyn std::error::Error>> {
336		/// let mut pm: PrefixMap<ipnet::Ipv4Net, _> = PrefixMap::new();
337		/// pm.insert("192.168.0.0/22".parse()?, 1);
338		/// pm.insert("192.168.0.0/23".parse()?, 2);
339		/// pm.insert("192.168.2.0/23".parse()?, 3);
340		/// pm.insert("192.168.0.0/24".parse()?, 4);
341		/// pm.insert("192.168.2.0/24".parse()?, 5);
342		/// assert_eq!(pm.values().collect::<Vec<_>>(), vec![&1, &2, &4, &3, &5]);
343		/// # Ok(())
344		/// # }
345		/// # #[cfg(not(feature = "ipnet"))]
346		/// # fn main() {}
347		/// ```
348		#[inline(always)]
349	0	pub fn values(&self) -> Values<'_, P, T> {
350	0	Values { inner: self.iter() }
351	0	}
352
353		/// Creates a consuming iterator visiting all values in lexicographic order. The iterator
354		/// element type is `P`.
355		#[inline(always)]
356	0	pub fn into_values(self) -> IntoValues<P, T> {
357	0	IntoValues {
358	0	inner: IntoIter {
359	0	table: self.table.into_inner(),
360	0	nodes: vec![0],
361	0	},
362	0	}
363	0	}
364
365		/// Get a mutable iterator over all values. The order of this iterator is lexicographic.
366	0	pub fn values_mut(&mut self) -> ValuesMut<'_, P, T> {
367	0	ValuesMut {
368	0	inner: self.iter_mut(),
369	0	}
370	0	}
371		}
372
373		impl<P, T> PrefixMap<P, T>
374		where
375		P: Prefix,
376		{
377		/// Get an iterator over the node itself and all children. All elements returned have a prefix
378		/// that is contained within `prefix` itself (or are the same). The iterator yields references
379		/// to both keys and values, i.e., type `(&'a P, &'a T)`. The iterator yields elements in
380		/// lexicographic order.
381		///
382		/// Note: Consider using [`AsView::view_at`] as an alternative.
383		///
384		/// ```
385		/// # use prefix_trie::*;
386		/// # #[cfg(feature = "ipnet")]
387		/// # fn main() -> Result<(), Box<dyn std::error::Error>> {
388		/// let mut pm: PrefixMap<ipnet::Ipv4Net, _> = PrefixMap::new();
389		/// pm.insert("192.168.0.0/22".parse()?, 1);
390		/// pm.insert("192.168.0.0/23".parse()?, 2);
391		/// pm.insert("192.168.2.0/23".parse()?, 3);
392		/// pm.insert("192.168.0.0/24".parse()?, 4);
393		/// pm.insert("192.168.2.0/24".parse()?, 5);
394		/// assert_eq!(
395		/// pm.children("192.168.0.0/23".parse()?).collect::<Vec<_>>(),
396		/// vec![
397		/// (&"192.168.0.0/23".parse()?, &2),
398		/// (&"192.168.0.0/24".parse()?, &4),
399		/// ]
400		/// );
401		/// # Ok(())
402		/// # }
403		/// # #[cfg(not(feature = "ipnet"))]
404		/// # fn main() {}
405		/// ```
406	0	pub fn children(&self, prefix: P) -> Iter<'_, P, T> {
407	0	self.view_at(prefix)
408	0	.map(\|x\| x.into_iter())
409	0	.unwrap_or_default()
410	0	}
411
412		/// Get an iterator of mutable references of the node itself and all its children. All elements
413		/// returned have a prefix that is contained within `prefix` itself (or are the same). The
414		/// iterator yields references to the keys, and mutable references to the values, i.e., type
415		/// `(&'a P, &'a mut T)`. The iterator yields elements in lexicographic order.
416		///
417		/// Note: Consider using [`AsViewMut::view_mut_at`] as an alternative.
418		///
419		/// ```
420		/// # use prefix_trie::*;
421		/// # #[cfg(feature = "ipnet")]
422		/// # fn main() -> Result<(), Box<dyn std::error::Error>> {
423		/// let mut pm: PrefixMap<ipnet::Ipv4Net, _> = PrefixMap::new();
424		/// pm.insert("192.168.0.0/22".parse()?, 1);
425		/// pm.insert("192.168.0.0/23".parse()?, 2);
426		/// pm.insert("192.168.0.0/24".parse()?, 3);
427		/// pm.insert("192.168.2.0/23".parse()?, 4);
428		/// pm.insert("192.168.2.0/24".parse()?, 5);
429		/// pm.children_mut("192.168.0.0/23".parse()?).for_each(\|(_, x)\| x = 10);
430		/// assert_eq!(
431		/// pm.into_iter().collect::<Vec<_>>(),
432		/// vec![
433		/// ("192.168.0.0/22".parse()?, 1),
434		/// ("192.168.0.0/23".parse()?, 20),
435		/// ("192.168.0.0/24".parse()?, 30),
436		/// ("192.168.2.0/23".parse()?, 4),
437		/// ("192.168.2.0/24".parse()?, 5),
438		/// ]
439		/// );
440		/// # Ok(())
441		/// # }
442		/// # #[cfg(not(feature = "ipnet"))]
443		/// # fn main() {}
444		/// ```
445	0	pub fn children_mut(&mut self, prefix: P) -> IterMut<'_, P, T> {
446	0	self.view_mut_at(prefix)
447	0	.map(\|x\| x.into_iter())
448	0	.unwrap_or_default()
449	0	}
450
451		/// Get an iterator over the node itself and all children with a value. All elements returned
452		/// have a prefix that is contained within `prefix` itself (or are the same). This function will
453		/// consume `self`, returning an iterator over all owned children.
454		///
455		/// ```
456		/// # use prefix_trie::*;
457		/// # #[cfg(feature = "ipnet")]
458		/// # fn main() -> Result<(), Box<dyn std::error::Error>> {
459		/// let mut pm: PrefixMap<ipnet::Ipv4Net, _> = PrefixMap::new();
460		/// pm.insert("192.168.0.0/22".parse()?, 1);
461		/// pm.insert("192.168.0.0/23".parse()?, 2);
462		/// pm.insert("192.168.2.0/23".parse()?, 3);
463		/// pm.insert("192.168.0.0/24".parse()?, 4);
464		/// pm.insert("192.168.2.0/24".parse()?, 5);
465		/// assert_eq!(
466		/// pm.into_children(&"192.168.0.0/23".parse()?).collect::<Vec<_>>(),
467		/// vec![
468		/// ("192.168.0.0/23".parse()?, 2),
469		/// ("192.168.0.0/24".parse()?, 4),
470		/// ]
471		/// );
472		/// # Ok(())
473		/// # }
474		/// # #[cfg(not(feature = "ipnet"))]
475		/// # fn main() {}
476		/// ```
477	0	pub fn into_children(self, prefix: &P) -> IntoIter<P, T> {
478	0	let nodes = lpm_children_iter_start(&self.table, prefix);
479	0	IntoIter {
480	0	table: self.table.into_inner(),
481	0	nodes,
482	0	}
483	0	}
484		}
485
486	0	fn lpm_children_iter_start<P: Prefix, T>(table: &Table<P, T>, prefix: &P) -> Vec<usize> {
487	0	let mut idx = 0;
488	0	let mut cur_p = &table[idx].prefix;
489
490		loop {
491	0	if cur_p.eq(prefix) {
492	0	break vec![idx];
493	0	}
494	0	let right = to_right(cur_p, prefix);
495	0	match table.get_child(idx, right) {
496	0	Some(c) => {
497	0	cur_p = &table[c].prefix;
498	0	if cur_p.contains(prefix) {
499	0	// continue traversal
500	0	idx = c;
501	0	} else if prefix.contains(cur_p) {
502	0	break vec![c];
503		} else {
504	0	break vec![];
505		}
506		}
507	0	None => break vec![],
508		}
509		}
510	0	}
511
512		impl<P, T> FromIterator<(P, T)> for PrefixMap<P, T>
513		where
514		P: Prefix,
515		{
516	0	fn from_iter<I: IntoIterator<Item = (P, T)>>(iter: I) -> Self {
517	0	let mut map = Self::new();
518	0	iter.into_iter().for_each(\|(p, v)\| {
519	0	map.insert(p, v);
520	0	});
521	0	map
522	0	}
523		}
524
525		/// An iterator that yields all items in a `PrefixMap` that covers a given prefix (including the
526		/// prefix itself if preseint). See [`PrefixMap::cover`] for how to create this iterator.
527		pub struct Cover<'a, P, T> {
528		pub(super) table: &'a Table<P, T>,
529		pub(super) idx: Option<usize>,
530		pub(super) prefix: &'a P,
531		}
532
533		impl<'a, P, T> Iterator for Cover<'a, P, T>
534		where
535		P: Prefix,
536		{
537		type Item = (&'a P, &'a T);
538
539	0	fn next(&mut self) -> Option<Self::Item> {
540		// check if self.idx is None. If so, then check if the first branch is present in the map
541	0	if self.idx.is_none() {
542	0	self.idx = Some(0);
543	0	let entry = &self.table[0];
544	0	if let Some(value) = entry.value.as_ref() {
545	0	return Some((&entry.prefix, value));
546	0	}
547	0	}
548
549		// if we reach here, then self.idx is not None!
550
551		loop {
552	0	let map::Direction::Enter { next, .. } =
553	0	self.table.get_direction(self.idx.unwrap(), self.prefix)
554		else {
555	0	return None;
556		};
557	0	self.idx = Some(next);
558	0	let entry = &self.table[next];
559	0	if let Some(value) = entry.value.as_ref() {
560	0	return Some((&entry.prefix, value));
561	0	}
562		}
563	0	}
564		}
565
566		/// An iterator that yields all keys (prefixes) in a `PrefixMap` that covers a given prefix
567		/// (including the prefix itself if preseint). See [`PrefixMap::cover_keys`] for how to create this
568		/// iterator.
569		pub struct CoverKeys<'a, P, T>(pub(super) Cover<'a, P, T>);
570
571		impl<'a, P, T> Iterator for CoverKeys<'a, P, T>
572		where
573		P: Prefix,
574		{
575		type Item = &'a P;
576
577	0	fn next(&mut self) -> Option<Self::Item> {
578	0	self.0.next().map(\|(p, _)\| p)
579	0	}
580		}
581
582		/// An iterator that yields all values in a `PrefixMap` that covers a given prefix (including the
583		/// prefix itself if preseint). See [`PrefixMap::cover_values`] for how to create this iterator.
584		pub struct CoverValues<'a, P, T>(pub(super) Cover<'a, P, T>);
585
586		impl<'a, P, T> Iterator for CoverValues<'a, P, T>
587		where
588		P: Prefix,
589		{
590		type Item = &'a T;
591
592	0	fn next(&mut self) -> Option<Self::Item> {
593	0	self.0.next().map(\|(_, t)\| t)
594	0	}
595		}