dymokomi/luce-prism
Source of release 0.6.1
## Immutable AVL index. Snapshots share subtrees; atomic counts own their lifetime.
## This index is in memory. The on-disk authority is the transaction journal.
import memory
from wal.bytes import Buffer, copied, compare, max_records, limit
pub struct Entry:
var references: @u64
pub var key: Buffer
pub var value: Buffer
pub func entry(key: const u8[], value: const u8[]) -> Entry*!:
var k = try copied(key)
errdefer k.close()
var v = try copied(value)
errdefer v.close()
let out = try new Entry(key = k, value = v) in memory.heap
out.references.store(1, .relaxed)
return out
pub func hold_entry(item: Entry*):
_ = item.references.add(1, .relaxed)
pub func drop_entry(item: Entry*):
if item.references.sub(1, .acq_rel) == 1:
item.key.close()
item.value.close()
free(item) in memory.heap
pub struct Node:
var references: @u64
pub var item: Entry*
pub var left: Node*?
pub var right: Node*?
pub var height: i32
pub var count: usize
pub func hold(node: Node*?) -> Node*?:
if let n = node: _ = n.references.add(1, .relaxed)
return node
pub func drop(node: Node*?):
if let n = node:
if n.references.sub(1, .acq_rel) == 1:
drop(n.left)
drop(n.right)
drop_entry(n.item)
free(n) in memory.heap
func height(node: Node*?) -> i32:
let n = node else return 0
return n.height
pub func count(node: Node*?) -> usize:
let n = node else return 0
return n.count
func make(item: Entry*, left: Node*?, right: Node*?) -> Node*!:
let total = count(left) + count(right) + 1
if total > max_records: error(limit, "database record limit exceeded")
let h = height(left) if height(left) > height(right) else height(right)
let out = try new Node(item = item, left = left, right = right, height = h + 1, count = total) in memory.heap
hold_entry(item)
_ = hold(left)
_ = hold(right)
out.references.store(1, .relaxed)
return out
func balanced(item: Entry*, left: Node*?, right: Node*?) -> Node*!:
if height(left) > height(right) + 1:
let l = left else trap("AVL left invariant")
if height(l.left) >= height(l.right):
let r = try make(item, l.right, right)
defer drop(r)
return try make(l.item, l.left, r)
let middle = l.right else trap("AVL left-right invariant")
let a = try make(l.item, l.left, middle.left)
defer drop(a)
let b = try make(item, middle.right, right)
defer drop(b)
return try make(middle.item, a, b)
if height(right) > height(left) + 1:
let r = right else trap("AVL right invariant")
if height(r.right) >= height(r.left):
let l = try make(item, left, r.left)
defer drop(l)
return try make(r.item, l, r.right)
let middle = r.left else trap("AVL right-left invariant")
let a = try make(item, left, middle.left)
defer drop(a)
let b = try make(r.item, middle.right, r.right)
defer drop(b)
return try make(middle.item, a, b)
return try make(item, left, right)
pub func find(root: Node*?, key: const u8[]) -> Entry*?:
var cursor = root
while let n = cursor:
let order = compare(key, n.item.key.span())
if order == 0: return n.item
cursor = n.left if order < 0 else n.right
return none
pub func put(root: Node*?, item: Entry*) -> Node*!:
let n = root else return try make(item, none, none)
let order = compare(item.key.span(), n.item.key.span())
if order == 0: return try make(item, n.left, n.right)
if order < 0:
let left = try put(n.left, item)
defer drop(left)
return try balanced(n.item, left, n.right)
let right = try put(n.right, item)
defer drop(right)
return try balanced(n.item, n.left, right)
pub func remove(root: Node*?, key: const u8[]) -> Node*?!:
let n = root else return none
let order = compare(key, n.item.key.span())
if order < 0:
let left = try remove(n.left, key)
defer drop(left)
return try balanced(n.item, left, n.right)
if order > 0:
let right = try remove(n.right, key)
defer drop(right)
return try balanced(n.item, n.left, right)
if n.left == none: return hold(n.right)
if n.right == none: return hold(n.left)
var next = n.right else trap("AVL removal invariant")
while let l = next.left: next = l
let right = try remove(n.right, next.item.key.span())
defer drop(right)
return try balanced(next.item, n.left, right)
pub func at(root: Node*?, index: usize) -> Entry*?:
let n = root else return none
let left = count(n.left)
if index < left: return at(n.left, index)
if index == left: return n.item
return at(n.right, index - left - 1)
pub func validate(root: Node*?) -> bool:
let n = root else return true
let difference = height(n.left) - height(n.right)
let h = height(n.left) if height(n.left) > height(n.right) else height(n.right)
return difference >= -1 and difference <= 1 and n.height == h + 1 and n.count == count(n.left) + count(n.right) + 1 and validate(n.left) and validate(n.right)