//! Open-addressed hash map from string keys to `i32` values.

//!

//! Uses DJB2 hashing with linear probing. The table size must be a power

//! of two and is provided by the caller via arena-allocated storage.

use std::mem;

/// Hash map entry.

export record Entry: Copy {

    /// Key.

    key: *[u8],

    /// Associated value.

    value: i32,

}

/// Open-addressed hash map with caller-provided storage.

export record Dict {

    /// Hash table entries.

    entries: *mut [Entry],

    /// Number of occupied entries.

    count: u32,

}

/// Create a dict backed by the given entry storage.

/// The storage length must be a power of two.

export fn init(entries: *mut [Entry]) -> Dict {

    for i in 0..entries.len {

        set entries[i] = Entry { key: &[], value: 0 };

    }

    return Dict { entries, count: 0 };

}

/// Insert or update a key-value pair. Panics if the table exceeds 50% load.

export fn insert(m: &mut Dict, key: *[u8], value: i32) {

    let mask = m.entries.len - 1;

    let mut idx = hash(key) & mask;

    loop {

        let entry = m.entries[idx];

        if entry.key.len == 0 {

            assert m.count < m.entries.len / 2, "dict::insert: table full";

            set m.entries[idx] = Entry { key, value };

            set m.count += 1;

            return;

        }

        if mem::eq(entry.key, key) {

            set m.entries[idx].value = value;

            return;

        }

        set idx = (idx + 1) & mask;

    }

}

/// Look up a value by key. Returns `nil` if not found.

export fn get(m: &Dict, key: *[u8]) -> ?i32 {

    let mask = m.entries.len - 1;

    let mut idx = hash(key) & mask;

    loop {

        let entry = m.entries[idx];

        if entry.key.len == 0 {

            return nil;

        }

        if mem::eq(entry.key, key) {

            return entry.value;

        }

        set idx = (idx + 1) & mask;

    }

}

/// DJB2 hash function.

export fn hash(str: *[u8]) -> u32 {

    let mut h: u32 = 5381;

    for b in str {

        set h = ((h << 5) + h) + b as u32;

    }

    return h;

}