tree.gno

  1package staker
  2
  3import (
  4	"gno.land/p/gnoswap/gnsmath/v1"
  5	"gno.land/p/gnoswap/utils/v1"
  6	rotree "gno.land/p/nt/bptree/rotree/v0"
  7	bptree "gno.land/p/nt/bptree/v0"
  8	ufmt "gno.land/p/nt/ufmt/v0"
  9)
 10
 11// UintTree wraps a B+ tree with nonnegative int64 timestamp keys, encoded as
 12// fixed-width 8-byte big-endian strings to preserve numeric ordering.
 13//
 14// Methods:
 15// - Get: Retrieves a value associated with an int64 key.
 16// - Set: Stores a value with an int64 key.
 17// - Has: Checks if an int64 key exists in the tree.
 18// - Remove: Removes an int64 key and its associated value.
 19// - Iterate: Iterates over keys and values in a range.
 20// - ReverseIterate: Iterates in reverse order over keys and values in a range.
 21type UintTree struct {
 22	tree   *bptree.BPTree // blockTimestamp -> any
 23	fanout int
 24}
 25
 26// NewBPTreeN allocates a raw BP-tree under /r/gnoswap/staker's realm
 27// context (the realm that declares Pool/Deposit/ExternalIncentive). The tree's
 28// PkgID is therefore /r/gnoswap/staker, matching the domain values it stores,
 29// so tree.Set leaf-slot writes clear the readonly-taint gate regardless of
 30// which realm (staker/v1, mock) calls Set (borrow rule #2 borrows m.Realm to
 31// the tree's owning realm). Implementations and mocks must allocate trees that
 32// hold /r/gnoswap/staker-declared values through here rather than calling
 33// bptree.NewBPTreeN directly in their own realm.
 34//
 35// Parameters:
 36//   - fanout: Number of child pointers per B+ tree node; controls the tree's branching factor.
 37//
 38// Returns:
 39//   - tree: Mutable raw B+ tree allocated in the staker realm context.
 40func NewBPTreeN(fanout int) *bptree.BPTree {
 41	return bptree.NewBPTreeN(fanout)
 42}
 43
 44// NewUintTree creates a new UintTree instance with default fanout 64.
 45//
 46// Returns:
 47//   - tree: Empty UintTree using the default fanout of 64.
 48func NewUintTree() *UintTree {
 49	return NewUintTreeN(64)
 50}
 51
 52// NewUintTreeN creates a new UintTree instance with the specified fanout.
 53//
 54// Parameters:
 55//   - fanout: Number of child pointers per B+ tree node used by the wrapped tree.
 56//
 57// Returns:
 58//   - tree: Empty UintTree configured with the requested fanout.
 59func NewUintTreeN(fanout int) *UintTree {
 60	return &UintTree{
 61		tree:   bptree.NewBPTreeN(fanout),
 62		fanout: fanout,
 63	}
 64}
 65
 66// Get looks up a value by its nonnegative int64 key.
 67//
 68// Parameters:
 69//   - key: Nonnegative timestamp-like key encoded into the tree's ordered key format.
 70//
 71// Returns:
 72//   - value: Stored value when the key maps to a non-nil entry; nil when absent.
 73//   - found: True when a non-nil value exists for key, and false otherwise.
 74func (self *UintTree) Get(key int64) (any, bool) {
 75	v := self.tree.Get(encodeInt64(key))
 76	if v == nil {
 77		return nil, false
 78	}
 79	return v, true
 80}
 81
 82// Set stores a value under a nonnegative int64 key.
 83//
 84// Parameters:
 85//   - key: Nonnegative timestamp-like key used as the ordered tree key; negative values panic.
 86//   - value: Value to associate with key.
 87func (self *UintTree) Set(key int64, value any) {
 88	self.tree.Set(encodeInt64(key), value)
 89}
 90
 91// Has reports whether an encoded key is present in the underlying tree.
 92//
 93// Parameters:
 94//   - key: Nonnegative timestamp-like key to test; negative values panic during encoding.
 95//
 96// Returns:
 97//   - present: True when the underlying tree contains key, including entries whose value may be nil according to the B+ tree.
 98func (self *UintTree) Has(key int64) bool {
 99	return self.tree.Has(encodeInt64(key))
100}
101
102// Remove deletes the value stored under a key, if any.
103//
104// Parameters:
105//   - key: Nonnegative timestamp-like key to remove; negative values panic during encoding.
106func (self *UintTree) Remove(key int64) {
107	self.tree.Remove(encodeInt64(key))
108}
109
110// Iterate visits entries in ascending key order over the underlying tree range.
111//
112// Parameters:
113//   - start: Nonnegative lower bound for the encoded key range.
114//   - end: Nonnegative upper bound for the encoded key range.
115//   - fn: Callback receiving each decoded key and value; returning true requests that iteration stop.
116func (self *UintTree) Iterate(start, end int64, fn func(key int64, value any) bool) {
117	self.tree.Iterate(encodeInt64(start), encodeInt64(end), func(key string, value any) bool {
118		return fn(decodeInt64(key), value)
119	})
120}
121
122// ReverseIterate visits entries in descending key order over the underlying tree range.
123//
124// Parameters:
125//   - start: Nonnegative lower bound for the encoded key range.
126//   - end: Nonnegative upper bound for the encoded key range.
127//   - fn: Callback receiving each decoded key and value; returning true requests that iteration stop.
128func (self *UintTree) ReverseIterate(start, end int64, fn func(key int64, value any) bool) {
129	self.tree.ReverseIterate(encodeInt64(start), encodeInt64(end), func(key string, value any) bool {
130		return fn(decodeInt64(key), value)
131	})
132}
133
134// Size returns the number of entries currently stored in the tree.
135//
136// Returns:
137//   - size: Number of key/value entries in the underlying B+ tree.
138func (self *UintTree) Size() int {
139	return self.tree.Size()
140}
141
142// IterateByOffset visits a page of entries beginning at an offset.
143//
144// Parameters:
145//   - offset: Zero-based number of entries to skip before invoking fn.
146//   - count: Maximum number of entries to visit.
147//   - fn: Callback receiving each decoded key and value; returning true requests that iteration stop.
148func (self *UintTree) IterateByOffset(offset, count int, fn func(key int64, value any) bool) {
149	self.tree.IterateByOffset(offset, count, func(key string, value any) bool {
150		return fn(decodeInt64(key), value)
151	})
152}
153
154// ReadOnly returns a read-only view of the underlying tree, so callers can
155// paginate it without gaining a handle on the mutable tree.
156//
157// Keys use utils.EncodeUint64's fixed-width binary encoding, not the int64
158// keys this type takes; utils.DecodeUint64 recovers the nonnegative value.
159//
160// Parameters:
161//   - makeEntrySafeFn: Callback that converts each stored value into the representation exposed through the read-only view.
162//
163// Returns:
164//   - tree: Read-only wrapper over the underlying tree for safe pagination.
165func (self *UintTree) ReadOnly(makeEntrySafeFn func(any) any) *rotree.ReadOnlyTree {
166	return rotree.Wrap(self.tree, makeEntrySafeFn)
167}
168
169// Clone returns a new UintTree with the same encoded keys and stored value references.
170//
171// Returns:
172//   - tree: New UintTree preserving this tree's fanout and entries; pointed-to values are not deep-cloned.
173func (self *UintTree) Clone() *UintTree {
174	if self == nil {
175		return nil
176	}
177
178	cloned := NewUintTreeN(self.fanout)
179	self.tree.Iterate("", "", func(key string, value any) bool {
180		cloned.tree.Set(key, value)
181		return false
182	})
183
184	return cloned
185}
186
187func encodeInt64(num int64) string {
188	if num < 0 {
189		panic(ufmt.Sprintf("negative value not supported: %d", num))
190	}
191	return utils.EncodeUint64(uint64(num))
192}
193
194func decodeInt64(s string) int64 {
195	return gnsmath.SafeUint64ToInt64(utils.DecodeUint64(s))
196}