dymokomi/luce-base
Source of release 0.44.0
0.44.0 / src / support / hashed.lucb
#==============================================================================================
#
# hashed - Keys to the indexes they were added with, by hash
#
# DESCRIPTION:
# The compiler keeps its things in lists (texts, functions, modules, declarations) and
# often asks where one of them is. A walk of the list per question is the square of
# its length; this open-addressed table answers in one probe or a few. It maps a
# hashable key to the index the caller gave it, and the caller's list stays the
# storage. The table borrows its keys; they must outlive it. Nothing walks the table
# in its own order, so the process-seeded hash of ยง7.4 never shows in the output.
#
#==============================================================================================
import memory
from luce import Equatable, Hashable
import strings
## Keys and the indexes they were added with.
pub struct Table[K: Hashable & Equatable]:
## Slot keys; a slot is free when its index is 0.
var keys: K[]
## Each slot's index + 1, or 0 for a free slot.
var indexes: u32[]
var used: usize
## The allocator the slots were made with, which their growth and release go on using.
var allocator: memory.Allocator
## A table with room for `expected` keys before it grows.
pub static func create(expected: usize) -> Table[K]!:
var size: usize = 16
while size < expected * 2 + 2:
size *= 2
var table = Table[K](keys = try new K[size] ---, indexes = try new u32[size] ---, used = 0, allocator = memory.allocator)
for i in 0..<size:
table.indexes[i] = 0
return table
## The index `key` was added with, or `none`; the first, when it was added twice.
pub func find(key: K) -> usize?:
let mask = self.keys.length - 1
var slot = (usize)key.hash() & mask
while self.indexes[slot] != 0:
if self.keys[slot] == key:
return (usize)self.indexes[slot] - 1
slot = (slot + 1) & mask
return none
## Whether `key` is in the table.
pub func has(key: K) -> bool:
return self.find(key) != none
## Add `key` with `index`, unless the key is there already; whether it was added.
pub func add(key: K, index: usize) -> bool!:
if self.find(key) != none:
return false
if (self.used + 1) * 2 > self.keys.length:
try self.grow()
self.place(key, u32(index + 1))
self.used += 1
return true
## How many keys the table holds.
pub func count() -> usize:
return self.used
## A copy in the current allocator, which its growth goes on using: what is added to one
## is not in the other. The keys are borrowed by both.
pub func copied() -> Table[K]!:
let keys = try new K[self.keys.length] ---
let indexes = try new u32[self.indexes.length] ---
memory.copy(keys, self.keys, keys.length)
memory.copy(indexes, self.indexes, indexes.length)
return Table[K](keys = keys, indexes = indexes, used = self.used, allocator = memory.allocator)
## Release the slots.
pub func destroy():
free(self.keys) in self.allocator
free(self.indexes) in self.allocator
func place(key: K, stored: u32):
let mask = self.keys.length - 1
var slot = (usize)key.hash() & mask
while self.indexes[slot] != 0:
slot = (slot + 1) & mask
self.keys[slot] = key
self.indexes[slot] = stored
func grow() -> !:
let old_keys = self.keys
let old_indexes = self.indexes
let size = old_keys.length * 2
self.keys = try new K[size] --- in self.allocator
self.indexes = try new u32[size] --- in self.allocator
for i in 0..<size:
self.indexes[i] = 0
for i in 0..<old_keys.length:
if old_indexes[i] != 0:
self.place(old_keys[i], old_indexes[i])
free(old_keys) in self.allocator
free(old_indexes) in self.allocator
test "names find the index they were added with, the first of two":
var table = try Table[str].create(2)
defer table.destroy()
var views: str[40] = ---
var rooms: u8[320] = ---
for i in 0..<views.length:
views[i] = try strings.format(rooms[i * 8..<i * 8 + 8], f"n{i}")
assert(try table.add(views[i], i))
assert(not try table.add(views[3], 99))
for i in 0..<views.length:
assert(table.find(views[i]) == i)
assert(table.find("absent") == none)
assert(table.count() == 40)
test "numbers and addresses are keys too":
var table = try Table[u64].create(0)
defer table.destroy()
for k in 0..<100:
_ = try table.add((u64)k *% 0x9E3779B97F4A7C15, (usize)k)
assert(table.find(5 *% 0x9E3779B97F4A7C15) == 5)
assert(not table.has(1))