hashmap.wil

/*
    Here is a simple hash table implementation.
    It uses the Fowler-Noll-Vo hash function and 
    stores 64-bit values. Hash collision is resolved 
    by open addressing.
*/

fn main()
{
    let map : hashmap = { }
        
    for (let i := 1, i <= 50, i++)
    {
        let key : void^ = i as void^
        let value = (i + 10) as void^
        map_put(@map, key, value)
    }

    printf("Value for the key %llu is %llu\\n", 
        10 as ulong, map_get(@map, 10 as void^) as ulong)

    printf("Value for the key %llu is %llu\\n", 
        20 as ulong, map_get(@map, 20 as void^) as ulong)

    printf("Value for the key %llu is %llu\\n", 
        100 as ulong, map_get(@map, 100 as void^) as ulong)
}

struct hashmap
{
    keys: void^^
    values: void^^
    count: ulong
    capacity: ulong
}

fn map_get(map: hashmap^, key: void^): void^
{
    if (map.count == 0)
    {
        return null
    }

    let index := hash_ptr(key) as ulong
    while (true)
    {
        index &= map.capacity - 1
        if (map.keys[index] == key)
        {
            return map.values[index]
        }
        else if (map.keys[index] == null)
        {
            return null
        }
        index++
    }
    return null
}

fn map_grow(map: hashmap^, new_capacity: ulong)
{
    new_capacity = max(16 as ulong, new_capacity)

    printf("Map grown from %llu to %llu\\n", map.capacity, new_capacity as ulong)

    let new_map : hashmap = 
    {
        keys = allocate(new_capacity * size_of_type(void^)) as void^^,
        values = allocate(new_capacity * size_of_type(void^)) as void^^,
        capacity = new_capacity,
    }

    print_stores = false
    for (let i : ulong = 0, i < map.capacity,  i++)
    {        
        if (map.keys[i])
        {
            map_put(@new_map, map.keys[i], map.values[i])
        }
    }
    print_stores = true

    delete map.keys
    delete map.values
    #map = new_map
}

let print_stores := true

fn map_put(map: hashmap^, key: void^, val: void^)
{
    if (key == null || val == null)
    {
        return
    }
    
    if (2 * map.count >= map.capacity)
    {
        map_grow(map, 2 * map.capacity)
    }
        
    let index := hash_ptr(key)
    while (true)
    {
        index &= map.capacity - 1
        if (map.keys[index] == null)
        {
            map.count++
            map.keys[index] = key
            map.values[index] = val            
            break
        }
        else if (map.keys[index] == key)
        {
            map.values[index] = val
            break
        }
        index++
    }

    if (print_stores)
    {
        printf("Value %llu for key %llu stored, total keys: %llu\\n", 
            val as ulong, key as ulong, map.count)           
    }
}

fn hash_ulong(x: ulong) : ulong
{    
    x *= 0xff51afd7ed558ccd as ulong
    x ^= x >> 32
    return x
}

fn hash_ptr(ptr: void^) : ulong
{
    return hash_ulong(ptr as ulong)
}

fn hash_bytes(buf: char^, len: ulong) : ulong
{
    // Fowler-Noll-Vo hash
    let x : ulong = 0xcbf29ce484222325
    for (let i : ulong = 0, i < len, i++)
    {
        x ^= buf[i] as ulong
        x *= 0x01000193
        x ^= x >> 32
    }
    return x
}