1use 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#[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
138fn 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
166fn 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]; let max_len = len.min(128); 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
190fn 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); 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 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 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 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 let key_rem = extract_bits(key, depth, remaining);
271 let shared = common_prefix_len(&edge_bits, edge_len, &key_rem, remaining);
272
273 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 if shared < edge_len {
283 let pivot_bit = get_bit_from_bytes(&edge_bits, shared);
284
285 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 child.set_left(node.left());
300 child.set_right(node.right());
301
302 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 if pivot_bit == 0 {
310 node.set_left(Some(child));
311 } else {
312 node.set_right(Some(child));
313 }
314
315 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 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 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 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 if shared < edge_len {
389 return None;
390 }
391
392 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 #[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 #[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 #[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 #[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 #[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 #[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 #[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 #[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 #[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}