fvm_std/collections/

hyper_list.rs

use crate::{runtime};
use crate::spread::SpreadLayout;
use crate::prelude::{Vec};
use crate::collections::entry_state::{ValueWrapper, EntryState};
use scale::{Decode, Encode};
use alloc::collections::BTreeMap;
use alloc::collections::btree_map::Entry;

pub struct HyperList<T> {
    size: u32, // index is u32, so size can be u32
    list_name: Vec<u8>,
    //prefix is "list_name@K"
    storage_prefix: Vec<u8>,
    //HyperList raw key is i64, index is u32
    cache_values: BTreeMap<i64, ValueWrapper<T>>,
}

static mut DEPLOY_LIST_ID :i32 = 0;

fn get_id() -> i32 {
    unsafe {
        DEPLOY_LIST_ID = DEPLOY_LIST_ID + 1;
        DEPLOY_LIST_ID.clone()
    }
}

impl<T> HyperList<T> {
    pub fn new() -> Self {
        let new_id = get_id();
        Self {
            size: 0,
            list_name: new_id.encode(),
            storage_prefix: "_".as_bytes().to_vec(),
            cache_values: BTreeMap::<i64, ValueWrapper<T>>::new(),
        }
    }
}

impl<T> HyperList<T>
    where
        T: Encode + Decode,
{

    // returns the value, the return can not be change
    fn get_by_key(&mut self, key: i64) -> Option<&T> {
        match self.cache_values.entry(key) {
            // not in cache
            Entry::Vacant(entry) => {
                // key to vec<u8>
                let storage_key = key.encode();// impl encode for i64
                let value = runtime::storage_read(storage_key.as_slice(), self.storage_prefix.as_slice());
                match value {
                    // get in DB
                    Some(v) => {
                        let input = &mut &v[..];
                        let res: T = T::decode(input).unwrap();
                        let wrapper = ValueWrapper::new(res, EntryState::NoChanged);
                        // save in cache
                        let va = entry.insert(wrapper);
                        va.value.as_ref()
                    }
                    // not in DB
                    None => {
                        None
                    }
                }
            }
            // in cache
            Entry::Occupied(entry) => {
                let ent = entry.into_mut();
                // has been deleted
                if ent.state == EntryState::Deleted {
                    return None;
                }
                ent.value.as_ref()
            }
        }
    }

    // the state should be changed, get None means be deleted or not exist 
    fn get_mut_by_key(&mut self, key: i64) -> Option<&mut T> {
        match self.cache_values.entry(key) {
            // not in cache
            Entry::Vacant(entry) => {
                let storage_key = key.encode();
                let value = runtime::storage_read(storage_key.as_slice(), self.storage_prefix.as_slice());
                match value {
                    // in DB
                    Some(v) => {
                        let input = &mut &v[..];
                        let res: T = T::decode(input).unwrap();
                        let wrapper = ValueWrapper::new(res, EntryState::Changed);
                        // save in cache
                        let va = entry.insert(wrapper);
                        va.value.as_mut()
                    }
                    // not in DB
                    None => {
                        None
                    }
                }
            }
            // in cache
            Entry::Occupied(entry) => {
                let ent = entry.into_mut();
                if ent.state == EntryState::Deleted {
                    return None;
                }
                ent.state = EntryState::Changed;
                ent.value.as_mut()
            }
        }
    }
    // replace: if old value exist, means replace, return old value
    // insert:  if old value not exist, means insert, return none
    fn insert_by_key(&mut self, key: i64, val: T) -> Option<T>{
        match self.get_mut_by_key(key) {
            // in cache or DB, replace
            Some(v)=>{
                let old_value = core::mem::replace(v, val);
                Some(old_value)
            }
            // insert new
            None=>{
                let wrapper = ValueWrapper::new(val, EntryState::Changed);
                // save in cache, if the old state is deleted, it will be updated
                self.cache_values.insert(key, wrapper);
                // update size
                self.size += 1;
                // no old value
                None
            }
        }
    }
    // remove, return old value if exist, else return none
    fn remove_by_key(&mut self, key: i64) -> Option<T> {
        // match self.get_mut_by_key(key) 
        match self.cache_values.entry(key) {
            // not in cache
            Entry::Vacant(entry) => {
                let storage_key = key.encode();
                let value = runtime::storage_read(storage_key.as_slice(), self.storage_prefix.as_slice());
                match value {
                    Some(v) => {
                        let input = &mut &v[..];
                        let res: T = T::decode(input).unwrap();
                        let wrapper = ValueWrapper::new_empty_value(EntryState::Deleted);
                        // push it to cache
                        entry.insert(wrapper);
                        self.size -= 1;  // change the size 
                        Some(res)
                    }
                    None => {
                        None
                    }
                }
            }
            // in cache
            Entry::Occupied(mut entry) => {
                // return from cache
                let old = entry.insert(ValueWrapper::new_empty_value(EntryState::Deleted));
                if old.state == EntryState::Deleted {
                    return None;
                }
                self.size -= 1;  // change the size
                return old.value;
            }
        }
    }

    // just call add
	pub fn push(&mut self, ele:  T) -> bool {
        self.insert(self.size, ele)
    }

    // insert ele
    // index<=size, index==size means append new value
    pub fn insert(&mut self, index: u32, ele: T) -> bool {
        // check index
        if index > self.size {
            return false;
        }
        // get key from mapping table
        match runtime::add_list_key(self.list_name.as_slice(), index) {
            Some(key) => {
                self.insert_by_key(key, ele);
                true
            }
            None => {
                false
            }
        }
    }

    // get immutable value
    pub fn get(&mut self, index: u32) -> Option<&T> {
        // check index
        if index >= self.size {
            return None;
        }
        match runtime::get_list_key(self.list_name.as_slice(), index) {
            Some(key) => {
                self.get_by_key(key)
            }
            None => {
                None
            }
        }
    }

    pub fn get_mut(&mut self, index: u32) -> Option<&mut T> {
        if index >= self.size {
            return None;
        }
        match  runtime::get_list_key(self.list_name.as_slice(), index){
            Some(key) => {
                self.get_mut_by_key(key)
            }
            None => {
                None
            }
        }
    }

    pub fn is_empty(&self) -> bool {
        self.size == 0
    }

    pub fn pop(&mut self) -> Option<T> {
        if self.len() == 0 {
            None
        } else {
           self.remove(self.len() - 1) 
        }
    }

    // remove index value and return old value
    // index<size,return old value, else return None
    pub fn remove(&mut self, index: u32) -> Option<T> {
        // check index
        if index >= self.size {
            return None;
        }
        match runtime::remove_list_key(self.list_name.as_slice(), index) {
            Some(key) => {
                self.remove_by_key(key)
            }
            None => {
                None
            }
        }
    }

    pub fn len(&self) -> u32 {
        self.size
    }

    //replace, index<size
    pub fn replace(&mut self, index: u32, ele :T) -> Option<T> {
        // check index
        if index >= self.size {
            return None;
        }
        match runtime::get_list_key(self.list_name.as_slice(), index) {
            Some(key) => {
                self.insert_by_key(key, ele)
            }
            None => {
                None
            }
        }
    }
}

impl<T> Default for HyperList<T> {
    fn default() -> Self {
        HyperList::new()
    }
}

impl<T> SpreadLayout for HyperList<T>
    where
        T: Encode + Decode
{
    // deploy will not call this function
    fn read_ledger(list_name: &[u8], _: &[u8]) -> Self {
        let mut list: HyperList<T> = HyperList::<T>::new();
        list.list_name = Vec::from(list_name);
        // storage_prefix is list_name@K
        list.storage_prefix = Vec::from([list_name, "@K".as_bytes()].concat());
        // read the root_info and get size in it
        let root_info = runtime::storage_read(list_name, "@HyperList".as_bytes()).unwrap();
        // decode will call u32::from_le_bytes, it is little endian decode
        list.size = <u32 as scale::Decode>::decode(&mut &root_info[0..4]).unwrap();
        list
    }

    fn write_ledger(&self, list_name: &[u8], deploy_flag: &[u8]) {
        // "write_list_keys_back" check the size and write mapping tables back, if size is not equal in VM, then error happens
        if deploy_flag == "deploy".as_bytes() {
            // when deploy self.list_name = id.encode()
            runtime::write_list_keys_back(self.list_name.as_slice(), list_name, self.size)
        } else {
            runtime::write_list_keys_back("".as_bytes(), list_name, self.size);
        }
        // write elements back
        let storage_prefix = Vec::from([list_name, "@K".as_bytes()].concat());
        self.cache_values.iter().for_each(|(key, value)| {
            match value.state {
                EntryState::Changed => {
                    let storage_key = key.encode();
                    let storage_value = value.value.as_ref().unwrap().encode();
                    runtime::storage_write(storage_key.as_slice(), storage_prefix.as_slice(), storage_value.as_slice());
                }
                EntryState::Deleted => {
                    let storage_key = key.encode();
                    runtime::storage_delete(storage_key.as_slice(), storage_prefix.as_slice());
                }
                _ => {}
            }
        });

    }
}

#[cfg(test)]
mod test {
    use crate::collections::hyper_list::HyperList;
    use crate::spread::SpreadLayout;
    use crate::runtime;
    use scale::Encode;
    use scale::Decode;
    #[test]
    fn use_list_normal() {
        let _mock = fvm_mock::build_runtime();
        // deploy
        let list: HyperList<String> =  HyperList::new();
        list.write_ledger("list".as_bytes(), "deploy".as_bytes());

        // invoke
        let mut list: HyperList<String> = HyperList::read_ledger("list".as_bytes(), "invoke".as_bytes());
        let res = list.insert(0, String::from("123"));
        assert_eq!(res, true);
        let res = list.get(0).unwrap();
        assert_eq!(res, &String::from("123"));
    }

    #[test]
    fn list_add_set() {
        let _mock = fvm_mock::build_runtime();
        // deploy
        let list: HyperList<i32> =  HyperList::new();
        list.write_ledger("list".as_bytes(), "deploy".as_bytes());

        // invoke
        let mut list: HyperList<i32> = HyperList::read_ledger("list".as_bytes(), "invoke".as_bytes());
        for i in 0..100 {
            let res = list.insert(i, (i+100) as i32);
            assert_eq!(res, true);
        }
        // write back
        list.write_ledger(list.list_name.as_slice(), "invoke".as_bytes());
        // clear cache
        list.cache_values.clear();
        // get
        for i in 0..100 {
            let res = list.get(i);
            assert_eq!(res, Some(&((i+100) as i32)));
        }
        list.write_ledger(list.list_name.as_slice(), "invoke".as_bytes());
    }


    #[test]
    fn list_delete() {
        #[derive(Encode, Decode, Eq, PartialEq, Debug)]
        struct Student {
            id: u32,
            name: String,
        }
        let _mock = fvm_mock::build_runtime();
        // deploy
        let list: HyperList<Student> =  HyperList::new();
        list.write_ledger("list".as_bytes(), "deploy".as_bytes());

        // invoke
        let mut list: HyperList<Student> = HyperList::read_ledger("list".as_bytes(), "invoke".as_bytes());
        // add
        let res = list.insert(0, Student { id: 1, name: String::from("s1") });
        assert_eq!(res, true);
        let res = list.insert(0, Student { id: 0, name: String::from("s0") });
        assert_eq!(res, true);
        assert_eq!(list.len(), 2);

        //delete 
        let old_value = list.remove(0);
        assert_eq!(old_value, Some(Student{id: 0, name: String::from("s0")}));
        assert_eq!(list.get(1), None);
        assert_eq!(list.is_empty(), false);
        assert_eq!(list.get(0), Some(&Student { id: 1, name: String::from("s1") }));

        // write back and clear cache
        list.storage_prefix = [list.list_name.as_slice(), "@K".as_bytes()].concat().to_vec();
        list.write_ledger(list.list_name.as_slice(), "invoke".as_bytes());
        list.cache_values.clear();
        // 1.encode get vec length is 4, 1i64.encode is 8
        assert_eq!(runtime::storage_read(1i64.encode().as_slice(), list.storage_prefix.as_slice()), None);
        assert_eq!(runtime::storage_read(0i64.encode().as_slice(), list.storage_prefix.as_slice()), Some(Student { id: 1, name: String::from("s1") }.encode()));
    }

    #[test]
    fn list_operate_many_times() {
        let _mock = fvm_mock::build_runtime();
        // deploy
        let list: HyperList<i32> =  HyperList::new();
        list.write_ledger("list".as_bytes(), "deploy".as_bytes());

        // invoke
        let mut list: HyperList<i32> = HyperList::read_ledger("list".as_bytes(), "invoke".as_bytes());
        // add(insert)
        assert_eq!(list.insert(0, 54), true);
        assert_eq!(list.insert(0, 56), true);
        assert_eq!(list.insert(4, 33), false);
        assert_eq!(list.get(0), Some(&56));
        assert_eq!(list.get_mut(0), Some(&mut 56));
        // write back and clear cache
        list.write_ledger(list.list_name.as_slice(), "invoke".as_bytes());
        list.cache_values.clear();

        // set(replace)
        assert_eq!(list.replace(0, 101), Some(56));
        assert_eq!(list.replace(1, 111), Some(54));
        assert_eq!(list.replace(0, 2331), Some(101));
        assert_eq!(list.replace(0, 100), Some(2331));
        // write back and clear cache
        list.write_ledger(list.list_name.as_slice(), "invoke".as_bytes());
        list.cache_values.clear();

        // remove
        assert_eq!(list.remove(1), Some(111));
        assert_eq!(list.remove(0), Some(100));
        assert_eq!(list.remove(0), None);

        assert_eq!(list.is_empty(), true);
        // write back and clear cache
        list.write_ledger(list.list_name.as_slice(), "invoke".as_bytes());
        list.cache_values.clear();

        // append
        assert_eq!(list.push(77), true);
        assert_eq!(list.push(88), true);
        assert_eq!(list.len(), 2);

        // write ele back
        list.write_ledger(list.list_name.as_slice(), "invoke".as_bytes());
        let  root = vec![0;24];
        let  first_four = 2.encode();
        let root = [ first_four, root].concat();
        runtime::storage_write(list.list_name.as_slice(), "@HyperList".as_bytes(), root.as_slice());

        // test read_ledger
        let new_list: HyperList<i64> = HyperList::read_ledger(list.list_name.as_slice(), "".as_bytes());
        assert_eq!(list.list_name, new_list.list_name);
        assert_eq!(list.storage_prefix, new_list.storage_prefix);
        assert_eq!(list.size, new_list.size);
    }
}