rtable/
tree.rs

1//
2// Routing Table
3//   Copyright (C) 2019,2020 Toshiaki Takada
4//
5
6use std::cell::RefCell;
7use std::cell::RefMut;
8use std::rc::Rc;
9use std::iter::Iterator;
10use std::iter::IntoIterator;
11
12use super::prefix::*;
13
14///
15/// Tree struct.
16///
17pub struct Tree<P: Prefixable, D> {
18    /// Top Node.
19    top: Option<Rc<Node<P, D>>>,
20
21    /// Number of node in this tree.
22    count: usize,
23}
24
25/// Utility function to check prefix match this node.
26fn node_match_prefix<P: Prefixable, D>(curr: Option<Rc<Node<P, D>>>, prefix: &P) -> bool {
27    match curr {
28        None => false,
29        Some(node) => {
30            node.prefix.len() <= prefix.len() && node.prefix().contains(prefix)
31        }
32    }
33}
34
35fn same_object<T>(a: *const T, b: *const T) -> bool {
36    a == b
37}
38
39///
40/// Tree impl.
41///
42impl<P: Prefixable, D> Tree<P, D> {
43    /// Constructor.
44    pub fn new() -> Tree<P, D> {
45        Tree {
46            top: None,
47            count: 0usize,
48        }
49    }
50
51    /// Return top node.
52    pub fn top(&self) -> Option<Rc<Node<P, D>>> {
53        self.top.clone()
54    }
55
56    /// Return count with data.
57    pub fn count(&self) -> usize {
58        self.count
59    }
60
61    /// Get node with given prefix, create one if it doesn't exist.
62    pub fn get_node(&mut self, prefix: &P) -> NodeIterator<P, D> {
63        self.get_node_ctor(prefix, None::<Box<dyn Fn() -> D>>)
64    }
65
66    /// Get node with given prefix, create one if it doesn't exist.
67    /// And also construct 'D' with given constructor.
68    pub fn get_node_ctor<F>(&mut self, prefix: &P, ctor: Option<F>) -> NodeIterator<P, D>
69        where F: Fn() -> D
70    {
71        let mut matched: Option<Rc<Node<P, D>>> = None;
72        let mut curr: Option<Rc<Node<P, D>>> = self.top.clone();
73        let mut new_node: Rc<Node<P, D>>;
74
75        while node_match_prefix(curr.clone(), prefix) {
76            let node = curr.clone().unwrap();
77            if node.prefix().len() == prefix.len() {
78                return NodeIterator::from_node(node)
79            }
80
81            matched = Some(node.clone());
82            curr = node.child_with(prefix.bit_at(node.prefix().len()));
83        }
84
85        match curr.clone() {
86            None => {
87                new_node = Rc::new(Node::new(prefix));
88                match matched {
89                    Some(node) => {
90                        Node::<P, D>::set_child(node, new_node.clone());
91                    },
92                    None => {
93                        self.top.replace(new_node.clone());
94                    }
95                }
96
97            },
98            Some(node) => {
99                new_node = Rc::new(Node::from_common(node.prefix(), prefix));
100                Node::<P, D>::set_child(new_node.clone(), node);
101
102                match matched {
103                    Some(node) => {
104                        Node::<P, D>::set_child(node, new_node.clone());
105                    },
106                    None => {
107                        self.top.replace(new_node.clone());
108                    }
109                }
110
111                if new_node.prefix().len() != prefix.len() {
112                    matched = Some(new_node.clone());
113                    new_node = Rc::new(Node::new(prefix));
114                    Node::<P, D>::set_child(matched.unwrap().clone(), new_node.clone());
115                }
116            }
117        }
118
119        if let Some(ctor) = ctor {
120            new_node.set_data(ctor());
121        }
122        NodeIterator::from_node(new_node)
123    }
124
125    /// Insert data with given prefix, and return:
126    /// - Some(data) if data already exist with the prefix.
127    /// - None if successfully inserted the data.
128    pub fn insert(&mut self, prefix: &P, data: D) -> Option<D> {
129        let it = self.lookup_exact(prefix);
130        match it.node() {
131            Some(node) => {
132                if node.has_data() {
133                    Some(data)
134                }
135                else {
136                    node.set_data(data);
137                    self.count += 1;
138                    None
139                }
140            },
141            None => {
142                let mut it = self.get_node(prefix);
143                it.set_data(data);
144                self.count += 1;
145                None
146            }
147        }
148    }
149
150    /// Update data with given prefix, and return:
151    /// - old data if data exists and successfully replace.
152    /// - None if data does not exist, and replace does not occur.
153    pub fn update(&mut self, prefix: &P, data: D) -> Option<D> {
154        let it = self.lookup_exact(prefix);
155        match it.node() {
156            Some(node) => {
157                if node.has_data() {
158                    node.set_data(data)
159                }
160                else {
161                    None
162                }
163            },
164            None => None,
165        }
166    }
167
168    /// Insert if data does not exist, or Update, and return:
169    /// - old data if data exists and successfully replace.
170    /// - None if data does not exist.
171    pub fn upsert(&mut self, prefix: &P, data: D) -> Option<D> {
172        let it = self.lookup_exact(prefix);
173        match it.node() {
174            Some(node) => {
175                if !node.has_data() {
176                    self.count += 1;
177                }
178                node.set_data(data)
179            },
180            None => {
181                self.get_node(prefix).set_data(data);
182                self.count += 1;
183                None
184            }
185        }
186    }
187
188    /// Delete data with the prefix if data exist, and return:
189    /// - old data if data exists and successfully delete.
190    /// - None if data does not exist.
191    pub fn delete(&mut self, prefix: &P) -> Option<D> {
192        let it = self.lookup_exact(prefix);
193        let old_data = match it.node() {
194            Some(node) => {
195                if node.has_data() {
196                    self.count -= 1;
197                }
198                node.unset_data()
199            },
200            None => None,
201        };
202        self.erase(it);
203        old_data
204    }
205
206    /// Perform exact match lookup.
207    pub fn lookup_exact(&self, prefix: &P) -> NodeIterator<P, D> {
208        let mut curr = self.top.clone();
209
210        while node_match_prefix(curr.clone(), prefix) {
211            let node = curr.clone().unwrap();
212            if node.prefix().len() == prefix.len() {
213                if node.has_data() {
214                    return NodeIterator::from_node(node)
215                }
216                else {
217                    break;
218                }
219            }
220
221            curr = node.child_with(prefix.bit_at(node.prefix().len()));
222        }
223
224        NodeIterator { node: None }
225    }
226
227    /// Perform longest match lookup.
228    pub fn lookup(&self, prefix: &P) -> NodeIterator<P, D> {
229        let mut curr = self.top.clone();
230        let mut matched: Option<Rc<Node<P, D>>> = None;
231
232        while node_match_prefix(curr.clone(), prefix) {
233            let node = curr.clone().unwrap();
234            if node.has_data() {
235                matched = Some(node.clone());
236            }
237
238            if node.prefix().len() == prefix.len() {
239                break;
240            }
241
242            curr = node.child_with(prefix.bit_at(node.prefix().len()));
243        }
244
245        if matched.is_some() {
246            NodeIterator::from_node(matched.unwrap())
247        }
248        else {
249            NodeIterator { node: None }
250        }
251    }
252
253    /// Erase a node from tree, and return iterator for next node.
254    pub fn erase(&mut self, it: NodeIterator<P, D>) -> NodeIterator<P, D> {
255        let curr = it.node();
256        let next = match curr {
257            Some(node) => node.next(),
258            None => None
259        };
260
261        if let Some(target) = curr {
262            let has_left = target.child(Child::Left).is_some();
263            let has_right = target.child(Child::Right).is_some();
264
265            // if the node has both children, we cannot erase, this is error situation.
266            if has_left && has_right {
267                return NodeIterator { node: None }
268            }
269
270            let child = if has_left {
271                target.children[Child::Left as usize].replace(None)
272            } else {
273                target.children[Child::Right as usize].replace(None)
274            };
275
276            let parent = target.parent().clone();
277            if child.is_some() {
278                match parent {
279                    Some(parent) => child.clone().unwrap().set_parent(parent.clone()),
280                    None => child.clone().unwrap().unset_parent()
281                }
282            }
283
284            let parent = target.parent().clone();
285            match parent {
286                Some(node) => {
287                    // TODO: refactoring.
288                    let bit = if node.has_child_with(Child::Left as u8) && same_object(node.child(Child::Left).unwrap().as_ref(), target.as_ref()) {
289                        Child::Left
290                    } else {
291                        Child::Right
292                    };
293
294                    match child {
295                        None => node.unset_child_at(bit as u8),
296                        Some(child) => node.set_child_at(child, bit as u8),
297                    }
298                },
299                None => {
300                    self.top = child.clone();
301                }
302            }
303
304            let parent = target.parent().clone();
305            if parent.is_some() {
306                let node = parent.clone().unwrap();
307                if !node.is_locked() {
308                    self.erase(NodeIterator { node: parent });
309                }
310            }
311        }
312
313        return NodeIterator { node: next }
314    }
315
316    /// Return node iterator.
317    pub fn node_iter(&self) -> NodeIterator<P, D> {
318        NodeIterator::<P, D> {
319            node: self.top.clone()
320        }
321    }
322}
323
324///
325/// Tree IntoIterator.
326///
327impl<P: Prefixable, D> IntoIterator for &Tree<P, D> {
328    type Item = Rc<Node<P, D>>;
329    type IntoIter = DataIterator<P, D>;
330
331    fn into_iter(self) -> Self::IntoIter {
332        let top = self.top.clone();
333
334        DataIterator::<P, D> {
335            node: top,
336        }
337    }
338}
339
340/// NodeIterator.
341pub struct NodeIterator<P: Prefixable, D> {
342    node: Option<Rc<Node<P, D>>>,
343}
344
345/// Impl NodeIterator.
346impl<P: Prefixable, D> NodeIterator<P, D> {
347    pub fn from_node(node: Rc<Node<P, D>>) -> NodeIterator<P, D> {
348        NodeIterator::<P, D> {
349            node: Some(node.clone())
350        }
351    }
352
353    pub fn node(&self) -> &Option<Rc<Node<P, D>>> {
354        &self.node
355    }
356
357    pub fn set_data(&mut self, data: D) {
358        let node = self.node.clone();
359        match node {
360            Some(node) => node.set_data(data),
361            None => None
362        };
363    }
364}
365
366/// Impl Iterator for NodeIterator.
367impl<P: Prefixable, D> Iterator for NodeIterator<P, D> {
368    type Item = Rc<Node<P, D>>;
369    fn next(&mut self) -> Option<Rc<Node<P, D>>> {
370        let node = self.node.clone();
371        match node {
372            Some(node) => {
373                self.node = node.next().clone();
374                Some(node)
375            },
376            None => None
377        }
378    }
379}
380
381/// DataIterator, only iterate node with data.
382pub struct DataIterator<P: Prefixable, D> {
383    node: Option<Rc<Node<P, D>>>,
384}
385
386/// Impl DataIterator.
387impl<P: Prefixable, D> DataIterator<P, D> {
388    pub fn node(&self) -> &Option<Rc<Node<P, D>>> {
389        &self.node
390    }
391}
392
393/// Impl Iterator for DataIterator.
394impl<P: Prefixable, D> Iterator for DataIterator<P, D> {
395    type Item = Rc<Node<P, D>>;
396    fn next(&mut self) -> Option<Rc<Node<P, D>>> {
397        let node = self.node.clone();
398        match node {
399            Some(node) => {
400                if !node.has_data() {
401                    let node = node.next_with_data().clone();
402                    match node {
403                        Some(node) => {
404                            self.node = node.next_with_data().clone();
405                            Some(node)
406                        },
407                        None => return None
408                    }
409                }
410                else {
411                    self.node = node.next_with_data().clone();
412                    Some(node)
413                }
414            },
415            None => None
416        }
417    }
418}
419
420///
421/// Enum Child.
422///
423pub enum Child {
424    Left = 0,
425    Right = 1,
426}
427
428///
429/// Node struct.
430///
431pub struct Node<P: Prefixable, D> {
432    /// Parent Node.
433    parent: RefCell<Option<Rc<Node<P, D>>>>,
434
435    /// Child Nodes.
436    children: [RefCell<Option<Rc<Node<P, D>>>>; 2],
437
438    /// Prefix associated with this node.
439    prefix: P,
440
441    /// Data.
442    data: RefCell<Option<D>>,
443}
444
445///
446/// Node impl.
447///
448impl<P: Prefixable, D> Node<P, D> {
449    /// Return new node.
450    pub fn new(prefix: &P) -> Node<P, D> {
451        Node {
452            parent: RefCell::new(None),
453            children: [RefCell::new(None), RefCell::new(None)],
454            prefix: P::from_prefix(prefix),
455            data: RefCell::new(None),
456        }
457    }
458
459    /// Return new node with common prefix.
460    pub fn from_common(prefix1: &P, prefix2: &P) -> Node<P, D> {
461        let pcommon = P::from_common(prefix1, prefix2);
462        Self::new(&pcommon)
463    }
464
465    /// Return reference to prefix.
466    pub fn prefix(&self) -> &P {
467        &self.prefix
468    }
469
470    /// Return one of child node - left(0) or right(1)
471    pub fn child(&self, bit: Child) -> Option<Rc<Node<P, D>>> {
472        self.children[bit as usize].borrow_mut().clone()
473    }
474
475    /// Return one of child node - left(0) or right(1)
476    pub fn child_with(&self, bit: u8) -> Option<Rc<Node<P, D>>> {
477        self.children[bit as usize].borrow_mut().clone()
478    }
479
480    /// Return true if child at left or right.
481    pub fn has_child_with(&self, bit: u8) -> bool {
482        if let Some(ref _node) = *self.children[bit as usize].borrow_mut() {
483            true
484        }
485        else {
486            false
487        }
488    }
489
490    /// Return parent node.
491    pub fn parent(&self) -> Option<Rc<Node<P, D>>> {
492        self.parent.borrow_mut().clone()
493    }
494
495    /// Set given node as a child at left or right
496    fn set_child(parent: Rc<Node<P, D>>, child: Rc<Node<P, D>>) {
497        let bit = child.prefix().bit_at(parent.prefix().len());
498        parent.set_child_at(child.clone(), bit);
499        child.set_parent(parent.clone());
500    }
501
502    /// Set child at left or right.
503    fn set_child_at(&self, child: Rc<Node<P, D>>, bit: u8) {
504        self.children[bit as usize].borrow_mut().replace(child.clone());
505    }
506
507    /// Unset child at left or fight.
508    fn unset_child_at(&self, bit: u8) {
509        self.children[bit as usize].replace(None);
510    }
511
512    /// Set parent.
513    pub fn set_parent(&self, parent: Rc<Node<P, D>>) {
514        self.parent.replace(Some(parent.clone()));
515    }
516
517    /// Unset parent.
518    pub fn unset_parent(&self) {
519        self.parent.replace(None);
520    }
521
522    /// Set data.
523    pub fn set_data(&self, data: D) -> Option<D> {
524        self.data.replace(Some(data))
525    }
526
527    /// Unset data.
528    pub fn unset_data(&self) -> Option<D> {
529        self.data.replace(None)
530    }
531
532    /// Return reference to data.
533    pub fn data(&self) -> RefMut<Option<D>> {
534        self.data.borrow_mut()
535    }
536
537    /// Return true if node has data.
538    pub fn has_data(&self) -> bool {
539        self.data.borrow_mut().is_some()
540    }
541
542    /// Return true if node has child or data.
543    pub fn is_locked(&self) -> bool {
544        if self.children[Child::Left as usize].borrow_mut().is_some() {
545            true
546        } else if self.children[Child::Right as usize].borrow_mut().is_some() {
547            true
548        } else if self.has_data() {
549            true
550        } else {
551            false
552        }
553    }
554
555    /// Return next Node.  TODO: refactoring
556    pub fn next(&self) -> Option<Rc<Node<P, D>>> {
557        if let Some(node) = self.child(Child::Left) {
558            return Some(node.clone())
559        }
560        else if let Some(node) = self.child(Child::Right) {
561            return Some(node.clone())
562        }
563        else {
564            if let Some(parent) = self.parent() {
565                if let Some(l_child) = parent.child(Child::Left) {
566                    if l_child.as_ref() as *const _ == self as *const _ {
567                        if let Some(r_child) = parent.child(Child::Right) {
568                            return Some(r_child.clone())
569                        }
570                    }
571                }
572
573                let mut curr = parent;
574                while let Some(parent) = curr.parent() {
575                    if let Some(l_child) = parent.child(Child::Left) {
576                        if l_child.as_ref() as *const _ == curr.as_ref() as *const _ {
577                            if let Some(r_child) = parent.child(Child::Right) {
578                                return Some(r_child.clone())
579                            }
580                        }
581                    }
582                    curr = parent;
583                }
584            }
585        }
586
587        None
588    }
589
590    /// Return next Node with data.
591    pub fn next_with_data(&self) -> Option<Rc<Node<P, D>>> {
592        let mut next = self.next();
593
594        while let Some(node) = next {
595            if node.has_data() {
596                return Some(node)
597            }
598            next = node.next();
599        }
600
601        None
602    }
603}
604
605///
606/// Unit tests for Tree and Node.
607///
608#[cfg(test)]
609mod tests {
610    use super::*;
611    use std::net::Ipv4Addr;
612    use std::net::Ipv6Addr;
613
614    pub struct Data {
615        pub v: u32
616    }
617
618    impl Data {
619        fn new(v: u32) -> Rc<Data> {
620            Rc::new(Data { v: v })
621        }
622    }
623
624    type RouteTableIpv4 = Tree<Prefix<Ipv4Addr>, Rc<Data>>;
625    type RouteTableIpv6 = Tree<Prefix<Ipv6Addr>, Rc<Data>>;
626
627    fn route_ipv4_add(tree: &mut RouteTableIpv4,
628                      prefix_str: &str, d: Rc<Data>) -> Result<(), PrefixParseError> {
629        let p = Prefix::<Ipv4Addr>::from_str(prefix_str)?;
630        tree.insert(&p, d);
631
632        Ok(())
633    }
634
635    fn route_ipv4_delete(tree: &mut RouteTableIpv4, prefix_str: &str) -> Result<(), PrefixParseError> {
636        let p = Prefix::<Ipv4Addr>::from_str(prefix_str)?;
637        tree.delete(&p);
638
639        Ok(())
640    }
641
642    fn route_ipv4_lookup(tree: &RouteTableIpv4, prefix_str: &str) -> Result<Option<(Rc<Data>, Prefix<Ipv4Addr>)>, PrefixParseError> {
643        let p = Prefix::<Ipv4Addr>::from_str(prefix_str)?;
644        let it = tree.lookup(&p);
645
646        match it.node().as_ref() {
647            Some(node) => {
648                let data = node.data().clone();
649                match data {
650                    Some(data) => Ok(Some((data.clone(), node.prefix().clone()))),
651                    None => Ok(None)
652                }
653            },
654            None => Ok(None)
655        }
656    }
657
658    fn route_ipv4_lookup_exact<'a>(tree: &RouteTableIpv4, prefix_str: &str) -> Result<Option<Rc<Data>>, PrefixParseError> {
659        let p = Prefix::<Ipv4Addr>::from_str(prefix_str)?;
660        let it = tree.lookup_exact(&p);
661
662        match it.node().as_ref() {
663            Some(node) => Ok(node.data().clone()),
664            None => Ok(None)
665        }
666    }
667
668    fn route_ipv6_add(tree: &mut RouteTableIpv6,
669                      prefix_str: &str, d: Rc<Data>) -> Result<(), PrefixParseError> {
670        let p = Prefix::<Ipv6Addr>::from_str(prefix_str)?;
671        tree.insert(&p, d);
672
673        Ok(())
674    }
675
676    fn route_ipv6_delete(tree: &mut RouteTableIpv6, prefix_str: &str) -> Result<(), PrefixParseError> {
677        let p = Prefix::<Ipv6Addr>::from_str(prefix_str)?;
678        tree.delete(&p);
679
680        Ok(())
681    }
682
683    fn route_ipv6_lookup(tree: &RouteTableIpv6, prefix_str: &str) -> Result<Option<(Rc<Data>, Prefix<Ipv6Addr>)>, PrefixParseError> {
684        let p = Prefix::<Ipv6Addr>::from_str(prefix_str)?;
685        let it = tree.lookup(&p);
686
687        match it.node().as_ref() {
688            Some(node) => {
689                let data = node.data().clone();
690                match data {
691                    Some(data) => Ok(Some((data.clone(), node.prefix().clone()))),
692                    None => Ok(None)
693                }
694            },
695            None => Ok(None)
696        }
697    }
698
699    fn route_ipv6_lookup_exact<'a>(tree: &RouteTableIpv6, prefix_str: &str) -> Result<Option<Rc<Data>>, PrefixParseError> {
700        let p = Prefix::<Ipv6Addr>::from_str(prefix_str)?;
701        let it = tree.lookup_exact(&p);
702
703        match it.node().as_ref() {
704            Some(node) => Ok(node.data().clone()),
705            None => Ok(None)
706        }
707    }
708
709    #[test]
710    pub fn test_tree_ipv4() {
711        let mut tree = RouteTableIpv4::new();
712
713        route_ipv4_add(&mut tree, "10.10.10.0/24", Data::new(100)).expect("Route add error");
714        route_ipv4_add(&mut tree, "10.10.0.0/16", Data::new(200)).expect("Route add error");
715
716        match route_ipv4_lookup(&tree, "10.10.10.0/24").expect("Route lookup error") {
717            Some((data, _)) => assert_eq!(data.v, 100),
718            None => assert!(false),
719        }
720
721        match route_ipv4_lookup_exact(&tree, "10.10.0.0/16").expect("Route lookup error") {
722            Some(data) => assert_eq!(data.v, 200),
723            None => assert!(false),
724        }
725
726        match route_ipv4_lookup_exact(&tree, "10.10.0.0/20").expect("Route lookup error") {
727            Some(_data) => assert!(false),
728            None => { },
729        }
730
731        match route_ipv4_lookup(&tree, "10.10.0.0/20").expect("Route lookup error") {
732            Some((data, p)) => {
733                assert_eq!(p.len(), 16);
734                assert_eq!(data.v, 200);
735            },
736            None => assert!(false),
737        }
738
739        route_ipv4_add(&mut tree, "0.0.0.0/0", Data::new(0)).expect("Route add error");
740
741        match route_ipv4_lookup(&tree, "10.0.0.0/8").expect("Route lookup error") {
742            Some((_data, p)) => {
743                assert_eq!(p.len(), 0);
744            },
745            None => assert!(false),
746        }
747
748        assert_eq!(tree.count(), 3);
749
750        // TODO: Actually it does not delete the route.
751        route_ipv4_delete(&mut tree, "10.10.0.0/20").expect("Route delete error");
752        assert_eq!(tree.count(), 3);
753
754        route_ipv4_add(&mut tree, "1.1.1.1/32", Data::new(0)).expect("Route add error");
755        route_ipv4_add(&mut tree, "192.168.1.0/24", Data::new(0)).expect("Route add error");
756
757        route_ipv4_add(&mut tree, "127.0.0.0/8", Data::new(0)).expect("Route add error");
758        route_ipv4_add(&mut tree, "20.20.0.0/20", Data::new(0)).expect("Route add error");
759        route_ipv4_add(&mut tree, "64.64.64.128/25", Data::new(0)).expect("Route add error");
760
761        let v: Vec<_> = tree.into_iter().map(|n| n.prefix().to_string()).collect();
762        assert_eq!(v, &["0.0.0.0/0", "1.1.1.1/32", "10.10.0.0/16", "10.10.10.0/24", "20.20.0.0/20", "64.64.64.128/25", "127.0.0.0/8", "192.168.1.0/24"]);
763
764        let v: Vec<_> = tree.node_iter().map(|n| n.prefix().to_string()).collect();
765        assert_eq!(v, &["0.0.0.0/0", "0.0.0.0/1", "0.0.0.0/3", "0.0.0.0/4", "1.1.1.1/32", "10.10.0.0/16", "10.10.10.0/24", "20.20.0.0/20", "64.0.0.0/2", "64.64.64.128/25", "127.0.0.0/8", "192.168.1.0/24"]);
766
767        assert_eq!(tree.count(), 8);
768
769        route_ipv4_delete(&mut tree, "10.10.10.0/24").expect("Route add error");
770        route_ipv4_delete(&mut tree, "10.10.0.0/16").expect("Route add error");
771        route_ipv4_delete(&mut tree, "0.0.0.0/0").expect("Route add error");
772        route_ipv4_delete(&mut tree, "1.1.1.1/32").expect("Route add error");
773        route_ipv4_delete(&mut tree, "192.168.1.0/24").expect("Route add error");
774        route_ipv4_delete(&mut tree, "127.0.0.0/8").expect("Route add error");
775        route_ipv4_delete(&mut tree, "20.20.0.0/20").expect("Route add error");
776        route_ipv4_delete(&mut tree, "64.64.64.128/25").expect("Route add error");
777
778        assert_eq!(tree.count(), 0);
779
780        let x: Vec<&str> = [].to_vec();
781
782        let v: Vec<_> = tree.into_iter().map(|n| n.prefix().to_string()).collect();
783        assert_eq!(v, x);
784
785        let v: Vec<_> = tree.node_iter().map(|n| n.prefix().to_string()).collect();
786        assert_eq!(v, x);
787    }
788
789    #[test]
790    pub fn test_tree_ipv6() {
791        let mut tree = RouteTableIpv6::new();
792
793        route_ipv6_add(&mut tree, "2001::/64", Data::new(100)).expect("Route add error");
794        route_ipv6_add(&mut tree, "2001::/48", Data::new(200)).expect("Route add error");
795
796        match route_ipv6_lookup(&tree, "2001::/64").expect("Route lookup error") {
797            Some((data, _)) => assert_eq!(data.v, 100),
798            None => assert!(false),
799        }
800
801        match route_ipv6_lookup_exact(&tree, "2001::/48").expect("Route lookup error") {
802            Some(data) => assert_eq!(data.v, 200),
803            None => assert!(false),
804        }
805
806        match route_ipv6_lookup_exact(&tree, "2001::/56").expect("Route lookup error") {
807            Some(_data) => assert!(false),
808            None => { },
809        }
810
811        match route_ipv6_lookup(&tree, "2001::/56").expect("Route lookup error") {
812            Some((data, p)) => {
813                assert_eq!(p.len(), 48);
814                assert_eq!(data.v, 200);
815            },
816            None => assert!(false),
817        }
818
819        route_ipv6_add(&mut tree, "::/0", Data::new(0)).expect("Route add error");
820
821        match route_ipv6_lookup(&tree, "2001::/32").expect("Route lookup error") {
822            Some((_data, p)) => {
823                assert_eq!(p.len(), 0);
824            },
825            None => assert!(false),
826        }
827
828        assert_eq!(tree.count(), 3);
829
830        // Likewise, it does not delete the route.
831        route_ipv6_delete(&mut tree, "2001::/56").expect("Route delete error");
832        assert_eq!(tree.count(), 3);
833
834        route_ipv6_add(&mut tree, "2001:db8::1/128", Data::new(0)).expect("Route add error");
835        route_ipv6_add(&mut tree, "3001:a:b::c/64", Data::new(0)).expect("Route add error");
836        route_ipv6_add(&mut tree, "7001:1:1::/64", Data::new(0)).expect("Route add error");
837        route_ipv6_add(&mut tree, "ff80::/10", Data::new(0)).expect("Route add error");
838        route_ipv6_add(&mut tree, "ff00::/8", Data::new(0)).expect("Route add error");
839
840        let v: Vec<_> = tree.into_iter().map(|n| n.prefix().to_string()).collect();
841        assert_eq!(v, &["::/0", "2001::/48", "2001::/64", "2001:db8::1/128", "3001:a:b::c/64", "7001:1:1::/64", "ff00::/8", "ff80::/10"]);
842        let v: Vec<_> = tree.node_iter().map(|n| n.prefix().to_string()).collect();
843        assert_eq!(v, &["::/0", "::/1", "2000::/3", "2001::/20", "2001::/48", "2001::/64", "2001:db8::1/128", "3001:a:b::c/64", "7001:1:1::/64", "ff00::/8", "ff80::/10"]);
844
845        route_ipv6_delete(&mut tree, "2001::/64").expect("Route add error");
846        route_ipv6_delete(&mut tree, "2001::/48").expect("Route add error");
847        route_ipv6_delete(&mut tree, "::/0").expect("Route add error");
848        route_ipv6_delete(&mut tree, "2001:db8::1/128").expect("Route add error");
849        route_ipv6_delete(&mut tree, "3001:a:b::c/64").expect("Route add error");
850        route_ipv6_delete(&mut tree, "7001:1:1::/64").expect("Route add error");
851        route_ipv6_delete(&mut tree, "ff80::/10").expect("Route add error");
852        route_ipv6_delete(&mut tree, "ff00::/8").expect("Route add error");
853
854        assert_eq!(tree.count(), 0);
855
856        let x: Vec<&str> = [].to_vec();
857
858        let v: Vec<_> = tree.into_iter().map(|n| n.prefix().to_string()).collect();
859        assert_eq!(v, x);
860
861        let v: Vec<_> = tree.node_iter().map(|n| n.prefix().to_string()).collect();
862        assert_eq!(v, x);
863    }
864}
rtable/tree.rs

rtable/
tree.rs
