Search Apps Documentation Source Content File Folder Download Copy Actions Download State String Boolean Number Struct Map Slice Pointer Function Closure Reference Nil Package Type Interface Unknown

v2 source pure

Package cow provides a Copy-on-Write (CoW) AVL tree implementation. This is a fork of gno.land/p/nt/avl that adds CoW...

Readme View source

gno.land/p/moul/cow/v1

TODO: describe this package.

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.

Overview

Package cow provides a Copy-on-Write (CoW) AVL tree implementation. This is a fork of gno.land/p/nt/avl that adds CoW functionality while maintaining the original AVL tree interface and properties.

Copy-on-Write creates a copy of a data structure only when it is modified, while still presenting the appearance of a full copy. When a tree is cloned, it initially shares all its nodes with the original tree. Only when a modification is made to either the original or the clone are new nodes created, and only along the path from the root to the modified node.

Key features:

  • O(1) cloning operation
  • Minimal memory usage through structural sharing
  • Full AVL tree functionality (self-balancing, ordered operations)
  • Thread-safe for concurrent reads of shared structures

While the CoW mechanism handles structural copying automatically, users need to consider how to handle the values stored in the tree:

  1. Simple Values (int, string, etc.): - These are copied by value automatically - No additional handling needed

  2. Complex Values (structs, pointers): - Only the reference is copied by default - Users must implement their own deep copy mechanism if needed

Example:

Example
 1// Create original tree
 2original := cow.NewTree()
 3original.Set("key1", "value1")
 4
 5// Create a clone - O(1) operation
 6clone := original.Clone()
 7
 8// Modify clone - only affected nodes are copied
 9clone.Set("key1", "modified")
10
11// Original remains unchanged
12val, _ := original.Get("key1") // Returns "value1"

Functions 2

func NewNode 

1func NewNode(key string, value any) *Node
source

NewNode creates a new node with the given key and value.

func NewTree 

1func NewTree() *Tree
source

NewTree creates a new empty AVL tree.

Types 3

type IterCbFn

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

type Node

struct 
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 nodes 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.

Methods on Node

func Equal

method on Node 
1func (node *Node) Equal(other *Node) bool
source

Equal compares two nodes for structural equality. WARNING: This is an expensive operation that recursively traverses the entire tree structure. It should only be used in tests or when absolutely necessary.

func Get

method on Node 
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.

func GetByIndex

method on Node 
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.

func Has

method on 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.

func IsLeaf

method on Node 
1func (node *Node) IsLeaf() bool
source

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

func Iterate

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

Shortcut for TraverseInRange.

func Key

method on Node 
1func (node *Node) Key() string
source

Key returns the key of the node.

func Remove

method on 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.

func ReverseIterate

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

Shortcut for TraverseInRange.

func Set

method on Node 
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.

func Size

method on Node 
1func (node *Node) Size() int
source

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

func TraverseByOffset

method on Node 
1func (node *Node) TraverseByOffset(offset, limit int, descending bool, leavesOnly bool, cb func(*Node) bool) bool
source

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

func TraverseInRange

method on Node 
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.

func Value

method on Node 
1func (node *Node) Value() any
source

Value returns the value of the node.

type Tree

struct 
1type Tree struct {
2	node *Node
3}
source

The zero struct can be used as an empty tree.

Methods on Tree

func Clone

method on Tree 
1func (tree *Tree) Clone() *Tree
source

Clone creates a shallow copy of the tree

func Equal

method on Tree 
1func (tree *Tree) Equal(other *Tree) bool
source

Equal returns true if the two trees contain the same key-value pairs. WARNING: This is an expensive operation that recursively traverses the entire tree structure. It should only be used in tests or when absolutely necessary.

func Get

method on Tree 
1func (tree *Tree) Get(key string) (value any, exists bool)
source

Get retrieves the value associated with the given key. It returns the value and a boolean indicating whether the key exists.

func GetByIndex

method on Tree 
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.

func Has

method on Tree 
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.

func Iterate

method on Tree 
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.

func IterateByOffset

method on Tree 
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.

func Remove

method on Tree 
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.

func ReverseIterate

method on Tree 
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.

func ReverseIterateByOffset

method on Tree 
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.

func Set

method on Tree 
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.

func Size

method on Tree 
1func (tree *Tree) Size() int
source

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

Source Files 4