798 } |
808 } |
799 |
809 |
800 #[test] |
810 #[test] |
801 fn test_immutable_find_simplest() -> Result<(), NodeMapError> { |
811 fn test_immutable_find_simplest() -> Result<(), NodeMapError> { |
802 let mut idx: TestIndex = HashMap::new(); |
812 let mut idx: TestIndex = HashMap::new(); |
803 pad_insert(&mut idx, 1, "1234deadcafe"); |
813 pad_insert(&mut idx, R!(1), "1234deadcafe"); |
804 |
814 |
805 let nt = NodeTree::from(vec![block! {1: Rev(1)}]); |
815 let nt = NodeTree::from(vec![block! {1: Rev(1)}]); |
806 assert_eq!(nt.find_bin(&idx, hex("1"))?, Some(1)); |
816 assert_eq!(nt.find_bin(&idx, hex("1"))?, Some(R!(1))); |
807 assert_eq!(nt.find_bin(&idx, hex("12"))?, Some(1)); |
817 assert_eq!(nt.find_bin(&idx, hex("12"))?, Some(R!(1))); |
808 assert_eq!(nt.find_bin(&idx, hex("1234de"))?, Some(1)); |
818 assert_eq!(nt.find_bin(&idx, hex("1234de"))?, Some(R!(1))); |
809 assert_eq!(nt.find_bin(&idx, hex("1a"))?, None); |
819 assert_eq!(nt.find_bin(&idx, hex("1a"))?, None); |
810 assert_eq!(nt.find_bin(&idx, hex("ab"))?, None); |
820 assert_eq!(nt.find_bin(&idx, hex("ab"))?, None); |
811 |
821 |
812 // and with full binary Nodes |
822 // and with full binary Nodes |
813 assert_eq!(nt.find_node(&idx, idx.get(&1.into()).unwrap())?, Some(1)); |
823 assert_eq!( |
|
824 nt.find_node(&idx, idx.get(&1.into()).unwrap())?, |
|
825 Some(R!(1)) |
|
826 ); |
814 let unknown = Node::from_hex(&hex_pad_right("3d")).unwrap(); |
827 let unknown = Node::from_hex(&hex_pad_right("3d")).unwrap(); |
815 assert_eq!(nt.find_node(&idx, &unknown)?, None); |
828 assert_eq!(nt.find_node(&idx, &unknown)?, None); |
816 Ok(()) |
829 Ok(()) |
817 } |
830 } |
818 |
831 |
819 #[test] |
832 #[test] |
820 fn test_immutable_find_one_jump() { |
833 fn test_immutable_find_one_jump() { |
821 let mut idx = TestIndex::new(); |
834 let mut idx = TestIndex::new(); |
822 pad_insert(&mut idx, 9, "012"); |
835 pad_insert(&mut idx, R!(9), "012"); |
823 pad_insert(&mut idx, 0, "00a"); |
836 pad_insert(&mut idx, R!(0), "00a"); |
824 |
837 |
825 let nt = sample_nodetree(); |
838 let nt = sample_nodetree(); |
826 |
839 |
827 assert_eq!(nt.find_bin(&idx, hex("0")), Err(MultipleResults)); |
840 assert_eq!(nt.find_bin(&idx, hex("0")), Err(MultipleResults)); |
828 assert_eq!(nt.find_bin(&idx, hex("01")), Ok(Some(9))); |
841 assert_eq!(nt.find_bin(&idx, hex("01")), Ok(Some(R!(9)))); |
829 assert_eq!(nt.find_bin(&idx, hex("00")), Err(MultipleResults)); |
842 assert_eq!(nt.find_bin(&idx, hex("00")), Err(MultipleResults)); |
830 assert_eq!(nt.find_bin(&idx, hex("00a")), Ok(Some(0))); |
843 assert_eq!(nt.find_bin(&idx, hex("00a")), Ok(Some(R!(0)))); |
831 assert_eq!(nt.unique_prefix_len_bin(&idx, hex("00a")), Ok(Some(3))); |
844 assert_eq!(nt.unique_prefix_len_bin(&idx, hex("00a")), Ok(Some(3))); |
832 assert_eq!(nt.find_bin(&idx, hex("000")), Ok(Some(NULL_REVISION))); |
845 assert_eq!(nt.find_bin(&idx, hex("000")), Ok(Some(NULL_REVISION))); |
833 } |
846 } |
834 |
847 |
835 #[test] |
848 #[test] |
836 fn test_mutated_find() -> Result<(), NodeMapError> { |
849 fn test_mutated_find() -> Result<(), NodeMapError> { |
837 let mut idx = TestIndex::new(); |
850 let mut idx = TestIndex::new(); |
838 pad_insert(&mut idx, 9, "012"); |
851 pad_insert(&mut idx, R!(9), "012"); |
839 pad_insert(&mut idx, 0, "00a"); |
852 pad_insert(&mut idx, R!(0), "00a"); |
840 pad_insert(&mut idx, 2, "cafe"); |
853 pad_insert(&mut idx, R!(2), "cafe"); |
841 pad_insert(&mut idx, 3, "15"); |
854 pad_insert(&mut idx, R!(3), "15"); |
842 pad_insert(&mut idx, 1, "10"); |
855 pad_insert(&mut idx, R!(1), "10"); |
843 |
856 |
844 let nt = NodeTree { |
857 let nt = NodeTree { |
845 readonly: sample_nodetree().readonly, |
858 readonly: sample_nodetree().readonly, |
846 growable: vec![block![0: Rev(1), 5: Rev(3)]], |
859 growable: vec![block![0: Rev(1), 5: Rev(3)]], |
847 root: block![0: Block(1), 1:Block(3), 12: Rev(2)], |
860 root: block![0: Block(1), 1:Block(3), 12: Rev(2)], |
848 masked_inner_blocks: 1, |
861 masked_inner_blocks: 1, |
849 }; |
862 }; |
850 assert_eq!(nt.find_bin(&idx, hex("10"))?, Some(1)); |
863 assert_eq!(nt.find_bin(&idx, hex("10"))?, Some(R!(1))); |
851 assert_eq!(nt.find_bin(&idx, hex("c"))?, Some(2)); |
864 assert_eq!(nt.find_bin(&idx, hex("c"))?, Some(R!(2))); |
852 assert_eq!(nt.unique_prefix_len_bin(&idx, hex("c"))?, Some(1)); |
865 assert_eq!(nt.unique_prefix_len_bin(&idx, hex("c"))?, Some(1)); |
853 assert_eq!(nt.find_bin(&idx, hex("00")), Err(MultipleResults)); |
866 assert_eq!(nt.find_bin(&idx, hex("00")), Err(MultipleResults)); |
854 assert_eq!(nt.find_bin(&idx, hex("000"))?, Some(NULL_REVISION)); |
867 assert_eq!(nt.find_bin(&idx, hex("000"))?, Some(NULL_REVISION)); |
855 assert_eq!(nt.unique_prefix_len_bin(&idx, hex("000"))?, Some(3)); |
868 assert_eq!(nt.unique_prefix_len_bin(&idx, hex("000"))?, Some(3)); |
856 assert_eq!(nt.find_bin(&idx, hex("01"))?, Some(9)); |
869 assert_eq!(nt.find_bin(&idx, hex("01"))?, Some(R!(9))); |
857 assert_eq!(nt.masked_readonly_blocks(), 2); |
870 assert_eq!(nt.masked_readonly_blocks(), 2); |
858 Ok(()) |
871 Ok(()) |
859 } |
872 } |
860 |
873 |
861 struct TestNtIndex { |
874 struct TestNtIndex { |
913 |
926 |
914 #[test] |
927 #[test] |
915 fn test_insert_full_mutable() -> Result<(), NodeMapError> { |
928 fn test_insert_full_mutable() -> Result<(), NodeMapError> { |
916 let mut idx = TestNtIndex::new(); |
929 let mut idx = TestNtIndex::new(); |
917 idx.insert(0, "1234")?; |
930 idx.insert(0, "1234")?; |
918 assert_eq!(idx.find_hex("1")?, Some(0)); |
931 assert_eq!(idx.find_hex("1")?, Some(R!(0))); |
919 assert_eq!(idx.find_hex("12")?, Some(0)); |
932 assert_eq!(idx.find_hex("12")?, Some(R!(0))); |
920 |
933 |
921 // let's trigger a simple split |
934 // let's trigger a simple split |
922 idx.insert(1, "1a34")?; |
935 idx.insert(1, "1a34")?; |
923 assert_eq!(idx.nt.growable.len(), 1); |
936 assert_eq!(idx.nt.growable.len(), 1); |
924 assert_eq!(idx.find_hex("12")?, Some(0)); |
937 assert_eq!(idx.find_hex("12")?, Some(R!(0))); |
925 assert_eq!(idx.find_hex("1a")?, Some(1)); |
938 assert_eq!(idx.find_hex("1a")?, Some(R!(1))); |
926 |
939 |
927 // reinserting is a no_op |
940 // reinserting is a no_op |
928 idx.insert(1, "1a34")?; |
941 idx.insert(1, "1a34")?; |
929 assert_eq!(idx.nt.growable.len(), 1); |
942 assert_eq!(idx.nt.growable.len(), 1); |
930 assert_eq!(idx.find_hex("12")?, Some(0)); |
943 assert_eq!(idx.find_hex("12")?, Some(R!(0))); |
931 assert_eq!(idx.find_hex("1a")?, Some(1)); |
944 assert_eq!(idx.find_hex("1a")?, Some(R!(1))); |
932 |
945 |
933 idx.insert(2, "1a01")?; |
946 idx.insert(2, "1a01")?; |
934 assert_eq!(idx.nt.growable.len(), 2); |
947 assert_eq!(idx.nt.growable.len(), 2); |
935 assert_eq!(idx.find_hex("1a"), Err(NodeMapError::MultipleResults)); |
948 assert_eq!(idx.find_hex("1a"), Err(NodeMapError::MultipleResults)); |
936 assert_eq!(idx.find_hex("12")?, Some(0)); |
949 assert_eq!(idx.find_hex("12")?, Some(R!(0))); |
937 assert_eq!(idx.find_hex("1a3")?, Some(1)); |
950 assert_eq!(idx.find_hex("1a3")?, Some(R!(1))); |
938 assert_eq!(idx.find_hex("1a0")?, Some(2)); |
951 assert_eq!(idx.find_hex("1a0")?, Some(R!(2))); |
939 assert_eq!(idx.find_hex("1a12")?, None); |
952 assert_eq!(idx.find_hex("1a12")?, None); |
940 |
953 |
941 // now let's make it split and create more than one additional block |
954 // now let's make it split and create more than one additional block |
942 idx.insert(3, "1a345")?; |
955 idx.insert(3, "1a345")?; |
943 assert_eq!(idx.nt.growable.len(), 4); |
956 assert_eq!(idx.nt.growable.len(), 4); |
944 assert_eq!(idx.find_hex("1a340")?, Some(1)); |
957 assert_eq!(idx.find_hex("1a340")?, Some(R!(1))); |
945 assert_eq!(idx.find_hex("1a345")?, Some(3)); |
958 assert_eq!(idx.find_hex("1a345")?, Some(R!(3))); |
946 assert_eq!(idx.find_hex("1a341")?, None); |
959 assert_eq!(idx.find_hex("1a341")?, None); |
947 |
960 |
948 // there's no readonly block to mask |
961 // there's no readonly block to mask |
949 assert_eq!(idx.nt.masked_readonly_blocks(), 0); |
962 assert_eq!(idx.nt.masked_readonly_blocks(), 0); |
950 Ok(()) |
963 Ok(()) |
1002 idx.insert(0, "1234")?; |
1015 idx.insert(0, "1234")?; |
1003 idx.insert(1, "1235")?; |
1016 idx.insert(1, "1235")?; |
1004 idx.insert(2, "131")?; |
1017 idx.insert(2, "131")?; |
1005 idx.insert(3, "cafe")?; |
1018 idx.insert(3, "cafe")?; |
1006 let mut idx = idx.commit(); |
1019 let mut idx = idx.commit(); |
1007 assert_eq!(idx.find_hex("1234")?, Some(0)); |
1020 assert_eq!(idx.find_hex("1234")?, Some(R!(0))); |
1008 assert_eq!(idx.find_hex("1235")?, Some(1)); |
1021 assert_eq!(idx.find_hex("1235")?, Some(R!(1))); |
1009 assert_eq!(idx.find_hex("131")?, Some(2)); |
1022 assert_eq!(idx.find_hex("131")?, Some(R!(2))); |
1010 assert_eq!(idx.find_hex("cafe")?, Some(3)); |
1023 assert_eq!(idx.find_hex("cafe")?, Some(R!(3))); |
1011 // we did not add anything since init from readonly |
1024 // we did not add anything since init from readonly |
1012 assert_eq!(idx.nt.masked_readonly_blocks(), 0); |
1025 assert_eq!(idx.nt.masked_readonly_blocks(), 0); |
1013 |
1026 |
1014 idx.insert(4, "123A")?; |
1027 idx.insert(4, "123A")?; |
1015 assert_eq!(idx.find_hex("1234")?, Some(0)); |
1028 assert_eq!(idx.find_hex("1234")?, Some(R!(0))); |
1016 assert_eq!(idx.find_hex("1235")?, Some(1)); |
1029 assert_eq!(idx.find_hex("1235")?, Some(R!(1))); |
1017 assert_eq!(idx.find_hex("131")?, Some(2)); |
1030 assert_eq!(idx.find_hex("131")?, Some(R!(2))); |
1018 assert_eq!(idx.find_hex("cafe")?, Some(3)); |
1031 assert_eq!(idx.find_hex("cafe")?, Some(R!(3))); |
1019 assert_eq!(idx.find_hex("123A")?, Some(4)); |
1032 assert_eq!(idx.find_hex("123A")?, Some(R!(4))); |
1020 // we masked blocks for all prefixes of "123", including the root |
1033 // we masked blocks for all prefixes of "123", including the root |
1021 assert_eq!(idx.nt.masked_readonly_blocks(), 4); |
1034 assert_eq!(idx.nt.masked_readonly_blocks(), 4); |
1022 |
1035 |
1023 eprintln!("{:?}", idx.nt); |
1036 eprintln!("{:?}", idx.nt); |
1024 idx.insert(5, "c0")?; |
1037 idx.insert(5, "c0")?; |
1025 assert_eq!(idx.find_hex("cafe")?, Some(3)); |
1038 assert_eq!(idx.find_hex("cafe")?, Some(R!(3))); |
1026 assert_eq!(idx.find_hex("c0")?, Some(5)); |
1039 assert_eq!(idx.find_hex("c0")?, Some(R!(5))); |
1027 assert_eq!(idx.find_hex("c1")?, None); |
1040 assert_eq!(idx.find_hex("c1")?, None); |
1028 assert_eq!(idx.find_hex("1234")?, Some(0)); |
1041 assert_eq!(idx.find_hex("1234")?, Some(R!(0))); |
1029 // inserting "c0" is just splitting the 'c' slot of the mutable root, |
1042 // inserting "c0" is just splitting the 'c' slot of the mutable root, |
1030 // it doesn't mask anything |
1043 // it doesn't mask anything |
1031 assert_eq!(idx.nt.masked_readonly_blocks(), 4); |
1044 assert_eq!(idx.nt.masked_readonly_blocks(), 4); |
1032 |
1045 |
1033 Ok(()) |
1046 Ok(()) |