Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-base

Source of release 0.44.0

0.44.0 / src / bind / table.lucb

#==============================================================================================
#
#   table - A names-to-values hash table for the binder
#
#   DESCRIPTION:
#       For the binder's typedefs, tags and constants. Storage comes from the allocator
#       current at creation and is never given back: the binder runs in one arena.
#
#==============================================================================================

import memory

## An open-addressing table from `str` names to `T` values.
pub struct Table[T]:
    var keys: str[]
    var values: T[]
    var count: usize

    ## An empty table sized for `capacity` entries.
    pub static func create(capacity: usize) -> Table[T]!:
        var room: usize = 16
        while room < capacity * 2:
            room *= 2
        var t = Table[T](keys = try new str[room] ---, values = try new T[room] ---, count = 0)
        for i in 0..<room:
            t.keys[i] = ""
        return t

    ## The value stored under `name`, or `none`.
    pub func get(name: str) -> T?:
        let mask = self.keys.length - 1
        var i = (usize)fnv(name) & mask
        while true:
            if self.keys[i].length == 0:
                return none
            if self.keys[i] == name:
                return self.values[i]
            i = (i + 1) & mask

    ## Whether `name` has a value.
    pub func has(name: str) -> bool:
        return self.get(name) != none

    ## Store `value` under `name`, replacing any earlier value and growing when full.
    pub func put(name: str, value: T) -> !:
        if (self.count + 1) * 2 > self.keys.length:
            try self.grow()
        let mask = self.keys.length - 1
        var i = (usize)fnv(name) & mask
        while true:
            if self.keys[i] == name:
                self.values[i] = value
                return
            if self.keys[i].length == 0:
                self.keys[i] = name
                self.values[i] = value
                self.count += 1
                return
            i = (i + 1) & mask

    func grow() -> !:
        let old_keys = self.keys
        let old_values = self.values
        self.keys = try new str[old_keys.length * 2] ---
        self.values = try new T[old_keys.length * 2] ---
        for i in 0..<self.keys.length:
            self.keys[i] = ""
        self.count = 0
        for i in 0..<old_keys.length:
            if old_keys[i].length > 0:
                try self.put(old_keys[i], old_values[i])

func fnv(text: str) -> u64:
    var h: u64 = 14695981039346656037
    for b in text.bytes:
        h = (h ^ (u64)b) *% 1099511628211
    return h

test "a table keeps what it is given and grows":
    var backing: u8[65536]
    var arena = memory.FixedBuffer.over(backing)
    with arena:
        var t = try Table[i64].create(2)
        var i: i64 = 0
        let names: str[5] = ["a", "b", "c", "d", "e"]
        for name in names:
            try t.put(name, i)
            i += 1
        assert(t.get("c") == 2)
        assert(t.get("z") == none)
        try t.put("c", 30)
        assert(t.get("c") == 30)
        assert(t.count == 5)