Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-base

Source of release 0.42.0

0.42.0 / src / support / hashed.lucb

#==============================================================================================
#
#   hashed - Keys to the indexes they were added with, by hash
#
#   DESCRIPTION:
#       The compiler keeps its things in lists (texts, functions, modules, declarations) and
#       often asks where one of them is. A walk of the list per question is the square of
#       its length; this open-addressed table answers in one probe or a few. It maps a
#       hashable key to the index the caller gave it, and the caller's list stays the
#       storage. The table borrows its keys; they must outlive it. Nothing walks the table
#       in its own order, so the process-seeded hash of ยง7.4 never shows in the output.
#
#==============================================================================================

import memory
from luce import Equatable, Hashable
import strings

## Keys and the indexes they were added with.
pub struct Table[K: Hashable & Equatable]:
    ## Slot keys; a slot is free when its index is 0.
    var keys: K[]
    ## Each slot's index + 1, or 0 for a free slot.
    var indexes: u32[]
    var used: usize
    ## The allocator the slots were made with, which their growth and release go on using.
    var allocator: memory.Allocator

    ## A table with room for `expected` keys before it grows.
    pub static func create(expected: usize) -> Table[K]!:
        var size: usize = 16
        while size < expected * 2 + 2:
            size *= 2
        var table = Table[K](keys = try new K[size] ---, indexes = try new u32[size] ---, used = 0, allocator = memory.allocator)
        for i in 0..<size:
            table.indexes[i] = 0
        return table

    ## The index `key` was added with, or `none`; the first, when it was added twice.
    pub func find(key: K) -> usize?:
        let mask = self.keys.length - 1
        var slot = (usize)key.hash() & mask
        while self.indexes[slot] != 0:
            if self.keys[slot] == key:
                return (usize)self.indexes[slot] - 1
            slot = (slot + 1) & mask
        return none

    ## Whether `key` is in the table.
    pub func has(key: K) -> bool:
        return self.find(key) != none

    ## Add `key` with `index`, unless the key is there already; whether it was added.
    pub func add(key: K, index: usize) -> bool!:
        if self.find(key) != none:
            return false
        if (self.used + 1) * 2 > self.keys.length:
            try self.grow()
        self.place(key, u32(index + 1))
        self.used += 1
        return true

    ## How many keys the table holds.
    pub func count() -> usize:
        return self.used

    ## A copy in the current allocator, which its growth goes on using: what is added to one
    ## is not in the other. The keys are borrowed by both.
    pub func copied() -> Table[K]!:
        let keys = try new K[self.keys.length] ---
        let indexes = try new u32[self.indexes.length] ---
        memory.copy(keys, self.keys, keys.length)
        memory.copy(indexes, self.indexes, indexes.length)
        return Table[K](keys = keys, indexes = indexes, used = self.used, allocator = memory.allocator)

    ## Release the slots.
    pub func destroy():
        free(self.keys) in self.allocator
        free(self.indexes) in self.allocator

    func place(key: K, stored: u32):
        let mask = self.keys.length - 1
        var slot = (usize)key.hash() & mask
        while self.indexes[slot] != 0:
            slot = (slot + 1) & mask
        self.keys[slot] = key
        self.indexes[slot] = stored

    func grow() -> !:
        let old_keys = self.keys
        let old_indexes = self.indexes
        let size = old_keys.length * 2
        self.keys = try new K[size] --- in self.allocator
        self.indexes = try new u32[size] --- in self.allocator
        for i in 0..<size:
            self.indexes[i] = 0
        for i in 0..<old_keys.length:
            if old_indexes[i] != 0:
                self.place(old_keys[i], old_indexes[i])
        free(old_keys) in self.allocator
        free(old_indexes) in self.allocator

test "names find the index they were added with, the first of two":
    var table = try Table[str].create(2)
    defer table.destroy()
    var views: str[40] = ---
    var rooms: u8[320] = ---
    for i in 0..<views.length:
        views[i] = try strings.format(rooms[i * 8..<i * 8 + 8], f"n{i}")
        assert(try table.add(views[i], i))
    assert(not try table.add(views[3], 99))
    for i in 0..<views.length:
        assert(table.find(views[i]) == i)
    assert(table.find("absent") == none)
    assert(table.count() == 40)

test "numbers and addresses are keys too":
    var table = try Table[u64].create(0)
    defer table.destroy()
    for k in 0..<100:
        _ = try table.add((u64)k *% 0x9E3779B97F4A7C15, (usize)k)
    assert(table.find(5 *% 0x9E3779B97F4A7C15) == 5)
    assert(not table.has(1))