maomi_tree/
lib.rs

1use std::{
2    cell::{Cell, RefCell},
3    fmt::Debug,
4    marker::PhantomData,
5    ops::{Deref, DerefMut},
6    rc::Rc,
7};
8
9// TODO try to detect memory leaks
10
11const SLICE_ITEMS: usize = 256;
12
13mod mem;
14use mem::{SliceAlloc, SliceRc, SliceWeak};
15
16struct ForestCtx<T> {
17    slice_alloc: RefCell<SliceAlloc<ForestRel<T>, SLICE_ITEMS>>,
18    ref_count: Cell<usize>,
19    mut_count: Cell<usize>,
20}
21
22impl<T> ForestCtx<T> {
23    pub fn new_node(self: &mut Rc<Self>, content: T) -> ForestNodeRc<T> {
24        let ctx = self.clone();
25        let slice = self.slice_alloc.borrow_mut().alloc(ForestRel {
26            ctx,
27            parent: None,
28            prev_sibling: None,
29            next_sibling: None,
30            first_child: None,
31            last_child: None,
32            content,
33        });
34        ForestNodeRc { inner: slice }
35    }
36}
37
38struct ForestRel<T> {
39    ctx: Rc<ForestCtx<T>>,
40    parent: Option<SliceWeak<ForestRel<T>, SLICE_ITEMS>>,
41    prev_sibling: Option<SliceWeak<ForestRel<T>, SLICE_ITEMS>>,
42    next_sibling: Option<SliceRc<ForestRel<T>, SLICE_ITEMS>>,
43    first_child: Option<SliceRc<ForestRel<T>, SLICE_ITEMS>>,
44    last_child: Option<SliceWeak<ForestRel<T>, SLICE_ITEMS>>,
45    content: T,
46}
47
48/// A node in a forest.
49pub struct ForestNodeRc<T> {
50    inner: SliceRc<ForestRel<T>, SLICE_ITEMS>,
51}
52
53impl<T> Clone for ForestNodeRc<T> {
54    #[inline]
55    fn clone(&self) -> Self {
56        Self {
57            inner: self.inner.clone(),
58        }
59    }
60}
61
62impl<T> ForestNodeRc<T> {
63    /// Create a node in a new forest.
64    #[inline]
65    pub fn new_forest(content: T) -> Self {
66        let mut ctx = Rc::new(ForestCtx {
67            slice_alloc: RefCell::new(SliceAlloc::new()),
68            ref_count: Cell::new(0),
69            mut_count: Cell::new(0),
70        });
71        ForestCtx::new_node(&mut ctx, content)
72    }
73
74    /// Get an immutable reference of the node.
75    ///
76    /// Returns `None` if already borrowed.
77    #[inline]
78    pub fn try_borrow<'a>(&'a self) -> Option<ForestNode<'a, T>> {
79        let inner = &self.inner;
80        let ctx = &unsafe { inner.data_ref() }.ctx;
81        if ctx.mut_count.get() > 0 {
82            None?;
83        }
84        ctx.ref_count.set(ctx.ref_count.get() + 1);
85        Some(ForestNode { inner })
86    }
87
88    /// Get an immutable reference of the node.
89    #[inline]
90    pub fn borrow<'a>(&'a self) -> ForestNode<'a, T> {
91        self.try_borrow().expect("Cannot borrow the forest node when a node has been mutably borrowed in the same forest")
92    }
93
94    /// Get a mutable reference of the tree root.
95    ///
96    /// Returns `None` if already borrowed.
97    #[inline]
98    pub fn try_borrow_mut<'a>(&'a self) -> Option<ForestNodeMut<'a, T>> {
99        let inner = self.inner.clone();
100        let ctx = &unsafe { inner.data_ref() }.ctx;
101        if ctx.ref_count.get() > 0 || ctx.mut_count.get() > 0 {
102            None?;
103        }
104        ctx.mut_count.set(1);
105        Some(ForestNodeMut {
106            inner,
107            _phantom: PhantomData,
108        })
109    }
110
111    /// Get a mutable reference of the tree root.
112    #[inline]
113    pub fn borrow_mut<'a>(&'a self) -> ForestNodeMut<'a, T> {
114        self.try_borrow_mut().expect(
115            "Cannot borrow the forest node when a node has been borrowed in the same forest",
116        )
117    }
118
119    /// Get a token.
120    #[inline]
121    pub fn token(&self) -> ForestToken {
122        ForestToken {
123            inner: self.inner.weak().leak(),
124        }
125    }
126
127    /// Check if two nodes are the same.
128    #[inline]
129    pub fn ptr_eq(&self, rhs: &Self) -> bool {
130        self.inner.mem() == rhs.inner.mem()
131    }
132}
133
134/// A stable memory address for a `ForestToken` .
135///
136/// Can be used as hash key.
137#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
138pub struct ForestTokenAddr(*const ());
139
140impl ForestTokenAddr {
141    /// Get a cloned token.
142    #[inline]
143    pub unsafe fn token(&self) -> ForestToken {
144        ForestToken {
145            inner: SliceWeak::clone_weak(self.0),
146        }
147    }
148
149    /// Get the underlying pointer.
150    #[inline]
151    pub fn ptr(&self) -> *const () {
152        self.0
153    }
154
155    /// Construct from a pointer.
156    #[inline]
157    pub unsafe fn from_ptr(ptr: *const ()) -> Self {
158        Self(ptr)
159    }
160}
161
162/// A static ref to a `ForestNodeRc<T>` .
163pub struct ForestToken {
164    inner: *const (),
165}
166
167impl Drop for ForestToken {
168    #[inline]
169    fn drop(&mut self) {
170        unsafe { SliceWeak::revoke_leaked(self.inner) };
171    }
172}
173
174impl Clone for ForestToken {
175    #[inline]
176    fn clone(&self) -> Self {
177        Self {
178            inner: unsafe { SliceWeak::clone_weak(self.inner) },
179        }
180    }
181}
182
183impl Debug for ForestToken {
184    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
185        f.debug_tuple("ForestToken").finish()
186    }
187}
188
189impl ForestToken {
190    /// Get the stable memory address (which can be used as hash key).
191    #[inline]
192    pub fn stable_addr(&self) -> ForestTokenAddr {
193        ForestTokenAddr(self.inner)
194    }
195
196    /// Resolve a token to a `ForestNodeRc` .
197    ///
198    /// It is unsafe if the `T` is not matched with the node which generates this token.
199    #[inline]
200    pub unsafe fn unsafe_resolve_token<'b, T>(&'b self) -> Option<ForestNodeRc<T>> {
201        let weak = SliceWeak::<ForestRel<T>, SLICE_ITEMS>::from_leaked(self.inner);
202        weak.clone().leak();
203        let rc = weak.rc()?;
204        Some(ForestNodeRc { inner: rc })
205    }
206}
207
208pub struct ForestNode<'a, T> {
209    inner: &'a SliceRc<ForestRel<T>, SLICE_ITEMS>,
210}
211
212impl<'a, T> Drop for ForestNode<'a, T> {
213    #[inline]
214    fn drop(&mut self) {
215        let ctx = &unsafe { self.inner.data_ref() }.ctx;
216        ctx.ref_count.set(ctx.ref_count.get() - 1);
217    }
218}
219
220impl<'a, T> Clone for ForestNode<'a, T> {
221    #[inline]
222    fn clone(&self) -> Self {
223        let ctx = &unsafe { self.inner.data_ref() }.ctx;
224        ctx.ref_count.set(ctx.ref_count.get() + 1);
225        Self { inner: self.inner }
226    }
227}
228
229impl<'a, T> Deref for ForestNode<'a, T> {
230    type Target = T;
231
232    #[inline]
233    fn deref(&self) -> &Self::Target {
234        &unsafe { self.inner.data_ref() }.content
235    }
236}
237
238impl<'a, T: Debug> Debug for ForestNode<'a, T> {
239    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
240        let content: &T = &**self;
241        write!(f, "ForestNode({:?}) [", content)?;
242        let mut cur = self.first_child();
243        if let Some(c) = cur {
244            write!(f, "{:?}", c)?;
245            cur = c.next_sibling();
246            while let Some(c) = cur {
247                write!(f, ", {:?}", c)?;
248                cur = c.next_sibling();
249            }
250        }
251        write!(f, "]")?;
252        Ok(())
253    }
254}
255
256impl<'a, T> ForestNode<'a, T> {
257    unsafe fn borrow_unchecked<'b>(
258        &self,
259        another: &'b SliceRc<ForestRel<T>, SLICE_ITEMS>,
260    ) -> ForestNode<'b, T> {
261        let ctx = &{ another.data_ref() }.ctx;
262        ctx.ref_count.set(ctx.ref_count.get() + 1);
263        ForestNode { inner: another }
264    }
265
266    /// Borrow another node in the same forest.
267    #[inline]
268    pub fn borrow<'b>(&self, target: &'b ForestNodeRc<T>) -> ForestNode<'b, T> {
269        unsafe {
270            if !Rc::ptr_eq(
271                &{ self.inner.data_ref() }.ctx,
272                &{ &*target.inner.data_ref() }.ctx,
273            ) {
274                panic!("The target node is not in the same forest")
275            }
276            self.borrow_unchecked(&target.inner)
277        }
278    }
279
280    /// Get the `ForestNodeRc` of current node.
281    #[inline]
282    pub fn rc(&self) -> ForestNodeRc<T> {
283        ForestNodeRc {
284            inner: self.inner.clone(),
285        }
286    }
287
288    /// Check if two nodes are the same.
289    #[inline]
290    pub fn ptr_eq(&self, rhs: &Self) -> bool {
291        self.inner.mem() == rhs.inner.mem()
292    }
293
294    /// Get the parent node.
295    #[inline]
296    pub fn parent_rc(&self) -> Option<ForestNodeRc<T>> {
297        let this = unsafe { self.inner.data_ref() };
298        this.parent
299            .as_ref()
300            .and_then(|x| x.rc())
301            .map(|x| ForestNodeRc { inner: x })
302    }
303
304    /// Get the next sibling node.
305    #[inline]
306    pub fn first_child_rc(&self) -> Option<ForestNodeRc<T>> {
307        let this = unsafe { self.inner.data_ref() };
308        this.first_child
309            .as_ref()
310            .map(|x| ForestNodeRc { inner: x.clone() })
311    }
312
313    /// Get the first child node.
314    #[inline]
315    pub fn first_child(&self) -> Option<ForestNode<'a, T>> {
316        let this = unsafe { self.inner.data_ref() };
317        this.first_child
318            .as_ref()
319            .map(|x| unsafe { self.borrow_unchecked(x) })
320    }
321
322    /// Get the last child node.
323    #[inline]
324    pub fn last_child_rc(&self) -> Option<ForestNodeRc<T>> {
325        let this = unsafe { self.inner.data_ref() };
326        this.last_child
327            .as_ref()
328            .and_then(|x| x.rc())
329            .map(|x| ForestNodeRc { inner: x })
330    }
331
332    /// Get the previous sibling node.
333    #[inline]
334    pub fn prev_sibling_rc(&self) -> Option<ForestNodeRc<T>> {
335        let this = unsafe { self.inner.data_ref() };
336        this.prev_sibling
337            .as_ref()
338            .and_then(|x| x.rc())
339            .map(|x| ForestNodeRc { inner: x })
340    }
341
342    /// Get the next sibling node.
343    #[inline]
344    pub fn next_sibling_rc(&self) -> Option<ForestNodeRc<T>> {
345        let this = unsafe { self.inner.data_ref() };
346        this.next_sibling
347            .as_ref()
348            .map(|x| ForestNodeRc { inner: x.clone() })
349    }
350
351    /// Get the next sibling node.
352    #[inline]
353    pub fn next_sibling(&self) -> Option<ForestNode<'a, T>> {
354        let this = unsafe { self.inner.data_ref() };
355        this.next_sibling
356            .as_ref()
357            .map(|x| unsafe { self.borrow_unchecked(x) })
358    }
359}
360
361pub struct ForestNodeMut<'a, T> {
362    inner: SliceRc<ForestRel<T>, SLICE_ITEMS>,
363    _phantom: PhantomData<&'a ()>,
364}
365
366impl<'a, T> Drop for ForestNodeMut<'a, T> {
367    #[inline]
368    fn drop(&mut self) {
369        let ctx = &unsafe { self.inner.data_ref() }.ctx;
370        ctx.mut_count.set(ctx.mut_count.get() - 1);
371    }
372}
373
374impl<'a, T> Deref for ForestNodeMut<'a, T> {
375    type Target = T;
376
377    #[inline]
378    fn deref(&self) -> &Self::Target {
379        &unsafe { self.inner.data_ref() }.content
380    }
381}
382
383impl<'a, T> DerefMut for ForestNodeMut<'a, T> {
384    #[inline]
385    fn deref_mut(&mut self) -> &mut Self::Target {
386        &mut unsafe { self.inner.data_mut() }.content
387    }
388}
389
390impl<'a, T: Debug> Debug for ForestNodeMut<'a, T> {
391    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
392        write!(f, "{:?}", self.as_ref())
393    }
394}
395
396impl<'a, T> ForestNodeMut<'a, T> {
397    unsafe fn borrow_mut_unchecked<'b>(
398        &'b self,
399        inner: &SliceRc<ForestRel<T>, SLICE_ITEMS>,
400    ) -> ForestNodeMut<'b, T> {
401        let ctx = &{ &*inner.data_ref() }.ctx;
402        ctx.mut_count.set(ctx.mut_count.get() + 1);
403        ForestNodeMut {
404            inner: inner.clone(),
405            _phantom: PhantomData,
406        }
407    }
408
409    /// Borrow another node in the same forest.
410    #[inline]
411    pub fn borrow_mut<'b>(&'b mut self, target: &'b ForestNodeRc<T>) -> ForestNodeMut<'b, T> {
412        unsafe {
413            if !Rc::ptr_eq(
414                &{ self.inner.data_ref() }.ctx,
415                &{ &*target.inner.data_ref() }.ctx,
416            ) {
417                panic!("The target node is not in the same forest")
418            }
419            self.borrow_mut_unchecked(&target.inner)
420        }
421    }
422
423    /// Resolve a token to a `ForestNodeRc` .
424    ///
425    /// The node which the token pointed to must be in the same forest and still has a valid `ForestNodeRc` .
426    #[inline]
427    pub fn resolve_token<'b>(&'b mut self, target: &ForestToken) -> Option<ForestNodeRc<T>> {
428        let weak = unsafe { SliceWeak::<ForestRel<T>, SLICE_ITEMS>::from_leaked(target.inner) };
429        weak.clone().leak();
430        let rc = weak.rc()?;
431        Some(ForestNodeRc { inner: rc })
432    }
433
434    /// Borrow another node with a token.
435    ///
436    /// The node which the token pointed to must be in the same forest and still has a valid `ForestNodeRc` .
437    #[inline]
438    pub fn borrow_mut_token<'b>(
439        &'b mut self,
440        target: &ForestToken,
441    ) -> Option<ForestNodeMut<'b, T>> {
442        let weak = unsafe { SliceWeak::<ForestRel<T>, SLICE_ITEMS>::from_leaked(target.inner) };
443        weak.clone().leak();
444        let rc = weak.rc()?;
445        Some(unsafe { self.borrow_mut_unchecked(&rc) })
446    }
447
448    /// Get an immutable reference.
449    #[inline]
450    pub fn as_ref<'b>(&'b self) -> ForestNode<'b, T> {
451        let ctx = &unsafe { self.inner.data_ref() }.ctx;
452        ctx.ref_count.set(ctx.ref_count.get() + 1);
453        ForestNode { inner: &self.inner }
454    }
455
456    /// Make a wrapped component the contained value, keeping the borrowing status.
457    #[inline]
458    pub fn map<'b, U>(
459        &'b mut self,
460        f: impl FnOnce(&'b mut T) -> &'b mut U,
461    ) -> ForestValueMut<'b, U> {
462        ForestValueMut { v: f(&mut **self) }
463    }
464
465    /// Get the `ForestNodeRc` of current node.
466    #[inline]
467    pub fn rc(&self) -> ForestNodeRc<T> {
468        ForestNodeRc {
469            inner: self.inner.clone(),
470        }
471    }
472
473    /// Get the parent node.
474    #[inline]
475    pub fn parent_rc(&self) -> Option<ForestNodeRc<T>> {
476        let this = unsafe { self.inner.data_ref() };
477        this.parent
478            .as_ref()
479            .and_then(|x| x.rc())
480            .map(|x| ForestNodeRc { inner: x })
481    }
482
483    /// Get the first child node.
484    #[inline]
485    pub fn first_child_rc(&mut self) -> Option<ForestNodeRc<T>> {
486        let this = unsafe { self.inner.data_ref() };
487        this.first_child
488            .as_ref()
489            .map(|x| ForestNodeRc { inner: x.clone() })
490    }
491
492    /// Get the first child node.
493    #[inline]
494    pub fn first_child_mut<'b>(&'b mut self) -> Option<ForestNodeMut<'b, T>> {
495        let this = unsafe { self.inner.data_ref() };
496        this.first_child
497            .as_ref()
498            .map(|x| unsafe { self.borrow_mut_unchecked(x) })
499    }
500
501    /// Get the last child node.
502    #[inline]
503    pub fn last_child_rc(&self) -> Option<ForestNodeRc<T>> {
504        let this = unsafe { self.inner.data_ref() };
505        this.last_child
506            .as_ref()
507            .and_then(|x| x.rc())
508            .map(|x| ForestNodeRc { inner: x })
509    }
510
511    /// Get the previous sibling node.
512    #[inline]
513    pub fn prev_sibling_rc(&self) -> Option<ForestNodeRc<T>> {
514        let this = unsafe { self.inner.data_ref() };
515        this.prev_sibling
516            .as_ref()
517            .and_then(|x| x.rc())
518            .map(|x| ForestNodeRc { inner: x })
519    }
520
521    /// Get the next sibling node.
522    #[inline]
523    pub fn next_sibling_rc(&mut self) -> Option<ForestNodeRc<T>> {
524        let this = unsafe { self.inner.data_ref() };
525        this.next_sibling
526            .as_ref()
527            .map(|x| ForestNodeRc { inner: x.clone() })
528    }
529
530    /// Get the next sibling node.
531    #[inline]
532    pub fn next_sibling_mut<'b>(&'b mut self) -> Option<ForestNodeMut<'b, T>> {
533        let this = unsafe { self.inner.data_ref() };
534        this.next_sibling
535            .as_ref()
536            .map(|x| unsafe { self.borrow_mut_unchecked(x) })
537    }
538
539    /// Create a new tree in the same forest.
540    #[inline]
541    pub fn new_tree(&mut self, content: T) -> ForestNodeRc<T> {
542        let ctx = &mut unsafe { self.inner.data_mut() }.ctx;
543        ctx.new_node(content)
544    }
545
546    fn check_insertion(
547        &self,
548        parent: &SliceWeak<ForestRel<T>, SLICE_ITEMS>,
549        target: &ForestNodeRc<T>,
550    ) {
551        let self_data = unsafe { self.inner.data_ref() };
552        let data = unsafe { &*target.inner.data_ref() };
553        if !Rc::ptr_eq(&self_data.ctx, &data.ctx) {
554            panic!("The child node is not in the same forest")
555        }
556        if data.parent.is_some() {
557            panic!("The child node already has a parent")
558        }
559        if target.inner.mem() == parent.mem() {
560            panic!("The child node is the same as the parent")
561        }
562    }
563
564    /// Append a tree as the last child node.
565    #[inline]
566    pub fn append(&mut self, target: &ForestNodeRc<T>) {
567        let parent_ptr = &self.inner;
568        self.check_insertion(&parent_ptr.weak(), target);
569        let parent = unsafe { &mut *parent_ptr.data_mut() };
570        let child_ptr = &target.inner;
571        let child = unsafe { &mut *child_ptr.data_mut() };
572        child.parent = Some(parent_ptr.weak());
573        if let Some(last_child_ptr) = &parent.last_child.as_ref().and_then(|x| x.rc()) {
574            let last_child = unsafe { &mut *last_child_ptr.data_mut() };
575            child.prev_sibling = Some(last_child_ptr.weak());
576            last_child.next_sibling = Some(child_ptr.clone());
577        } else {
578            parent.first_child = Some(child_ptr.clone());
579        }
580        parent.last_child = Some(child_ptr.weak());
581    }
582
583    /// Insert a tree as the previous sibling node of the current node.
584    #[inline]
585    pub fn insert(&mut self, target: &ForestNodeRc<T>) {
586        let before_ptr = &self.inner;
587        let before = unsafe { &mut *before_ptr.data_mut() };
588        let parent_ptr = match before.parent.as_ref() {
589            None => return,
590            Some(x) => x,
591        };
592        self.check_insertion(parent_ptr, target);
593        let parent_ptr = parent_ptr.rc();
594        let mut parent = parent_ptr.as_ref().map(|x| unsafe { &mut *x.data_mut() });
595        let child_ptr = &target.inner;
596        let child = unsafe { &mut *child_ptr.data_mut() };
597        child.parent = parent_ptr.as_ref().map(|x| x.weak());
598        match before.prev_sibling.as_ref() {
599            None => {
600                if let Some(parent) = &mut parent {
601                    parent.first_child = Some(child_ptr.clone());
602                }
603            }
604            Some(prev_ptr) => {
605                if let Some(prev_ptr) = prev_ptr.rc() {
606                    let prev = unsafe { &mut *prev_ptr.data_mut() };
607                    prev.next_sibling = Some(child_ptr.clone());
608                }
609            }
610        }
611        child.prev_sibling = before.prev_sibling.take();
612        child.next_sibling = Some(before_ptr.clone());
613        before.prev_sibling = Some(child_ptr.weak());
614    }
615
616    /// Remove the node from its parent node.
617    #[inline]
618    pub fn detach(self) -> ForestNodeRc<T> {
619        let child_ptr = self.inner.clone();
620        let child = unsafe { &mut *child_ptr.data_mut() };
621        let parent_ptr = child.parent.as_ref().and_then(|x| x.rc());
622        let mut parent = parent_ptr.as_ref().map(|x| unsafe { &mut *x.data_mut() });
623        let prev_ptr = child.prev_sibling.as_ref();
624        let next_ptr = child.next_sibling.as_ref();
625        match &next_ptr {
626            None => {
627                if let Some(parent) = &mut parent {
628                    parent.last_child = prev_ptr.cloned();
629                }
630            }
631            Some(next_ptr) => {
632                let next = unsafe { &mut *next_ptr.data_mut() };
633                next.prev_sibling = prev_ptr.cloned();
634            }
635        }
636        match prev_ptr {
637            None => {
638                if let Some(parent) = &mut parent {
639                    parent.first_child = next_ptr.cloned();
640                }
641            }
642            Some(prev_ptr) => {
643                if let Some(prev_ptr) = prev_ptr.rc() {
644                    let prev = unsafe { &mut *prev_ptr.data_mut() };
645                    prev.next_sibling = next_ptr.cloned();
646                }
647            }
648        }
649        child.parent = None;
650        child.prev_sibling = None;
651        child.next_sibling = None;
652        ForestNodeRc { inner: child_ptr }
653    }
654}
655
656pub struct ForestValue<'a, T> {
657    v: &'a T,
658}
659
660impl<'a, T> Deref for ForestValue<'a, T> {
661    type Target = T;
662
663    fn deref(&self) -> &Self::Target {
664        self.v
665    }
666}
667
668impl<'a, T> ForestValue<'a, T> {
669    #[inline]
670    pub fn map<U>(&'a self, f: impl FnOnce(&'a T) -> &'a U) -> ForestValue<'a, U> {
671        ForestValue { v: f(self.v) }
672    }
673}
674
675pub struct ForestValueMut<'a, T> {
676    v: &'a mut T,
677}
678
679impl<'a, T> Deref for ForestValueMut<'a, T> {
680    type Target = T;
681
682    fn deref(&self) -> &Self::Target {
683        self.v
684    }
685}
686
687impl<'a, T> DerefMut for ForestValueMut<'a, T> {
688    fn deref_mut(&mut self) -> &mut Self::Target {
689        &mut self.v
690    }
691}
692
693impl<'a, T> ForestValueMut<'a, T> {
694    #[inline]
695    pub fn as_ref<'b>(&'b self) -> ForestValue<'b, T> {
696        ForestValue { v: self.v }
697    }
698
699    #[inline]
700    pub fn map<'b, U>(
701        &'b mut self,
702        f: impl FnOnce(&'b mut T) -> &'b mut U,
703    ) -> ForestValueMut<'b, U> {
704        ForestValueMut { v: f(self.v) }
705    }
706}
707
708#[cfg(test)]
709mod test {
710    use super::*;
711
712    struct DropTest {
713        v: usize,
714        dropped: bool,
715    }
716
717    impl Debug for DropTest {
718        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
719            write!(f, "{:?}", self.v)
720        }
721    }
722
723    impl Drop for DropTest {
724        fn drop(&mut self) {
725            assert_eq!(self.dropped, false);
726            self.dropped = true;
727        }
728    }
729
730    impl From<usize> for DropTest {
731        fn from(v: usize) -> Self {
732            Self { v, dropped: false }
733        }
734    }
735
736    fn check_pointers(tree: &ForestNode<DropTest>) {
737        fn rec(node: &ForestNode<DropTest>) {
738            let mut prev = None;
739            let mut cur_option = node.first_child();
740            while let Some(cur) = cur_option {
741                assert!(cur.parent_rc().as_ref().unwrap().ptr_eq(&node.rc()));
742                if let Some(prev) = prev.as_ref() {
743                    assert!(cur.prev_sibling_rc().unwrap().ptr_eq(&prev));
744                } else {
745                    assert!(cur.prev_sibling_rc().is_none())
746                }
747                rec(&cur);
748                assert_eq!(cur.dropped, false);
749                prev = Some(cur.rc());
750                cur_option = cur.next_sibling();
751            }
752            if let Some(prev) = prev.as_ref() {
753                assert!(node.last_child_rc().unwrap().ptr_eq(&prev));
754            } else {
755                assert!(node.last_child_rc().is_none())
756            }
757        }
758        assert!(tree.parent_rc().is_none());
759        assert!(tree.next_sibling().is_none());
760        assert!(tree.prev_sibling_rc().is_none());
761        rec(&tree);
762    }
763
764    #[test]
765    fn append() {
766        let tree: ForestNodeRc<DropTest> = ForestNodeRc::new_forest(1.into());
767        {
768            let mut n1 = tree.borrow_mut();
769            let n2 = n1.new_tree(2.into());
770            {
771                let mut n2 = n1.borrow_mut(&n2);
772                let n3 = n2.new_tree(3.into());
773                n2.append(&n3);
774                let n4 = n2.new_tree(4.into());
775                n2.append(&n4);
776            }
777            n1.append(&n2);
778            assert_eq!(
779                format!("{:?}", n1),
780                r#"ForestNode(1) [ForestNode(2) [ForestNode(3) [], ForestNode(4) []]]"#
781            );
782        }
783        check_pointers(&tree.borrow());
784    }
785
786    #[test]
787    fn insert() {
788        let tree: ForestNodeRc<DropTest> = ForestNodeRc::new_forest(1.into());
789        {
790            let mut n1 = tree.borrow_mut();
791            let n2 = n1.new_tree(2.into());
792            {
793                let mut n2 = n1.borrow_mut(&n2);
794                let n3 = n2.new_tree(3.into());
795                n2.append(&n3);
796                let n4 = n2.new_tree(4.into());
797                n2.first_child_mut().unwrap().insert(&n4);
798                let n5 = n2.new_tree(5.into());
799                n2.first_child_mut()
800                    .unwrap()
801                    .next_sibling_mut()
802                    .unwrap()
803                    .insert(&n5);
804            }
805            n1.append(&n2);
806            assert_eq!(
807                format!("{:?}", n1),
808                r#"ForestNode(1) [ForestNode(2) [ForestNode(4) [], ForestNode(5) [], ForestNode(3) []]]"#
809            );
810        }
811        check_pointers(&tree.borrow());
812    }
813
814    #[test]
815    fn detach() {
816        let tree: ForestNodeRc<DropTest> = ForestNodeRc::new_forest(1.into());
817        {
818            let mut n1 = tree.borrow_mut();
819            let n2 = n1.new_tree(2.into());
820            {
821                let mut n2 = n1.borrow_mut(&n2);
822                let n3 = n2.new_tree(3.into());
823                n2.append(&n3);
824                let n4 = n2.new_tree(4.into());
825                n2.append(&n4);
826                let n5 = n2.new_tree(5.into());
827                n2.append(&n5);
828            }
829            n1.append(&n2);
830            assert_eq!(
831                format!("{:?}", n1),
832                r#"ForestNode(1) [ForestNode(2) [ForestNode(3) [], ForestNode(4) [], ForestNode(5) []]]"#
833            );
834            {
835                let n4 = {
836                    let mut n2 = n1.first_child_mut().unwrap();
837                    let mut n3 = n2.first_child_mut().unwrap();
838                    let n4 = n3.next_sibling_mut().unwrap();
839                    n4.detach()
840                };
841                assert_eq!(format!("{:?}", n1.borrow_mut(&n4)), r#"ForestNode(4) []"#);
842            }
843            assert_eq!(
844                format!("{:?}", n1),
845                r#"ForestNode(1) [ForestNode(2) [ForestNode(3) [], ForestNode(5) []]]"#
846            );
847            {
848                let n2 = {
849                    let n2 = n1.first_child_mut().unwrap();
850                    n2.detach()
851                };
852                assert_eq!(
853                    format!("{:?}", n1.borrow_mut(&n2)),
854                    r#"ForestNode(2) [ForestNode(3) [], ForestNode(5) []]"#
855                );
856            }
857            assert_eq!(format!("{:?}", n1), r#"ForestNode(1) []"#);
858        }
859        check_pointers(&tree.borrow());
860    }
861}
maomi_tree/lib.rs

maomi_tree/
lib.rs
