dymokomi/luce-geocore
Source of release 0.7.4
0.7.4 / 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]]
## 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()