Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-prism

Source of release 0.6.0

0.6.0 / src / wal / tree.lucb

## 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)