gno.land/p/moul/cow

A copy-on-write AVL tree: a fork of p/nt/avl with the same API, plus O(1) cloning.

1t := cow.NewTree()
2t.Set("a", 1)
3
4snapshot := t.Clone()   // O(1): shares every node with t
5t.Set("b", 2)           // only the root-to-"b" path is copied

Clone copies a pointer. Both trees then present as full independent copies, but they share structure until one of them is written to, and a write only copies the nodes along the path from the root to the modified node: O(log n) new nodes, not O(n).

What it is for

On chain, the storage bill follows what changed. A snapshot taken by copying an avl tree writes the whole tree; a snapshot taken by Clone writes nothing. That makes cheap versioning practical: a proposal that must be evaluated against the state at submission time, an undo point before a batch, a before/after diff, a speculative apply you might throw away.

The one thing to get right

Structural sharing is automatic. Value copying is not.

• Simple values (int, string, ...) are copied by value. Nothing to do.
• Structs and pointers are copied by reference. Mutating the pointed-to value through one tree mutates what the other tree sees, which is exactly the bug copy-on-write was supposed to prevent.

If your values are mutable, store an immutable representation or deep-copy on write yourself. The tree cannot do it for you.

API

Same as p/nt/avl. On Tree: Set, Get, Has, Remove, Size, GetByIndex, Iterate, ReverseIterate, IterateByOffset, ReverseIterateByOffset, plus Clone. Node additionally exposes TraverseInRange and TraverseByOffset for walking inner nodes.

Equal (on either type) is a full recursive structural comparison. It is there for tests: do not call it from realm code.

Part of moul/gno-contracts — moul's versioned gno.land contracts. See the repository for the full catalog, build/test tooling, and usage.

⚠️ Disclaimer: provided as-is, without warranty; not security-audited. Full disclaimer: DISCLAIMER.