func NewNode
NewNode creates a new node with the given key and value.
v0 source pure
v0 - Unaudited: This is an initial version that has not yet been formally audited. A fully audited version will be pu...
View source
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.Treeandbptree(gno.land/p/nt/bptree/v0) expose the sameITreeinterface; 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
*Treefrom a realm getter: a caller can then callSet/Removeon it under your realm's authority (readonly taint does not block method dispatch). Return values, copies, or a read-onlyrotreeview.
Subpackages
gno.land/p/nt/avl/v0/pager- pagination helper for trees and lists.gno.land/p/nt/avl/v0/rotree- read-only view of aTree.
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
v0 - Unaudited: This is an initial version 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.
Package avl provides a gas-efficient AVL tree implementation for storing key-value data in Gno realms.
2
4
type ITree
interface 1type ITree interface {
2 Size() int
3 Has(key string) bool
4 Get(key string) any
5 GetByIndex(index int) (key string, value any)
6 Iterate(start, end string, cb IterCbFn) bool
7 ReverseIterate(start, end string, cb IterCbFn) bool
8 IterateByOffset(offset int, count int, cb IterCbFn) bool
9 ReverseIterateByOffset(offset int, count int, cb IterCbFn) bool
10
11 Set(key string, value any) (updated bool)
12 Remove(key string) (value any, removed bool)
13}type IterCbFn
functype Node
struct1type Node struct {
2 key string // key is the unique identifier for the node.
3 value any // value is the data stored in the node.
4 height int8 // height is the height of the node in the tree.
5 size int // size is the number of leaf nodes (key-value pairs) in the subtree rooted at this node.
6 leftNode *Node // leftNode is the left child of the node.
7 rightNode *Node // rightNode is the right child of the node.
8}Node represents a node in an AVL tree.
Methods on Node
func Get
method on NodeGet searches for a node with the given key in the subtree rooted at the node and returns its index, value, and whether it exists.
func GetByIndex
method on NodeGetByIndex retrieves the key-value pair of the node at the given index in the subtree rooted at the node.
func Has
method on NodeHas checks if a node with the given key exists in the subtree rooted at the node.
func IsLeaf
method on NodeIsLeaf checks if the node is a leaf node (has no children).
func Iterate
method on NodeShortcut for TraverseInRange.
func Key
method on NodeKey returns the key of the node.
func Remove
method on NodeRemove deletes the node with the given key from the subtree rooted at the node. returns the new root of the subtree, the new leftmost leaf key (if changed), the removed value and the removal was successful.
func ReverseIterate
method on NodeShortcut for TraverseInRange.
func Set
method on NodeSet inserts a new node with the given key-value pair into the subtree rooted at the node, and returns the new root of the subtree and whether an existing node was updated.
XXX consider a better way to do this... perhaps split Node from Node.
func Size
method on NodeSize returns the size of the subtree rooted at the node.
func TraverseByOffset
method on Node1func (node *Node) TraverseByOffset(offset, limit int, ascending bool, leavesOnly bool, cb func(*Node) bool) boolTraverseByOffset traverses all nodes, including inner nodes. A limit of math.MaxInt means no limit.
func TraverseInRange
method on Node1func (node *Node) TraverseInRange(start, end string, ascending bool, leavesOnly bool, cb func(*Node) bool) boolTraverseInRange traverses all nodes, including inner nodes. Start is inclusive and end is exclusive when ascending, Start and end are inclusive when descending. Empty start and empty end denote no start and no end. If leavesOnly is true, only visit leaf nodes. NOTE: To simulate an exclusive reverse traversal, just append 0x00 to start.
func Value
method on NodeValue returns the value of the node.
type Tree
structThe zero struct can be used as an empty tree.
Methods on Tree
func Get
method on TreeGet retrieves the value associated with the given key. It returns the value if the key exists, or nil if it doesn't. Note that a key stored with a nil value is indistinguishable from an absent key; use Has to check for existence. This allows for a simpler usage pattern with type assertions:
func GetByIndex
method on TreeGetByIndex retrieves the key-value pair at the specified index in the tree. It returns the key and value at the given index.
func Has
method on TreeHas checks whether a key exists in the tree. It returns true if the key exists, otherwise false.
func Iterate
method on TreeIterate performs an in-order traversal of the tree within the specified key range. It calls the provided callback function for each key-value pair encountered. If the callback returns true, the iteration is stopped.
func IterateByOffset
method on TreeIterateByOffset performs an in-order traversal of the tree starting from the specified offset. It calls the provided callback function for each key-value pair encountered, up to the specified count. If the callback returns true, the iteration is stopped.
func Remove
method on TreeRemove removes a key-value pair from the tree. It returns the removed value and a boolean indicating whether the key was found and removed.
func ReverseIterate
method on TreeReverseIterate performs a reverse in-order traversal of the tree within the specified key range. It calls the provided callback function for each key-value pair encountered. If the callback returns true, the iteration is stopped.
func ReverseIterateByOffset
method on TreeReverseIterateByOffset performs a reverse in-order traversal of the tree starting from the specified offset. It calls the provided callback function for each key-value pair encountered, up to the specified count. If the callback returns true, the iteration is stopped.
func Set
method on TreeSet inserts a key-value pair into the tree. If the key already exists, the value will be updated. It returns a boolean indicating whether the key was newly inserted or updated.
func Size
method on TreeSize returns the number of key-value pair in the tree.