Line data Source code
1 : // Copyright 2024 The LevelDB-Go and Pebble Authors. All rights reserved. Use
2 : // of this source code is governed by a BSD-style license that can be found in
3 : // the LICENSE file.
4 :
5 : package colblk
6 :
7 : import (
8 : "bytes"
9 : "context"
10 : "encoding/binary"
11 : "fmt"
12 : "os"
13 : "sync"
14 : "unsafe"
15 :
16 : "github.com/cockroachdb/errors"
17 : "github.com/cockroachdb/pebble/internal/base"
18 : "github.com/cockroachdb/pebble/internal/binfmt"
19 : "github.com/cockroachdb/pebble/internal/invariants"
20 : "github.com/cockroachdb/pebble/internal/keyspan"
21 : "github.com/cockroachdb/pebble/internal/treeprinter"
22 : "github.com/cockroachdb/pebble/sstable/block"
23 : )
24 :
25 : // the keyspan header encodes a 32-bit count of the number of unique boundary
26 : // user keys in the block.
27 : const keyspanHeaderSize = 4
28 :
29 : // keyspan block column indexes
30 : const (
31 : // Columns with 1 row per unique boundary user key contained within the
32 : // block (with the count indicated via the keyspan custom block header).
33 : keyspanColBoundaryUserKeys = 0
34 : keyspanColBoundaryKeyIndices = 1
35 : // Columns with 1 row per keyspan.Key (with the count indicated via the
36 : // columnar header's row count).
37 : keyspanColTrailers = 2
38 : keyspanColSuffixes = 3
39 : keyspanColValues = 4
40 : keyspanColumnCount = 5
41 : )
42 :
43 : // A KeyspanBlockWriter writes keyspan blocks. See the colblk package
44 : // documentation for more details on the schema.
45 : type KeyspanBlockWriter struct {
46 : equal base.Equal
47 :
48 : // boundary columns
49 : boundaryUserKeys RawBytesBuilder
50 : boundaryKeyIndexes UintBuilder
51 :
52 : // keyspan.Key columns
53 : trailers UintBuilder
54 : suffixes RawBytesBuilder
55 : values RawBytesBuilder
56 :
57 : enc blockEncoder
58 : keyCount int
59 : unsafeLastUserKey []byte
60 : }
61 :
62 : // Init initializes a keyspan block writer.
63 1 : func (w *KeyspanBlockWriter) Init(equal base.Equal) {
64 1 : w.equal = equal
65 1 : w.boundaryUserKeys.Init()
66 1 : w.boundaryKeyIndexes.Init()
67 1 : w.trailers.Init()
68 1 : w.suffixes.Init()
69 1 : w.values.Init()
70 1 : w.keyCount = 0
71 1 : w.unsafeLastUserKey = nil
72 1 : }
73 :
74 : // Reset resets the keyspan block writer to an empty state, retaining memory for
75 : // reuse.
76 1 : func (w *KeyspanBlockWriter) Reset() {
77 1 : w.boundaryUserKeys.Reset()
78 1 : w.boundaryKeyIndexes.Reset()
79 1 : w.trailers.Reset()
80 1 : w.suffixes.Reset()
81 1 : w.values.Reset()
82 1 : w.enc.reset()
83 1 : w.keyCount = 0
84 1 : w.unsafeLastUserKey = nil
85 1 : }
86 :
87 : // AddSpan appends a new Span to the pending block. Spans must already be
88 : // fragmented (non-overlapping) and added in sorted order.
89 1 : func (w *KeyspanBlockWriter) AddSpan(s keyspan.Span) {
90 1 : // When keyspans are fragmented, abutting spans share a user key. One span's
91 1 : // end key is the next span's start key. Check if the previous user key
92 1 : // equals this span's start key, and avoid encoding it again if so.
93 1 : if w.unsafeLastUserKey == nil || !w.equal(w.unsafeLastUserKey, s.Start) {
94 1 : w.boundaryKeyIndexes.Set(w.boundaryUserKeys.rows, uint64(w.keyCount))
95 1 : w.boundaryUserKeys.Put(s.Start)
96 1 : }
97 : // The end key must be strictly greater than the start key and spans are
98 : // already sorted, so the end key is guaranteed to not be present in the
99 : // column yet. We need to encode it.
100 1 : w.boundaryKeyIndexes.Set(w.boundaryUserKeys.rows, uint64(w.keyCount+len(s.Keys)))
101 1 : w.boundaryUserKeys.Put(s.End)
102 1 :
103 1 : // Hold on to a slice of the copy of s.End we just added to the bytes
104 1 : // builder so that we can compare it to the next span's start key.
105 1 : w.unsafeLastUserKey = w.boundaryUserKeys.data[len(w.boundaryUserKeys.data)-len(s.End):]
106 1 :
107 1 : // Encode each keyspan.Key in the span.
108 1 : for i := range s.Keys {
109 1 : w.trailers.Set(w.keyCount, uint64(s.Keys[i].Trailer))
110 1 : w.suffixes.Put(s.Keys[i].Suffix)
111 1 : w.values.Put(s.Keys[i].Value)
112 1 : w.keyCount++
113 1 : }
114 : }
115 :
116 : // KeyCount returns the count of keyspan.Keys written to the writer.
117 1 : func (w *KeyspanBlockWriter) KeyCount() int {
118 1 : return w.keyCount
119 1 : }
120 :
121 : // UnsafeBoundaryKeys returns the smallest and largest keys written to the
122 : // keyspan block so far. The returned internal keys have user keys that point
123 : // directly into the block writer's memory and must not be mutated.
124 1 : func (w *KeyspanBlockWriter) UnsafeBoundaryKeys() (smallest, largest base.InternalKey) {
125 1 : if w.keyCount == 0 {
126 0 : return smallest, largest
127 0 : }
128 1 : smallest.UserKey = w.boundaryUserKeys.UnsafeGet(0)
129 1 : smallest.Trailer = base.InternalKeyTrailer(w.trailers.Get(0))
130 1 : largest.UserKey = w.boundaryUserKeys.UnsafeGet(w.boundaryUserKeys.rows - 1)
131 1 : largest.Trailer = base.MakeTrailer(base.SeqNumMax,
132 1 : base.InternalKeyTrailer(w.trailers.Get(w.keyCount-1)).Kind())
133 1 : return smallest, largest
134 : }
135 :
136 : // UnsafeLastSpan returns the start and end user keys of the last span written
137 : // to the block and the trailer of its largest key. The returned keys point
138 : // directly into the block writer's memory and must not be mutated.
139 : func (w *KeyspanBlockWriter) UnsafeLastSpan() (
140 : start, end []byte,
141 : largestTrailer base.InternalKeyTrailer,
142 1 : ) {
143 1 : if w.keyCount == 0 {
144 0 : return nil, nil, 0
145 0 : }
146 1 : return w.boundaryUserKeys.UnsafeGet(w.boundaryUserKeys.rows - 2),
147 1 : w.boundaryUserKeys.UnsafeGet(w.boundaryUserKeys.rows - 1),
148 1 : base.InternalKeyTrailer(w.trailers.Get(w.keyCount - 1))
149 : }
150 :
151 : // Size returns the size of the pending block.
152 1 : func (w *KeyspanBlockWriter) Size() int {
153 1 : off := blockHeaderSize(keyspanColumnCount, keyspanHeaderSize)
154 1 : // Span boundary columns (with userKeyCount elements).
155 1 : off = w.boundaryUserKeys.Size(w.boundaryUserKeys.rows, off)
156 1 : off = w.boundaryKeyIndexes.Size(w.boundaryUserKeys.rows, off)
157 1 :
158 1 : // keyspan.Key columns (with keyCount elements).
159 1 : off = w.trailers.Size(w.keyCount, off)
160 1 : off = w.suffixes.Size(w.keyCount, off)
161 1 : off = w.values.Size(w.keyCount, off)
162 1 : off++ // trailing padding
163 1 : return int(off)
164 1 : }
165 :
166 : // Finish finalizes the pending block and returns the encoded block.
167 1 : func (w *KeyspanBlockWriter) Finish() []byte {
168 1 : w.enc.init(w.Size(), Header{
169 1 : Version: Version1,
170 1 : Columns: keyspanColumnCount,
171 1 : Rows: uint32(w.keyCount),
172 1 : }, keyspanHeaderSize)
173 1 :
174 1 : // The keyspan block has a 4-byte custom header used to encode the number of
175 1 : // user keys encoded within the user key and start indices columns. All
176 1 : // other columns have the number of rows indicated by the shared columnar
177 1 : // block header.
178 1 : binary.LittleEndian.PutUint32(w.enc.data()[:keyspanHeaderSize], uint32(w.boundaryUserKeys.rows))
179 1 :
180 1 : // Columns with userKeyCount elements.
181 1 : w.enc.encode(w.boundaryUserKeys.rows, &w.boundaryUserKeys)
182 1 : w.enc.encode(w.boundaryUserKeys.rows, &w.boundaryKeyIndexes)
183 1 : // Columns with keyCount elements.
184 1 : w.enc.encode(w.keyCount, &w.trailers)
185 1 : w.enc.encode(w.keyCount, &w.suffixes)
186 1 : w.enc.encode(w.keyCount, &w.values)
187 1 : return w.enc.finish()
188 1 : }
189 :
190 : // String returns a string representation of the pending block's state.
191 1 : func (w *KeyspanBlockWriter) String() string {
192 1 : var buf bytes.Buffer
193 1 : size := uint32(w.Size())
194 1 : fmt.Fprintf(&buf, "size=%d:\n", size)
195 1 :
196 1 : fmt.Fprint(&buf, "0: user keys: ")
197 1 : w.boundaryUserKeys.WriteDebug(&buf, w.boundaryUserKeys.rows)
198 1 : fmt.Fprintln(&buf)
199 1 : fmt.Fprint(&buf, "1: start indices: ")
200 1 : w.boundaryKeyIndexes.WriteDebug(&buf, w.boundaryUserKeys.rows)
201 1 : fmt.Fprintln(&buf)
202 1 :
203 1 : fmt.Fprint(&buf, "2: trailers: ")
204 1 : w.trailers.WriteDebug(&buf, w.keyCount)
205 1 : fmt.Fprintln(&buf)
206 1 : fmt.Fprint(&buf, "3: suffixes: ")
207 1 : w.suffixes.WriteDebug(&buf, w.keyCount)
208 1 : fmt.Fprintln(&buf)
209 1 : fmt.Fprint(&buf, "4: values: ")
210 1 : w.values.WriteDebug(&buf, w.keyCount)
211 1 : fmt.Fprintln(&buf)
212 1 :
213 1 : return buf.String()
214 1 : }
215 :
216 : // A KeyspanDecoder exposes facilities for decoding a keyspan block. A
217 : // KeyspanDecoder is safe for concurrent use after initialization.
218 : type KeyspanDecoder struct {
219 : blockDecoder BlockDecoder
220 : // Span boundary columns with boundaryKeysCount elements.
221 : boundaryKeysCount uint32
222 : boundaryKeys RawBytes
223 : boundaryKeyIndices UnsafeUints
224 :
225 : // keyspan.Key columns with blockDecoder.header.Rows elements.
226 : trailers UnsafeUints
227 : suffixes RawBytes
228 : values RawBytes
229 : }
230 :
231 : // Init initializes the keyspan decoder with the given block data.
232 1 : func (d *KeyspanDecoder) Init(data []byte) {
233 1 : d.boundaryKeysCount = binary.LittleEndian.Uint32(data[:4])
234 1 : d.blockDecoder.Init(data, keyspanHeaderSize)
235 1 : // The boundary key columns have a different number of rows than the other
236 1 : // columns, so we call DecodeColumn directly, taking care to pass in
237 1 : // rows=r.boundaryKeysCount.
238 1 : d.boundaryKeys = DecodeColumn(&d.blockDecoder, keyspanColBoundaryUserKeys,
239 1 : int(d.boundaryKeysCount), DataTypeBytes, DecodeRawBytes)
240 1 : d.boundaryKeyIndices = DecodeColumn(&d.blockDecoder, keyspanColBoundaryKeyIndices,
241 1 : int(d.boundaryKeysCount), DataTypeUint, DecodeUnsafeUints)
242 1 :
243 1 : d.trailers = d.blockDecoder.Uints(keyspanColTrailers)
244 1 : d.suffixes = d.blockDecoder.RawBytes(keyspanColSuffixes)
245 1 : d.values = d.blockDecoder.RawBytes(keyspanColValues)
246 1 : }
247 :
248 : // DebugString prints a human-readable explanation of the keyspan block's binary
249 : // representation.
250 1 : func (d *KeyspanDecoder) DebugString() string {
251 1 : f := binfmt.New(d.blockDecoder.data).LineWidth(20)
252 1 : tp := treeprinter.New()
253 1 : d.Describe(f, tp.Child("keyspan-decoder"))
254 1 : return tp.String()
255 1 : }
256 :
257 : // Describe describes the binary format of the keyspan block, assuming
258 : // f.Offset() is positioned at the beginning of the same keyspan block described
259 : // by r.
260 1 : func (d *KeyspanDecoder) Describe(f *binfmt.Formatter, tp treeprinter.Node) {
261 1 : // Set the relative offset. When loaded into memory, the beginning of blocks
262 1 : // are aligned. Padding that ensures alignment is done relative to the
263 1 : // current offset. Setting the relative offset ensures that if we're
264 1 : // describing this block within a larger structure (eg, f.Offset()>0), we
265 1 : // compute padding appropriately assuming the current byte f.Offset() is
266 1 : // aligned.
267 1 : f.SetAnchorOffset()
268 1 :
269 1 : n := tp.Child("keyspan block header")
270 1 : f.HexBytesln(4, "user key count: %d", d.boundaryKeysCount)
271 1 : f.ToTreePrinter(n)
272 1 : d.blockDecoder.headerToBinFormatter(f, n)
273 1 :
274 1 : for i := 0; i < keyspanColumnCount; i++ {
275 1 : // Not all columns in a keyspan block have the same number of rows; the
276 1 : // boundary columns columns are different (and their lengths are held in
277 1 : // the keyspan block header that precedes the ordinary columnar block
278 1 : // header).
279 1 : rows := int(d.blockDecoder.header.Rows)
280 1 : if i == keyspanColBoundaryUserKeys || i == keyspanColBoundaryKeyIndices {
281 1 : rows = int(d.boundaryKeysCount)
282 1 : }
283 1 : d.blockDecoder.columnToBinFormatter(f, n, i, rows)
284 : }
285 1 : f.HexBytesln(1, "block padding byte")
286 1 : f.ToTreePrinter(n)
287 : }
288 :
289 : // searchBoundaryKeys returns the index of the first boundary key greater than
290 : // or equal to key and whether or not the key was found exactly.
291 : func (d *KeyspanDecoder) searchBoundaryKeysWithSyntheticPrefix(
292 : cmp base.Compare, key []byte, syntheticPrefix block.SyntheticPrefix,
293 1 : ) (index int, equal bool) {
294 1 : if syntheticPrefix.IsSet() {
295 1 : // The seek key must have the synthetic prefix, otherwise it falls entirely
296 1 : // before or after the block's boundary keys.
297 1 : var keyPrefix []byte
298 1 : keyPrefix, key = splitKey(key, len(syntheticPrefix))
299 1 : if cmp := bytes.Compare(keyPrefix, syntheticPrefix); cmp != 0 {
300 1 : if cmp < 0 {
301 1 : return 0, false
302 1 : }
303 1 : return int(d.boundaryKeysCount), false
304 : }
305 : }
306 :
307 1 : i, j := 0, int(d.boundaryKeysCount)
308 1 : for i < j {
309 1 : h := int(uint(i+j) >> 1) // avoid overflow when computing h
310 1 : // i ≤ h < j
311 1 : switch cmp(key, d.boundaryKeys.At(h)) {
312 1 : case +1:
313 1 : i = h + 1
314 1 : case 0:
315 1 : return h, true
316 1 : default:
317 1 : // -1
318 1 : j = h
319 : }
320 : }
321 1 : return i, false
322 : }
323 :
324 : // NewKeyspanIter constructs a new iterator over a keyspan columnar block.
325 : func NewKeyspanIter(
326 : cmp base.Compare, h block.BufferHandle, transforms block.FragmentIterTransforms,
327 1 : ) *KeyspanIter {
328 1 : i := keyspanIterPool.Get().(*KeyspanIter)
329 1 : i.closeCheck = invariants.CloseChecker{}
330 1 : i.handle = h
331 1 : d := (*KeyspanDecoder)(unsafe.Pointer(h.BlockMetadata()))
332 1 : i.init(cmp, d, transforms)
333 1 : return i
334 1 : }
335 :
336 : var keyspanIterPool = sync.Pool{
337 1 : New: func() interface{} {
338 1 : i := &KeyspanIter{}
339 1 : invariants.SetFinalizer(i, func(obj interface{}) {
340 1 : if i := obj.(*KeyspanIter); i.handle.Valid() {
341 0 : fmt.Fprintf(os.Stderr, "KeyspanIter.handle is not nil: %#v\n", i.handle)
342 0 : os.Exit(1)
343 0 : }
344 : })
345 1 : return i
346 : },
347 : }
348 :
349 : // A KeyspanIter is an iterator over a columnar keyspan block. It implements the
350 : // keyspan.FragmentIterator interface.
351 : type KeyspanIter struct {
352 : keyspanIter
353 : handle block.BufferHandle
354 :
355 : closeCheck invariants.CloseChecker
356 : }
357 :
358 : // Close closes the iterator.
359 1 : func (i *KeyspanIter) Close() {
360 1 : i.handle.Release()
361 1 : i.handle = block.BufferHandle{}
362 1 :
363 1 : if invariants.Sometimes(25) {
364 1 : // In invariants mode, sometimes don't add the object to the pool so
365 1 : // that we can check for double closes that take longer than the object
366 1 : // stays in the pool.
367 1 : return
368 1 : }
369 :
370 1 : i.keyspanIter.Close()
371 1 : i.closeCheck.Close()
372 1 : keyspanIterPool.Put(i)
373 : }
374 :
375 : // A keyspanIter is an iterator over a keyspan block. It implements the
376 : // keyspan.FragmentIterator interface.
377 : type keyspanIter struct {
378 : r *KeyspanDecoder
379 : cmp base.Compare
380 : transforms block.FragmentIterTransforms
381 : noTransforms bool
382 : span keyspan.Span
383 : // When positioned, the current span's start key is the user key at
384 : // i.r.userKeys.At(i.startBoundIndex)
385 : // and the current span's end key is the user key at
386 : // i.r.userKeys.At(i.startBoundIndex+1)
387 : startBoundIndex int
388 : keyBuf [2]keyspan.Key
389 : // startKeyBuf and endKeyBuf are used when transforms.SyntheticPrefix is
390 : // set.
391 : startKeyBuf []byte
392 : endKeyBuf []byte
393 : }
394 :
395 : // Assert that KeyspanIter implements the FragmentIterator interface.
396 : var _ keyspan.FragmentIterator = (*keyspanIter)(nil)
397 :
398 : // init initializes the iterator with the given comparison function and keyspan
399 : // decoder.
400 : func (i *keyspanIter) init(
401 : cmp base.Compare, r *KeyspanDecoder, transforms block.FragmentIterTransforms,
402 1 : ) {
403 1 : i.r = r
404 1 : i.cmp = cmp
405 1 : i.transforms = transforms
406 1 : i.noTransforms = transforms.NoTransforms()
407 1 : i.span.Start, i.span.End = nil, nil
408 1 : i.startBoundIndex = -1
409 1 : if i.span.Keys == nil {
410 1 : i.span.Keys = i.keyBuf[:0]
411 1 : }
412 1 : i.startKeyBuf = i.startKeyBuf[:0]
413 1 : i.endKeyBuf = i.endKeyBuf[:0]
414 1 : if transforms.HasSyntheticPrefix() {
415 1 : i.startKeyBuf = append(i.startKeyBuf, transforms.SyntheticPrefix()...)
416 1 : i.endKeyBuf = append(i.endKeyBuf, transforms.SyntheticPrefix()...)
417 1 : }
418 : }
419 :
420 : // SeekGE moves the iterator to the first span covering a key greater than
421 : // or equal to the given key. This is equivalent to seeking to the first
422 : // span with an end key greater than the given key.
423 1 : func (i *keyspanIter) SeekGE(key []byte) (*keyspan.Span, error) {
424 1 : // Seek among the boundary keys.
425 1 : j, eq := i.r.searchBoundaryKeysWithSyntheticPrefix(i.cmp, key, i.transforms.SyntheticPrefix())
426 1 : // If the found boundary key does not exactly equal the given key, it's
427 1 : // strictly greater than key. We need to back up one to consider the span
428 1 : // that ends at the this boundary key.
429 1 : if !eq {
430 1 : j = max(j-1, 0)
431 1 : }
432 1 : return i.gatherKeysForward(j), nil
433 : }
434 :
435 : // SeekLT moves the iterator to the last span covering a key less than the
436 : // given key. This is equivalent to seeking to the last span with a start
437 : // key less than the given key.
438 1 : func (i *keyspanIter) SeekLT(key []byte) (*keyspan.Span, error) {
439 1 : j, _ := i.r.searchBoundaryKeysWithSyntheticPrefix(i.cmp, key, i.transforms.SyntheticPrefix())
440 1 : // searchBoundaryKeys seeks to the first boundary key greater than or equal
441 1 : // to key. The span beginning at the boundary key j necessarily does NOT
442 1 : // cover any key less < key (it only contains keys ≥ key). Back up one to
443 1 : // the first span that begins before [key], or to -1 if there is no such
444 1 : // span.
445 1 : j--
446 1 :
447 1 : // If all boundaries are less than [key], or only the last boundary is
448 1 : // greater than the key, then we want the last span so we clamp the index to
449 1 : // the second to last boundary.
450 1 : return i.gatherKeysBackward(min(j, int(i.r.boundaryKeysCount)-2)), nil
451 1 : }
452 :
453 : // First moves the iterator to the first span.
454 1 : func (i *keyspanIter) First() (*keyspan.Span, error) {
455 1 : return i.gatherKeysForward(0), nil
456 1 : }
457 :
458 : // Last moves the iterator to the last span.
459 1 : func (i *keyspanIter) Last() (*keyspan.Span, error) {
460 1 : return i.gatherKeysBackward(int(i.r.boundaryKeysCount) - 2), nil
461 1 : }
462 :
463 : // Next moves the iterator to the next span.
464 1 : func (i *keyspanIter) Next() (*keyspan.Span, error) {
465 1 : return i.gatherKeysForward(i.startBoundIndex + 1), nil
466 1 : }
467 :
468 : // Prev moves the iterator to the previous span.
469 1 : func (i *keyspanIter) Prev() (*keyspan.Span, error) {
470 1 : return i.gatherKeysBackward(max(i.startBoundIndex-1, -1)), nil
471 1 : }
472 :
473 : // gatherKeysForward returns the first non-empty Span in the forward direction,
474 : // starting with the span formed by using the boundary key at index
475 : // [startBoundIndex] as the span's start boundary.
476 1 : func (i *keyspanIter) gatherKeysForward(startBoundIndex int) *keyspan.Span {
477 1 : if invariants.Enabled && startBoundIndex < 0 {
478 0 : panic(errors.AssertionFailedf("out of bounds: i.startBoundIndex=%d", startBoundIndex))
479 : }
480 1 : i.startBoundIndex = startBoundIndex
481 1 : if i.startBoundIndex >= int(i.r.boundaryKeysCount)-1 {
482 1 : return nil
483 1 : }
484 1 : if !i.isNonemptySpan(i.startBoundIndex) {
485 1 : if i.startBoundIndex == int(i.r.boundaryKeysCount)-2 {
486 0 : // Corruption error
487 0 : panic(base.CorruptionErrorf("keyspan block has empty span at end"))
488 : }
489 1 : i.startBoundIndex++
490 1 : if !i.isNonemptySpan(i.startBoundIndex) {
491 0 : panic(base.CorruptionErrorf("keyspan block has consecutive empty spans"))
492 : }
493 : }
494 1 : return i.materializeSpan()
495 : }
496 :
497 : // gatherKeysBackward returns the first non-empty Span in the backward direction,
498 : // starting with the span formed by using the boundary key at index
499 : // [startBoundIndex] as the span's start boundary.
500 1 : func (i *keyspanIter) gatherKeysBackward(startBoundIndex int) *keyspan.Span {
501 1 : i.startBoundIndex = startBoundIndex
502 1 : if i.startBoundIndex < 0 {
503 1 : return nil
504 1 : }
505 1 : if invariants.Enabled && i.startBoundIndex >= int(i.r.boundaryKeysCount)-1 {
506 0 : panic(errors.AssertionFailedf("out of bounds: i.startBoundIndex=%d, i.r.boundaryKeysCount=%d",
507 0 : i.startBoundIndex, i.r.boundaryKeysCount))
508 : }
509 1 : if !i.isNonemptySpan(i.startBoundIndex) {
510 1 : if i.startBoundIndex == 0 {
511 0 : // Corruption error
512 0 : panic(base.CorruptionErrorf("keyspan block has empty span at beginning"))
513 : }
514 1 : i.startBoundIndex--
515 1 : if !i.isNonemptySpan(i.startBoundIndex) {
516 0 : panic(base.CorruptionErrorf("keyspan block has consecutive empty spans"))
517 : }
518 : }
519 1 : return i.materializeSpan()
520 : }
521 :
522 : // isNonemptySpan returns true if the span starting at i.startBoundIndex
523 : // contains keys.
524 1 : func (i *keyspanIter) isNonemptySpan(startBoundIndex int) bool {
525 1 : return i.r.boundaryKeyIndices.At(startBoundIndex) < i.r.boundaryKeyIndices.At(startBoundIndex+1)
526 1 : }
527 :
528 : // materializeSpan constructs the current span from i.startBoundIndex and
529 : // i.{start,end}KeyIndex.
530 1 : func (i *keyspanIter) materializeSpan() *keyspan.Span {
531 1 : i.span = keyspan.Span{
532 1 : Start: i.r.boundaryKeys.At(i.startBoundIndex),
533 1 : End: i.r.boundaryKeys.At(i.startBoundIndex + 1),
534 1 : Keys: i.span.Keys[:0],
535 1 : }
536 1 : startIndex := i.r.boundaryKeyIndices.At(i.startBoundIndex)
537 1 : endIndex := i.r.boundaryKeyIndices.At(i.startBoundIndex + 1)
538 1 : if cap(i.span.Keys) < int(endIndex-startIndex) {
539 1 : i.span.Keys = make([]keyspan.Key, 0, int(endIndex-startIndex))
540 1 : }
541 1 : for j := startIndex; j < endIndex; j++ {
542 1 : i.span.Keys = append(i.span.Keys, keyspan.Key{
543 1 : Trailer: base.InternalKeyTrailer(i.r.trailers.At(int(j))),
544 1 : Suffix: i.r.suffixes.At(int(j)),
545 1 : Value: i.r.values.At(int(j)),
546 1 : })
547 1 : }
548 1 : if i.noTransforms {
549 1 : return &i.span
550 1 : }
551 1 : if i.transforms.SyntheticSeqNum != block.NoSyntheticSeqNum {
552 1 : for j := range i.span.Keys {
553 1 : i.span.Keys[j].Trailer = base.MakeTrailer(
554 1 : base.SeqNum(i.transforms.SyntheticSeqNum), i.span.Keys[j].Trailer.Kind())
555 1 : }
556 : }
557 1 : if i.transforms.HasSyntheticSuffix() {
558 1 : for j := range i.span.Keys {
559 1 : k := &i.span.Keys[j]
560 1 : switch k.Kind() {
561 1 : case base.InternalKeyKindRangeKeySet:
562 1 : if len(k.Suffix) > 0 {
563 1 : // TODO(jackson): Assert synthetic suffix is >= k.Suffix.
564 1 : k.Suffix = i.transforms.SyntheticSuffix()
565 1 : }
566 0 : case base.InternalKeyKindRangeKeyDelete:
567 : // Nothing to do.
568 0 : default:
569 0 : panic(base.AssertionFailedf("synthetic suffix not supported with key kind %s", k.Kind()))
570 : }
571 : }
572 : }
573 1 : if i.transforms.HasSyntheticPrefix() || invariants.Sometimes(10) {
574 1 : syntheticPrefix := i.transforms.SyntheticPrefix()
575 1 : i.startKeyBuf = i.startKeyBuf[:len(syntheticPrefix)]
576 1 : i.endKeyBuf = i.endKeyBuf[:len(syntheticPrefix)]
577 1 : if invariants.Enabled {
578 1 : if !bytes.Equal(i.startKeyBuf, syntheticPrefix) {
579 0 : panic(errors.AssertionFailedf("keyspanIter: synthetic prefix mismatch %q, %q",
580 0 : i.startKeyBuf, syntheticPrefix))
581 : }
582 1 : if !bytes.Equal(i.endKeyBuf, syntheticPrefix) {
583 0 : panic(errors.AssertionFailedf("keyspanIter: synthetic prefix mismatch %q, %q",
584 0 : i.endKeyBuf, syntheticPrefix))
585 : }
586 : }
587 1 : i.startKeyBuf = append(i.startKeyBuf, i.span.Start...)
588 1 : i.endKeyBuf = append(i.endKeyBuf, i.span.End...)
589 1 : i.span.Start = i.startKeyBuf
590 1 : i.span.End = i.endKeyBuf
591 : }
592 :
593 1 : return &i.span
594 : }
595 :
596 : // Close closes the iterator.
597 1 : func (i *keyspanIter) Close() {
598 1 : *i = keyspanIter{}
599 1 : }
600 :
601 : // SetContext implements keyspan.FragmentIterator.
602 0 : func (i *keyspanIter) SetContext(context.Context) {}
603 :
604 : // WrapChildren implements keyspan.FragmentIterator.
605 0 : func (i *keyspanIter) WrapChildren(keyspan.WrapFn) {}
606 :
607 : // DebugTree is part of the FragmentIterator interface.
608 0 : func (i *keyspanIter) DebugTree(tp treeprinter.Node) {
609 0 : tp.Childf("%T(%p)", i, i)
610 0 : }
|
