Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-base

Source of release 0.46.0

0.46.0 / src / back / assemble / lookup.lucb

#==============================================================================================
#
#   lookup - Names to the numbers they were given, for the assembler's hot path
#
#   DESCRIPTION:
#       Every label, symbol reference and mnemonic of a source is looked up by name, millions
#       of times in a large program. This table hashes a name with FNV-1a, which is a few
#       instructions a byte, keeps each slot's hash beside its number so a probe compares
#       bytes only when the hashes agree, and borrows its names, which the source or the
#       assembler's arena keeps. Nothing walks it in its own order, so the output never
#       depends on the hash.
#
#==============================================================================================

import memory

## Names, by hash, to the numbers they were added with.
pub struct Lookup:
    var hashes: u64[]
    ## Each slot's number + 1; 0 for a free slot.
    var numbers: u32[]
    var names: str[]
    var used: usize

    ## A table with room for `expected` names before it grows.
    pub static func create(expected: usize) -> Lookup!:
        var size: usize = 64
        while size < expected * 2:
            size *= 2
        return Lookup(hashes = try new u64[size], numbers = try new u32[size], names = try new str[size] ---, used = 0)

    ## The number `name` was added with, or none.
    pub func find(name: str) -> u32?:
        let h = fnv(name)
        let mask = self.hashes.length - 1
        var slot = (usize)h & mask
        while self.numbers[slot] != 0:
            if self.hashes[slot] == h and self.names[slot] == name:
                return self.numbers[slot] - 1
            slot = (slot + 1) & mask
        return none

    ## Add `name` with `number`; it must not be there already.
    pub func add(name: str, number: u32) -> !:
        if (self.used + 1) * 2 > self.hashes.length:
            try self.grow()
        self.place(name, fnv(name), number + 1)
        self.used += 1

    func place(name: str, h: u64, stored: u32):
        let mask = self.hashes.length - 1
        var slot = (usize)h & mask
        while self.numbers[slot] != 0:
            slot = (slot + 1) & mask
        self.hashes[slot] = h
        self.numbers[slot] = stored
        self.names[slot] = name

    func grow() -> !:
        let hashes = self.hashes
        let numbers = self.numbers
        let names = self.names
        let size = hashes.length * 2
        self.hashes = try new u64[size]
        self.numbers = try new u32[size]
        self.names = try new str[size] ---
        for k in 0..<hashes.length:
            if numbers[k] != 0:
                self.place(names[k], hashes[k], numbers[k])
        free(hashes)
        free(numbers)
        free(names)

## FNV-1a of `name`'s bytes.
func fnv(name: str) -> u64:
    var h: u64 = 0xCBF29CE484222325
    for b in name.bytes:
        h = (h ^ (u64)b) *% 0x100000001B3
    return h

test "names find the numbers they were added with, past growth":
    var table = try Lookup.create(1)
    var names: str[300] = ---
    var rooms: u8[3000] = ---
    for i in 0..<names.length:
        let room = rooms[i * 10..<i * 10 + 10]
        var n = i
        var k: usize = 0
        while true:
            room[k] = (u8)(n % 10) + '0'
            n = n // 10
            k += 1
            if n == 0:
                break
        names[i] = (str)room[..<k]
        try table.add(names[i], u32(i))
    for i in 0..<names.length:
        assert(table.find(names[i]) == u32(i))
    assert(table.find("absent") == none)