var ErrOutOfBounds, ErrDeleted
Error variables
v1 source pure
Package ulist provides an append-only list implementation using a binary tree structure, optimized for scenarios requ...
View source
gno.land/p/moul/ulist/v1
Append-only list backed by a binary tree, with index-preserving compaction.
An index is the element's position in the tree, so Delete is a soft delete:
it clears the data and leaves the node, because moving a live element would
silently invalidate an index another realm is holding. That leaves reclaimable
storage behind, and on gno.land storage is money: every byte of realm state
locks GNOT, refunded to whoever signs the transaction that frees it.
v1 adds the pair that turns those dead nodes back into a refund:
Compactable() int |
how many nodes a compaction would free, right now, for free. Reads nothing, mutates nothing, so a caller can poll it before paying gas |
Compact() int |
frees every node whose subtree holds no live element, and returns how many. Nothing live moves, so every index stays valid and TotalSize is unchanged |
Which deletions can be compacted, which cannot
Index 0 is the root and index i sits at depth bitlen(i+1)-1, so the oldest
indices are the ancestors of the newest. A node is only freeable when its
whole subtree is dead, which gives a result worth knowing before you design
around this:
| You delete | Compactable |
Why |
|---|---|---|
| the oldest entries | 0, always | every newer entry keeps their ancestors alive |
| the newest entries | immediately non-zero | they are the leaves |
Measured on chain with 32 entries of 512 bytes: deleting the oldest 16 refunded
8,896 bytes and left nothing to compact. Deleting the newest 16 refunded the
same 8,896 bytes and then Compact returned a further 27,679, because a
node costs far more than the payload it holds. The structure is roughly two
thirds of the total cost, so being unable to compact leaves most of the money
on the table.
So an expiry queue that reaps oldest-first can never compact, which is the
opposite of the intuition. Delete from the top down, or wait for a run of
deletions to reach the leaves. Compactable is free, so a caller never has to
guess which case it is in.
v1, not an addition to v0, because one behaviour changes: a soft-deleted
element can be restored with Set, but not once Compact has freed its node
and the deposit has been refunded. Set on such an index returns
ErrOutOfBounds. That is the trade the refund pays for.
v0
is unchanged and still deployed: it is part of the gnoland1 genesis set.
Whether compacting is worth its gas depends on the gas price of the day, which
a contract cannot know. p/moul/x/storagecost
turns a Compactable count into a verdict in GNOT, and
r/moul/x/reaper
is a realm that does it in public.
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.
Package ulist provides an append-only list implementation using a binary tree structure, optimized for scenarios requiring sequential inserts with auto-incrementing indices.
The implementation uses a binary tree where new elements are added by following a path determined by the binary representation of the index. This provides automatic balancing for append operations without requiring any balancing logic.
Unlike the AVL tree-based list implementation (p/demo/avl/list), ulist is specifically designed for append-only operations and does not require rebalancing. This makes it more efficient for sequential inserts but less flexible for general-purpose list operations.
Key differences from AVL list: * Append-only design (no arbitrary inserts) * No tree rebalancing needed * Simpler implementation * More memory efficient for sequential operations * Less flexible than AVL (no arbitrary inserts/reordering)
Key characteristics:
- O(log n) append and access operations
- Perfect balance for power-of-2 sizes
- No balancing needed
- Memory efficient
- Natural support for range queries
- Support for soft deletion of elements, and index-preserving compaction of what those deletions leave behind (see compact.gno)
- Forward and reverse iteration capabilities
- Offset-based iteration with count control
1
1
4
type Entry
structEntry represents a key-value pair in the list, where Index is the position and Value is the stored data
type IList
interface 1type IList interface {
2 // Basic operations
3 Append(values ...any)
4 Get(index int) any
5 Delete(indices ...int) error
6 Size() int
7 TotalSize() int
8 Set(index int, value any) error
9
10 // Must variants that panic instead of returning errors
11 MustDelete(indices ...int)
12 MustGet(index int) any
13 MustSet(index int, value any)
14
15 // Range operations
16 GetRange(start, end int) []Entry
17 GetByOffset(offset int, count int) []Entry
18
19 // Iterator operations
20 Iterator(start, end int, cb IterCbFn) bool
21 IteratorByOffset(offset int, count int, cb IterCbFn) bool
22}IList defines the interface for an ulist.List compatible structure.
type IterCbFn
funcIterCbFn is a callback function type used in iteration methods. Return true to stop iteration, false to continue.
type List
structList represents an append-only binary tree list
Methods on List
func Append
method on ListAppend adds one or more values to the end of the list. Values are added sequentially, and the list grows automatically.
func Compact
method on ListCompact frees every tree node whose subtree holds no live element, and returns the number of nodes freed.
Indices are preserved exactly: TotalSize is unchanged, Size is unchanged, and every live element keeps the index it had. Appends continue from the same number.
Deleted elements swept up by a Compact become permanently unrestorable: Set on such an index returns ErrOutOfBounds where before it would have restored the value. That is the trade the refund pays for, and it is the reason this behaviour is v1 rather than an addition to v0.
func Compactable
method on ListCompactable reports how many tree nodes Compact would free right now.
It reads and mutates nothing, so a caller can poll it to decide whether compaction is worth its gas before paying for it. Zero means every dead node still shares a subtree with a live element, and compacting would cost gas to free nothing.
func Delete
method on ListDelete marks the elements at the specified indices as deleted. Returns ErrOutOfBounds if any index is invalid or ErrDeleted if the element was already deleted.
func Get
method on ListGet retrieves the value at the specified index. Returns nil if the index is out of bounds or if the element was deleted.
func GetByOffset
method on ListGetByOffset returns a slice of Entry starting from offset for count elements. If count is positive, returns elements forward; if negative, returns elements backward. The operation stops after abs(count) elements or when reaching list bounds. Deleted elements are skipped.
func GetRange
method on ListGetRange returns a slice of Entry containing elements between start and end indices. If start > end, elements are returned in reverse order. Deleted elements are skipped.
func Iterator
method on ListIterator performs iteration between start and end indices, calling cb for each entry. If start > end, iteration is performed in reverse order. Returns true if iteration was stopped early by the callback returning true. Skips deleted elements.
func IteratorByOffset
method on ListIteratorByOffset performs iteration starting from offset for count elements. If count is positive, iterates forward; if negative, iterates backward. The iteration stops after abs(count) elements or when reaching list bounds. Skips deleted elements.
func MustDelete
method on ListMustDelete deletes elements at the specified indices. Panics if any index is invalid or if any element was already deleted.
func MustGet
method on ListMustGet retrieves the value at the specified index. Panics if the index is out of bounds or if the element was deleted.
func MustSet
method on ListMustSet updates or restores a value at the specified index. Panics if the index is out of bounds.
func Set
method on ListSet updates or restores a value at the specified index if within bounds Returns ErrOutOfBounds if the index is invalid
func Size
method on ListSize returns the number of active (non-deleted) elements in the list
func TotalSize
method on ListTotalSize returns the total number of elements ever added to the list, including deleted elements
1
- errors stdlib
