tablestg 0.1.0

use crate::Key;

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

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

/// Number of entries, maximum is 255.
const ENTS: usize = 127;
/// Number of slots.
const SLOTS: usize = 253; // Fairly arbitrary, a larger number reduces collisions.

// Page offsets,
const REFA: usize = 0;
const SLOT: usize = REFA + ENTS * 16;
const NEXT: usize = SLOT + SLOTS;
const USED: usize = NEXT + ENTS;
const FREE: usize = USED + 1;
pub const SIZE: usize = FREE + 1;

impl<'a> Reader<'a> {
    /// Get id associated with key.
    pub fn get<K: Key>(&self, key: &K, hash: u64) -> Option<u64> {
        let slot = (hash % SLOTS as u64) as usize;
        let mut entry = self.data[SLOT + slot];
        while entry != 0 {
            let (r, h) = self.get_ref(entry);
            if h == hash && key.equal(r) {
                return Some(r);
            }
            entry = self.get_next(entry);
        }
        None
    }

    fn get_next(&self, ix: u8) -> u8 {
        self.data[NEXT + (ix - 1) as usize]
    }

    /// Get id and hash from entry array.
    fn get_ref(&self, entry: u8) -> (u64, u64) {
        let off = REFA + (entry as usize - 1) * 16;
        let loc = &self.data[off..off + 8];
        let r = u64::from_le_bytes(loc.try_into().unwrap());
        let loc = &self.data[off + 8..off + 16];
        let h = u64::from_le_bytes(loc.try_into().unwrap());
        (r, h)
    }

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

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

impl<'a> Iterator for Iter<'a> {
    type Item = (u64, 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 (r, h) = self.r.get_ref(entry);
        self.entry = self.r.get_next(entry);
        Some((r, h))
    }
}

impl<'a> Writer<'a> {
    /// 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, id: u64, hash: u64) {
        let slot = (hash % SLOTS as u64) as usize;
        let new_entry = self.alloc_entry();
        self.set_ref(new_entry, id, 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] as usize == ENTS
    }

    /// Remove a key.
    pub fn remove<K: Key>(&mut self, key: &K, hash: u64) -> Option<u64> {
        let slot = (hash % SLOTS as u64) as usize;
        let mut entry = self.data[SLOT + slot];
        let mut prev = None;
        while entry != 0 {
            let (r, h) = self.get_ref(entry);
            let next = self.get_next(entry);
            if h == hash && key.equal(r) {
                // 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(r);
            }
            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, ix: u8) -> u8 {
        self.data[NEXT + (ix - 1) as usize]
    }

    fn set_next(&mut self, ix: u8, val: u8) {
        self.data[NEXT + (ix - 1) as usize] = val;
    }

    /// Get id and hash from entry array.
    fn get_ref(&self, entry: u8) -> (u64, u64) {
        let off = REFA + (entry as usize - 1) * 16;
        let loc = &self.data[off..off + 8];
        let r = u64::from_le_bytes(loc.try_into().unwrap());
        let loc = &self.data[off + 8..off + 16];
        let h = u64::from_le_bytes(loc.try_into().unwrap());
        (r, h)
    }

    fn set_ref(&mut self, entry: u8, id: u64, hash: u64) {
        let off = REFA + (entry as usize - 1) * 16;
        let loc = &mut self.data[off..off + 8];
        loc.copy_from_slice(&id.to_le_bytes());
        let loc = &mut self.data[off + 8..off + 16];
        loc.copy_from_slice(&hash.to_le_bytes());
    }
}

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

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

#[test]
fn test_hmp() {
    let mut data = vec![0; SIZE];

    let lim = ENTS as u64;

    for tv in 1..lim {
        let mut p = Writer { data: &mut data };
        let key = TestKey { value: tv };
        p.insert(key.value, key.hash());
    }

    for tv in 1..lim {
        let p = Reader { data: &data };
        let key = TestKey { value: tv };
        let x = p.get(&key, key.hash());

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

    {
        let p = Reader { data: &data };
        for _e in p.iter() {
            // println!("e={:?}", e);
        }
    }

    for tv in 1..lim {
        let mut p = Writer { data: &mut data };
        let key = TestKey { value: tv };
        let x = p.remove(&key, key.hash());

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