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

zenoh_keyexpr/keyexpr_tree/
box_tree.rs
