addrset.gno

 1// Package addrset provides a set of blockchain addresses backed by a
 2// B+ tree, with a read-only view type for safe cross-realm exposure.
 3//
 4// It mirrors the gno.land/p/moul/addrset API on a
 5// gno.land/p/nt/bptree/v0 backing: a B+ tree packs many entries per
 6// persisted node, so a stored address costs ~0.9 KB vs the
 7// one-node-per-entry AVL backing's ~2.0 KB (2.2x asymptotically, 1.6x
 8// at 10 entries; insert gas ~2.1x less). Prefer this package when sets
 9// are part of persisted realm state; the omitted Tree() escape hatch is
10// deliberate, so the backing store never leaks.
11//
12// Two behavioral differences from the AVL-backed moul package, both
13// consequences of the in-place-mutating backing:
14//
15//   - the set must NOT be mutated (Add/Remove) from inside an iteration
16//     callback — the AVL backing's copy-on-write tolerated it, this one
17//     does not;
18//   - do not copy a non-zero Set by value — the copies share live tree
19//     nodes while their roots and sizes diverge (the AVL backing's
20//     copies were independent snapshots).
21//
22// Example:
23//
24//	var set addrset.Set // the zero value is an empty, usable set
25//
26//	set.Add(addr)   // true (newly added)
27//	set.Has(addr)   // true
28//	set.Remove(addr) // true (was present)
29package addrset
30
31import "gno.land/p/nt/bptree/v0"
32
33// Set stores a set of addresses in sorted order. The zero value is an
34// empty, usable set.
35type Set struct {
36	tree bptree.BPTree
37}
38
39// Add inserts an address into the set.
40// Returns true if the address was newly added, false if it already existed.
41func (s *Set) Add(addr address) bool {
42	return !s.tree.Set(string(addr), nil)
43}
44
45// Remove deletes an address from the set.
46// Returns true if the address was found and removed, false if it didn't exist.
47func (s *Set) Remove(addr address) bool {
48	_, removed := s.tree.Remove(string(addr))
49	return removed
50}
51
52// Has checks if an address exists in the set.
53func (s *Set) Has(addr address) bool {
54	return s.tree.Has(string(addr))
55}
56
57// Size returns the number of addresses in the set.
58func (s *Set) Size() int {
59	return s.tree.Size()
60}
61
62// IterateByOffset walks through addresses in sorted order, starting at
63// the given offset and visiting up to count addresses. The callback
64// returns true to stop iteration. The set must not be modified during
65// iteration (no Add or Remove from the callback).
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)
73// order, starting at the given offset (counted from the end) and
74// visiting up to count addresses. The callback returns true to stop
75// iteration. The set must not be modified during iteration (no Add or
76// Remove from the callback).
77func (s *Set) ReverseIterateByOffset(offset int, count int, cb func(addr address) bool) {
78	s.tree.ReverseIterateByOffset(offset, count, func(key string, _ any) bool {
79		return cb(address(key))
80	})
81}