tablestg 0.3.0

use crate::*;

/// Stores up to 64 records.
struct TablePage<'a> {
    pub bmp: u64,
    pub v: TreeVec<'a>,
    pub record_size: usize,
}

impl<'a> TablePage<'a> {
    fn restore(mut v: TreeVec<'a>, record_size: usize) -> Self {
        let bmp = v.read_u64(0);
        Self {
            bmp,
            v,
            record_size,
        }
    }

    fn save_bmp(&mut self) {
        self.v.write_u64(0, self.bmp);
    }

    pub fn valid(&self) -> usize {
        self.bmp.count_ones() as usize
    }

    fn index(&self, id: u8) -> usize {
        let mask: u64 = (1u64 << id) - 1;
        let upto: u64 = mask & self.bmp;

        upto.count_ones() as usize
    }

    fn test_bit(&self, id: u8) -> bool {
        let mask: u64 = 1u64 << id;
        let test: u64 = mask & self.bmp;
        test != 0
    }

    fn set_bit(&mut self, id: u8) {
        let mask: u64 = 1u64 << id;
        self.bmp |= mask;
    }

    fn clear_bit(&mut self, id: u8) {
        let mask: u64 = 1u64 << id;
        let mask = u64::MAX - mask;
        self.bmp &= mask;
    }

    /*
        fn last_id(&self) -> u8
        {
           if self.bmp == 0 { return 0; }
           1 + self.bmp.ilog2() as u8
        }
    */

    fn offset(&self, ix: usize) -> u64 {
        8 + (ix as u64) * self.record_size as u64
    }

    pub fn append(&mut self, id: u8, user_data: &[u8]) {
        assert!(user_data.len() <= self.record_size);
        assert!(!self.test_bit(id));

        let ix = self.index(id);
        let off = self.offset(ix);

        self.v.write(off, user_data);
        self.set_bit(id);
    }

    pub fn read(&mut self, id: u8, user_data: &mut [u8]) {
        assert!(self.test_bit(id));

        let ix = self.index(id);
        let off = self.offset(ix);
        self.v.read(off, user_data);
    }

    pub fn update(&mut self, id: u8, user_data: &[u8]) {
        assert!(self.test_bit(id));

        let ix = self.index(id);
        let off = self.offset(ix);
        self.v.write(off, user_data);
    }

    pub fn delete(&mut self, id: u8) {
        assert!(self.test_bit(id));

        // Shuffle remaining records down.
        let ix = self.index(id);
        let mut buf = vec![0; self.record_size];

        for i in ix..self.valid() {
            let off = self.offset(i);
            self.v.read(off + self.record_size as u64, &mut buf);
            self.v.write(off, &buf);
        }
        // ToDo : truncate self.v, size = 8 + self.valid() * self.record_size
        self.clear_bit(id);
    }
}

/// Stores records, which have 64 bit ids.
///
/// ToDo : implement iterator struct to rapidly traverse all records.
///
/// Note : no reference to PageSet as we want to operate on many tables all at once.
#[derive(Debug)]
pub struct Table {
    pub next_id: u64,
    pub root: u64, // Root of TreeVec that stores TablePage root info.
    pub len: u64,  // Length of TreeVec that stores TablePage root info.
    pub record_size: usize,
    pub rpp: u64, // Can be either 64 or less (for large record sizes).
}

impl Table {
    /// Append a new record to the table, returns id of new record.
    pub fn append(&mut self, user_data: &[u8], ps: &mut PageSet) -> u64 {
        assert!(self.record_size >= user_data.len());

        let id = self.next_id;
        self.next_id += 1;
        // self.info_changed = true;

        let pix = id / self.rpp;
        let local_id = (id % self.rpp) as u8;

        let (root, len) = self.get_child_tv(pix, ps);

        let v = TreeVec::new(root, len, ps);

        let mut tp = TablePage::restore(v, self.record_size);
        tp.append(local_id, user_data);
        tp.save_bmp();

        let (root, len) = (tp.v.root, tp.v.len);
        self.save_child_tv(pix, root, len, ps);

        id
    }

    /// Read a record, identified by supplied id.
    pub fn read(&self, id: u64, user_data: &mut [u8], ps: &mut PageSet) {
        assert!(self.record_size >= user_data.len());
        let pix = id / self.rpp;
        let local_id = (id % self.rpp) as u8;
        let (root, len) = self.get_child_tv(pix, ps);

        let v = TreeVec::new(root, len, ps);
        let mut tp = TablePage::restore(v, self.record_size);
        tp.read(local_id, user_data);
    }

    /// Update a record, identified by supplied id.
    pub fn update(&mut self, id: u64, user_data: &[u8], ps: &mut PageSet) {
        assert!(self.record_size >= user_data.len());
        let pix = id / self.rpp;
        let local_id = (id % self.rpp) as u8;
        let (root, len) = self.get_child_tv(pix, ps);

        let v = TreeVec::new(root, len, ps);
        let mut tp = TablePage::restore(v, self.record_size);
        tp.update(local_id, user_data);
    }

    /// Delete record identified by supplied id.
    pub fn delete(&mut self, id: u64, ps: &mut PageSet) {
        let pix = id / self.rpp;
        let local_id = (id % self.rpp) as u8;
        let (root, len) = self.get_child_tv(pix, ps);

        let v = TreeVec::new(root, len, ps);
        let mut tp = TablePage::restore(v, self.record_size);
        tp.delete(local_id);
    }

    /// Delete range of records.
    pub fn delete_range(&mut self, mut id: u64, mut count: usize, ps: &mut PageSet) {
        // Should be optimised to use tp.delete_range.
        while count > 0 {
            self.delete(id, ps);
            id += 1;
            count -= 1;
        }
    }

    /// Get root and len of TablePage specified by supplied pix.
    fn get_child_tv(&self, pix: u64, ps: &mut PageSet) -> (u64, u64) {
        let mut tv = TreeVec::new(self.root, self.len, ps);
        let mut buf = [0u8; 16];
        tv.read(pix * 16, &mut buf);

        // Extract root and length from buf.
        let loc = &buf[0..8];
        let mut root = u64::from_le_bytes(loc.try_into().unwrap());

        let loc = &buf[8..16];
        let mut len = u64::from_le_bytes(loc.try_into().unwrap());

        if root == 0 {
            root = tv.ps.new_page();
            len = 0;
        }
        (root, len)
    }

    /// Save root and len of TablePage specified by supplied pix.
    fn save_child_tv(&mut self, pix: u64, root: u64, len: u64, ps: &mut PageSet) {
        let mut buf = [0u8; 16];

        let loc = &mut buf[0..8];
        loc.copy_from_slice(&root.to_le_bytes());

        let loc = &mut buf[8..16];
        loc.copy_from_slice(&len.to_le_bytes());

        let mut tv = TreeVec::new(self.root, self.len, ps);
        tv.write(pix * 16, &buf);

        if tv.root_changed || tv.len_changed {
            self.root = tv.root;
            self.len = tv.len;
            // self.info_changed = true;
        }
    }
}

#[cfg(test)]
pub fn test_table(ps: &mut PageSet) {
    let mut t = Box::new(Table {
        next_id: 0,
        root: ps.new_page(),
        len: 0,
        record_size: 6,
        rpp: 64,
    });

    let d1 = b"George";
    let id1 = t.append(d1, ps);
    let mut buf = [0u8; 6];
    t.read(id1, &mut buf, ps);
    println!("buf={}", tos(&buf));
    assert_eq!(d1, &buf);

    let d2 = b"Barwoo";
    let id2 = t.append(d2, ps);
    let mut buf = [0u8; 6];
    t.read(id2, &mut buf, ps);
    println!("buf={}", tos(&buf));
    assert_eq!(d2, &buf);

    let d3 = b"Marily";
    let id3 = t.append(d3, ps);

    println!("table info = {:?}", t);

    t.delete(id2, ps);

    // Check 3rd record still ok after delete.
    let mut buf = [0u8; 6];
    t.read(id3, &mut buf, ps);
    println!("buf={}", tos(&buf));
    assert_eq!(d3, &buf);

    println!("table info = {:?}", t);

    let d1x = b"Cather";
    t.update(id1, d1x, ps);

    let mut buf = [0u8; 6];
    t.read(id1, &mut buf, ps);
    println!("buf={}", tos(&buf));
    assert_eq!(d1x, &buf);
}