dymokomi/luce-usd
Source of release 0.9.6
0.9.6 / 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()