store.gno
8.84 Kb · 338 lines
1// Package store holds GnoRadio's string codecs: records (fields behind a
2// length header, read and changed without decoding), packed id lists (9
3// bytes per id, sorted, JSON-ready), base-64 fixed-width numbers, the 8-digit
4// keys and page rows of the data realm, and the Ops builder of data.Batch.
5// It keeps no state: every realm stores these strings in the data realm.
6package store
7
8import "strconv"
9
10// ---- Records: fields behind a length header, sliced without scanning ----
11
12// In the VM every byte a loop touches costs gas (strings.Split of a 200-byte
13// record is about 2M gas). A record starts with the field count and each
14// field's length (base-64 digits), so reading a field is a few slices.
15
16// Digits are the base-64 digits of record headers and of Num and Fixed,
17// ordered so that fixed-width numbers sort as their values do.
18const Digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz-_"
19
20const digits = Digits
21
22// dec decodes record headers, dec64 the numbers of Num: one table each
23// spares a conversion per digit.
24var (
25 dec [128]int
26 dec64 [128]int64
27)
28
29func init() {
30 for i := 0; i < len(digits); i++ {
31 dec[digits[i]], dec64[digits[i]] = i, int64(i)
32 }
33}
34
35// Num reads the w-digit base-64 number at position at of s (one expression
36// for the usual widths: every VM step costs gas).
37func Num(s string, at, w int) int64 {
38 switch w {
39 case 1:
40 return dec64[s[at]]
41 case 2:
42 return dec64[s[at]]<<6 | dec64[s[at+1]]
43 case 4:
44 return dec64[s[at]]<<18 | dec64[s[at+1]]<<12 | dec64[s[at+2]]<<6 | dec64[s[at+3]]
45 case 6:
46 return dec64[s[at]]<<30 | dec64[s[at+1]]<<24 | dec64[s[at+2]]<<18 | dec64[s[at+3]]<<12 | dec64[s[at+4]]<<6 | dec64[s[at+5]]
47 }
48 var v int64
49 for i := at; i < at+w; i++ {
50 v = v<<6 | dec64[s[i]]
51 }
52 return v
53}
54
55// Fixed writes v in w base-64 digits.
56func Fixed(v int64, w int) string { return string(AppendFixed(make([]byte, 0, w), v, w)) }
57
58// AppendFixed appends v in w base-64 digits to b (one append for the usual
59// widths). It panics when v does not fit.
60func AppendFixed(b []byte, v int64, w int) []byte {
61 if v < 0 || v>>(6*w) != 0 {
62 panic("store: number out of range")
63 }
64 switch w {
65 case 1:
66 return append(b, digits[v])
67 case 2:
68 return append(b, digits[v>>6], digits[v&63])
69 case 4:
70 return append(b, digits[v>>18], digits[v>>12&63], digits[v>>6&63], digits[v&63])
71 case 6:
72 return append(b, digits[v>>30], digits[v>>24&63], digits[v>>18&63], digits[v>>12&63], digits[v>>6&63], digits[v&63])
73 }
74 for i := w - 1; i >= 0; i-- {
75 b = append(b, digits[v>>(6*i)&63])
76 }
77 return b
78}
79
80// MaxField is the longest field a record holds (3 base-64 digits).
81const MaxField = 1<<18 - 1
82
83// Rec packs fields into a record (at most 63 fields).
84func Rec(fs ...string) string {
85 if len(fs) > 63 {
86 panic("store: too many fields")
87 }
88 h := make([]byte, 1, 1+3*len(fs))
89 h[0] = digits[len(fs)]
90 body := make([]byte, 0, 64)
91 for _, f := range fs {
92 n := len(f)
93 if n > MaxField {
94 panic("store: field too long")
95 }
96 h = append(h, digits[n>>12&63], digits[n>>6&63], digits[n&63])
97 body = append(body, f...)
98 }
99 return string(h) + string(body)
100}
101
102func fieldLen(rec string, i int) int {
103 return dec[rec[1+3*i]]<<12 | dec[rec[2+3*i]]<<6 | dec[rec[3+3*i]]
104}
105
106// Fields unpacks a record.
107func Fields(rec string) []string {
108 n := dec[rec[0]]
109 out := make([]string, n)
110 p := 1 + 3*n
111 for i := 0; i < n; i++ {
112 l := fieldLen(rec, i)
113 out[i] = rec[p : p+l]
114 p += l
115 }
116 return out
117}
118
119// Field returns field i of a record ("" past the last field).
120func Field(rec string, i int) string {
121 n := dec[rec[0]]
122 if i >= n {
123 return ""
124 }
125 p := 1 + 3*n
126 for k := 0; k < i; k++ {
127 p += fieldLen(rec, k)
128 }
129 return rec[p : p+fieldLen(rec, i)]
130}
131
132// With returns rec with field i replaced by v, without decoding the record.
133func With(rec string, i int, v string) string {
134 n := dec[rec[0]]
135 if i < 0 || i >= n || len(v) > MaxField {
136 panic("store: bad field")
137 }
138 p := 1 + 3*n
139 for k := 0; k < i; k++ {
140 p += fieldLen(rec, k)
141 }
142 l := len(v)
143 h := string([]byte{digits[l>>12&63], digits[l>>6&63], digits[l&63]})
144 return rec[:1+3*i] + h + rec[4+3*i:p] + v + rec[p+fieldLen(rec, i):]
145}
146
147// Append returns rec with v added as its last field, without decoding the
148// record ("" is a record of no fields).
149func Append(rec, v string) string {
150 if rec == "" {
151 return Rec(v)
152 }
153 n := dec[rec[0]]
154 if n >= 63 || len(v) > MaxField {
155 panic("store: bad field")
156 }
157 l := len(v)
158 h := string([]byte{digits[n+1], digits[l>>12&63], digits[l>>6&63], digits[l&63]})
159 return h[:1] + rec[1:1+3*n] + h[1:] + rec[1+3*n:] + v
160}
161
162// ---- Id lists: W bytes per id (" 123,"), sortable and JSON-ready ----
163
164// W is the width of one id in a list (ids up to 99,999,999). The padding is
165// spaces and the separator a comma, so "[" + list without its last comma +
166// "]" is already a JSON array: exporting a list costs no per-id work.
167const W = 9
168
169// Enc writes one id of a list.
170func Enc(id int) string {
171 if id < 0 || id > 99999999 {
172 panic("store: id out of range")
173 }
174 s := strconv.Itoa(id)
175 return " "[len(s):] + s + ","
176}
177
178// At returns the i-th id of a list.
179func At(list string, i int) int {
180 n := 0
181 for k := i * W; k < i*W+W-1; k++ {
182 if c := list[k]; c != ' ' {
183 n = n*10 + int(c-'0')
184 }
185 }
186 return n
187}
188
189// Count is the number of ids in a list.
190func Count(list string) int { return len(list) / W }
191
192// JSON returns a list as a JSON array.
193func JSON(list string) string {
194 if list == "" {
195 return "[]"
196 }
197 return "[" + list[:len(list)-1] + "]"
198}
199
200// Ints decodes a list.
201func Ints(list string) []int {
202 out := make([]int, 0, Count(list))
203 for i := 0; i < Count(list); i++ {
204 out = append(out, At(list, i))
205 }
206 return out
207}
208
209// Pack encodes ids in their order.
210func Pack(ids []int) string {
211 b := make([]byte, 0, W*len(ids))
212 for _, id := range ids {
213 b = append(b, Enc(id)...)
214 }
215 return string(b)
216}
217
218// Page returns up to limit ids from offset, from the end when desc.
219func Page(list string, offset, limit int, desc bool) []int {
220 n := Count(list)
221 var out []int
222 for k := offset; k >= 0 && k < n && len(out) < limit; k++ {
223 i := k
224 if desc {
225 i = n - 1 - k
226 }
227 out = append(out, At(list, i))
228 }
229 return out
230}
231
232// find returns the position of id in a sorted list, or where it goes.
233func find(list string, id int) (int, bool) {
234 lo, hi := 0, Count(list)
235 for lo < hi {
236 mid := (lo + hi) / 2
237 if At(list, mid) < id {
238 lo = mid + 1
239 } else {
240 hi = mid
241 }
242 }
243 return lo, lo < Count(list) && At(list, lo) == id
244}
245
246// Add inserts id into a sorted list; false if already there.
247func Add(sorted string, id int) (string, bool) {
248 i, ok := find(sorted, id)
249 if ok {
250 return sorted, false
251 }
252 return sorted[:i*W] + Enc(id) + sorted[i*W:], true
253}
254
255// Remove deletes id from a sorted list; false if absent.
256func Remove(sorted string, id int) (string, bool) {
257 i, ok := find(sorted, id)
258 if !ok {
259 return sorted, false
260 }
261 return sorted[:i*W] + sorted[i*W+W:], true
262}
263
264// ---- Keys, page rows and batch ops for the data realm ----
265
266// Pad writes a number as an 8-digit key, so keys sort as numbers do.
267func Pad(n int) string {
268 if n < 0 || n > 99999999 {
269 panic("store: key number out of range")
270 }
271 s := strconv.Itoa(n)
272 return "00000000"[len(s):] + s
273}
274
275// TimeKey writes a unix time as a 12-digit key, so keys sort as times do.
276func TimeKey(t int64) string {
277 s := strconv.FormatInt(t, 10)
278 return "000000000000"[len(s):] + s
279}
280
281// Slot is where record id (from 1) of a chunked collection lives: the key
282// of its chunk of size records and its index there.
283func Slot(id, size int) (string, int) { return Pad((id - 1) / size), (id - 1) % size }
284
285// Limit is a page size: n, or max when n is out of 1..max.
286func Limit(n, max int) int {
287 if n < 1 || n > max {
288 return max
289 }
290 return n
291}
292
293// Row encodes one key and value of a page: "len:key" + "len:value".
294func Row(k, v string) string {
295 return strconv.Itoa(len(k)) + ":" + k + strconv.Itoa(len(v)) + ":" + v
296}
297
298// Rows decodes a page of Row strings into its keys and values.
299func Rows(page string) (keys, values []string) {
300 for page != "" {
301 var k, v string
302 k, page = cut(page)
303 v, page = cut(page)
304 keys, values = append(keys, k), append(values, v)
305 }
306 return keys, values
307}
308
309// cut reads one "len:bytes" item off the front of s.
310func cut(s string) (item, rest string) {
311 i, n := 0, 0
312 for i < len(s) && i < 6 && s[i] >= '0' && s[i] <= '9' {
313 n = n*10 + int(s[i]-'0') // the length, read as it is scanned
314 i++
315 }
316 if i == 0 || i == len(s) || s[i] != ':' {
317 panic("store: bad row")
318 }
319 if n > len(s)-i-1 {
320 panic("store: bad row")
321 }
322 return s[i+1 : i+1+n], s[i+1+n:]
323}
324
325// Batch op names: an op is four strings (name, collection, key, value).
326const (
327 OpSet = "set"
328 OpDel = "del"
329)
330
331// Ops builds the argument of data.Batch: ops = ops.Set(c, k, v).
332type Ops []string
333
334// Set adds a write of v at key k of collection c.
335func (o Ops) Set(c, k, v string) Ops { return append(o, OpSet, c, k, v) }
336
337// Del adds a removal of key k of collection c.
338func (o Ops) Del(c, k string) Ops { return append(o, OpDel, c, k, "") }
