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}
