Package Info
Namespace: nt
Path: /p/nt/avl/v0
Type: pure
Gno: 0.9
Creator: g1edq4…leuc8p
Block: 0
Code stats
Files: 10
.gno files: 8
Tests: 5
Funcs: 37 (2 exported)
Types: 4

Metadata

published
public
Documented
README
Tests

Package Index

v0 source pure

v0 - Unaudited: This is an initial version that has not yet been formally audited. A fully audited version will be pu...

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 Tree Package

The avl package provides a gas-efficient AVL tree implementation for storing key-value data in Gno realms.

Basic Usage

 1package myrealm
 2
 3import "gno.land/p/nt/avl/v0"
 4
 5// This AVL tree will be persisted after transaction calls
 6var tree *avl.Tree
 7
 8func Set(key string, value int) {
 9	// tree.Set takes in a string key, and a value that can be of any type
10	tree.Set(key, value)
11}
12
13func Get(key string) int {
14	// tree.Get returns the value at given key, or nil if the key does not exist.
15	// Use a type assertion to convert the raw value into the proper type.
16	rawValue := tree.Get(key)
17	if rawValue == nil {
18		panic("value at given key does not exist")
19	}
20
21	return rawValue.(int)
22}
23
24func Exists(key string) bool {
25	// tree.Has returns true if the key exists, without retrieving the value.
26	return tree.Has(key)
27}

Storage Architecture: AVL Tree vs Map

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

Maps are stored as a single, monolithic object. When you access any value in a map, Gno must load the entire map into memory. For a map with 1,000 entries, accessing one value means loading all 1,000 entries.

AVL trees store each node as a separate object. When you access a value, Gno only loads the nodes along the search path (typically log2(n) nodes). For a tree with 1,000 entries, accessing one value loads ~10 nodes; but a tree with 1,000,000 entries only needs to load ~20 nodes.

Storage Comparison Example

Consider a realm with 1,000 key-value pairs. Here's what happens when you access a single value:

Map storage:

Object :4 = map{
  ("0" string):("123" string),
  ("1" string):("123" string),
  ...
  ("999" string):("123" string)
}

Accessing map["100"] loads object :4 (contains all 1,000 pairs)
Gas cost is proportional to total map size (1,000 entries)
1 object fetch, but massive data load

AVL tree storage:

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}

Accessing tree.Get("100") loads ~10 objects (the search path)
Gas cost is proportional to log2(n) ≈ 10 nodes
10 object fetches, each containing only a single node

 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}

source

1type IterCbFn func(key string, value any) bool

source

1type 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}

source

Node represents a node in an AVL tree.

1func (node *Node) Get(key string) (index int, value any, exists bool)

source

Get searches for a node with the given key in the subtree rooted at the node and returns its index, value, and whether it exists.

1func (node *Node) GetByIndex(index int) (key string, value any)

source

GetByIndex retrieves the key-value pair of the node at the given index in the subtree rooted at the node.

1func (node *Node) Has(key string) (has bool)

source

Has checks if a node with the given key exists in the subtree rooted at the node.

1func (node *Node) IsLeaf() bool

source

IsLeaf checks if the node is a leaf node (has no children).

1func (node *Node) Iterate(start, end string, cb func(*Node) bool) bool

source

Shortcut for TraverseInRange.

1func (node *Node) Key() string

source

Key returns the key of the node.

1func (node *Node) Remove(key string) (
2	newNode *Node, newKey string, value any, removed bool,
3)

source

Remove 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.

1func (node *Node) ReverseIterate(start, end string, cb func(*Node) bool) bool

source

Shortcut for TraverseInRange.

1func (node *Node) Set(key string, value any) (newSelf *Node, updated bool)

source

Set 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.

1func (node *Node) Size() int

source

Size returns the size of the subtree rooted at the node.

1func (node *Node) TraverseByOffset(offset, limit int, ascending bool, leavesOnly bool, cb func(*Node) bool) bool

source

TraverseByOffset traverses all nodes, including inner nodes. A limit of math.MaxInt means no limit.

1func (node *Node) TraverseInRange(start, end string, ascending bool, leavesOnly bool, cb func(*Node) bool) bool

source

TraverseInRange 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.

1func (node *Node) Value() any

source

Value returns the value of the node.

1type Tree struct {
2	node *Node
3}

source

The zero struct can be used as an empty tree.

1func (tree *Tree) Get(key string) any

source

Get 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:

Example

1if value, ok := tree.Get("key").(MyType); ok {
2    // use value
3}

1func (tree *Tree) GetByIndex(index int) (key string, value any)

source

GetByIndex retrieves the key-value pair at the specified index in the tree. It returns the key and value at the given index.

1func (tree *Tree) Has(key string) (has bool)

source

Has checks whether a key exists in the tree. It returns true if the key exists, otherwise false.

1func (tree *Tree) Iterate(start, end string, cb IterCbFn) bool

source

Iterate 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.

1func (tree *Tree) IterateByOffset(offset int, count int, cb IterCbFn) bool

source

IterateByOffset 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.

1func (tree *Tree) Remove(key string) (value any, removed bool)

source

Remove removes a key-value pair from the tree. It returns the removed value and a boolean indicating whether the key was found and removed.

1func (tree *Tree) ReverseIterate(start, end string, cb IterCbFn) bool

source

ReverseIterate 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.

1func (tree *Tree) ReverseIterateByOffset(offset int, count int, cb IterCbFn) bool

source

ReverseIterateByOffset 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.

1func (tree *Tree) Set(key string, value any) (updated bool)

source

Set 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.

1func (tree *Tree) Size() int

source

Size returns the number of key-value pair in the tree.

pager
rotree

Readme View source

AVL Tree Package

Basic Usage

Storage Architecture: AVL Tree vs Map

Storage Comparison Example

Further Reading

Overview

Functions 2

Types 4

Methods on Node

Methods on Tree

Source Files 10

Directories 2