dymokomi/luce-base
Source of release 0.41.0
0.41.0 / src / bind / table.lucb
#==============================================================================================
#
# table - A names-to-values hash table for the binder
#
# DESCRIPTION:
# For the binder's typedefs, tags and constants. Storage comes from the allocator
# current at creation and is never given back: the binder runs in one arena.
#
#==============================================================================================
import memory
## An open-addressing table from `str` names to `T` values.
pub struct Table[T]:
var keys: str[]
var values: T[]
var count: usize
## An empty table sized for `capacity` entries.
pub static func create(capacity: usize) -> Table[T]!:
var room: usize = 16
while room < capacity * 2:
room *= 2
var t = Table[T](keys = try new str[room] ---, values = try new T[room] ---, count = 0)
for i in 0..<room:
t.keys[i] = ""
return t
## The value stored under `name`, or `none`.
pub func get(name: str) -> T?:
let mask = self.keys.length - 1
var i = (usize)fnv(name) & mask
while true:
if self.keys[i].length == 0:
return none
if self.keys[i] == name:
return self.values[i]
i = (i + 1) & mask
## Whether `name` has a value.
pub func has(name: str) -> bool:
return self.get(name) != none
## Store `value` under `name`, replacing any earlier value and growing when full.
pub func put(name: str, value: T) -> !:
if (self.count + 1) * 2 > self.keys.length:
try self.grow()
let mask = self.keys.length - 1
var i = (usize)fnv(name) & mask
while true:
if self.keys[i] == name:
self.values[i] = value
return
if self.keys[i].length == 0:
self.keys[i] = name
self.values[i] = value
self.count += 1
return
i = (i + 1) & mask
func grow() -> !:
let old_keys = self.keys
let old_values = self.values
self.keys = try new str[old_keys.length * 2] ---
self.values = try new T[old_keys.length * 2] ---
for i in 0..<self.keys.length:
self.keys[i] = ""
self.count = 0
for i in 0..<old_keys.length:
if old_keys[i].length > 0:
try self.put(old_keys[i], old_values[i])
func fnv(text: str) -> u64:
var h: u64 = 14695981039346656037
for b in text.bytes:
h = (h ^ (u64)b) *% 1099511628211
return h
test "a table keeps what it is given and grows":
var backing: u8[65536]
var arena = memory.FixedBuffer.over(backing)
with arena:
var t = try Table[i64].create(2)
var i: i64 = 0
let names: str[5] = ["a", "b", "c", "d", "e"]
for name in names:
try t.put(name, i)
i += 1
assert(t.get("c") == 2)
assert(t.get("z") == none)
try t.put("c", 30)
assert(t.get("c") == 30)
assert(t.count == 5)