vivecoded swisstable

gistfile1.txt

use ingot::evm
use ingot::codec::{ Cursor, Encode, Decode }
use ingot::evm::{ MemBuffer }
use ingot::mydefault::{ MyDefault }
use ingot::option::{ Option }

// Constants for the hash table
const TABLE_SIZE: usize = 32  // Fixed size table
const EMPTY: u256 = 0
const DELETED: u256 = 1
const OCCUPIED: u256 = 2

pub struct SwissTable<V> {
    keys: [u256; 32],
    values: [V; 32],
    states: [u256; 32],  // 0 = empty, 1 = deleted, 2 = occupied
    size: usize
}

impl<V> SwissTable<V> 
where 
    V: Encode + Decode + MyDefault
{
    pub fn new() -> Self {
        SwissTable {
            keys: [0; 32],
            values: [V::default(); 32],
            states: [EMPTY; 32],
            size: 0
        }
    }

    fn hash(key: u256) -> usize {
        // Simple hash function using keccak256
        let buf = evm::malloc(len: 32)  // u256 is always 32 bytes
        let mut cursor = Cursor {
            inner: MemBuffer {
                ptr: buf.offset,
                len: buf.len.upcast()
            },
            pos: 0
        }
        key.encode(cursor)
        let hash = evm::__keccak256(args: buf)
        (hash % TABLE_SIZE.upcast()).downcast_truncate()
    }

    pub fn insert(mut self, mut key: u256, mut value: V) -> bool {
        if self.size >= TABLE_SIZE {
            return false  // Table is full
        }

        let mut index = Self::hash(key)
        let mut distance = 0

        while true {
            if self.states[index.upcast()] == EMPTY || self.states[index.upcast()] == DELETED {
                // Found a spot to insert
                self.keys[index.upcast()] = key
                self.values[index.upcast()] = value
                self.states[index.upcast()] = OCCUPIED
                self.size += 1
                return true
            }

            // Robin Hood hashing: if current element has traveled less than us,
            // swap and continue searching
            if self.states[index.upcast()] == OCCUPIED {
                let current_key = self.keys[index.upcast()]
                let current_hash = Self::hash(key: current_key)
                let current_distance = (index - current_hash) % TABLE_SIZE

                if current_distance < distance {
                    // Swap
                    let temp_key = self.keys[index.upcast()]
                    let temp_value = self.values[index.upcast()]
                    self.keys[index.upcast()] = key
                    self.values[index.upcast()] = value
                    key = temp_key
                    value = temp_value
                    distance = current_distance
                }
            }

            index = (index + 1) % TABLE_SIZE
            distance += 1
        }
        true
    }

    pub fn get(self, key: u256) -> Option<V> {
        let mut index = Self::hash(key)
        let mut distance = 0

        while self.states[index.upcast()] != EMPTY {
            if ((self.states[index.upcast()] == OCCUPIED) && (self.keys[index.upcast()] == key)) {
                return Option::Some(self.values[index.upcast()])
            }

            // If we find a deleted slot or a slot with higher distance,
            // the key doesn't exist
            if self.states[index.upcast()] == DELETED || (self.states[index.upcast()] == OCCUPIED &&  (index - Self::hash(key: self.keys[index.upcast()])) % TABLE_SIZE < distance) {
                return Option::None
            }

            index = (index + 1) % TABLE_SIZE
            distance += 1
        }

        Option::None
    }

    pub fn remove(mut self, key: u256) -> bool {
        let mut index = Self::hash(key)
        let mut distance = 0

        while self.states[index.upcast()] != EMPTY {
            if self.states[index.upcast()] == OCCUPIED && self.keys[index.upcast()] == key {
                self.states[index.upcast()] = DELETED
                self.size -= 1
                return true
            }

            if self.states[index.upcast()] == DELETED || (self.states[index.upcast()] == OCCUPIED && (index - Self::hash(key: self.keys[index.upcast()])) % TABLE_SIZE < distance) {
                return false
            }

            index = (index + 1) % TABLE_SIZE
            distance += 1
        }

        false
    }
}