dymokomi/luce-prism
Source of release 0.6.1
0.6.1 / src / collections / index.lucb
## Open-addressed UTF-8 key index with ordered buckets and amortized constant append.
import memory
from storage import Buffer, List, text_copy
from types import limit_exceeded
pub struct Bucket:
pub var key: Buffer
pub var rows: List[usize]
pub func close():
self.key.close()
self.rows.close()
func hash_key(key: str) -> usize:
var value: u64 = 2166136261
for byte in key.bytes:
value = ((value ^ (u64)byte) * 16777619) & 4294967295
return (usize)value
## Prepared appends let the model update several indexes without partial writes.
## At most one append may be pending on an index; commit performs no allocation.
pub struct Pending:
pub var existing: usize?
pub var row: usize
pub var bucket: Bucket
pub func close():
self.bucket.close()
pub struct Index:
pub var buckets: List[Bucket]
var slots: usize[]
pub func find(key: str) -> usize?:
if self.slots.length == 0:
return none
var position = hash_key(key) & (self.slots.length - 1)
while self.slots[position] != 0:
let index = self.slots[position] - 1
if self.buckets.items[index].key.view() == key:
return index
position = (position + 1) & (self.slots.length - 1)
return none
func capacity(count: usize) -> !:
if count <= self.slots.length // 2:
return
if count > 1048576:
error(limit_exceeded, "Prism index key limit exceeded")
let size = self.slots.length * 2 if self.slots.length > 0 else 16
let slots = try new usize[size] --- in memory.heap
for i in 0..<slots.length:
slots[i] = 0
for index in 0..<self.buckets.count:
var position = hash_key(self.buckets.items[index].key.view()) & (size - 1)
while slots[position] != 0:
position = (position + 1) & (size - 1)
slots[position] = index + 1
if self.slots.length > 0:
free(self.slots) in memory.heap
self.slots = slots
pub func add(key: str, row: usize) -> usize!:
var pending = try self.prepare(key, row)
return self.commit(&pending)
pub func prepare(key: str, row: usize) -> Pending!:
if let index = self.find(key):
try self.buckets.items[index].rows.reserve(self.buckets.items[index].rows.count + 1)
return Pending(existing = index, row = row)
try self.capacity(self.buckets.count + 1)
try self.buckets.reserve(self.buckets.count + 1)
var bucket: Bucket
errdefer bucket.close()
bucket.key = try text_copy(key)
try bucket.rows.push(row)
return Pending(row = row, bucket = bucket)
pub func commit(pending: Pending*) -> usize:
if let index = pending.existing:
let rows = &self.buckets.items[index].rows
rows.items[rows.count] = pending.row
rows.count += 1
return index
let index = self.buckets.count
self.buckets.items[index] = pending.bucket
self.buckets.count += 1
pending.bucket = Bucket()
var position = hash_key(self.buckets.items[index].key.view()) & (self.slots.length - 1)
while self.slots[position] != 0:
position = (position + 1) & (self.slots.length - 1)
self.slots[position] = index + 1
return index
pub func close():
for i in 0..<self.buckets.count:
self.buckets.items[i].close()
self.buckets.close()
if self.slots.length > 0:
free(self.slots) in memory.heap
var empty: usize[]
self.slots = empty