Landin library reference source

core/tree

Shared: available on every enabled target.

An append-only store of named leaves and branches addressed by node identifiers.

A branch names a contiguous range of previously published nodes. Leaf totals are precomputed, so queries use constant stack and time. Shared children count once for each incoming path. Names borrow their UTF-8 backing; releasing the tree frees node storage, not names.

Items

Executable example

This complete program is maintained in the repository runtime tests. View source.

import core/tree

exercise: () -> (ok: bool) ! tree.no_such_node =
    ok = false
    value := tree.new()
    return when tree.length(value) <> 0 or tree.ordinal(tree.id(usize(42))) <> 42
    _ = tree.get(value, tree.id(usize(0))) else (problem)
        ok = problem == tree.no_such_node
        return
    end
end exercise

public main: () -> (code: i32) =
    code = 1
    ok := exercise() else false
    if ok then
        code = 42
    end if
end main

node type

public node: type = node_value

core/tree/tree.ldn:42

Opaque named leaf or branch with a precomputed leaf total. The name is borrowed UTF-8.

node_id type

public node_id: type = identifier

core/tree/tree.ldn:7

Opaque target-sized ordinal identifying a node in a particular tree. It does not retain or identify the tree itself.

tree type

public tree: type = tree_value

core/tree/tree.ldn:49

Append-only store of named nodes. Branches reference contiguous ranges of already published nodes; allocation is supplied explicitly.

invalid_children atom

public invalid_children: atom

core/tree/tree.ldn:22

The requested child interval is not wholly within already published nodes.

no_such_node atom

public no_such_node: atom

core/tree/tree.ldn:20

The node identifier is outside the tree's stored node range.

too_many_leaves atom

public too_many_leaves: atom

core/tree/tree.ldn:26

The branch's leaf total cannot be represented in target usize.

too_many_nodes atom

public too_many_nodes: atom

core/tree/tree.ldn:24

Another node identifier cannot be represented in target usize.

add_branch function

public add_branch: (provider: type is mem.allocator, inout value: tree_value,
                    inout state: provider, escaping name: utf8,
                    first: node_id, count: usize)
                   -> (id: node_id)
                   ! mem.out_of_memory | too_many_nodes
                   | invalid_children | too_many_leaves

core/tree/tree.ldn:100

Append a branch over a contiguous interval of existing nodes. Retains the name, validates children and leaf totals before publication, and permits an empty interval.

Edges name only previously published nodes. Their leaf totals are fixed, so their cumulative totals give bounded-stack queries at any depth. Shared children count once for each incoming path, as recursive counting would. An empty child interval has total zero.

add_leaf function

public add_leaf: (provider: type is mem.allocator, inout value: tree_value,
                  inout state: provider, escaping name: utf8)
                 -> (id: node_id) ! mem.out_of_memory | too_many_nodes

core/tree/tree.ldn:69

Append a named leaf and return its identifier. Retains the name's backing; allocation or identifier exhaustion leaves existing nodes unchanged.

count_leaves function

public count_leaves: (value: tree_value, id: node_id)
                     -> (count: usize) ! no_such_node

core/tree/tree.ldn:170

Return the node's precomputed leaf total in constant time. Shared children count once per incoming path; an empty branch counts zero.

get function

public get: (value: tree_value, id: node_id)
            -> (result: node_value from value) ! no_such_node

core/tree/tree.ldn:155

Copy the node selected by an identifier. Reports no_such_node if absent; the name remains borrowed from its original backing.

id function

public id: (ordinal: usize) -> (value: identifier)

core/tree/tree.ldn:11

Wrap an ordinal as a node identifier without validating membership in a tree.

length function

public length: (value: tree_value) -> (count: usize)

core/tree/tree.ldn:57

Return the number of published nodes.

name function

public name: (value: node_value) -> (text: utf8 from value)

core/tree/tree.ldn:164

Lend the UTF-8 name retained in a node.

new function

public new: () -> (result: tree_value)

core/tree/tree.ldn:52

Create an empty tree without allocating.

ordinal function

public ordinal: (value: identifier) -> (number: usize)

core/tree/tree.ldn:16

Return the ordinal carried by a node identifier.

release function

public release: (provider: type is mem.allocator, inout value: tree_value,
                 inout state: provider) -> none

core/tree/tree.ldn:181

Release node storage through the original allocator and reset the tree. Name backing remains owned by its caller.