Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-geocore

Source of release 0.7.9

0.7.9 / src / core / strings.lucb

## String tables for text attributes, after Houdini's string attributes: each
## element stores an i32 index into a table of distinct strings, so a million
## faces named by a few hundred paths cost 4 bytes each. A table is one shared
## column: the string count (u32), each string's end offset (u32), then the
## bytes. `TableBuilder` interns strings once each, in first-seen order.
import memory
import errors
from core.shared import Column
from core.growing import Growing

## The strings in `table` (an empty column holds none).
pub func table_count(table: const u8[]) -> usize:
    if table.length < 4: return 0
    return (usize)memory.read[u32]((void*)&table[0])

## String `index` of `table`, a view valid while the column is.
pub func table_text(table: const u8[], index: usize) -> str:
    let count = table_count(table)
    if index >= count: return ""
    let bytes = 4 + count * 4
    let start = 0 if index == 0 else (usize)memory.read[u32]((void*)&table[4 + (index - 1) * 4])
    let end = (usize)memory.read[u32]((void*)&table[4 + index * 4])
    return (str)table[bytes + start..<bytes + end]

## Interns strings and publishes their table. Lookups hash into an open
## addressing index over the interned strings.
pub struct TableBuilder:
    var bytes: Growing[u8]
    var ends: Growing[u32]
    ## Interned index + 1 per slot; 0 is empty. Capacity is a power of two.
    var slots: Growing[u32]

    pub func init():
        self.bytes = Growing[u8]()
        self.ends = Growing[u32]()
        self.slots = Growing[u32]()

    pub func count() -> usize:
        return self.ends.count

    pub func text(index: usize) -> str:
        let start = 0 if index == 0 else (usize)self.ends.items[index - 1]
        return (str)self.bytes.items[start..<(usize)self.ends.items[index]]

    ## Whether `text` is interned already.
    pub func holds(text: str) -> bool:
        if self.slots.count == 0: return false
        let mask = self.slots.count - 1
        var slot = (usize)text.hash() & mask
        while self.slots.items[slot] != 0:
            if self.text((usize)self.slots.items[slot] - 1) == text: return true
            slot = (slot + 1) & mask
        return false

    ## The index of `text`, added when new.
    pub func intern(text: str) -> i32!:
        if self.slots.count == 0 or (self.ends.count + 1) * 2 > self.slots.count:
            try self.rehash(64 if self.slots.count == 0 else self.slots.count * 2)
        let mask = self.slots.count - 1
        var slot = (usize)text.hash() & mask
        while self.slots.items[slot] != 0:
            let index = (usize)self.slots.items[slot] - 1
            if self.text(index) == text: return (i32)index
            slot = (slot + 1) & mask
        if self.bytes.count + text.length > 2147483647 or self.ends.count >= 16777216:
            error(errors.limit, "a string table holds at most 16M strings and 2 GiB")
        try self.bytes.reserve(self.bytes.count + text.length)
        if text.length > 0: memory.copy(self.bytes.items[self.bytes.count..], text.bytes, text.length)
        self.bytes.count += text.length
        try self.ends.push((u32)self.bytes.count)
        self.slots.items[slot] = (u32)self.ends.count
        return (i32)(self.ends.count - 1)

    func rehash(capacity: usize) -> !:
        try self.slots.fill(capacity, 0)
        let mask = capacity - 1
        for index in 0..<self.ends.count:
            var slot = (usize)self.text(index).hash() & mask
            while self.slots.items[slot] != 0: slot = (slot + 1) & mask
            self.slots.items[slot] = (u32)(index + 1)

    ## The table as one column.
    pub func finish() -> Column[u8]!:
        let count = self.ends.count
        var column = try Column[u8].allocate(4 + count * 4 + self.bytes.count)
        let out = column.span()
        memory.write[u32]((void*)&out[0], (u32)count)
        for index in 0..<count: memory.write[u32]((void*)&out[4 + index * 4], self.ends.items[index])
        if self.bytes.count > 0: memory.copy(out[4 + count * 4..], self.bytes.view(), self.bytes.count)
        return column

    pub func close():
        self.bytes.close()
        self.ends.close()
        self.slots.close()