addrset.gno

 1// Package addrset provides a set of blockchain addresses, backed by a B+ tree.
 2//
 3// It is the B+ tree successor to [gno.land/p/moul/addrset/v0] (which is backed
 4// by an AVL tree): a bump to v1 because the backing data structure — and thus
 5// the on-chain storage layout — changed. The exported API is the same as v0
 6// (Add/Remove/Has/Size/IterateByOffset/ReverseIterateByOffset) EXCEPT that the
 7// v0 `Tree() avl.ITree` escape hatch is intentionally removed, so the backing
 8// store never leaks across realms.
 9//
10// A B+ tree packs many entries per persisted node, so a stored address costs
11// roughly ~0.9 KB vs the AVL backing's ~2.0 KB (and inserts spend materially
12// less gas). Prefer v1 when the set is part of persisted realm state.
13//
14// Two behavioral differences from v0, both consequences of the in-place-
15// mutating B+ tree backing:
16//
17//   - do NOT mutate the set (Add/Remove) from inside an iteration callback —
18//     the AVL backing's copy-on-write tolerated it, this one does not;
19//   - do NOT copy a non-zero Set by value — the copies would share live tree
20//     nodes while their roots and sizes diverge (v0's copies were independent
21//     snapshots).
22//
23// Example:
24//
25//	var set addrset.Set // the zero value is an empty, usable set
26//
27//	set.Add(addr)    // true (newly added)
28//	set.Has(addr)    // true
29//	set.Remove(addr) // true (was present)
30package addrset
31
32import "gno.land/p/nt/bptree/v0"
33
34// Set stores a set of addresses in sorted order. The zero value is an empty,
35// usable set.
36type Set struct {
37	tree bptree.BPTree
38}
39
40// Add inserts an address into the set.
41// Returns true if the address was newly added, false if it already existed.
42func (s *Set) Add(addr address) bool {
43	return !s.tree.Set(string(addr), nil)
44}
45
46// Remove deletes an address from the set.
47// Returns true if the address was found and removed, false if it didn't exist.
48func (s *Set) Remove(addr address) bool {
49	_, removed := s.tree.Remove(string(addr))
50	return removed
51}
52
53// Has checks if an address exists in the set.
54func (s *Set) Has(addr address) bool {
55	return s.tree.Has(string(addr))
56}
57
58// Size returns the number of addresses in the set.
59func (s *Set) Size() int {
60	return s.tree.Size()
61}
62
63// IterateByOffset walks through addresses in sorted order, starting at the
64// given offset and visiting up to count addresses. The callback returns true
65// to stop iteration. The set must not be modified during iteration.
66func (s *Set) IterateByOffset(offset int, count int, cb func(addr address) bool) {
67	s.tree.IterateByOffset(offset, count, func(key string, _ any) bool {
68		return cb(address(key))
69	})
70}
71
72// ReverseIterateByOffset walks through addresses in reverse (descending) order,
73// starting at the given offset (counted from the end) and visiting up to count
74// addresses. The callback returns true to stop iteration. The set must not be
75// modified during iteration.
76func (s *Set) ReverseIterateByOffset(offset int, count int, cb func(addr address) bool) {
77	s.tree.ReverseIterateByOffset(offset, count, func(key string, _ any) bool {
78		return cb(address(key))
79	})
80}