Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-usd

Source of release 0.9.3

0.9.3 / src / sdf / tokens.lucb

## Interned strings, after OpenUSD's TfToken (pxr/base/tf/token.cpp): every
## distinct string gets a small integer id, so names, keys and string values
## compare, hash and store as one u32. Id 0 is the empty string.
##
## One table is shared by every layer of a load (see `Names`), so ids compare
## across layers. The bytes live in fixed chunks that never move, so a view
## `text(id)` returns stays valid for the table's lifetime, across later
## interning. A table is not thread-safe: one thread interns at a time.
import memory
import errors
from luce_geocore.core.growing import Growing

## Bytes per storage chunk; a longer string gets a chunk of its own.
let chunk_bytes: usize = 262144
## The most distinct strings one table holds.
pub let most_tokens: usize = 268435456

pub struct Tokens:
    ## Each token's text, viewing chunk storage.
    var texts: Growing[str]
    ## Token id + 1 per slot, 0 empty; capacity a power of two.
    var slots: Growing[u32]
    ## Every chunk, for release, and the free tail of the newest.
    var chunks: Growing[u8[]]
    var tail: u8[]

    pub func init() -> !:
        var texts = Growing[str]()
        try texts.push("")
        self.texts = texts
        self.slots = Growing[u32]()
        self.chunks = Growing[u8[]]()
        var empty: u8[]
        self.tail = empty

    ## Distinct strings, the empty one included.
    pub func count() -> usize:
        return self.texts.count

    ## The text of `token`; valid while the table is.
    pub func text(token: u32) -> str:
        return self.texts.items[(usize)token]

    ## The id of `text`, added when new.
    pub func intern(text: str) -> u32!:
        if text.length == 0: return 0
        if self.slots.count == 0 or self.texts.count * 2 >= self.slots.count:
            try self.rehash(1024 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 id = self.slots.items[slot] - 1
            if self.texts.items[(usize)id] == text: return id
            slot = (slot + 1) & mask
        if self.texts.count >= most_tokens:
            error(errors.limit, "a token table holds at most 256M strings")
        let stored = try self.store(text)
        let id = (u32)self.texts.count
        try self.texts.push(stored)
        self.slots.items[slot] = id + 1
        return id

    ## The id of `text` when it is interned already.
    pub func find(text: str) -> u32?:
        if text.length == 0: return 0
        if self.slots.count == 0: return none
        let mask = self.slots.count - 1
        var slot = (usize)text.hash() & mask
        while self.slots.items[slot] != 0:
            let id = self.slots.items[slot] - 1
            if self.texts.items[(usize)id] == text: return id
            slot = (slot + 1) & mask
        return none

    ## A copy of `text` in chunk storage.
    func store(text: str) -> str!:
        if text.length > self.tail.length:
            let size = text.length if text.length > chunk_bytes // 4 else chunk_bytes
            let chunk = try new u8[size] --- in memory.heap
            errdefer free(chunk) in memory.heap
            try self.chunks.push(chunk)
            if size == chunk_bytes: self.tail = chunk
            else:
                memory.copy(chunk, text.bytes, text.length)
                return (str)chunk[..<text.length]
        memory.copy(self.tail, text.bytes, text.length)
        let stored = (str)self.tail[..<text.length]
        self.tail = self.tail[text.length..]
        return stored

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

    pub func close():
        for chunk in self.chunks.view(): free(chunk) in memory.heap
        self.chunks.close()
        self.texts.close()
        self.slots.close()