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            // SAFETY: upheld by the surrounding invariants and prior validation.
162            let chunk = unsafe { core::mem::transmute::<&keyexpr, &keyexpr>(node.chunk()) };
163            match node.parent {
164                None => &mut self.children,
165                // SAFETY: upheld by the surrounding invariants and prior validation.
166                Some(parent) => unsafe { &mut (*parent.as_ptr()).children },
167            }
168            .remove(chunk)
169            .and_then(|node| node.weight)
170        }
171    }
172
173    fn node_mut_or_create<'b>(&'b mut self, at: &keyexpr) -> &'b mut Self::Node {
174        if at.is_wild_impl() {
175            self.wildness.set(true);
176        }
177        let mut chunks = at.chunks_impl();
178        let mut node = self
179            .children
180            .entry(chunks.next().unwrap())
181            .get_or_insert_with(move |k| {
182                Box::new(KeyExprTreeNode {
183                    parent: None,
184                    chunk: k.into(),
185                    children: Default::default(),
186                    weight: None,
187                })
188            });
189        for chunk in chunks {
190            let parent = NonNull::from(node.as_ref());
191            node = node.children.entry(chunk).get_or_insert_with(move |k| {
192                Box::new(KeyExprTreeNode {
193                    parent: Some(parent),
194                    chunk: k.into(),
195                    children: Default::default(),
196                    weight: None,
197                })
198            })
199        }
200        node
201    }
202    type TreeIterItemMut = <Self::TreeIterMut as Iterator>::Item;
203    type TreeIterMut =
204        TreeIterMut<'a, Children, Box<KeyExprTreeNode<Weight, Wildness, Children>>, Weight>;
205    fn tree_iter_mut(&'a mut self) -> Self::TreeIterMut {
206        TreeIterMut::new(&mut self.children)
207    }
208
209    type IntersectionItemMut = <Self::IntersectionMut as Iterator>::Item;
210    type IntersectionMut = IterOrOption<
211        IntersectionMut<'a, Children, Box<KeyExprTreeNode<Weight, Wildness, Children>>, Weight>,
212        &'a mut Self::Node,
213    >;
214    fn intersecting_nodes_mut(&'a mut self, ke: &'a keyexpr) -> Self::IntersectionMut {
215        if self.wildness.get() || ke.is_wild_impl() {
216            IntersectionMut::new(&mut self.children, ke).into()
217        } else {
218            let node = self.node_mut(ke);
219            IterOrOption::Opt(node)
220        }
221    }
222    type InclusionItemMut = <Self::InclusionMut as Iterator>::Item;
223    type InclusionMut = IterOrOption<
224        InclusionMut<'a, Children, Box<KeyExprTreeNode<Weight, Wildness, Children>>, Weight>,
225        &'a mut Self::Node,
226    >;
227    fn included_nodes_mut(&'a mut self, ke: &'a keyexpr) -> Self::InclusionMut {
228        if self.wildness.get() || ke.is_wild_impl() {
229            InclusionMut::new(&mut self.children, ke).into()
230        } else {
231            let node = self.node_mut(ke);
232            IterOrOption::Opt(node)
233        }
234    }
235    type IncluderItemMut = <Self::IncluderMut as Iterator>::Item;
236    type IncluderMut = IterOrOption<
237        IncluderMut<'a, Children, Box<KeyExprTreeNode<Weight, Wildness, Children>>, Weight>,
238        &'a mut Self::Node,
239    >;
240    fn nodes_including_mut(&'a mut self, ke: &'a keyexpr) -> Self::IncluderMut {
241        if self.wildness.get() || ke.is_wild_impl() {
242            IncluderMut::new(&mut self.children, ke).into()
243        } else {
244            let node = self.node_mut(ke);
245            IterOrOption::Opt(node)
246        }
247    }
248
249    fn prune_where<F: FnMut(&mut Self::Node) -> bool>(&mut self, mut predicate: F) {
250        let mut wild = false;
251        self.children
252            .filter_out(&mut |child| match child.as_mut().prune(&mut predicate) {
253                PruneResult::Delete => true,
254                PruneResult::NonWild => false,
255                PruneResult::Wild => {
256                    wild = true;
257                    false
258                }
259            });
260        self.wildness.set(wild);
261    }
262}
263
264#[repr(C)]
265pub struct KeyExprTreeNode<Weight, Wildness: IWildness, Children: IChildrenProvider<Box<Self>>> {
266    parent: Option<NonNull<Self>>,
267    chunk: OwnedKeyExpr,
268    children: Children::Assoc,
269    weight: Option<Weight>,
270}
271
272unsafe impl<Weight: Send, Wildness: IWildness + Send, Children: IChildrenProvider<Box<Self>> + Send>
273    Send for KeyExprTreeNode<Weight, Wildness, Children>
274{
275}
276unsafe impl<Weight: Sync, Wildness: IWildness + Sync, Children: IChildrenProvider<Box<Self>> + Sync>
277    Sync for KeyExprTreeNode<Weight, Wildness, Children>
278{
279}
280
281impl<Weight, Wildness: IWildness, Children: IChildrenProvider<Box<Self>>> IKeyExprTreeNode<Weight>
282    for KeyExprTreeNode<Weight, Wildness, Children>
283where
284    Children::Assoc: IChildren<Box<Self>>,
285{
286}
287impl<Weight, Wildness: IWildness, Children: IChildrenProvider<Box<Self>>> UIKeyExprTreeNode<Weight>
288    for KeyExprTreeNode<Weight, Wildness, Children>
289where
290    Children::Assoc: IChildren<Box<Self>>,
291{
292    type Parent = Self;
293    /// # Safety
294    /// Callers must uphold the invariants required by this unsafe API.
295    unsafe fn __parent(&self) -> Option<&Self> {
296        // SAFETY: upheld by the surrounding invariants and prior validation.
297        self.parent.as_ref().map(|node| unsafe {
298            // this is safe, as a mutable reference to the parent was needed to get a mutable reference to this node in the first place.
299            node.as_ref()
300        })
301    }
302    /// # Safety
303    /// Callers must uphold the invariants required by this unsafe API.
304    unsafe fn __keyexpr(&self) -> OwnedKeyExpr {
305        // SAFETY: upheld by the surrounding invariants and prior validation.
306        unsafe {
307            // self._keyexpr is guaranteed to return a valid KE, so no checks are necessary
308            OwnedKeyExpr::from_string_unchecked(self._keyexpr(0))
309        }
310    }
311    /// # Safety
312    /// Callers must uphold the invariants required by this unsafe API.
313    unsafe fn __weight(&self) -> Option<&Weight> {
314        self.weight.as_ref()
315    }
316    type Child = Box<Self>;
317    type Children = Children::Assoc;
318
319    /// # Safety
320    /// Callers must uphold the invariants required by this unsafe API.
321    unsafe fn __children(&self) -> &Self::Children {
322        &self.children
323    }
324}
325impl<Weight, Wildness: IWildness, Children: IChildrenProvider<Box<Self>>>
326    IKeyExprTreeNodeMut<Weight> for KeyExprTreeNode<Weight, Wildness, Children>
327where
328    Children::Assoc: IChildren<Box<Self>>,
329{
330    fn parent_mut(&mut self) -> Option<&mut Self> {
331        match &mut self.parent {
332            None => None,
333            // SAFETY: upheld by the surrounding invariants and prior validation.
334            Some(node) => Some(unsafe {
335                // this is safe, as a mutable reference to the parent was needed to get a mutable reference to this node in the first place.
336                node.as_mut()
337            }),
338        }
339    }
340    fn weight_mut(&mut self) -> Option<&mut Weight> {
341        self.weight.as_mut()
342    }
343    fn take_weight(&mut self) -> Option<Weight> {
344        self.weight.take()
345    }
346    fn insert_weight(&mut self, weight: Weight) -> Option<Weight> {
347        self.weight.replace(weight)
348    }
349
350    fn children_mut(&mut self) -> &mut Self::Children {
351        &mut self.children
352    }
353}
354
355impl<Weight, Wildness: IWildness, Children: IChildrenProvider<Box<Self>>>
356    KeyExprTreeNode<Weight, Wildness, Children>
357where
358    Children::Assoc: IChildren<Box<Self>>,
359{
360    fn _keyexpr(&self, capacity: usize) -> String {
361        let mut s = match self.parent() {
362            Some(parent) => parent._keyexpr(capacity + self.chunk.len() + 1) + "/",
363            None => String::with_capacity(capacity + self.chunk.len()),
364        };
365        s.push_str(self.chunk.as_str());
366        s
367    }
368    fn prune<F: FnMut(&mut Self) -> bool>(&mut self, predicate: &mut F) -> PruneResult {
369        let mut result = PruneResult::NonWild;
370        self.children
371            .filter_out(&mut |child| match child.as_node_mut().prune(predicate) {
372                PruneResult::Delete => true,
373                PruneResult::NonWild => false,
374                PruneResult::Wild => {
375                    result = PruneResult::Wild;
376                    false
377                }
378            });
379        if predicate(self) && self.children.is_empty() {
380            result = PruneResult::Delete
381        } else if self.chunk.is_wild_impl() {
382            result = PruneResult::Wild
383        }
384        result
385    }
386}
387pub(crate) enum PruneResult {
388    Delete,
389    NonWild,
390    Wild,
391}
392
393impl<Weight, Wildness: IWildness, Children: IChildrenProvider<Box<Self>>> HasChunk
394    for KeyExprTreeNode<Weight, Wildness, Children>
395{
396    fn chunk(&self) -> &keyexpr {
397        &self.chunk
398    }
399}
400impl<Weight, Wildness: IWildness, Children: IChildrenProvider<Box<Self>>> AsRef<Self>
401    for KeyExprTreeNode<Weight, Wildness, Children>
402{
403    fn as_ref(&self) -> &Self {
404        self
405    }
406}
407impl<Weight, Wildness: IWildness, Children: IChildrenProvider<Box<Self>>> AsMut<Self>
408    for KeyExprTreeNode<Weight, Wildness, Children>
409{
410    fn as_mut(&mut self) -> &mut Self {
411        self
412    }
413}
414
415impl<
416        'a,
417        K: AsRef<keyexpr>,
418        Weight,
419        Wildness: IWildness,
420        Children: IChildrenProvider<Box<KeyExprTreeNode<Weight, Wildness, Children>>>,
421    > core::iter::FromIterator<(K, Weight)> for KeBoxTree<Weight, Wildness, Children>
422where
423    Self: IKeyExprTreeMut<'a, Weight>,
424{
425    fn from_iter<T: IntoIterator<Item = (K, Weight)>>(iter: T) -> Self {
426        let mut tree = Self::default();
427        for (key, value) in iter {
428            tree.insert(key.as_ref(), value);
429        }
430        tree
431    }
432}
zenoh_keyexpr/keyexpr_tree/box_tree.rs

zenoh_keyexpr/keyexpr_tree/
box_tree.rs
