tablestg 0.1.0

use crate::*;

/// Hash Map implemented as list of buckets.
pub struct HashMap<'a> {
    /// Number of buckets.
    buckets: u64,
    /// Root page.
    root: u64,
    /// Pageset.
    ps: &'a mut PageSet,
    /// Has root changed?
    new_root: bool,
}

impl<'a> HashMap<'a> {
    /// Start a new map with specified number of buckets.
    pub fn new(ps: &'a mut PageSet, buckets: u64) -> Self {
        let mut pt = PageTree::new(ps.new_page(), 1, ps);
        pt.resize(buckets);
        Self {
            buckets,
            root: pt.root,
            ps,
            new_root: true,
        }
    }

    /// Insert id, must not be a duplicate ( but this is not checked ).
    pub fn insert<K: Key>(&mut self, key: &K, id: u64) {
        let hash = key.hash();
        self.do_insert(id, hash);
    }

    /// Get id from specified key, returns None if key not found.
    pub fn get<K: Key>(&mut self, key: &K) -> Option<u64> {
        let hash = key.hash();
        let pnum = self.get_page_num(hash, false);
        if pnum == 0 {
            return None;
        }
        let (data, changed) = self.ps.load(pnum);
        let result = bucket::Reader { data: &data }.get(key, hash);
        self.ps.note(pnum, data, changed);
        result
    }

    /// Remove a key, returns id or None if key not found.
    pub fn remove<K: Key>(&mut self, key: &K) -> Option<u64> {
        let hash = key.hash();
        let pnum = self.get_page_num(hash, false);
        if pnum != 0 {
            let (mut data, changed) = self.ps.load(pnum);
            let md = Arc::make_mut(&mut data);
            let mut w = bucket::Writer { data: md };
            let result = w.remove(key, hash);
            self.ps.note(pnum, data, changed || result.is_some());
            return result;
        }
        None
    }

    /// Has root and buckets changed ( so needs to be saved )?
    pub fn root_changed(&self) -> bool {
        self.new_root
    }

    /// Get the root and number of buckets. These can change on any insert.
    pub fn save(&self) -> (u64, u64) {
        (self.root, self.buckets)
    }

    /// Restore from saved root and buckets.
    pub fn restore(ps: &'a mut PageSet, (root, buckets): (u64, u64)) -> Self {
        Self {
            root,
            buckets,
            ps,
            new_root: false,
        }
    }

    /// Get Vec of all id/hash pairs.
    pub fn all(&mut self) -> Vec<(u64, u64)> {
        let mut pt = PageTree::new(self.root, self.buckets, self.ps);
        let mut result = Vec::new();
        for pix in 0..self.buckets {
            let pnum = pt.get(pix, false);
            if pnum != 0 {
                let (data, changed) = pt.ps.load(pnum);
                let r = bucket::Reader { data: &data };
                for x in r.iter() {
                    result.push(x);
                }
                pt.ps.note(pnum, data, changed);
            }
        }
        result
    }

    /// Delete everything. Map is no longer usable.
    pub fn delete(&mut self) {
        let mut pt = PageTree::new(self.root, self.buckets, self.ps);
        pt.drop_pages();
        self.root = 0;
    }

    fn get_page_num(&mut self, hash: u64, create: bool) -> u64 {
        let pix = hash % self.buckets;
        PageTree::new(self.root, self.buckets, self.ps).get(pix, create)
    }

    fn do_insert(&mut self, id: u64, hash: u64) {
        while self.try_insert(id, hash) {
            self.expand();
        }
    }

    fn try_insert(&mut self, id: u64, hash: u64) -> bool {
        let pnum = self.get_page_num(hash, true);
        let (mut data, changed) = self.ps.load(pnum);

        let md = Arc::make_mut(&mut data);
        md.resize(bucket::SIZE, 0);

        let mut w = bucket::Writer { data: md };
        if w.full() {
            self.ps.note(pnum, data, changed);
            true
        } else {
            w.insert(id, hash);
            self.ps.note(pnum, data, true);
            false
        }
    }

    fn expand(&mut self) {
        let buckets = 1 + self.buckets * 9 / 8;
        let list = self.all();
        self.delete();

        let mut m = HashMap::new(self.ps, buckets);
        for (r, h) in list {
            m.do_insert(r, h);
        }

        self.root = m.root;
        self.buckets = m.buckets;
        self.new_root = true;
    }
}

#[cfg(test)]
struct TestKey {
    value: u64,
}

#[cfg(test)]
impl Key for TestKey {
    fn hash(&self) -> u64 {
        self.value + 99
    }
    fn equal(&self, r: u64) -> bool {
        self.value == r
    }
}

#[cfg(test)]
pub fn test_hash(ps: &mut PageSet) {
    let mut hm = HashMap::new(ps, 1);

    let last = 800;

    for tv in 1..last {
        let key = TestKey { value: tv };
        hm.insert(&key, tv);
    }
    println!("test_hash hm.buckets={}", hm.buckets);

    for tv in 1..last {
        let key = TestKey { value: tv };
        let x = hm.get(&key);

        // println!("x={:?}", x);
        assert!(x == Some(tv));
    }

    for tv in 1..last {
        let key = TestKey { value: tv };
        let x = hm.remove(&key);

        // println!("x={:?}", x);
        assert!(x == Some(tv));
    }
}