zenoh_keyexpr/keyexpr_tree/iters/
tree_iter.rs

1//
2// Copyright (c) 2023 ZettaScale Technology
3//
4// This program and the accompanying materials are made available under the
5// terms of the Eclipse Public License 2.0 which is available at
6// http://www.eclipse.org/legal/epl-2.0, or the Apache License, Version 2.0
7// which is available at https://www.apache.org/licenses/LICENSE-2.0.
8//
9// SPDX-License-Identifier: EPL-2.0 OR Apache-2.0
10//
11// Contributors:
12//   ZettaScale Zenoh Team, <zenoh@zettascale.tech>
13//
14
15use alloc::vec::Vec;
16use core::num::NonZeroUsize;
17
18use crate::keyexpr_tree::*;
19pub struct TreeIter<'a, Children: IChildrenProvider<Node>, Node: UIKeyExprTreeNode<Weight>, Weight>
20where
21    Children::Assoc: IChildren<Node> + 'a,
22    <Children::Assoc as IChildren<Node>>::Node: 'a,
23{
24    iterators: Vec<<Children::Assoc as IChildren<Node>>::Iter<'a>>,
25    _marker: core::marker::PhantomData<Weight>,
26}
27
28impl<'a, Children: IChildrenProvider<Node>, Node: UIKeyExprTreeNode<Weight>, Weight>
29    core::fmt::Debug for TreeIter<'a, Children, Node, Weight>
30where
31    Children::Assoc: IChildren<Node> + 'a,
32    <Children::Assoc as IChildren<Node>>::Node: 'a,
33{
34    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
35        f.debug_struct("TreeIter")
36            .field("depth", &self.iterators.len())
37            .finish()
38    }
39}
40
41impl<'a, Children: IChildrenProvider<Node>, Node: UIKeyExprTreeNode<Weight>, Weight>
42    TreeIter<'a, Children, Node, Weight>
43where
44    Children::Assoc: IChildren<Node> + 'a,
45{
46    pub(crate) fn new(children: &'a Children::Assoc) -> Self {
47        let mut iterators = Vec::with_capacity(16);
48        iterators.push(children.children());
49        Self {
50            iterators,
51            _marker: Default::default(),
52        }
53    }
54    pub fn with_depth(self) -> DepthInstrumented<Self> {
55        DepthInstrumented(self)
56    }
57}
58
59impl<
60        'a,
61        Children: IChildrenProvider<Node>,
62        Node: UIKeyExprTreeNode<Weight, Children = Children::Assoc> + 'a,
63        Weight,
64    > Iterator for TreeIter<'a, Children, Node, Weight>
65where
66    Children::Assoc: IChildren<Node> + 'a,
67{
68    type Item = &'a Node;
69    fn next(&mut self) -> Option<Self::Item> {
70        loop {
71            match self.iterators.last_mut()?.next() {
72                Some(node) => {
73                    // SAFETY: upheld by the surrounding invariants and prior validation.
74                    let iterator = unsafe { node.as_node().__children() }.children();
75                    self.iterators.push(iterator);
76                    return Some(node.as_node());
77                }
78                None => {
79                    self.iterators.pop();
80                }
81            }
82        }
83    }
84}
85pub struct TreeIterMut<
86    'a,
87    Children: IChildrenProvider<Node>,
88    Node: IKeyExprTreeNode<Weight>,
89    Weight,
90> where
91    Children::Assoc: IChildren<Node> + 'a,
92    <Children::Assoc as IChildren<Node>>::Node: 'a,
93{
94    iterators: Vec<<Children::Assoc as IChildren<Node>>::IterMut<'a>>,
95    _marker: core::marker::PhantomData<Weight>,
96}
97
98impl<'a, Children: IChildrenProvider<Node>, Node: IKeyExprTreeNode<Weight>, Weight> core::fmt::Debug
99    for TreeIterMut<'a, Children, Node, Weight>
100where
101    Children::Assoc: IChildren<Node> + 'a,
102    <Children::Assoc as IChildren<Node>>::Node: 'a,
103{
104    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
105        f.debug_struct("TreeIterMut")
106            .field("depth", &self.iterators.len())
107            .finish()
108    }
109}
110
111impl<'a, Children: IChildrenProvider<Node>, Node: IKeyExprTreeNode<Weight>, Weight>
112    TreeIterMut<'a, Children, Node, Weight>
113where
114    Children::Assoc: IChildren<Node> + 'a,
115{
116    pub(crate) fn new(children: &'a mut Children::Assoc) -> Self {
117        let mut iterators = Vec::with_capacity(16);
118        iterators.push(children.children_mut());
119        Self {
120            iterators,
121            _marker: Default::default(),
122        }
123    }
124}
125
126impl<
127        'a,
128        Children: IChildrenProvider<Node>,
129        Node: IKeyExprTreeNodeMut<Weight, Children = Children::Assoc> + 'a,
130        Weight,
131    > Iterator for TreeIterMut<'a, Children, Node, Weight>
132where
133    Children::Assoc: IChildren<Node> + 'a,
134{
135    type Item = &'a mut <Children::Assoc as IChildren<Node>>::Node;
136    fn next(&mut self) -> Option<Self::Item> {
137        loop {
138            match self.iterators.last_mut()?.next() {
139                Some(node) => {
140                    // SAFETY: upheld by the surrounding invariants and prior validation.
141                    let iterator = unsafe { &mut *(node.as_node_mut() as *mut Node) }
142                        .children_mut()
143                        .children_mut();
144                    self.iterators.push(iterator);
145                    return Some(node);
146                }
147                None => {
148                    self.iterators.pop();
149                }
150            }
151        }
152    }
153}
154
155pub struct DepthInstrumented<T>(T);
156
157impl<T> core::fmt::Debug for DepthInstrumented<T> {
158    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
159        f.debug_tuple("DepthInstrumented").field(&"..").finish()
160    }
161}
162impl<
163        'a,
164        Children: IChildrenProvider<Node>,
165        Node: IKeyExprTreeNode<Weight, Children = Children::Assoc> + 'a,
166        Weight,
167    > Iterator for DepthInstrumented<TreeIter<'a, Children, Node, Weight>>
168where
169    Children::Assoc: IChildren<Node> + 'a,
170{
171    type Item = (NonZeroUsize, &'a <Children::Assoc as IChildren<Node>>::Node);
172    fn next(&mut self) -> Option<Self::Item> {
173        loop {
174            let depth = self.0.iterators.len();
175            match self.0.iterators.last_mut()?.next() {
176                Some(node) => {
177                    // SAFETY: upheld by the surrounding invariants and prior validation.
178                    let iterator = unsafe { node.as_node().__children() }.children();
179                    self.0.iterators.push(iterator);
180                    // SAFETY: upheld by the surrounding invariants and prior validation.
181                    return Some((unsafe { NonZeroUsize::new_unchecked(depth) }, node));
182                }
183                None => {
184                    self.0.iterators.pop();
185                }
186            }
187        }
188    }
189}
zenoh_keyexpr/keyexpr_tree/iters/tree_iter.rs

zenoh_keyexpr/keyexpr_tree/iters/
tree_iter.rs
