Skip to content Search Apps Documentation Source Content Run Reset Eval Playground File Folder Download Copy Actions State String Boolean Number Struct Map Slice Pointer Function Closure Reference Nil Package Type Interface Unknown

Community realm. Read the code first. Community realm, deployed by its author. Read the code before you interact or send coins.

kv.gno

6.98 Kb · 266 lines
  1package golf
  2
  3import (
  4	"strconv"
  5	"strings"
  6
  7	"gno.land/r/nym-alexiscolin000/gnogolf/store"
  8)
  9
 10// The data lives in store (the realm apart from these rules: a new version of
 11// the rules takes it on). A view is the rows of one of its collections under a
 12// prefix, read straight from store and written through this transaction's
 13// writes: queued as the call goes, read back by Get and Has, and sent to store
 14// in one batch as the entrypoint returns (flush). Iterate and ReverseIterate
 15// merge this call's writes into store's rows as they come; Size, index and
 16// IterateByOffset, a page by place, read store as it stands, so one over rows
 17// this call has written to panics instead (only the reads take them, which
 18// write nothing).
 19type view struct {
 20	c string // the collection
 21	p string // the prefix: "" for the whole collection, else ending with a space, which no id holds
 22}
 23
 24var (
 25	queued []string          // set/del ops, four strings each, in order
 26	over   map[string]string // collection + "\x00" + key -> its value now; "\x00" for removed
 27	dirty  map[string]bool   // the collections written to
 28	seen   map[string]*entry // the versions found in this call that writes: one object each (find)
 29)
 30
 31// begin opens a call that writes: every crossing entrypoint that writes
 32// starts with it and ends with flush.
 33func begin() { seen = map[string]*entry{} }
 34
 35const gone = "\x00"
 36
 37func (v view) end() string {
 38	if v.p == "" {
 39		return ""
 40	}
 41	return v.p[:len(v.p)-1] + "!"
 42}
 43
 44func (v view) Get(k string) (string, bool) {
 45	if x, ok := over[v.c+"\x00"+v.p+k]; ok {
 46		return x, x != gone
 47	}
 48	return store.Get(v.c, v.p+k)
 49}
 50
 51func (v view) Has(k string) bool {
 52	_, ok := v.Get(k)
 53	return ok
 54}
 55
 56func (v view) Set(k, x string) {
 57	queue("set", v.c, v.p+k, x)
 58}
 59
 60// Remove drops a row, reporting whether it was there.
 61func (v view) Remove(k string) bool {
 62	if !v.Has(k) {
 63		return false
 64	}
 65	queue("del", v.c, v.p+k, gone)
 66	return true
 67}
 68
 69func queue(op, c, k, x string) {
 70	if over == nil {
 71		over, dirty = map[string]string{}, map[string]bool{}
 72	}
 73	if op == "del" {
 74		queued = append(queued, op, c, k, "")
 75	} else {
 76		queued = append(queued, op, c, k, x)
 77	}
 78	over[c+"\x00"+k] = x
 79	dirty[c] = true
 80}
 81
 82// flush sends this call's writes to store, in batches of what store takes in
 83// one call: every crossing entrypoint that writes ends with it, once it went
 84// through (begin opens it).
 85func flush(cur realm) {
 86	for i := 0; i < len(queued); i += 4 * 64 {
 87		j := i + 4*64
 88		if j > len(queued) {
 89			j = len(queued)
 90		}
 91		store.Batch(cross(cur), queued[i:j])
 92	}
 93	queued, over, dirty, seen = nil, nil, nil, nil
 94}
 95
 96// clean refuses a walk over rows this call has written to (store has not got them yet)
 97func (v view) clean() {
 98	if !dirty[v.c] {
 99		return
100	}
101	for k := range over {
102		if strings.HasPrefix(k, v.c+"\x00"+v.p) {
103			panic("golf: a walk over " + v.c + " " + v.p + "after writing to it in the same call")
104		}
105	}
106}
107
108// Size is how many rows the view holds.
109func (v view) Size() int {
110	v.clean()
111	if v.p == "" {
112		return store.Size(v.c)
113	}
114	return store.Index(v.c, v.end()) - store.Index(v.c, v.p)
115}
116
117// index is how many of its rows sort before k: k's place, from 0.
118func (v view) index(k string) int {
119	v.clean()
120	return store.Index(v.c, v.p+k) - store.Index(v.c, v.p)
121}
122
123// Iterate is the rows in [start, end) ascending, end "" for no bound; cb
124// returning true stops it, and Iterate then reports true.
125func (v view) Iterate(start, end string, cb func(key, x string) bool) bool {
126	return v.walk(start, end, cb, false)
127}
128
129// ReverseIterate is the rows in [start, end] descending (store's, as v1's
130// bptree: its end is kept), end "" for no bound.
131func (v view) ReverseIterate(start, end string, cb func(key, x string) bool) bool {
132	return v.walk(start, end, cb, true)
133}
134
135func (v view) walk(start, end string, cb func(key, x string) bool, back bool) bool {
136	lo, hi := v.p+start, v.end()
137	if end != "" {
138		hi = v.p + end
139	}
140	// this call's own writes in the range, in walk order: merged into store's
141	// rows as they come (a finish on an archived hole, then its drain over it)
142	in := func(k string) bool { return k >= lo && (hi == "" || k < hi || back && k == hi) }
143	var mine []string
144	for ck := range over {
145		if c, k, _ := strings.Cut(ck, "\x00"); c == v.c && in(k) {
146			mine = append(mine, k)
147		}
148	}
149	sortKeys(mine, back)
150	emit := func(k, x string) bool { return cb(k[len(v.p):], x) }
151	// ours before k (or all of them, k ""), as they stand; true if the walk stopped
152	flushMine := func(k string) bool {
153		for len(mine) > 0 && (k == "" || (!back && mine[0] < k) || (back && mine[0] > k)) {
154			m := mine[0]
155			mine = mine[1:]
156			if x := over[v.c+"\x00"+m]; x != gone && emit(m, x) {
157				return true
158			}
159		}
160		return false
161	}
162	// (store's back walk keeps its end, its forward one does not: a back page
163	// after the first starts with the last one's key again, skipped). Pages
164	// start small and double: most walks stop after a row or a few.
165	again, size := "", firstRead
166	for {
167		var page string
168		if back {
169			page = store.PageBack(v.c, lo, hi, size)
170		} else {
171			page = store.Page(v.c, lo, hi, size)
172		}
173		n, last := 0, ""
174		for page != "" {
175			var k, x string
176			k, x, page = nextRow(page)
177			n, last = n+1, k
178			if k == again {
179				continue
180			}
181			if flushMine(k) {
182				return true
183			}
184			if len(mine) > 0 && mine[0] == k { // ours: as it stands now
185				mine = mine[1:]
186				if x = over[v.c+"\x00"+k]; x == gone {
187					continue
188				}
189			}
190			if emit(k, x) {
191				return true
192			}
193		}
194		if n < size {
195			return flushMine("")
196		}
197		if back {
198			hi, again = last, last
199		} else {
200			lo = last + "\x00" // (the next key up)
201		}
202		if size *= 2; size > maxRead {
203			size = maxRead
204		}
205	}
206}
207
208// sortKeys sorts keys ascending, or descending for back (a handful: insertion sort).
209func sortKeys(ks []string, back bool) {
210	for i := 1; i < len(ks); i++ {
211		for j := i; j > 0 && (!back && ks[j] < ks[j-1] || back && ks[j] > ks[j-1]); j-- {
212			ks[j], ks[j-1] = ks[j-1], ks[j]
213		}
214	}
215}
216
217// IterateByOffset is count rows from the offset-th, fewer at the end.
218func (v view) IterateByOffset(offset, count int, cb func(key, x string) bool) bool {
219	v.clean()
220	from, end := store.Index(v.c, v.p)+offset, v.end()
221	for count > 0 {
222		n := count
223		if n > maxRead {
224			n = maxRead
225		}
226		page, got := store.PageAt(v.c, from, n), 0
227		for page != "" {
228			var k, x string
229			k, x, page = nextRow(page)
230			if end != "" && k >= end || cb(k[len(v.p):], x) {
231				return true
232			}
233			got++
234		}
235		if got < n {
236			return false
237		}
238		from, count = from+got, count-got
239	}
240	return false
241}
242
243// A page of store: the first a walk asks for, and the largest.
244const (
245	firstRead = 8
246	maxRead   = 300
247)
248
249// nextRow is a page's first row (store.Page: each length, ":", itself) and the rest.
250func nextRow(page string) (string, string, string) {
251	k, rest := field(page)
252	x, rest := field(rest)
253	return k, x, rest
254}
255
256func field(s string) (string, string) {
257	i := strings.IndexByte(s, ':')
258	if i < 0 {
259		panic("golf: store's page unread")
260	}
261	n, err := strconv.Atoi(s[:i])
262	if err != nil || n < 0 || i+1+n > len(s) {
263		panic("golf: store's page unread")
264	}
265	return s[i+1 : i+1+n], s[i+1+n:]
266}