tablestg 0.4.10

//! Everything is very preliminary, this crate is not yet at all stable.

pub use atom_file::Data;
use std::hash::Hash;

/// [PageSet] - keeps track of changed pages that need saving.
pub mod pageset;
pub use pageset::*;

/// [BuckMap] - maps keys to const size values using 64 bit hash.
pub mod buckmap;
pub use buckmap::*;

/// [VBuckMap] - maps keys to small variable size values using 64 bit hash.
pub mod vbuckmap;
pub use vbuckmap::*;

/*
/// [Table] -- fixed size record storage. Divided into pages, each page stores up to 128 records.
pub mod table;
pub use table::*;
*/

/// [VarValAddr] -- storage of variable length values.
pub mod varval;
pub use varval::*;

/// ToDo
pub mod sys;
pub use sys::*;

/// [DataType] -- describes data type
pub mod datatype;
pub use datatype::*;

/// [Value] -- generic instance of a data type
pub mod value;
pub use value::*;

// Private modules.

/// [PageTree] - list of pages implemented as tree.
mod pagetree;
use pagetree::*;

/// [TreeVec] -- a variable length list of bytes.
pub mod treevec;
use treevec::*;

/// Bucket for [BuckMap].
mod bucket;

/// Bucket for [VBuckMap].
pub mod vbucket;

const PAGE_SIZE: u64 = 3952;
// pub const PAGE_SIZE: u64 =  3952;
// pub const PAGE_SIZE: u64 =  4612;

use pstd::localalloc::Local;
/// `StringA<Local>`
pub type LString = pstd::StringA<Local>;
/// `VecA<T, Local>`
pub type LVec<T> = pstd::VecA<T, Local>;
/// `BoxA<T, Local>`
pub type LBox<T> = pstd::BoxA<T, Local>;

pub use pstd::rc::Rc;
pub use std::sync::Arc; // pstd::Arc does not yet have make_mut

mod test;

#[cfg(test)]
fn tos(s: &[u8]) -> &str {
    str::from_utf8(s).unwrap()
}

/*
   Could have multiple VarVarStores (each is a simple TreeVec).
   When free space becomes significant (say 20%, or after a long time), garbage collect the store.
   When the Store has been emptied, free all pages and add it to free slot list.
   Note: large records (>16kb) are stored as TreeVec not in a VarValStore.
   Stores should be limited to some reasonable size, say 4MB.
   Index into store is then 22 bits. Index into Store TreeVec can be 32 bits.
   This means garbage collecting a store is reasonably cheap.

   To Access a Store, we first get the Meta info using a TreeVec.
   Meta Data for store:
      Total Free Bytes, TreeVec root and length, Next free Slot.

   Global Info: TreeVec ( root + length ).
   Header : First Free Slot, Number of Slots, Current Store (index).

   Table module is no longer used.
*/

/* Next:

   Expressions, Instructions, Functions.

   Execution of batch of statements.

   Parsing SQL variant to convert to instructions.

*/

pub struct Exp {
    pub inner: ExpInner,
}

pub enum ExpInner {
    LocalVarRef(usize),
    Binary(LBox<Exp>, LBox<Exp>),
}

/*
Design new page format for BTree-based tables.

Allow variable length fields ( indirection within page ).
Fast sequential access.
Don't worry about update speed too much ( append to free space, when it is exhausted, reformat on save ).
Start with a specification ( insert, delete, update, iterate etc ) Make it generic over row type.
*/

pub trait Row {
    fn size(&self) -> usize;
    fn compare(&self, data: &[u8]) -> Ordering;
    fn store(&self, data: &mut [u8]);
}

/* Page structure.
   data area: each record has length (if data is variable length),
      followed by fixed size data and variable size data ( up to 255 bytes ).
   slot array of 12-bit offsets ( sorted in order ),
      also flag indicating if data is variabkle length.
*/

use std::cmp::Ordering;
use std::marker::PhantomData;

pub struct OpenPage<T: Row> {
    pub data: Data,
    pub pd: PhantomData<T>,
}

impl<T: Row> OpenPage<T> {
    // Create a new page.
    pub fn new(n: usize) -> Self {
        let data = Arc::new(vec![0; n]);
        Self {
            data,
            pd: PhantomData,
        }
    }

    /// Number of rows.
    pub fn rows(&self) -> usize {
        self.data[0] as usize
    }

    pub fn space(&self) -> usize {
        self.data.len() - self.rows() * 2 - self.alloc()
    }

    // Insert row into page.
    pub fn insert(&mut self, r: &T) -> bool {
        let n = r.size();
        if self.space() < n + 2 {
            return false;
        }

        let ipos = self.search(r);
        println!("ipos={}", ipos);

        let end = self.alloc();
        let rows = self.rows();

        let md = Arc::make_mut(&mut self.data);

        let start = if ipos < rows {
            let start = Self::row_off(md, ipos);

            for i in 0..end - start {
                md[end + n - i - 1] = md[end - i - 1];
            }

            // Move existing row offsets up, increasing offsets by dist.
            let mut x = rows;
            while x != ipos {
                let off = Self::row_off(md, x - 1);
                Self::set_row_off(md, x, off + n);
                x -= 1;
            }
            start
        } else {
            end
        };

        r.store(&mut md[start..start + n]);

        Self::set_row_off(md, ipos, start);
        Self::set_rows(md, rows + 1);
        Self::set_alloc(md, end + n);

        true
    }

    /// Get data for ith row.
    pub fn slice(&self, i: usize) -> &[u8] {
        let off = Self::row_off(&self.data, i);
        let end = if i + 1 == self.rows() {
            self.alloc()
        } else {
            Self::row_off(&self.data, i + 1)
        };
        &self.data[off..end]
    }

    fn search(&self, r: &T) -> usize {
        let mut i = 0;
        let mut j = self.rows();
        while i != j {
            let m = (i + j) / 2;
            let s = self.slice(m);
            match r.compare(s) {
                Ordering::Equal => panic!("duplicate"),
                Ordering::Greater => i = m + 1,
                Ordering::Less => j = m,
            }
        }
        i
    }

    fn set_rows(md: &mut [u8], to: usize) {
        md[0] = to as u8;
    }

    /// Amount of data allocated ( includes 3 byte header )
    fn alloc(&self) -> usize {
        3 + self.data[1] as usize + (self.data[2] as usize * 256)
    }

    fn set_alloc(md: &mut [u8], to: usize) {
        let to = to - 3;
        md[1] = (to % 256) as u8;
        md[2] = ((to / 256) % 256) as u8;
    }
    /// Offset of ith row.
    fn row_off(d: &[u8], i: usize) -> usize {
        let x = d.len() - (i + 1) * 2;
        d[x] as usize + (d[x + 1] as usize) * 256
    }

    fn set_row_off(md: &mut [u8], i: usize, to: usize) {
        let x = md.len() - (i + 1) * 2;
        md[x] = (to % 256) as u8;
        md[x + 1] = ((to / 256) % 256) as u8;
    }
}

#[derive(Debug)]
pub struct TestRow {
    s: String,
}

impl Row for TestRow {
    fn size(&self) -> usize {
        self.s.len()
    }
    fn compare(&self, data: &[u8]) -> Ordering {
        self.s.as_bytes().cmp(data)
    }
    fn store(&self, data: &mut [u8]) {
        data.copy_from_slice(self.s.as_bytes());
    }
}

#[cfg(test)]
fn insert(op: &mut OpenPage<TestRow>, s: &str) {
    let r = TestRow { s: s.to_string() };
    op.insert(&r);
    println!("space={} data={:?}", op.space(), op.data);
}

#[test]
fn test_openpage() {
    let mut op = OpenPage::<TestRow>::new(300);
    let p = &mut op;

    insert(p, "hello george");
    insert(p, "zzzz");
    insert(p, "aaa");
    insert(p, "ddddd");
    insert(p, "yyy");

    for i in 0..op.rows() {
        println!("i={} r={:?}", i, tos(op.slice(i)));
    }

    println!("Ok George");
}

/*
   Another approach would be to use hash tables, but have VarVal store lengths and record status ( Deleted ).
   Low bit of length is reserved for "deleted" flag.
   When we scan a table, the deleted rows are ignored.
   This allows both fast random access, and fast table scan.

   But for small fixed size records, can simply store data in the hash table.
   Or store variable size records in hash table page.

   Entry is offset and length of data.
   Hash page structure is

   Slots | Entries | Data

   When an entry is deleted, there can be free space in the data area.
   This is tracked. If bucket is full, can compress to new bucket ( only entry offsets are changed ).

*/