zenoh_keyexpr/keyexpr_tree/
box_tree.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
15#[cfg(not(feature = "std"))]
16use alloc::boxed::Box;
17use alloc::string::String;
18use core::ptr::NonNull;
19
20use super::support::IterOrOption;
21use crate::{
22    keyexpr,
23    keyexpr_tree::{support::IWildness, *},
24};
25
26/// A fully owned KeTree.
27///
28/// Note that most of `KeBoxTree`'s methods are declared in the [`IKeyExprTree`] and [`IKeyExprTreeMut`] traits.
29#[repr(C)]
30pub struct KeBoxTree<
31    Weight,
32    Wildness: IWildness = bool,
33    Children: IChildrenProvider<Box<KeyExprTreeNode<Weight, Wildness, Children>>> = DefaultChildrenProvider,
34> {
35    children: Children::Assoc,
36    wildness: Wildness,
37}
38
39impl<Weight> KeBoxTree<Weight, bool, DefaultChildrenProvider>
40where
41    DefaultChildrenProvider:
42        IChildrenProvider<Box<KeyExprTreeNode<Weight, bool, DefaultChildrenProvider>>>,
43{
44    pub fn new() -> Self {
45        Default::default()
46    }
47}
48impl<
49        Weight,
50        Children: IChildrenProvider<Box<KeyExprTreeNode<Weight, Wildness, Children>>>,
51        Wildness: IWildness,
52    > Default for KeBoxTree<Weight, Wildness, Children>
53{
54    fn default() -> Self {
55        KeBoxTree {
56            children: Default::default(),
57            wildness: Wildness::non_wild(),
58        }
59    }
60}
61
62impl<
63        'a,
64        Weight,
65        Children: IChildrenProvider<Box<KeyExprTreeNode<Weight, Wildness, Children>>>,
66        Wildness: IWildness,
67    > IKeyExprTree<'a, Weight> for KeBoxTree<Weight, Wildness, Children>
68where
69    Weight: 'a,
70    Children: 'a,
71    Children::Assoc: IChildren<
72            Box<KeyExprTreeNode<Weight, Wildness, Children>>,
73            Node = Box<KeyExprTreeNode<Weight, Wildness, Children>>,
74        > + 'a,
75{
76    type Node = KeyExprTreeNode<Weight, Wildness, Children>;
77    fn node(&'a self, at: &keyexpr) -> Option<&'a Self::Node> {
78        let mut chunks = at.chunks_impl();
79        let mut node = self.children.child_at(chunks.next().unwrap())?;
80        for chunk in chunks {
81            node = node.as_node().children.child_at(chunk)?;
82        }
83        Some(node.as_node())
84    }
85    type TreeIterItem = <Self::TreeIter as Iterator>::Item;
86    type TreeIter =
87        TreeIter<'a, Children, Box<KeyExprTreeNode<Weight, Wildness, Children>>, Weight>;
88    fn tree_iter(&'a self) -> Self::TreeIter {
89        TreeIter::new(&self.children)
90    }
91    type IntersectionItem = <Self::Intersection as Iterator>::Item;
92    type Intersection = IterOrOption<
93        Intersection<'a, Children, Box<KeyExprTreeNode<Weight, Wildness, Children>>, Weight>,
94        &'a Self::Node,
95    >;
96    fn intersecting_nodes(&'a self, ke: &'a keyexpr) -> Self::Intersection {
97        if self.wildness.get() || ke.is_wild_impl() {
98            Intersection::new(&self.children, ke).into()
99        } else {
100            let node = self.node(ke);
101            IterOrOption::Opt(node)
102        }
103    }
104
105    type InclusionItem = <Self::Inclusion as Iterator>::Item;
106    type Inclusion = IterOrOption<
107        Inclusion<'a, Children, Box<KeyExprTreeNode<Weight, Wildness, Children>>, Weight>,
108        &'a Self::Node,
109    >;
110    fn included_nodes(&'a self, ke: &'a keyexpr) -> Self::Inclusion {
111        if self.wildness.get() || ke.is_wild_impl() {
112            Inclusion::new(&self.children, ke).into()
113        } else {
114            let node = self.node(ke);
115            IterOrOption::Opt(node)
116        }
117    }
118
119    type IncluderItem = <Self::Includer as Iterator>::Item;
120    type Includer = IterOrOption<
121        Includer<'a, Children, Box<KeyExprTreeNode<Weight, Wildness, Children>>, Weight>,
122        &'a Self::Node,
123    >;
124    fn nodes_including(&'a self, ke: &'a keyexpr) -> Self::Includer {
125        if self.wildness.get() || ke.is_wild_impl() {
126            Includer::new(&self.children, ke).into()
127        } else {
128            let node = self.node(ke);
129            IterOrOption::Opt(node)
130        }
131    }
132}
133impl<
134        'a,
135        Weight,
136        Children: IChildrenProvider<Box<KeyExprTreeNode<Weight, Wildness, Children>>>,
137        Wildness: IWildness,
138    > IKeyExprTreeMut<'a, Weight> for KeBoxTree<Weight, Wildness, Children>
139where
140    Weight: 'a,
141    Children: 'a,
142    Children::Assoc: IChildren<
143            Box<KeyExprTreeNode<Weight, Wildness, Children>>,
144            Node = Box<KeyExprTreeNode<Weight, Wildness, Children>>,
145        > + 'a,
146{
147    fn node_mut<'b>(&'b mut self, at: &keyexpr) -> Option<&'b mut Self::Node> {
148        let mut chunks = at.chunks_impl();
149        let mut node = self.children.child_at_mut(chunks.next().unwrap())?;
150        for chunk in chunks {
151            node = node.as_node_mut().children.child_at_mut(chunk)?;
152        }
153        Some(node.as_node_mut())
154    }
155
156    fn remove(&mut self, at: &keyexpr) -> Option<Weight> {
157        let node = self.node_mut(at)?;
158        if !node.children.is_empty() {
159            node.weight.take()
160        } else {
161            let chunk = unsafe { core::mem::transmute::<&keyexpr, &keyexpr>(node.chunk()) };
162            match node.parent {
163                None => &mut self.children,
164                Some(parent) => unsafe { &mut (*parent.as_ptr()).children },
165            }
166            .remove(chunk)
167            .and_then(|node| node.weight)
168        }
169    }
170
171    fn node_mut_or_create<'b>(&'b mut self, at: &keyexpr) -> &'b mut Self::Node {
172        if at.is_wild_impl() {
173            self.wildness.set(true);
174        }
175        let mut chunks = at.chunks_impl();
176        let mut node = self
177            .children
178            .entry(chunks.next().unwrap())
179            .get_or_insert_with(move |k| {
180                Box::new(KeyExprTreeNode {
181                    parent: None,
182                    chunk: k.into(),
183                    children: Default::default(),
184                    weight: None,
185                })
186            });
187        for chunk in chunks {
188            let parent = NonNull::from(node.as_ref());
189            node = node.children.entry(chunk).get_or_insert_with(move |k| {
190                Box::new(KeyExprTreeNode {
191                    parent: Some(parent),
192                    chunk: k.into(),
193                    children: Default::default(),
194                    weight: None,
195                })
196            })
197        }
198        node
199    }
200    type TreeIterItemMut = <Self::TreeIterMut as Iterator>::Item;
201    type TreeIterMut =
202        TreeIterMut<'a, Children, Box<KeyExprTreeNode<Weight, Wildness, Children>>, Weight>;
203    fn tree_iter_mut(&'a mut self) -> Self::TreeIterMut {
204        TreeIterMut::new(&mut self.children)
205    }
206
207    type IntersectionItemMut = <Self::IntersectionMut as Iterator>::Item;
208    type IntersectionMut = IterOrOption<
209        IntersectionMut<'a, Children, Box<KeyExprTreeNode<Weight, Wildness, Children>>, Weight>,
210        &'a mut Self::Node,
211    >;
212    fn intersecting_nodes_mut(&'a mut self, ke: &'a keyexpr) -> Self::IntersectionMut {
213        if self.wildness.get() || ke.is_wild_impl() {
214            IntersectionMut::new(&mut self.children, ke).into()
215        } else {
216            let node = self.node_mut(ke);
217            IterOrOption::Opt(node)
218        }
219    }
220    type InclusionItemMut = <Self::InclusionMut as Iterator>::Item;
221    type InclusionMut = IterOrOption<
222        InclusionMut<'a, Children, Box<KeyExprTreeNode<Weight, Wildness, Children>>, Weight>,
223        &'a mut Self::Node,
224    >;
225    fn included_nodes_mut(&'a mut self, ke: &'a keyexpr) -> Self::InclusionMut {
226        if self.wildness.get() || ke.is_wild_impl() {
227            InclusionMut::new(&mut self.children, ke).into()
228        } else {
229            let node = self.node_mut(ke);
230            IterOrOption::Opt(node)
231        }
232    }
233    type IncluderItemMut = <Self::IncluderMut as Iterator>::Item;
234    type IncluderMut = IterOrOption<
235        IncluderMut<'a, Children, Box<KeyExprTreeNode<Weight, Wildness, Children>>, Weight>,
236        &'a mut Self::Node,
237    >;
238    fn nodes_including_mut(&'a mut self, ke: &'a keyexpr) -> Self::IncluderMut {
239        if self.wildness.get() || ke.is_wild_impl() {
240            IncluderMut::new(&mut self.children, ke).into()
241        } else {
242            let node = self.node_mut(ke);
243            IterOrOption::Opt(node)
244        }
245    }
246
247    fn prune_where<F: FnMut(&mut Self::Node) -> bool>(&mut self, mut predicate: F) {
248        let mut wild = false;
249        self.children
250            .filter_out(&mut |child| match child.as_mut().prune(&mut predicate) {
251                PruneResult::Delete => true,
252                PruneResult::NonWild => false,
253                PruneResult::Wild => {
254                    wild = true;
255                    false
256                }
257            });
258        self.wildness.set(wild);
259    }
260}
261
262#[repr(C)]
263pub struct KeyExprTreeNode<Weight, Wildness: IWildness, Children: IChildrenProvider<Box<Self>>> {
264    parent: Option<NonNull<Self>>,
265    chunk: OwnedKeyExpr,
266    children: Children::Assoc,
267    weight: Option<Weight>,
268}
269
270unsafe impl<Weight: Send, Wildness: IWildness + Send, Children: IChildrenProvider<Box<Self>> + Send>
271    Send for KeyExprTreeNode<Weight, Wildness, Children>
272{
273}
274unsafe impl<Weight: Sync, Wildness: IWildness + Sync, Children: IChildrenProvider<Box<Self>> + Sync>
275    Sync for KeyExprTreeNode<Weight, Wildness, Children>
276{
277}
278
279impl<Weight, Wildness: IWildness, Children: IChildrenProvider<Box<Self>>> IKeyExprTreeNode<Weight>
280    for KeyExprTreeNode<Weight, Wildness, Children>
281where
282    Children::Assoc: IChildren<Box<Self>>,
283{
284}
285impl<Weight, Wildness: IWildness, Children: IChildrenProvider<Box<Self>>> UIKeyExprTreeNode<Weight>
286    for KeyExprTreeNode<Weight, Wildness, Children>
287where
288    Children::Assoc: IChildren<Box<Self>>,
289{
290    type Parent = Self;
291    unsafe fn __parent(&self) -> Option<&Self> {
292        self.parent.as_ref().map(|node| unsafe {
293            // this is safe, as a mutable reference to the parent was needed to get a mutable reference to this node in the first place.
294            node.as_ref()
295        })
296    }
297    unsafe fn __keyexpr(&self) -> OwnedKeyExpr {
298        unsafe {
299            // self._keyexpr is guaranteed to return a valid KE, so no checks are necessary
300            OwnedKeyExpr::from_string_unchecked(self._keyexpr(0))
301        }
302    }
303    unsafe fn __weight(&self) -> Option<&Weight> {
304        self.weight.as_ref()
305    }
306    type Child = Box<Self>;
307    type Children = Children::Assoc;
308
309    unsafe fn __children(&self) -> &Self::Children {
310        &self.children
311    }
312}
313impl<Weight, Wildness: IWildness, Children: IChildrenProvider<Box<Self>>>
314    IKeyExprTreeNodeMut<Weight> for KeyExprTreeNode<Weight, Wildness, Children>
315where
316    Children::Assoc: IChildren<Box<Self>>,
317{
318    fn parent_mut(&mut self) -> Option<&mut Self> {
319        match &mut self.parent {
320            None => None,
321            Some(node) => Some(unsafe {
322                // this is safe, as a mutable reference to the parent was needed to get a mutable reference to this node in the first place.
323                node.as_mut()
324            }),
325        }
326    }
327    fn weight_mut(&mut self) -> Option<&mut Weight> {
328        self.weight.as_mut()
329    }
330    fn take_weight(&mut self) -> Option<Weight> {
331        self.weight.take()
332    }
333    fn insert_weight(&mut self, weight: Weight) -> Option<Weight> {
334        self.weight.replace(weight)
335    }
336
337    fn children_mut(&mut self) -> &mut Self::Children {
338        &mut self.children
339    }
340}
341
342impl<Weight, Wildness: IWildness, Children: IChildrenProvider<Box<Self>>>
343    KeyExprTreeNode<Weight, Wildness, Children>
344where
345    Children::Assoc: IChildren<Box<Self>>,
346{
347    fn _keyexpr(&self, capacity: usize) -> String {
348        let mut s = match self.parent() {
349            Some(parent) => parent._keyexpr(capacity + self.chunk.len() + 1) + "/",
350            None => String::with_capacity(capacity + self.chunk.len()),
351        };
352        s.push_str(self.chunk.as_str());
353        s
354    }
355    fn prune<F: FnMut(&mut Self) -> bool>(&mut self, predicate: &mut F) -> PruneResult {
356        let mut result = PruneResult::NonWild;
357        self.children
358            .filter_out(&mut |child| match child.as_node_mut().prune(predicate) {
359                PruneResult::Delete => true,
360                PruneResult::NonWild => false,
361                PruneResult::Wild => {
362                    result = PruneResult::Wild;
363                    false
364                }
365            });
366        if predicate(self) && self.children.is_empty() {
367            result = PruneResult::Delete
368        } else if self.chunk.is_wild_impl() {
369            result = PruneResult::Wild
370        }
371        result
372    }
373}
374pub(crate) enum PruneResult {
375    Delete,
376    NonWild,
377    Wild,
378}
379
380impl<Weight, Wildness: IWildness, Children: IChildrenProvider<Box<Self>>> HasChunk
381    for KeyExprTreeNode<Weight, Wildness, Children>
382{
383    fn chunk(&self) -> &keyexpr {
384        &self.chunk
385    }
386}
387impl<Weight, Wildness: IWildness, Children: IChildrenProvider<Box<Self>>> AsRef<Self>
388    for KeyExprTreeNode<Weight, Wildness, Children>
389{
390    fn as_ref(&self) -> &Self {
391        self
392    }
393}
394impl<Weight, Wildness: IWildness, Children: IChildrenProvider<Box<Self>>> AsMut<Self>
395    for KeyExprTreeNode<Weight, Wildness, Children>
396{
397    fn as_mut(&mut self) -> &mut Self {
398        self
399    }
400}
401
402impl<
403        'a,
404        K: AsRef<keyexpr>,
405        Weight,
406        Wildness: IWildness,
407        Children: IChildrenProvider<Box<KeyExprTreeNode<Weight, Wildness, Children>>>,
408    > core::iter::FromIterator<(K, Weight)> for KeBoxTree<Weight, Wildness, Children>
409where
410    Self: IKeyExprTreeMut<'a, Weight>,
411{
412    fn from_iter<T: IntoIterator<Item = (K, Weight)>>(iter: T) -> Self {
413        let mut tree = Self::default();
414        for (key, value) in iter {
415            tree.insert(key.as_ref(), value);
416        }
417        tree
418    }
419}
zenoh_keyexpr/keyexpr_tree/box_tree.rs

zenoh_keyexpr/keyexpr_tree/
box_tree.rs
