Links Without Pointers

Trees, graphs and linked lists are made of links between values. In C a link is a pointer, which costs eight bytes and means nothing outside the process that created it. In Rust, linked structures are hard enough that the usual advice is to put the nodes in a Vec and link them with integer indices.

Goose has a third option. A link can be stored as a relative reference: a narrow offset that the compiler turns back into an ordinary reference when you read it. This chapter shows the two kinds of relative reference and the data structures they make easy.

#Self-relative links13.1

T&<u32> is a reference to a T, stored as a 32-bit offset from the field that holds it to the thing it points at. The width can be u8, u16, u32, u64 or varint. Its optional form, T&<u32>?, uses offset 0 as null, so a link costs four bytes including the ability to be empty.

You use a relative reference exactly like any other reference. Reading the field gives you an ordinary T&, and storing a reference into the field encodes the offset. Here is a binary search tree of geese, ordered by weight, that lives entirely inside one grow-only array:

struct Node { name: u8[..8], weight: i32, left: Node&<u32>?, right: Node&<u32>? }

fn insert(tree: Node[>..]&, name: u8[:], weight: i32) {
    if tree.len == 0 { tree.push(Node { name: name, weight: weight }); return; }
    var cur .= tree[0];
    loop {
        if weight < cur.weight {
            let l = cur.left;
            if l { cur .= l; continue; }
            cur.left .= tree.push(Node { name: name, weight: weight });
            return;
        }
        let r = cur.right;
        if r { cur .= r; continue; }
        cur.right .= tree.push(Node { name: name, weight: weight });
        return;
    }
}

recursive fn in_order(n: Node&, out: u8[>..]&) {
    let l = n.left;
    if l { in_order(l, out); }
    format(out, n.name, " ");
    let r = n.right;
    if r { in_order(r, out); }
}

fn main() {
    var tree: Node[>..] = [];
    insert(tree, "Ada", 45);
    insert(tree, "Bea", 52);
    insert(tree, "Cleo", 38);
    insert(tree, "Dot", 41);
    insert(tree, "Eve", 60);
    var out: u8[>..] = [];
    in_order(tree[0], out);
    print(out, "| ", tree.len, " nodes in ", bytes_of(tree).len, " bytes");
}

Cleo Dot Ada Bea Eve | 5 nodes in 105 bytes

Look at the line that grows the tree, cur.left .= tree.push(Node { name: name, weight: weight });. push builds the new node at the end of the array and returns a reference to it, and .= stores that reference into cur.left as an offset. The push cannot invalidate cur, because a grow-only array never moves. In safe Rust this is the point where you would give up on references and switch to indices.

Each node is 21 bytes: a 9-byte name, a 4-byte weight and two 4-byte links. With pointers the links alone would be 16 bytes.

Two features from earlier chapters are doing a lot of work here. The links are optional, so they must be narrowed before use. That is why the code copies cur.left into the local l and tests it. And the walk is recursive fn, which Chapter 17 explains in full. Its growable output is passed in by reference rather than owned by the recursion.

#Same root, exactly13.1.1

A self-relative offset only makes sense if the link and its target are in the same block of memory, so the compiler checks that the reference you store comes from the same array as the field you store it in:

struct Node { v: i64, next: Node&<u32>? }

fn main() {
    var a: Node[>..] = [Node { v: 1 }];
    var b: Node[>..] = [Node { v: 2 }];
    a[0].next .= b[0];
}

error: a relative reference must point within the same root as its location (§3.9); this reference is rooted at b

The payoff is that a structure built from self-relative links means the same thing wherever it is in memory. The whole tree above is position-independent: you could write its bytes to a file and read them back at a different address, and every link would still be right. Chapter 21 does exactly that.

#Values with self-relative links are not copied13.1.2

The flip side of position independence is that a value containing a self-relative link cannot be copied anywhere else, because the copy's offsets would point at the wrong place. The compiler stops you, and suggests what to do instead:

struct Node { name: u8[..8], weight: i32, left: Node&<u32>?, right: Node&<u32>? }

fn main() {
    var tree: Node[>..] = [Node { name: "Ada", weight: 45 }];
    let root = tree[0];
}

error: copying a value of type Node, which contains self-relative references, is not supported; construct it in place, or bind a reference to it with .=: let root .= tree[0]

The same goes for copy(tree) of the whole array. In practice this is rarely a problem: you build nodes in place with push, and you refer to them with references.

#Links into a pool13.2

The second kind of relative reference is measured from the start of a named global array, the pool, rather than from the field: T&<u32 in pool>. Two things follow from that:

• Arrays other than the pool can hold links into it, which self-relative links cannot do.
• A value holding in pool links can be copied freely, because its offsets do not depend on where it is.

Here a flock records each goose's mate as a 2-byte link, and a separate index lists the geese in some other order:

struct Goose { name: u8[..8], mate: Goose&<u16 in flock>? }

var flock: Goose[>..] = [];
var by_age: (Goose&<u32 in flock>)[>..] = [];

fn main() {
    let ada .= flock.push(Goose { name: "Ada", .. });
    let bob .= flock.push(Goose { name: "Bob", .. });
    flock.push(Goose { name: "Cy", .. });
    ada.mate .= bob;
    bob.mate .= ada;
    by_age.push(flock[2]);
    by_age.push(flock[0]);
    by_age.push(flock[1]);
    for g in by_age { print(g.name); }
    let m = flock[1].mate;
    if m { print("Bob's mate is ", m.name); }
    var twin = flock[0];               // a copy: fine for in-pool links
    twin.name = "Ada II";
    print(twin.name, " ", flock[0].name);
}

Cy
Ada
Bob
Bob's mate is Ada
Ada II Ada

The array type (Goose&<u32 in flock>)[>..] needs parentheses so that the [>..] applies to the link type as a whole.

Because the pool is named in the type, it has to be a global. A local array has no name that a type could mention. For links within a local array, use self-relative links. For an index into a local array, use plain references: (Goose&)[>..] costs eight bytes per entry.

#self: links that point back13.3

A non-optional link can never be null, which raises a puzzle: how do you build the first node of a structure whose links must always point somewhere? There is nothing for them to point at yet.

The answer is self. Written as the whole initializer of a relative reference field, it means "the value this literal is building". It is how you make a ring, or the sentinel node of a circular list:

struct Ring { id: i64, next: Ring&<u32 in ring> }

var ring: Ring[>..] = [];

fn main() {
    ring.push(Ring { id: 0, next: self });       // a ring of one
    for i in 1..4 {
        let last .= ring[ring.len - 1];
        let n .= ring.push(Ring { id: i, next: ring[0] });
        last.next .= n;
    }
    var cur .= ring[0];
    var out: u8[>..] = [];
    for k in 6 { format(out, cur.id, " "); cur .= cur.next; }
    print(out);
}

0 1 2 3 0 1

Once the first node exists, every later link has a real target, so no link in the ring is ever null and walking it needs no null checks at all.

#An index for a sequential array13.4

Chapter 7 left a problem open: an array of variable-size elements is compact, but cannot be indexed. Links into a pool solve it. Keep a second array of four-byte links beside the packed one, and push a link each time you push an element:

enum Note { Text { body: u8[varint] }, Weight { kg: f32 }, Blank }

var notes: Note..[>..] = [];
var note_at: (Note..&<u32 in notes>)[>..] = [];

fn main() {
    note_at.push(notes.push(Note.Text { body: "fed at dawn" }));
    note_at.push(notes.push(Note.Weight { kg: 4.5 }));
    note_at.push(notes.push(Note.Blank));
    for i in [2, 0, 1] {
        match note_at[i] {
            Text t => print(i, ": ", t.body),
            Weight w => print(i, ": ", w.kg, " kg"),
            Blank => print(i, ": (blank)"),
        }
    }
}

2: (blank)
0: fed at dawn
1: 4.5 kg

The notes stay packed at their own sizes, and note_at[i] reaches any of them with a load and an add.

#Choosing a link13.5

The offset width is up to you. A u16 link is enough for a pool of up to 64 KB, and the compiler checks the offset whenever you store into a field that might be too narrow for the array.

#Exercises13.6

1. Add a function count_lighter(tree: Node[>..]&, w: i32) -> i64 to the tree example that counts the geese lighter than w without visiting the whole tree.

2. Build a singly linked list of the numbers 1 to 5 in a local Link[>..], using self-relative next: Link&<u32>? links, where each new number is pushed and linked from the previous one. Walk it to print the numbers.

3. In the flock example, what would go wrong if mate were a self-relative link, Goose&<u16>?, and you tried to push flock[0] into by_age? Try changing by_age to hold self-relative links and read the error.