Skip to content Search Apps Documentation Source Content Run Reset Eval Playground File Folder Download Copy Actions State String Boolean Number Struct Map Slice Pointer Function Closure Reference Nil Package Type Interface Unknown

/p/nt/avl/v0

Directory · 10 Files
README.md Open

v0 - Unaudited This is an initial version of this package that has not yet been formally audited. A fully audited version will be published as a subsequent release. Use in production at your own risk.

avl - Gas-efficient AVL tree

A self-balancing AVL tree for storing key-value data in Gno realms. Each node is persisted as a separate object, so operations only load O(log n) nodes from storage instead of the entire collection.

Usage

 1package myrealm
 2
 3import "gno.land/p/nt/avl/v0"
 4
 5// Persisted across transactions.
 6var tree avl.Tree
 7
 8func Set(key string, value int) {
 9    tree.Set(key, value)
10}
11
12func Get(key string) int {
13    // Get returns nil for an absent key. A stored nil value looks the same,
14    // so use Has when you must tell absent from present-but-nil.
15    raw := tree.Get(key)
16    if raw == nil {
17        panic("not found")
18    }
19    return raw.(int)
20}
21
22// Iterate a bounded key range, stopping early when possible. Iterating
23// the whole tree with ("", "") loads every node (O(n) storage reads);
24// for large or user-growable trees, paginate with the pager subpackage.
25func ListRange(start, end string) {
26    tree.Iterate(start, end, func(key string, value any) bool {
27        // return true to stop early
28        return false
29    })
30}

API

 1type Tree struct{ /* unexported */ }
 2
 3func NewTree() *Tree
 4
 5// Read
 6func (t *Tree) Size() int
 7func (t *Tree) Has(key string) bool
 8func (t *Tree) Get(key string) (value any) // nil if the key is absent
 9func (t *Tree) GetByIndex(index int) (key string, value any)
10func (t *Tree) Iterate(start, end string, cb IterCbFn) bool
11func (t *Tree) ReverseIterate(start, end string, cb IterCbFn) bool
12func (t *Tree) IterateByOffset(offset, count int, cb IterCbFn) bool
13func (t *Tree) ReverseIterateByOffset(offset, count int, cb IterCbFn) bool
14
15// Write
16func (t *Tree) Set(key string, value any) (updated bool)
17func (t *Tree) Remove(key string) (value any, removed bool)
18
19type IterCbFn func(key string, value any) bool
20
21type ITree interface { /* same shape as Tree's methods */ }

The zero value of Tree is a usable empty tree. Get returns nil for an absent key, so use Has to distinguish a stored nil value from a missing one. Iterate uses [start, end) (start inclusive, end exclusive); empty strings mean unbounded. Callbacks return true to stop early.

Notes

  • avl.Tree and bptree (gno.land/p/nt/bptree/v0) expose the same ITree interface; bptree swaps AVL balancing for a B+ layout with better cache locality. seqid (gno.land/p/nt/seqid/v0) generates ordered keys usable in either.
  • Never return the live *Tree from a realm getter: a caller can then call Set/Remove on it under your realm's authority (readonly taint does not block method dispatch). Return values, copies, or a read-only rotree view.

Subpackages

  • gno.land/p/nt/avl/pager/v0 - pagination helper for trees and lists.
  • gno.land/p/nt/avl/rotree/v0 - read-only view of a Tree.

Why AVL over Map?

In Gno, the choice between avl.Tree and map is about how data is persisted.

Maps are stored as a single monolithic object. Accessing any value loads the entire map. A map with 1,000 entries loads all 1,000 on every read.

AVL trees store each node as a separate object. Accessing a value loads only the nodes along the search path — ~log2(n). A tree with 1,000 entries loads ~10 nodes; a tree with 1,000,000 entries still loads only ~20.

Storage comparison (1,000 entries)

Map:

Object :4 = map{
  ("0" string):("123" string),
  ("1" string):("123" string),
  ...
  ("999" string):("123" string)
}
  • map["100"] loads object :4 — all 1,000 pairs.
  • Gas cost proportional to total map size.

AVL tree:

Object :6  = Node{key="4",   height=10, size=1000, left=:7,  right=...}
Object :9  = Node{key="2",   height=9,  size=334,  left=:10, right=...}
Object :11 = Node{key="14",  height=8,  size=112,  left=:12, right=...}
Object :13 = Node{key="12",  height=6,  size=46,   left=:14, right=...}
Object :15 = Node{key="11",  height=5,  size=24,   left=:16, right=...}
Object :17 = Node{key="102", height=4,  size=13,   left=:18, right=...}
Object :19 = Node{key="100", height=3,  size=5,    left=:30, right=...}
Object :31 = Node{key="101", height=1,  size=2,    left=:32, right=...}
Object :33 = Node{key="100", value="123", height=0, size=1}
  • tree.Get("100") loads ~10 objects (the search path only).
  • Gas cost proportional to log2(n).

Further reading