Arenas & links

Many small linked items in one block.

On this page

An Arena[T] keeps many items of one type in a single block, and a Link[T] points at one of them. Use it for trees, graphs and grids with many small nodes: it is faster and smaller than separate objects.

Add and read items#

add stores an item and returns its link. arena[link] reads a copy of the item:

Valk

struct Node {
    value: int
    left: ?Link[Node] (null)
    right: ?Link[Node] (null)
}

fn sum(nodes: Arena[Node], link: ?Link[Node]) int {
    if !isset(link) : return 0
    let node = nodes[link]
    return node.value + sum(nodes, node.left) + sum(nodes, node.right)
}

fn main() {
    let nodes = Arena[Node]{}
    let leaf = nodes.add(Node { value: 2 })
    let root = nodes.add(Node { value: 1, left: leaf })

    println(nodes[root].value) // 1
    println(sum(nodes, root))  // 3
}

Change items#

ref gives a writable borrow to change fields in place; assigning to arena[link] replaces the whole item:

Valk

struct Node {
    value: int
}

fn main() {
    let nodes = Arena[Node]{}
    let a = nodes.add(Node { value: 1 })
    nodes.ref(a).value = 5
    println(nodes[a].value) // 5
    nodes[a] = Node { value: 9 }
    println(nodes[a].value) // 9
}

Links and positions#

Items are numbered in the order they were added. link(index) turns a position into a link, as in a grid, and link.index gives it back:

Valk

struct Cell {
    alive: bool
}

fn main() {
    let cells = Arena[Cell].new(100) // room for 100 before it grows
    each 0 .. 100 as i : cells.add(Cell { alive: i % 3 == 0 })

    let cell = cells.link(42)
    println(cell.index)        // 42
    println(cells[cell].alive) // true
    println(cells.length)      // 100
}

Methods#

Method	Does
`add(item)`	Store an item, return its link
`arena[link]`, `get(link)`	A copy of the item
`arena[link] = item`, `set(link, item)`	Replace the item
`ref(link)`	A writable borrow of the item
`link(index)`	The link for a position
`next_link()`	The link the next `add` returns, for an item that refers to itself
`length`	Number of items
`clear()`	Drop all items, keep the memory for reuse
`view()`	A faster view for loops that add nothing
`clone()`	An independent copy; existing links work on it

Things to know#

Items cannot be removed one by one. clear drops them all; dropping the arena frees everything.
Links of different item types do not mix, and nodes[0] or an unchecked ?Link is a compile error.
Reads are bounds checked: a link from another arena, or kept past clear, can reach the wrong item or panic, but never invalid memory.
In a loop that only reads and writes, let view = nodes.view() works like the arena but is faster. Items added after it was made are not in it.
A non-nullable link skips a null check on each read, so prefer Link[T] over ?Link[T] in hot loops.

View page source ↗