gno.land/p/moul/ulist/v1⧉

# `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`](https://github.com/moul/gno-contracts/tree/f6d0693f5161db423c042a4fe7c78057593cff80/p/moul/ulist)
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`](https://github.com/moul/gno-contracts/tree/main/p/moul/x/storagecost)
turns a `Compactable` count into a verdict in GNOT, and
[`r/moul/x/reaper`](https://github.com/moul/gno-contracts/tree/main/r/moul/x/reaper)
is a realm that does it in public.

<!-- BEGIN GNOCONTRACTS FOOTER (generated by `make readmes`; do not edit below) -->

---

Part of **[moul/gno-contracts](https://github.com/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](https://github.com/moul/gno-contracts/blob/main/DISCLAIMER.md).

<!-- END GNOCONTRACTS FOOTER -->