tablestg 0.3.0

use crate::{Key, PAGE_SIZE, PageSet, SmallFixed};
use std::marker::PhantomData;

/// For reading Hash Map Bucket.
pub struct Reader<'a, T>
where
    T: SmallFixed,
{
    pub data: &'a [u8],
    pd: PhantomData<T>,
}

/// For writing Hash Map Bucket.
pub struct Writer<'a, T>
where
    T: SmallFixed,
{
    pub data: &'a mut [u8],
    pd: PhantomData<T>,
}

/// Number of slots.
const SLOTS: usize = 253; // Fairly arbitrary, a larger number reduces collisions.

// Page offsets,
// USED, FREE are single byte fields.
// SLOT is 253 bytes.
// This is follow by entry array, each entry has has 1 byte NEXT, 8 byte hash, T::size() bytes.

const USED: usize = 0;
const FREE: usize = USED + 1;
const SLOT: usize = FREE + 1;
const VALA: usize = SLOT + SLOTS;

/// Bucket capacity ( number of entries )
fn ents<T>() -> u8
where
    T: SmallFixed,
{
    let mut result = (PAGE_SIZE as usize - VALA) / esize::<T>();
    if result > 255 {
        result = 255;
    }
    result as u8
}

/// Size of entry.
fn esize<T>() -> usize
where
    T: SmallFixed,
{
    // One byte for next link, 8 bytes for hash, T::size() for value.
    1 + 8 + T::size()
}

/// Bucket size
pub fn size<T>() -> usize
where
    T: SmallFixed,
{
    VALA + (ents::<T>() as usize) * esize::<T>()
}

fn eoff<T>(entry: u8) -> usize
where
    T: SmallFixed,
{
    VALA + (entry as usize - 1) * esize::<T>()
}

impl<'a, T> Reader<'a, T>
where
    T: SmallFixed,
{
    pub fn new(data: &'a [u8]) -> Self {
        Self {
            data,
            pd: PhantomData,
        }
    }

    /// Get value associated with key.
    pub fn get<K: Key<T>>(&self, key: &K, hash: u64, ps: &mut PageSet) -> Option<T> {
        let slot = (hash % SLOTS as u64) as usize;
        let mut entry = self.data[SLOT + slot];
        while entry != 0 {
            let (v, h) = self.get_vh(entry);
            if h == hash && key.equal(&v, ps) {
                return Some(v);
            }
            entry = self.get_next(entry);
        }
        None
    }

    fn get_next(&self, entry: u8) -> u8 {
        self.data[eoff::<T>(entry)]
    }

    /// Get value and hash from entry array.
    fn get_vh(&self, entry: u8) -> (T, u64) {
        let off = eoff::<T>(entry) + 1;
        let loc = &self.data[off..off + 8];
        let h = u64::from_le_bytes(loc.try_into().unwrap());
        let loc = &self.data[off + 8..off + 8 + T::size()];
        let v = T::load(loc);
        (v, h)
    }

    /// Iterator - returns id/hash pairs.
    pub fn iter(self) -> Iter<'a, T> {
        Iter {
            slot: 0,
            entry: 0,
            r: self,
        }
    }
}

/// Iterator - returns T/hash pairs.
pub struct Iter<'a, T>
where
    T: SmallFixed,
{
    slot: usize,
    entry: u8,
    r: Reader<'a, T>,
}

impl<'a, T> Iterator for Iter<'a, T>
where
    T: SmallFixed,
{
    type Item = (T, u64);
    fn next(&mut self) -> Option<Self::Item> {
        let mut entry = self.entry;
        while entry == 0 {
            if self.slot == SLOTS {
                return None;
            }
            entry = self.r.data[SLOT + self.slot];
            self.slot += 1;
        }
        let (v, h) = self.r.get_vh(entry);
        self.entry = self.r.get_next(entry);
        Some((v, h))
    }
}

impl<'a, T> Writer<'a, T>
where
    T: SmallFixed,
{
    pub fn new(data: &'a mut [u8]) -> Self {
        Self {
            data,
            pd: PhantomData,
        }
    }

    /// Insert into Hash Map Page.
    ///
    /// Pre-conditions : page must not be full, must have already done lookup to check key is not already in page.
    pub fn insert(&mut self, v: T, hash: u64) {
        let slot = (hash % SLOTS as u64) as usize;
        let new_entry = self.alloc_entry();
        self.set_vh(new_entry, v, hash);
        let old_entry = self.data[SLOT + slot];
        self.set_next(new_entry, old_entry);
        self.data[SLOT + slot] = new_entry;
    }

    /// Is the page full? This must be checked before attempting to insert.
    pub fn full(&self) -> bool {
        self.data[FREE] == 0 && self.data[USED] == ents::<T>()
    }

    /// Remove a key.
    pub fn remove<K: Key<T>>(&mut self, key: &K, hash: u64, ps: &mut PageSet) -> Option<T> {
        let slot = (hash % SLOTS as u64) as usize;
        let mut entry = self.data[SLOT + slot];
        let mut prev = None;
        while entry != 0 {
            let (v, h) = self.get_vh(entry);
            let next = self.get_next(entry);
            if h == hash && key.equal(&v, ps) {
                // Remove entry.
                if let Some(prev) = prev {
                    self.set_next(prev, next);
                } else {
                    self.data[SLOT + slot] = next;
                }
                // Put entry in free chain.
                self.set_next(entry, self.data[FREE]);
                self.data[FREE] = entry;
                return Some(v);
            }
            prev = Some(entry);
            entry = next;
        }
        None
    }

    fn alloc_entry(&mut self) -> u8 {
        let result = self.data[FREE];
        if result != 0 {
            self.data[FREE] = self.get_next(result);
            return result;
        }
        let result = self.data[USED];
        self.data[USED] += 1;
        result + 1
    }

    fn get_next(&self, entry: u8) -> u8 {
        self.data[eoff::<T>(entry)]
    }

    fn set_next(&mut self, entry: u8, val: u8) {
        self.data[eoff::<T>(entry)] = val;
    }

    /// Get value and hash from entry array.
    fn get_vh(&self, entry: u8) -> (T, u64) {
        let off = eoff::<T>(entry) + 1;
        let loc = &self.data[off..off + 8];
        let h = u64::from_le_bytes(loc.try_into().unwrap());

        let loc = &self.data[off + 8..off + 8 + T::size()];
        let v = T::load(loc);
        (v, h)
    }

    fn set_vh(&mut self, entry: u8, v: T, hash: u64) {
        let off = eoff::<T>(entry) + 1;
        let loc = &mut self.data[off..off + 8];
        loc.copy_from_slice(&hash.to_le_bytes());

        // println!( "data len={} off={} T::size={} size::<T>={}", self.data.len(), 8+off, T::size(), size::<T>() );

        let loc = &mut self.data[off + 8..off + 8 + T::size()];
        v.save(loc)
    }
}