Skip to main content

radixip/
tree.rs

1//! Route tree implementations.
2//!
3//! Two concrete [`RouteTree`] types are provided:
4//!
5//! - [`UncompressedTree`] — bit-by-bit binary trie; every edge is exactly 1 bit.
6//! - [`CompressedTree`]   — Patricia / radix trie; each edge carries a variable-length
7//!   bit string, skipping over non-branching paths for faster traversal.
8//!
9//! Both trees store `Arc<dyn Node>`, so the node variant (Normal, Atomic,
10//! Padded, LockFree, or their Compressed equivalents) is chosen at construction
11//! time via [`NodeBuilder`] and [`NodeVariant`].
12
13use crate::lpm::{get_bit, longest_prefix_match_binary};
14use crate::node::NodeBuilder;
15use crate::traits::{Node, NodeVariant, RouteTree};
16use crate::types::Metadata;
17use ipnetwork::IpNetwork;
18use std::net::IpAddr;
19use std::sync::Arc;
20
21//
22// UNCOMPRESSED TREE  (bit-by-bit binary trie)
23//
24
25#[derive(Clone)]
26pub struct UncompressedTree {
27    root: Arc<dyn Node>,
28    node_builder: NodeBuilder,
29}
30
31impl UncompressedTree {
32    pub fn new(node_variant: NodeVariant) -> Self {
33        let builder = NodeBuilder::new(node_variant);
34        Self {
35            root: builder.build(),
36            node_builder: builder,
37        }
38    }
39}
40
41impl RouteTree for UncompressedTree {
42    fn insert(&self, prefix: IpNetwork, metadata: Metadata) -> Result<bool, String> {
43        let ip = prefix.network();
44        let prefix_len = prefix.prefix() as usize;
45
46        let mut current_arc = self.root.clone();
47
48        for depth in 0..prefix_len {
49            let bit = get_bit(ip, depth);
50            let next = if bit == 0 {
51                current_arc.left()
52            } else {
53                current_arc.right()
54            };
55
56            match next {
57                Some(node) => {
58                    current_arc = node;
59                }
60                None => {
61                    let new_node = self.node_builder.build();
62                    if bit == 0 {
63                        current_arc.set_left(Some(new_node.clone()));
64                    } else {
65                        current_arc.set_right(Some(new_node.clone()));
66                    }
67                    current_arc = new_node;
68                }
69            }
70        }
71
72        let is_new = current_arc.metadata().is_none();
73        current_arc.set_prefix(prefix);
74        current_arc.set_metadata(metadata);
75
76        Ok(is_new)
77    }
78
79    fn lookup(&self, ip: &IpAddr) -> Option<Metadata> {
80        longest_prefix_match_binary(&*self.root, *ip)
81    }
82
83    fn remove(&self, prefix: &IpNetwork) -> Option<Metadata> {
84        let ip = prefix.network();
85        let prefix_len = prefix.prefix() as usize;
86
87        let mut current_arc = self.root.clone();
88
89        for depth in 0..prefix_len {
90            let bit = get_bit(ip, depth);
91            let next = if bit == 0 {
92                current_arc.left()
93            } else {
94                current_arc.right()
95            };
96            match next {
97                Some(node) => current_arc = node,
98                None => return None,
99            }
100        }
101
102        let removed = current_arc.metadata();
103        if removed.is_some() {
104            current_arc.clear_metadata();
105        }
106
107        removed
108    }
109
110    fn contains(&self, prefix: &IpNetwork) -> bool {
111        let ip = prefix.network();
112        let prefix_len = prefix.prefix() as usize;
113
114        let mut current_arc = self.root.clone();
115
116        for depth in 0..prefix_len {
117            let bit = get_bit(ip, depth);
118            let next = if bit == 0 {
119                current_arc.left()
120            } else {
121                current_arc.right()
122            };
123            match next {
124                Some(node) => current_arc = node,
125                None => return false,
126            }
127        }
128
129        current_arc.metadata().is_some()
130    }
131
132    fn clear(&self) {
133        self.root.set_left(None);
134        self.root.set_right(None);
135    }
136}
137
138//
139// COMPRESSED TREE  (Patricia / radix trie)
140//
141// Each node stores an `edge_bits: [u8;16]` representing the compressed
142// bit-string for that edge, instead of traversing one bit at a time.
143// Non-branching chains of nodes are folded into a single node, giving
144// O(k) lookups where k is the number of *branching points*, not the
145// prefix length.
146//
147// On insert: if an existing edge partially matches the new prefix we split
148// the node at the diverging bit, creating a new internal node and two children.
149//
150// On lookup: at each node we check that `edge_bits` fully matches the
151// corresponding bits of the query before moving to the next child.
152//
153// The tree works with any node variant that implements the `edge_bits`,
154// `edge_len`, and `set_edge` extensions of `Node`.  Compressed variants
155// are picked via `NodeBuilder` from `NodeVariant::Compressed*`.
156//
157
158/// Helper to read edge fields from a node via the trait extension.
159/// Returns (edge_bits_clone, edge_len) for a compressed node.
160fn node_edge(node: &Arc<dyn Node>) -> ([u8; 16], usize) {
161    let bits = node.edge_bits().unwrap_or_default();
162    let len = node.edge_len().unwrap_or(0);
163    (bits, len)
164}
165
166/// Extract bit `pos` from a byte slice (big-endian, MSB-first).
167fn get_bit_from_bytes(bytes: &[u8], pos: usize) -> u8 {
168    let byte_idx = pos / 8;
169    let bit_idx = 7 - (pos % 8);
170    if byte_idx >= bytes.len() {
171        return 0;
172    }
173    (bytes[byte_idx] >> bit_idx) & 1
174}
175
176fn extract_bits(bytes: &[u8], start: usize, len: usize) -> [u8; 16] {
177    let mut out = [0u8; 16]; // Fixed 16-byte array
178    let max_len = len.min(128); // Max bits for 16 bytes
179    for i in 0..max_len {
180        let b = get_bit_from_bytes(bytes, start + i);
181        let byte_i = i / 8;
182        let bit_i = 7 - (i % 8);
183        if byte_i < 16 {
184            out[byte_i] |= b << bit_i;
185        }
186    }
187    out
188}
189
190/// How many leading bits do two bit-arrays share?
191fn common_prefix_len(a: &[u8], a_len: usize, b: &[u8], b_len: usize) -> usize {
192    let max = a_len.min(b_len);
193    for i in 0..max {
194        if get_bit_from_bytes(a, i) != get_bit_from_bytes(b, i) {
195            return i;
196        }
197    }
198    max
199}
200
201fn ip_to_bytes(ip: IpAddr) -> [u8; 16] {
202    match ip {
203        IpAddr::V4(v4) => {
204            let octets = v4.octets();
205            let mut result = [0u8; 16];
206            result[12..16].copy_from_slice(&octets); // IPv4 in last 4 bytes
207            result
208        }
209        IpAddr::V6(v6) => v6.octets(),
210    }
211}
212
213#[derive(Clone)]
214pub struct CompressedTree {
215    root: Arc<dyn Node>,
216    node_builder: NodeBuilder,
217}
218
219impl CompressedTree {
220    pub fn new(node_variant: NodeVariant) -> Self {
221        // Ensure we use a compressed variant, upgrading if necessary.
222        let variant = match node_variant {
223            NodeVariant::NormalTrieNode | NodeVariant::NormalRadixNode => {
224                NodeVariant::NormalRadixNode
225            }
226            NodeVariant::AtomicTrieNode | NodeVariant::AtomicRadixNode => {
227                NodeVariant::AtomicRadixNode
228            }
229            NodeVariant::PaddedTrieNode | NodeVariant::PaddedRadixNode => {
230                NodeVariant::PaddedRadixNode
231            }
232            NodeVariant::LockFreeTrieNode | NodeVariant::LockFreeRadixNode => {
233                NodeVariant::LockFreeRadixNode
234            }
235        };
236        let builder = NodeBuilder::new(variant);
237        Self {
238            root: builder.build(),
239            node_builder: builder,
240        }
241    }
242
243    /// Insert into the Patricia trie, splitting nodes as needed.
244    fn insert_inner(
245        node: &Arc<dyn Node>,
246        node_builder: &NodeBuilder,
247        key: &[u8],
248        key_len: usize,
249        depth: usize,
250        prefix: IpNetwork,
251        metadata: Metadata,
252    ) -> bool {
253        let (edge_bits, edge_len) = node_edge(node);
254        let remaining = key_len.saturating_sub(depth);
255
256        // Empty node: store directly
257        if edge_len == 0
258            && node.metadata().is_none()
259            && node.left().is_none()
260            && node.right().is_none()
261        {
262            let new_bits = extract_bits(key, depth, remaining);
263            node.set_edge(new_bits, remaining);
264            node.set_prefix(prefix);
265            node.set_metadata(metadata);
266            return true;
267        }
268
269        // How many bits of edge match the incoming key?
270        let key_rem = extract_bits(key, depth, remaining);
271        let shared = common_prefix_len(&edge_bits, edge_len, &key_rem, remaining);
272
273        // Exact match — update metadata at this node.
274        if shared == edge_len && shared == remaining {
275            let is_new = node.metadata().is_none();
276            node.set_metadata(metadata);
277            node.set_prefix(prefix);
278            return is_new;
279        }
280
281        // Partial match — split this node at the diverging bit.
282        if shared < edge_len {
283            let pivot_bit = get_bit_from_bytes(&edge_bits, shared);
284
285            // Build a child carrying the remainder of the current edge.
286            let child_edge_bits = extract_bits(&edge_bits, shared + 1, edge_len - shared - 1);
287            let child_edge_len = edge_len - shared - 1;
288            let child = node_builder.build();
289            child.set_edge(child_edge_bits, child_edge_len);
290            if let Some(m) = node.metadata() {
291                child.set_metadata(m);
292                node.clear_metadata();
293            }
294            if let Some(p) = node.prefix() {
295                child.set_prefix(p);
296            }
297
298            // Move children of current node down to child.
299            child.set_left(node.left());
300            child.set_right(node.right());
301
302            // Trim current node edge to shared prefix.
303            let new_edge = extract_bits(&edge_bits, 0, shared);
304            node.set_edge(new_edge, shared);
305            node.set_left(None);
306            node.set_right(None);
307
308            // Wire child into the appropriate side.
309            if pivot_bit == 0 {
310                node.set_left(Some(child));
311            } else {
312                node.set_right(Some(child));
313            }
314
315            // Place the new prefix in the other side (or here if shared == remaining).
316            if shared == remaining {
317                node.set_metadata(metadata);
318                node.set_prefix(prefix);
319                return true;
320            }
321
322            let new_bit = get_bit_from_bytes(&key_rem, shared);
323            let new_leaf_edge = extract_bits(&key_rem, shared + 1, remaining - shared - 1);
324            let new_leaf = node_builder.build();
325            new_leaf.set_edge(new_leaf_edge, remaining - shared - 1);
326            new_leaf.set_prefix(prefix);
327            new_leaf.set_metadata(metadata);
328
329            if new_bit == 0 {
330                node.set_left(Some(new_leaf));
331            } else {
332                node.set_right(Some(new_leaf));
333            }
334            return true;
335        }
336
337        // shared == edge_len but bits remain — descend into the correct child.
338        let next_bit = get_bit_from_bytes(&key_rem, shared);
339
340        let child_opt = if next_bit == 0 {
341            node.left()
342        } else {
343            node.right()
344        };
345
346        if let Some(child) = child_opt {
347            Self::insert_inner(
348                &child,
349                node_builder,
350                key,
351                key_len,
352                depth + shared + 1,
353                prefix,
354                metadata,
355            )
356        } else {
357            // Allocate a new leaf child.
358            let new_depth = depth + shared + 1;
359            let new_remaining = key_len.saturating_sub(new_depth);
360            let leaf_edge = extract_bits(key, new_depth, new_remaining);
361            let leaf = node_builder.build();
362            leaf.set_edge(leaf_edge, new_remaining);
363            leaf.set_prefix(prefix);
364            leaf.set_metadata(metadata);
365
366            if next_bit == 0 {
367                node.set_left(Some(leaf));
368            } else {
369                node.set_right(Some(leaf));
370            }
371            true
372        }
373    }
374
375    /// Walk the trie returning the most-specific matching prefix.
376    fn lookup_inner(node: &Arc<dyn Node>, key: &[u8], depth: usize) -> Option<Metadata> {
377        let (edge_bits, edge_len) = node_edge(node);
378
379        if edge_len == 0 && node.metadata().is_none() {
380            return None;
381        }
382
383        let remaining = (key.len() * 8).saturating_sub(depth);
384        let key_rem = extract_bits(key, depth, remaining);
385        let shared = common_prefix_len(&edge_bits, edge_len, &key_rem, remaining);
386
387        // Edge doesn't fully match — no route here.
388        if shared < edge_len {
389            return None;
390        }
391
392        // Edge matched: record any terminal at this node, then keep descending.
393        let mut best = node.metadata();
394        let new_depth = depth + shared;
395
396        if new_depth >= key.len() * 8 {
397            return best;
398        }
399
400        let next_bit = get_bit_from_bytes(key, new_depth);
401        let child_opt = if next_bit == 0 {
402            node.left()
403        } else {
404            node.right()
405        };
406
407        if let Some(child) = child_opt {
408            if let Some(deeper) = Self::lookup_inner(&child, key, new_depth + 1) {
409                best = Some(deeper);
410            }
411        }
412        best
413    }
414
415    fn remove_inner(
416        node: &Arc<dyn Node>,
417        key: &[u8],
418        key_len: usize,
419        depth: usize,
420    ) -> Option<Metadata> {
421        let (edge_bits, edge_len) = node_edge(node);
422        let remaining = key_len.saturating_sub(depth);
423        let key_rem = extract_bits(key, depth, remaining);
424        let shared = common_prefix_len(&edge_bits, edge_len, &key_rem, remaining);
425
426        if shared < edge_len {
427            return None;
428        }
429
430        if shared == remaining {
431            let removed = node.metadata();
432            node.clear_metadata();
433            return removed;
434        }
435
436        let next_bit = get_bit_from_bytes(key, depth + shared);
437        let child_opt = if next_bit == 0 {
438            node.left()
439        } else {
440            node.right()
441        };
442
443        if let Some(child) = child_opt {
444            Self::remove_inner(&child, key, key_len, depth + shared + 1)
445        } else {
446            None
447        }
448    }
449
450    fn contains_inner(node: &Arc<dyn Node>, key: &[u8], key_len: usize, depth: usize) -> bool {
451        let (edge_bits, edge_len) = node_edge(node);
452        let remaining = key_len.saturating_sub(depth);
453        let key_rem = extract_bits(key, depth, remaining);
454        let shared = common_prefix_len(&edge_bits, edge_len, &key_rem, remaining);
455
456        if shared < edge_len {
457            return false;
458        }
459        if shared == remaining {
460            return node.metadata().is_some();
461        }
462
463        let next_bit = get_bit_from_bytes(key, depth + shared);
464        let child_opt = if next_bit == 0 {
465            node.left()
466        } else {
467            node.right()
468        };
469
470        if let Some(child) = child_opt {
471            Self::contains_inner(&child, key, key_len, depth + shared + 1)
472        } else {
473            false
474        }
475    }
476
477    fn clear_inner(node: &Arc<dyn Node>) {
478        node.set_edge([0u8; 16], 0);
479        node.clear_metadata();
480        node.set_left(None);
481        node.set_right(None);
482    }
483}
484
485impl RouteTree for CompressedTree {
486    fn insert(&self, prefix: IpNetwork, metadata: Metadata) -> Result<bool, String> {
487        let ip = prefix.network();
488        let key = ip_to_bytes(ip);
489        let key_len = prefix.prefix() as usize;
490        let is_new = Self::insert_inner(
491            &self.root,
492            &self.node_builder,
493            &key,
494            key_len,
495            0,
496            prefix,
497            metadata,
498        );
499        Ok(is_new)
500    }
501
502    fn lookup(&self, ip: &IpAddr) -> Option<Metadata> {
503        let key = ip_to_bytes(*ip);
504        Self::lookup_inner(&self.root, &key, 0)
505    }
506
507    fn remove(&self, prefix: &IpNetwork) -> Option<Metadata> {
508        let ip = prefix.network();
509        let key = ip_to_bytes(ip);
510        let key_len = prefix.prefix() as usize;
511        Self::remove_inner(&self.root, &key, key_len, 0)
512    }
513
514    fn contains(&self, prefix: &IpNetwork) -> bool {
515        let ip = prefix.network();
516        let key = ip_to_bytes(ip);
517        let key_len = prefix.prefix() as usize;
518        Self::contains_inner(&self.root, &key, key_len, 0)
519    }
520
521    fn clear(&self) {
522        Self::clear_inner(&self.root);
523    }
524}
525
526#[cfg(test)]
527mod tests {
528    use super::*;
529    use std::str::FromStr;
530
531    fn create_metadata(label: &str) -> Metadata {
532        Metadata::new(label.to_string())
533    }
534
535    //
536    // COMPRESSED TREE TESTS
537    //
538
539    #[test]
540    fn test_compressed_trie_v4() {
541        let tree = CompressedTree::new(NodeVariant::NormalRadixNode);
542
543        let prefix1 = IpNetwork::from_str("192.168.0.0/16").unwrap();
544        let prefix2 = IpNetwork::from_str("192.168.1.0/24").unwrap();
545
546        tree.insert(prefix1, create_metadata("local")).unwrap();
547        tree.insert(prefix2, create_metadata("subnet")).unwrap();
548
549        let ip = IpAddr::from_str("192.168.1.5").unwrap();
550        assert_eq!(tree.lookup(&ip), Some(create_metadata("subnet")));
551    }
552
553    #[test]
554    fn test_compressed_trie_v6() {
555        let tree = CompressedTree::new(NodeVariant::NormalRadixNode);
556
557        let prefix = IpNetwork::from_str("2001:db8::/32").unwrap();
558        tree.insert(prefix, create_metadata("v6_network")).unwrap();
559
560        let ip = IpAddr::from_str("2001:db8:1234::1").unwrap();
561        assert!(tree.lookup(&ip).is_some());
562    }
563
564    #[test]
565    fn test_compressed_all_variants() {
566        for variant in [
567            NodeVariant::NormalRadixNode,
568            NodeVariant::AtomicRadixNode,
569            NodeVariant::PaddedRadixNode,
570            NodeVariant::LockFreeRadixNode,
571        ] {
572            let tree = CompressedTree::new(variant);
573            let prefix = IpNetwork::from_str("10.0.0.0/8").unwrap();
574            tree.insert(prefix, create_metadata("test")).unwrap();
575            let ip = IpAddr::from_str("10.1.2.3").unwrap();
576            assert_eq!(
577                tree.lookup(&ip),
578                Some(create_metadata("test")),
579                "variant {:?} failed",
580                variant
581            );
582        }
583    }
584
585    //
586    // UNCOMPRESSED TREE TESTS
587    //
588
589    #[test]
590    fn test_new_tree() {
591        let tree = UncompressedTree::new(NodeVariant::NormalTrieNode);
592        let ip = IpAddr::from_str("192.168.1.1").unwrap();
593        assert_eq!(tree.lookup(&ip), None);
594    }
595
596    #[test]
597    fn test_insert_single_prefix_v4() {
598        let tree = UncompressedTree::new(NodeVariant::NormalTrieNode);
599        let prefix = IpNetwork::from_str("192.168.0.0/16").unwrap();
600        let metadata = create_metadata("local_network");
601
602        let result = tree.insert(prefix, metadata.clone());
603        assert!(result.is_ok());
604        assert_eq!(result.unwrap(), true);
605
606        let ip = IpAddr::from_str("192.168.1.5").unwrap();
607        assert_eq!(tree.lookup(&ip), Some(metadata.clone()));
608
609        let ip_outside = IpAddr::from_str("10.0.0.1").unwrap();
610        assert_eq!(tree.lookup(&ip_outside), None);
611    }
612
613    #[test]
614    fn test_insert_single_prefix_v6() {
615        let tree = UncompressedTree::new(NodeVariant::NormalTrieNode);
616        let prefix = IpNetwork::from_str("2001:db8::/32").unwrap();
617        let metadata = create_metadata("ipv6_network");
618
619        let result = tree.insert(prefix, metadata.clone());
620        assert!(result.is_ok());
621        assert_eq!(result.unwrap(), true);
622
623        let ip = IpAddr::from_str("2001:db8:1234::1").unwrap();
624        assert_eq!(tree.lookup(&ip), Some(metadata.clone()));
625    }
626
627    //
628    // LONGEST PREFIX MATCH TESTS
629    //
630
631    #[test]
632    fn test_longest_prefix_match_v4() {
633        let tree = UncompressedTree::new(NodeVariant::NormalTrieNode);
634
635        let prefix1 = IpNetwork::from_str("192.168.0.0/16").unwrap();
636        let prefix2 = IpNetwork::from_str("192.168.1.0/24").unwrap();
637        let prefix3 = IpNetwork::from_str("192.168.1.128/25").unwrap();
638
639        let meta1 = create_metadata("network");
640        let meta2 = create_metadata("subnet");
641        let meta3 = create_metadata("subnet_half");
642
643        tree.insert(prefix1, meta1.clone()).unwrap();
644        tree.insert(prefix2, meta2.clone()).unwrap();
645        tree.insert(prefix3, meta3.clone()).unwrap();
646
647        let ip = IpAddr::from_str("192.168.1.200").unwrap();
648        assert_eq!(tree.lookup(&ip), Some(meta3.clone()));
649
650        let ip = IpAddr::from_str("192.168.1.50").unwrap();
651        assert_eq!(tree.lookup(&ip), Some(meta2.clone()));
652
653        let ip = IpAddr::from_str("192.168.2.1").unwrap();
654        assert_eq!(tree.lookup(&ip), Some(meta1.clone()));
655    }
656
657    #[test]
658    fn test_longest_prefix_match_v6() {
659        let tree = UncompressedTree::new(NodeVariant::NormalTrieNode);
660
661        let prefix1 = IpNetwork::from_str("2001:db8::/32").unwrap();
662        let prefix2 = IpNetwork::from_str("2001:db8:1234::/48").unwrap();
663        let prefix3 = IpNetwork::from_str("2001:db8:1234:5678::/64").unwrap();
664
665        let meta1 = create_metadata("network");
666        let meta2 = create_metadata("subnet");
667        let meta3 = create_metadata("host_network");
668
669        tree.insert(prefix1, meta1.clone()).unwrap();
670        tree.insert(prefix2, meta2.clone()).unwrap();
671        tree.insert(prefix3, meta3.clone()).unwrap();
672
673        let ip = IpAddr::from_str("2001:db8:1234:5678::1").unwrap();
674        assert_eq!(tree.lookup(&ip), Some(meta3.clone()));
675
676        let ip = IpAddr::from_str("2001:db8:1234:5679::1").unwrap();
677        assert_eq!(tree.lookup(&ip), Some(meta2.clone()));
678
679        let ip = IpAddr::from_str("2001:db8:5678::1").unwrap();
680        assert_eq!(tree.lookup(&ip), Some(meta1.clone()));
681    }
682
683    //
684    // REMOVE OPERATIONS TESTS
685    //
686
687    #[test]
688    fn test_remove_existing_prefix() {
689        let tree = UncompressedTree::new(NodeVariant::NormalTrieNode);
690        let prefix = IpNetwork::from_str("192.168.0.0/16").unwrap();
691        let metadata = create_metadata("network");
692
693        tree.insert(prefix, metadata.clone()).unwrap();
694
695        let ip = IpAddr::from_str("192.168.1.1").unwrap();
696        assert_eq!(tree.lookup(&ip), Some(metadata.clone()));
697
698        let removed = tree.remove(&prefix);
699        assert_eq!(removed, Some(metadata.clone()));
700
701        assert_eq!(tree.lookup(&ip), None);
702    }
703
704    #[test]
705    fn test_remove_nonexistent_prefix() {
706        let tree = UncompressedTree::new(NodeVariant::NormalTrieNode);
707        let prefix = IpNetwork::from_str("192.168.0.0/16").unwrap();
708
709        let removed = tree.remove(&prefix);
710        assert_eq!(removed, None);
711    }
712
713    #[test]
714    fn test_remove_with_overlapping_prefixes() {
715        let tree = UncompressedTree::new(NodeVariant::NormalTrieNode);
716
717        let prefix1 = IpNetwork::from_str("192.168.0.0/16").unwrap();
718        let prefix2 = IpNetwork::from_str("192.168.1.0/24").unwrap();
719
720        let meta1 = create_metadata("network");
721        let meta2 = create_metadata("subnet");
722
723        tree.insert(prefix1, meta1.clone()).unwrap();
724        tree.insert(prefix2, meta2.clone()).unwrap();
725
726        let removed = tree.remove(&prefix2);
727        assert_eq!(removed, Some(meta2.clone()));
728
729        let ip = IpAddr::from_str("192.168.1.5").unwrap();
730        assert_eq!(tree.lookup(&ip), Some(meta1.clone()));
731
732        let removed = tree.remove(&prefix1);
733        assert_eq!(removed, Some(meta1.clone()));
734
735        assert_eq!(tree.lookup(&ip), None);
736    }
737
738    //
739    // CONTAINS TESTS
740    //
741
742    #[test]
743    fn test_contains() {
744        let tree = UncompressedTree::new(NodeVariant::NormalTrieNode);
745        let prefix = IpNetwork::from_str("192.168.0.0/16").unwrap();
746        let metadata = create_metadata("network");
747
748        tree.insert(prefix, metadata).unwrap();
749
750        assert!(tree.contains(&prefix));
751
752        let different_prefix = IpNetwork::from_str("10.0.0.0/8").unwrap();
753        assert!(!tree.contains(&different_prefix));
754    }
755
756    //
757    // CLEAR TESTS
758    //
759
760    #[test]
761    fn test_clear() {
762        let tree = UncompressedTree::new(NodeVariant::NormalTrieNode);
763
764        let prefix1 = IpNetwork::from_str("192.168.0.0/16").unwrap();
765        let prefix2 = IpNetwork::from_str("10.0.0.0/8").unwrap();
766
767        tree.insert(prefix1, create_metadata("network1")).unwrap();
768        tree.insert(prefix2, create_metadata("network2")).unwrap();
769
770        let ip1 = IpAddr::from_str("192.168.1.1").unwrap();
771        let ip2 = IpAddr::from_str("10.0.0.1").unwrap();
772        assert!(tree.lookup(&ip1).is_some());
773        assert!(tree.lookup(&ip2).is_some());
774
775        tree.clear();
776
777        assert!(tree.lookup(&ip1).is_none());
778        assert!(tree.lookup(&ip2).is_none());
779    }
780
781    //
782    // EDGE CASE TESTS
783    //
784
785    #[test]
786    fn test_default_route() {
787        let tree = UncompressedTree::new(NodeVariant::NormalTrieNode);
788
789        let default_v4 = IpNetwork::from_str("0.0.0.0/0").unwrap();
790        let meta_default = create_metadata("default");
791        tree.insert(default_v4, meta_default.clone()).unwrap();
792
793        let ip1 = IpAddr::from_str("192.168.1.1").unwrap();
794        let ip2 = IpAddr::from_str("10.0.0.1").unwrap();
795        let ip3 = IpAddr::from_str("8.8.8.8").unwrap();
796
797        assert_eq!(tree.lookup(&ip1), Some(meta_default.clone()));
798        assert_eq!(tree.lookup(&ip2), Some(meta_default.clone()));
799        assert_eq!(tree.lookup(&ip3), Some(meta_default.clone()));
800
801        let default_v6 = IpNetwork::from_str("::/0").unwrap();
802        let meta_v6_default = create_metadata("v6_default");
803        tree.insert(default_v6, meta_v6_default.clone()).unwrap();
804
805        let ip_v6 = IpAddr::from_str("2001:db8::1").unwrap();
806        assert_eq!(tree.lookup(&ip_v6), Some(meta_v6_default.clone()));
807    }
808
809    #[test]
810    fn test_host_address_32_prefix() {
811        let tree = UncompressedTree::new(NodeVariant::NormalTrieNode);
812
813        let host_prefix = IpNetwork::from_str("192.168.1.100/32").unwrap();
814        let meta_host = create_metadata("host");
815        tree.insert(host_prefix, meta_host.clone()).unwrap();
816
817        let exact_ip = IpAddr::from_str("192.168.1.100").unwrap();
818        assert_eq!(tree.lookup(&exact_ip), Some(meta_host.clone()));
819
820        let different_ip = IpAddr::from_str("192.168.1.101").unwrap();
821        assert_eq!(tree.lookup(&different_ip), None);
822    }
823
824    #[test]
825    fn test_insert_duplicate_prefix() {
826        let tree = UncompressedTree::new(NodeVariant::NormalTrieNode);
827        let prefix = IpNetwork::from_str("192.168.0.0/16").unwrap();
828        let meta1 = create_metadata("first");
829        let meta2 = create_metadata("second");
830
831        let result1 = tree.insert(prefix, meta1.clone());
832        assert!(result1.is_ok());
833        assert_eq!(result1.unwrap(), true);
834
835        let result2 = tree.insert(prefix, meta2.clone());
836        assert!(result2.is_ok());
837        assert_eq!(result2.unwrap(), false);
838
839        let ip = IpAddr::from_str("192.168.1.1").unwrap();
840        assert_eq!(tree.lookup(&ip), Some(meta2));
841    }
842
843    #[test]
844    fn test_multiple_inserts_different_prefixes() {
845        let tree = UncompressedTree::new(NodeVariant::NormalTrieNode);
846
847        let prefixes = vec![
848            ("192.168.0.0/16", "network_a"),
849            ("10.0.0.0/8", "network_b"),
850            ("172.16.0.0/12", "network_c"),
851            ("192.168.1.0/24", "subnet_a"),
852        ];
853
854        for (prefix_str, label) in prefixes {
855            let prefix = IpNetwork::from_str(prefix_str).unwrap();
856            let result = tree.insert(prefix, create_metadata(label));
857            assert!(result.is_ok());
858            assert_eq!(result.unwrap(), true);
859        }
860
861        let test_cases = vec![
862            ("192.168.1.5", "subnet_a"),
863            ("192.168.2.1", "network_a"),
864            ("10.1.1.1", "network_b"),
865            ("172.16.1.1", "network_c"),
866        ];
867
868        for (ip_str, expected_label) in test_cases {
869            let ip = IpAddr::from_str(ip_str).unwrap();
870            let result = tree.lookup(&ip);
871            assert_eq!(result, Some(create_metadata(expected_label)));
872        }
873    }
874
875    //
876    // MIXED IPv4 AND IPv6 TESTS
877    //
878
879    #[test]
880    fn test_mixed_ipv4_ipv6() {
881        let tree = UncompressedTree::new(NodeVariant::NormalTrieNode);
882
883        let v4_prefix = IpNetwork::from_str("192.168.0.0/16").unwrap();
884        let v4_meta = create_metadata("v4_network");
885        tree.insert(v4_prefix, v4_meta.clone()).unwrap();
886
887        let v6_prefix = IpNetwork::from_str("2001:db8::/32").unwrap();
888        let v6_meta = create_metadata("v6_network");
889        tree.insert(v6_prefix, v6_meta.clone()).unwrap();
890
891        let v4_ip = IpAddr::from_str("192.168.1.1").unwrap();
892        assert_eq!(tree.lookup(&v4_ip), Some(v4_meta));
893
894        let v6_ip = IpAddr::from_str("2001:db8:1234::1").unwrap();
895        assert_eq!(tree.lookup(&v6_ip), Some(v6_meta));
896
897        let wrong_ip = IpAddr::from_str("10.0.0.1").unwrap();
898        assert_eq!(tree.lookup(&wrong_ip), None);
899    }
900
901    //
902    // PERFORMANCE/BENCHMARK HELPER TESTS
903    //
904
905    #[test]
906    fn test_large_number_of_routes() {
907        let tree = UncompressedTree::new(NodeVariant::NormalTrieNode);
908
909        for i in 0..100u32 {
910            let prefix_str = format!("192.168.{}.0/24", i);
911            let prefix = IpNetwork::from_str(&prefix_str).unwrap();
912            let meta = create_metadata(&format!("subnet_{}", i));
913            tree.insert(prefix, meta).unwrap();
914        }
915
916        for i in 0..100u32 {
917            let ip_str = format!("192.168.{}.1", i);
918            let ip = IpAddr::from_str(&ip_str).unwrap();
919            let result = tree.lookup(&ip);
920            assert!(result.is_some());
921            assert_eq!(result.unwrap(), create_metadata(&format!("subnet_{}", i)));
922        }
923    }
924}