citahub / cita_trie

Rust implementation of the Modified Patricia Tree (aka Trie).
Apache License 2.0
71 stars 28 forks source link

fix: delete all stale keys #19

Closed yejiayu closed 5 years ago

yejiayu commented 5 years ago

fix #17

All loaded hash_node is recorded when insert_at or delete_at, and then all generated hash_node is recorded at commit.

Finally, their supplemental set is keys that has been deleted.

cryptowen commented 5 years ago

I add a test by random insert and delete, it does not pass. Have not figured out why yet.

    #[test]
    fn test_delete_stale_keys_with_random_insert_and_delete() {
        let mut memdb = MemoryDB::new();
        let mut trie = PatriciaTrie::new(&mut memdb, RLPNodeCodec::default());

        let mut rng = rand::thread_rng();
        let mut keys = vec![];
        for _ in 0..100 {
            let random_bytes: Vec<u8> = (0..rng.gen_range(2, 30))
                .map(|_| rand::random::<u8>())
                .collect();
            trie.insert(&random_bytes, &random_bytes)
                .unwrap();
            keys.push(random_bytes.clone());
        }
        trie.commit().unwrap();
        let slice = &mut keys;
        slice.shuffle(&mut rng);

        for key in slice.iter() {
            trie.remove(key).unwrap();
        }
        trie.commit().unwrap();
        assert_eq!(1, trie.db.len().unwrap());

        let codec = RLPNodeCodec::default();
        let empty_node_key = codec.decode_hash(&codec.encode_empty(), false);
        let value = trie.db.get(empty_node_key.as_ref()).unwrap().unwrap();
        assert_eq!(value, codec.encode_empty())
    }
laizy commented 5 years ago

@huwenchao because hash node loaded in degenerate function also need to be added in self.passing_keys