README.md
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.
