Line data Source code
1 : // Copyright 2020 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 manifest
6 :
7 : import (
8 : "bytes"
9 : stdcmp "cmp"
10 : "fmt"
11 : "strings"
12 : "sync/atomic"
13 : "unsafe"
14 :
15 : "github.com/cockroachdb/errors"
16 : "github.com/cockroachdb/pebble/internal/invariants"
17 : )
18 :
19 : // The Annotator type defined below is used by other packages to lazily
20 : // compute a value over a B-Tree. Each node of the B-Tree stores one
21 : // `annotation` per annotator, containing the result of the computation over
22 : // the node's subtree.
23 : //
24 : // An annotation is marked as valid if it's current with the current subtree
25 : // state. Annotations are marked as invalid whenever a node will be mutated
26 : // (in mut). Annotators may also return `false` from `Accumulate` to signal
27 : // that a computation for a file is not stable and may change in the future.
28 : // Annotations that include these unstable values are also marked as invalid
29 : // on the node, ensuring that future queries for the annotation will recompute
30 : // the value.
31 :
32 : // An Annotator defines a computation over a level's FileMetadata. If the
33 : // computation is stable and uses inputs that are fixed for the lifetime of
34 : // a FileMetadata, the LevelMetadata's internal data structures are annotated
35 : // with the intermediary computations. This allows the computation to be
36 : // computed incrementally as edits are applied to a level.
37 : type Annotator interface {
38 : // Zero returns the zero value of an annotation. This value is returned
39 : // when a LevelMetadata is empty. The dst argument, if non-nil, is an
40 : // obsolete value previously returned by this Annotator and may be
41 : // overwritten and reused to avoid a memory allocation.
42 : Zero(dst interface{}) (v interface{})
43 :
44 : // Accumulate computes the annotation for a single file in a level's
45 : // metadata. It merges the file's value into dst and returns a bool flag
46 : // indicating whether or not the value is stable and okay to cache as an
47 : // annotation. If the file's value may change over the life of the file,
48 : // the annotator must return false.
49 : //
50 : // Implementations may modify dst and return it to avoid an allocation.
51 : Accumulate(m *FileMetadata, dst interface{}) (v interface{}, cacheOK bool)
52 :
53 : // Merge combines two values src and dst, returning the result.
54 : // Implementations may modify dst and return it to avoid an allocation.
55 : Merge(src interface{}, dst interface{}) interface{}
56 : }
57 :
58 : type btreeCmp func(*FileMetadata, *FileMetadata) int
59 :
60 2 : func btreeCmpSeqNum(a, b *FileMetadata) int {
61 2 : return a.cmpSeqNum(b)
62 2 : }
63 :
64 2 : func btreeCmpSmallestKey(cmp Compare) btreeCmp {
65 2 : return func(a, b *FileMetadata) int {
66 2 : return a.cmpSmallestKey(b, cmp)
67 2 : }
68 : }
69 :
70 : // btreeCmpSpecificOrder is used in tests to construct a B-Tree with a
71 : // specific ordering of FileMetadata within the tree. It's typically used to
72 : // test consistency checking code that needs to construct a malformed B-Tree.
73 1 : func btreeCmpSpecificOrder(files []*FileMetadata) btreeCmp {
74 1 : m := map[*FileMetadata]int{}
75 1 : for i, f := range files {
76 1 : m[f] = i
77 1 : }
78 1 : return func(a, b *FileMetadata) int {
79 1 : ai, aok := m[a]
80 1 : bi, bok := m[b]
81 1 : if !aok || !bok {
82 0 : panic("btreeCmpSliceOrder called with unknown files")
83 : }
84 1 : return stdcmp.Compare(ai, bi)
85 : }
86 : }
87 :
88 : const (
89 : degree = 16
90 : maxItems = 2*degree - 1
91 : minItems = degree - 1
92 : )
93 :
94 : type annotation struct {
95 : annotator Annotator
96 : // v is an annotation value, the output of either
97 : // annotator.Value or annotator.Merge.
98 : v interface{}
99 : // valid indicates whether future reads of the annotation may use v as-is.
100 : // If false, v will be zeroed and recalculated.
101 : valid bool
102 : }
103 :
104 : type leafNode struct {
105 : ref atomic.Int32
106 : count int16
107 : leaf bool
108 : // subtreeCount holds the count of files in the entire subtree formed by
109 : // this node. For leaf nodes, subtreeCount is always equal to count. For
110 : // non-leaf nodes, it's the sum of count plus all the children's
111 : // subtreeCounts.
112 : //
113 : // NB: We could move this field to the end of the node struct, since leaf =>
114 : // count=subtreeCount, however the unsafe casting [leafToNode] performs make
115 : // it risky and cumbersome.
116 : subtreeCount int
117 : items [maxItems]*FileMetadata
118 : // annot contains one annotation per annotator, merged over the entire
119 : // node's files (and all descendants for non-leaf nodes).
120 : annot []annotation
121 : }
122 :
123 : type node struct {
124 : leafNode
125 : children [maxItems + 1]*node
126 : }
127 :
128 : //go:nocheckptr casts a ptr to a smaller struct to a ptr to a larger struct.
129 2 : func leafToNode(ln *leafNode) *node {
130 2 : return (*node)(unsafe.Pointer(ln))
131 2 : }
132 :
133 2 : func newLeafNode() *node {
134 2 : n := leafToNode(new(leafNode))
135 2 : n.leaf = true
136 2 : n.ref.Store(1)
137 2 : return n
138 2 : }
139 :
140 2 : func newNode() *node {
141 2 : n := new(node)
142 2 : n.ref.Store(1)
143 2 : return n
144 2 : }
145 :
146 : // mut creates and returns a mutable node reference. If the node is not shared
147 : // with any other trees then it can be modified in place. Otherwise, it must be
148 : // cloned to ensure unique ownership. In this way, we enforce a copy-on-write
149 : // policy which transparently incorporates the idea of local mutations, like
150 : // Clojure's transients or Haskell's ST monad, where nodes are only copied
151 : // during the first time that they are modified between Clone operations.
152 : //
153 : // When a node is cloned, the provided pointer will be redirected to the new
154 : // mutable node.
155 2 : func mut(n **node) *node {
156 2 : if (*n).ref.Load() == 1 {
157 2 : // Exclusive ownership. Can mutate in place.
158 2 :
159 2 : // Whenever a node will be mutated, reset its annotations to be marked
160 2 : // as uncached. This ensures any future calls to (*node).annotation
161 2 : // will recompute annotations on the modified subtree.
162 2 : for i := range (*n).annot {
163 1 : (*n).annot[i].valid = false
164 1 : }
165 2 : return *n
166 : }
167 : // If we do not have unique ownership over the node then we
168 : // clone it to gain unique ownership. After doing so, we can
169 : // release our reference to the old node. We pass recursive
170 : // as true because even though we just observed the node's
171 : // reference count to be greater than 1, we might be racing
172 : // with another call to decRef on this node.
173 2 : c := (*n).clone()
174 2 : (*n).decRef(true /* contentsToo */, nil)
175 2 : *n = c
176 2 : // NB: We don't need to clear annotations, because (*node).clone does not
177 2 : // copy them.
178 2 : return *n
179 : }
180 :
181 : // incRef acquires a reference to the node.
182 2 : func (n *node) incRef() {
183 2 : n.ref.Add(1)
184 2 : }
185 :
186 : // decRef releases a reference to the node. If requested, the method will unref
187 : // its items and recurse into child nodes and decrease their refcounts as well.
188 : // Some internal codepaths that manually copy the node's items or children to
189 : // new nodes pass contentsToo=false to preserve existing reference counts during
190 : // operations that should yield a net-zero change to descendant refcounts.
191 : // When a node is released, its contained files are dereferenced.
192 2 : func (n *node) decRef(contentsToo bool, obsolete *[]*FileBacking) {
193 2 : if n.ref.Add(-1) > 0 {
194 2 : // Other references remain. Can't free.
195 2 : return
196 2 : }
197 :
198 : // Dereference the node's metadata and release child references if
199 : // requested. Some internal callers may not want to propagate the deref
200 : // because they're manually copying the filemetadata and children to other
201 : // nodes, and they want to preserve the existing reference count.
202 2 : if contentsToo {
203 2 : for _, f := range n.items[:n.count] {
204 2 : if f.FileBacking.Unref() == 0 {
205 2 : // There are two sources of node dereferences: tree mutations
206 2 : // and Version dereferences. Files should only be made obsolete
207 2 : // during Version dereferences, during which `obsolete` will be
208 2 : // non-nil.
209 2 : if obsolete == nil {
210 0 : panic(fmt.Sprintf("file metadata %s dereferenced to zero during tree mutation", f.FileNum))
211 : }
212 : // Reference counting is performed on the FileBacking. In the case
213 : // of a virtual sstable, this reference counting is performed on
214 : // a FileBacking which is shared by every single virtual sstable
215 : // with the same backing sstable. If the reference count hits 0,
216 : // then we know that the FileBacking won't be required by any
217 : // sstable in Pebble, and that the backing sstable can be deleted.
218 2 : *obsolete = append(*obsolete, f.FileBacking)
219 : }
220 : }
221 2 : if !n.leaf {
222 2 : for i := int16(0); i <= n.count; i++ {
223 2 : n.children[i].decRef(true /* contentsToo */, obsolete)
224 2 : }
225 : }
226 : }
227 : }
228 :
229 : // clone creates a clone of the receiver with a single reference count.
230 2 : func (n *node) clone() *node {
231 2 : var c *node
232 2 : if n.leaf {
233 2 : c = newLeafNode()
234 2 : } else {
235 2 : c = newNode()
236 2 : }
237 : // NB: copy field-by-field without touching n.ref to avoid
238 : // triggering the race detector and looking like a data race.
239 2 : c.count = n.count
240 2 : c.items = n.items
241 2 : c.subtreeCount = n.subtreeCount
242 2 : // Increase the refcount of each contained item.
243 2 : for _, f := range n.items[:n.count] {
244 2 : f.FileBacking.Ref()
245 2 : }
246 2 : if !c.leaf {
247 2 : // Copy children and increase each refcount.
248 2 : c.children = n.children
249 2 : for i := int16(0); i <= c.count; i++ {
250 2 : c.children[i].incRef()
251 2 : }
252 : }
253 2 : return c
254 : }
255 :
256 : // insertAt inserts the provided file and node at the provided index. This
257 : // function is for use only as a helper function for internal B-Tree code.
258 : // Clients should not invoke it directly.
259 2 : func (n *node) insertAt(index int, item *FileMetadata, nd *node) {
260 2 : if index < int(n.count) {
261 2 : copy(n.items[index+1:n.count+1], n.items[index:n.count])
262 2 : if !n.leaf {
263 2 : copy(n.children[index+2:n.count+2], n.children[index+1:n.count+1])
264 2 : }
265 : }
266 2 : n.items[index] = item
267 2 : if !n.leaf {
268 2 : n.children[index+1] = nd
269 2 : }
270 2 : n.count++
271 : }
272 :
273 : // pushBack inserts the provided file and node at the tail of the node's items.
274 : // This function is for use only as a helper function for internal B-Tree code.
275 : // Clients should not invoke it directly.
276 2 : func (n *node) pushBack(item *FileMetadata, nd *node) {
277 2 : n.items[n.count] = item
278 2 : if !n.leaf {
279 2 : n.children[n.count+1] = nd
280 2 : }
281 2 : n.count++
282 : }
283 :
284 : // pushFront inserts the provided file and node at the head of the
285 : // node's items. This function is for use only as a helper function for internal B-Tree
286 : // code. Clients should not invoke it directly.
287 2 : func (n *node) pushFront(item *FileMetadata, nd *node) {
288 2 : if !n.leaf {
289 2 : copy(n.children[1:n.count+2], n.children[:n.count+1])
290 2 : n.children[0] = nd
291 2 : }
292 2 : copy(n.items[1:n.count+1], n.items[:n.count])
293 2 : n.items[0] = item
294 2 : n.count++
295 : }
296 :
297 : // removeAt removes a value at a given index, pulling all subsequent values
298 : // back. This function is for use only as a helper function for internal B-Tree
299 : // code. Clients should not invoke it directly.
300 2 : func (n *node) removeAt(index int) (*FileMetadata, *node) {
301 2 : var child *node
302 2 : if !n.leaf {
303 2 : child = n.children[index+1]
304 2 : copy(n.children[index+1:n.count], n.children[index+2:n.count+1])
305 2 : n.children[n.count] = nil
306 2 : }
307 2 : n.count--
308 2 : out := n.items[index]
309 2 : copy(n.items[index:n.count], n.items[index+1:n.count+1])
310 2 : n.items[n.count] = nil
311 2 : return out, child
312 : }
313 :
314 : // popBack removes and returns the last element in the list. This function is
315 : // for use only as a helper function for internal B-Tree code. Clients should
316 : // not invoke it directly.
317 2 : func (n *node) popBack() (*FileMetadata, *node) {
318 2 : n.count--
319 2 : out := n.items[n.count]
320 2 : n.items[n.count] = nil
321 2 : if n.leaf {
322 2 : return out, nil
323 2 : }
324 2 : child := n.children[n.count+1]
325 2 : n.children[n.count+1] = nil
326 2 : return out, child
327 : }
328 :
329 : // popFront removes and returns the first element in the list. This function is
330 : // for use only as a helper function for internal B-Tree code. Clients should
331 : // not invoke it directly.
332 2 : func (n *node) popFront() (*FileMetadata, *node) {
333 2 : n.count--
334 2 : var child *node
335 2 : if !n.leaf {
336 2 : child = n.children[0]
337 2 : copy(n.children[:n.count+1], n.children[1:n.count+2])
338 2 : n.children[n.count+1] = nil
339 2 : }
340 2 : out := n.items[0]
341 2 : copy(n.items[:n.count], n.items[1:n.count+1])
342 2 : n.items[n.count] = nil
343 2 : return out, child
344 : }
345 :
346 : // find returns the index where the given item should be inserted into this
347 : // list. 'found' is true if the item already exists in the list at the given
348 : // index.
349 : //
350 : // This function is for use only as a helper function for internal B-Tree code.
351 : // Clients should not invoke it directly.
352 2 : func (n *node) find(cmp btreeCmp, item *FileMetadata) (index int, found bool) {
353 2 : // Logic copied from sort.Search. Inlining this gave
354 2 : // an 11% speedup on BenchmarkBTreeDeleteInsert.
355 2 : i, j := 0, int(n.count)
356 2 : for i < j {
357 2 : h := int(uint(i+j) >> 1) // avoid overflow when computing h
358 2 : // i ≤ h < j
359 2 : v := cmp(item, n.items[h])
360 2 : if v == 0 {
361 2 : return h, true
362 2 : } else if v > 0 {
363 2 : i = h + 1
364 2 : } else {
365 2 : j = h
366 2 : }
367 : }
368 2 : return i, false
369 : }
370 :
371 : // split splits the given node at the given index. The current node shrinks,
372 : // and this function returns the item that existed at that index and a new
373 : // node containing all items/children after it.
374 : //
375 : // split is called when we want to perform a transformation like the one
376 : // depicted in the following diagram.
377 : //
378 : // Before:
379 : // +-----------+
380 : // n *node | x y z |
381 : // +--/-/-\-\--+
382 : //
383 : // After:
384 : // +-----------+
385 : // | y | n's parent
386 : // +----/-\----+
387 : // / \
388 : // v v
389 : // +-----------+ +-----------+
390 : // n *node | x | | z | next *node
391 : // +-----------+ +-----------+
392 : //
393 : // split does not perform the complete transformation; the caller is responsible
394 : // for updating the parent appropriately. split splits `n` into two nodes, `n`
395 : // and `next`, returning `next` and the file that separates them. In the diagram
396 : // above, `n.split` removes y and z from `n`, returning y in the first return
397 : // value and `next` in the second return value. The caller is responsible for
398 : // updating n's parent to now contain `y` as the separator between nodes `n` and
399 : // `next`.
400 : //
401 : // This function is for use only as a helper function for internal B-Tree code.
402 : // Clients should not invoke it directly.
403 2 : func (n *node) split(i int) (*FileMetadata, *node) {
404 2 : out := n.items[i]
405 2 : var next *node
406 2 : if n.leaf {
407 2 : next = newLeafNode()
408 2 : } else {
409 2 : next = newNode()
410 2 : }
411 2 : next.count = n.count - int16(i+1)
412 2 : copy(next.items[:], n.items[i+1:n.count])
413 2 : for j := int16(i); j < n.count; j++ {
414 2 : n.items[j] = nil
415 2 : }
416 2 : if !n.leaf {
417 2 : copy(next.children[:], n.children[i+1:n.count+1])
418 2 : descendantsMoved := 0
419 2 : for j := int16(i + 1); j <= n.count; j++ {
420 2 : descendantsMoved += n.children[j].subtreeCount
421 2 : n.children[j] = nil
422 2 : }
423 2 : n.subtreeCount -= descendantsMoved
424 2 : next.subtreeCount += descendantsMoved
425 : }
426 2 : n.count = int16(i)
427 2 : // NB: We subtract one more than `next.count` from n's subtreeCount because
428 2 : // the item at index `i` was removed from `n.items`. We'll return the item
429 2 : // at index `i`, and the caller is responsible for updating the subtree
430 2 : // count of whichever node adopts it.
431 2 : n.subtreeCount -= int(next.count) + 1
432 2 : next.subtreeCount += int(next.count)
433 2 : return out, next
434 : }
435 :
436 : // Insert inserts a item into the subtree rooted at this node, making sure no
437 : // nodes in the subtree exceed maxItems items.
438 2 : func (n *node) Insert(cmp btreeCmp, item *FileMetadata) error {
439 2 : i, found := n.find(cmp, item)
440 2 : if found {
441 1 : // cmp provides a total ordering of the files within a level.
442 1 : // If we're inserting a metadata that's equal to an existing item
443 1 : // in the tree, we're inserting a file into a level twice.
444 1 : return errors.Errorf("files %s and %s collided on sort keys",
445 1 : errors.Safe(item.FileNum), errors.Safe(n.items[i].FileNum))
446 1 : }
447 2 : if n.leaf {
448 2 : n.insertAt(i, item, nil)
449 2 : n.subtreeCount++
450 2 : return nil
451 2 : }
452 2 : if n.children[i].count >= maxItems {
453 2 : splitLa, splitNode := mut(&n.children[i]).split(maxItems / 2)
454 2 : n.insertAt(i, splitLa, splitNode)
455 2 :
456 2 : switch cmp := cmp(item, n.items[i]); {
457 2 : case cmp < 0:
458 : // no change, we want first split node
459 2 : case cmp > 0:
460 2 : i++ // we want second split node
461 0 : default:
462 0 : // cmp provides a total ordering of the files within a level.
463 0 : // If we're inserting a metadata that's equal to an existing item
464 0 : // in the tree, we're inserting a file into a level twice.
465 0 : return errors.Errorf("files %s and %s collided on sort keys",
466 0 : errors.Safe(item.FileNum), errors.Safe(n.items[i].FileNum))
467 : }
468 : }
469 :
470 2 : err := mut(&n.children[i]).Insert(cmp, item)
471 2 : if err == nil {
472 2 : n.subtreeCount++
473 2 : }
474 2 : return err
475 : }
476 :
477 : // removeMax removes and returns the maximum item from the subtree rooted at
478 : // this node. This function is for use only as a helper function for internal
479 : // B-Tree code. Clients should not invoke it directly.
480 2 : func (n *node) removeMax() *FileMetadata {
481 2 : if n.leaf {
482 2 : n.count--
483 2 : n.subtreeCount--
484 2 : out := n.items[n.count]
485 2 : n.items[n.count] = nil
486 2 : return out
487 2 : }
488 2 : child := mut(&n.children[n.count])
489 2 : if child.count <= minItems {
490 1 : n.rebalanceOrMerge(int(n.count))
491 1 : return n.removeMax()
492 1 : }
493 2 : n.subtreeCount--
494 2 : return child.removeMax()
495 : }
496 :
497 : // Remove removes a item from the subtree rooted at this node. Returns
498 : // the item that was removed or nil if no matching item was found.
499 2 : func (n *node) Remove(cmp btreeCmp, item *FileMetadata) (out *FileMetadata) {
500 2 : i, found := n.find(cmp, item)
501 2 : if n.leaf {
502 2 : if found {
503 2 : out, _ = n.removeAt(i)
504 2 : n.subtreeCount--
505 2 : return out
506 2 : }
507 1 : return nil
508 : }
509 2 : if n.children[i].count <= minItems {
510 2 : // Child not large enough to remove from.
511 2 : n.rebalanceOrMerge(i)
512 2 : return n.Remove(cmp, item)
513 2 : }
514 2 : child := mut(&n.children[i])
515 2 : if found {
516 2 : // Replace the item being removed with the max item in our left child.
517 2 : out = n.items[i]
518 2 : n.items[i] = child.removeMax()
519 2 : n.subtreeCount--
520 2 : return out
521 2 : }
522 : // File is not in this node and child is large enough to remove from.
523 2 : out = child.Remove(cmp, item)
524 2 : if out != nil {
525 2 : n.subtreeCount--
526 2 : }
527 2 : return out
528 : }
529 :
530 : // rebalanceOrMerge grows child 'i' to ensure it has sufficient room to remove a
531 : // item from it while keeping it at or above minItems. This function is for use
532 : // only as a helper function for internal B-Tree code. Clients should not invoke
533 : // it directly.
534 2 : func (n *node) rebalanceOrMerge(i int) {
535 2 : switch {
536 2 : case i > 0 && n.children[i-1].count > minItems:
537 2 : // Rebalance from left sibling.
538 2 : //
539 2 : // +-----------+
540 2 : // | y |
541 2 : // +----/-\----+
542 2 : // / \
543 2 : // v v
544 2 : // +-----------+ +-----------+
545 2 : // | x | | |
546 2 : // +----------\+ +-----------+
547 2 : // \
548 2 : // v
549 2 : // a
550 2 : //
551 2 : // After:
552 2 : //
553 2 : // +-----------+
554 2 : // | x |
555 2 : // +----/-\----+
556 2 : // / \
557 2 : // v v
558 2 : // +-----------+ +-----------+
559 2 : // | | | y |
560 2 : // +-----------+ +/----------+
561 2 : // /
562 2 : // v
563 2 : // a
564 2 : //
565 2 : left := mut(&n.children[i-1])
566 2 : child := mut(&n.children[i])
567 2 : xLa, grandChild := left.popBack()
568 2 : yLa := n.items[i-1]
569 2 : child.pushFront(yLa, grandChild)
570 2 : n.items[i-1] = xLa
571 2 : child.subtreeCount++
572 2 : left.subtreeCount--
573 2 : if grandChild != nil {
574 2 : child.subtreeCount += grandChild.subtreeCount
575 2 : left.subtreeCount -= grandChild.subtreeCount
576 2 : }
577 :
578 2 : case i < int(n.count) && n.children[i+1].count > minItems:
579 2 : // Rebalance from right sibling.
580 2 : //
581 2 : // +-----------+
582 2 : // | y |
583 2 : // +----/-\----+
584 2 : // / \
585 2 : // v v
586 2 : // +-----------+ +-----------+
587 2 : // | | | x |
588 2 : // +-----------+ +/----------+
589 2 : // /
590 2 : // v
591 2 : // a
592 2 : //
593 2 : // After:
594 2 : //
595 2 : // +-----------+
596 2 : // | x |
597 2 : // +----/-\----+
598 2 : // / \
599 2 : // v v
600 2 : // +-----------+ +-----------+
601 2 : // | y | | |
602 2 : // +----------\+ +-----------+
603 2 : // \
604 2 : // v
605 2 : // a
606 2 : //
607 2 : right := mut(&n.children[i+1])
608 2 : child := mut(&n.children[i])
609 2 : xLa, grandChild := right.popFront()
610 2 : yLa := n.items[i]
611 2 : child.pushBack(yLa, grandChild)
612 2 : child.subtreeCount++
613 2 : right.subtreeCount--
614 2 : if grandChild != nil {
615 2 : child.subtreeCount += grandChild.subtreeCount
616 2 : right.subtreeCount -= grandChild.subtreeCount
617 2 : }
618 2 : n.items[i] = xLa
619 :
620 2 : default:
621 2 : // Merge with either the left or right sibling.
622 2 : //
623 2 : // +-----------+
624 2 : // | u y v |
625 2 : // +----/-\----+
626 2 : // / \
627 2 : // v v
628 2 : // +-----------+ +-----------+
629 2 : // | x | | z |
630 2 : // +-----------+ +-----------+
631 2 : //
632 2 : // After:
633 2 : //
634 2 : // +-----------+
635 2 : // | u v |
636 2 : // +-----|-----+
637 2 : // |
638 2 : // v
639 2 : // +-----------+
640 2 : // | x y z |
641 2 : // +-----------+
642 2 : //
643 2 : if i >= int(n.count) {
644 2 : i = int(n.count - 1)
645 2 : }
646 2 : child := mut(&n.children[i])
647 2 : // Make mergeChild mutable, bumping the refcounts on its children if necessary.
648 2 : _ = mut(&n.children[i+1])
649 2 : mergeLa, mergeChild := n.removeAt(i)
650 2 : child.items[child.count] = mergeLa
651 2 : copy(child.items[child.count+1:], mergeChild.items[:mergeChild.count])
652 2 : if !child.leaf {
653 2 : copy(child.children[child.count+1:], mergeChild.children[:mergeChild.count+1])
654 2 : }
655 2 : child.count += mergeChild.count + 1
656 2 : child.subtreeCount += mergeChild.subtreeCount + 1
657 2 :
658 2 : mergeChild.decRef(false /* contentsToo */, nil)
659 : }
660 : }
661 :
662 : // InvalidateAnnotation removes any existing cached annotations for the provided
663 : // annotator from this node's subtree.
664 1 : func (n *node) InvalidateAnnotation(a Annotator) {
665 1 : // Find this annotator's annotation on this node.
666 1 : var annot *annotation
667 1 : for i := range n.annot {
668 0 : if n.annot[i].annotator == a {
669 0 : annot = &n.annot[i]
670 0 : }
671 : }
672 :
673 1 : if annot != nil && annot.valid {
674 0 : annot.valid = false
675 0 : annot.v = a.Zero(annot.v)
676 0 : }
677 1 : if !n.leaf {
678 0 : for i := int16(0); i <= n.count; i++ {
679 0 : n.children[i].InvalidateAnnotation(a)
680 0 : }
681 : }
682 : }
683 :
684 : // Annotation retrieves, computing if not already computed, the provided
685 : // annotator's annotation of this node. The second return value indicates
686 : // whether the future reads of this annotation may use the first return value
687 : // as-is. If false, the annotation is not stable and may change on a subsequent
688 : // computation.
689 2 : func (n *node) Annotation(a Annotator) (interface{}, bool) {
690 2 : // Find this annotator's annotation on this node.
691 2 : var annot *annotation
692 2 : for i := range n.annot {
693 2 : if n.annot[i].annotator == a {
694 2 : annot = &n.annot[i]
695 2 : }
696 : }
697 :
698 : // If it exists and is marked as valid, we can return it without
699 : // recomputing anything.
700 2 : if annot != nil && annot.valid {
701 2 : return annot.v, true
702 2 : }
703 :
704 2 : if annot == nil {
705 2 : // This is n's first time being annotated by a.
706 2 : // Create a new zeroed annotation.
707 2 : n.annot = append(n.annot, annotation{
708 2 : annotator: a,
709 2 : v: a.Zero(nil),
710 2 : })
711 2 : annot = &n.annot[len(n.annot)-1]
712 2 : } else {
713 2 : // There's an existing annotation that must be recomputed.
714 2 : // Zero its value.
715 2 : annot.v = a.Zero(annot.v)
716 2 : }
717 :
718 2 : annot.valid = true
719 2 : for i := int16(0); i <= n.count; i++ {
720 2 : if !n.leaf {
721 2 : v, ok := n.children[i].Annotation(a)
722 2 : annot.v = a.Merge(v, annot.v)
723 2 : annot.valid = annot.valid && ok
724 2 : }
725 2 : if i < n.count {
726 2 : v, ok := a.Accumulate(n.items[i], annot.v)
727 2 : annot.v = v
728 2 : annot.valid = annot.valid && ok
729 2 : }
730 : }
731 2 : return annot.v, annot.valid
732 : }
733 :
734 2 : func (n *node) verifyInvariants() {
735 2 : recomputedSubtreeCount := int(n.count)
736 2 : if !n.leaf {
737 2 : for i := int16(0); i <= n.count; i++ {
738 2 : n.children[i].verifyInvariants()
739 2 : recomputedSubtreeCount += n.children[i].subtreeCount
740 2 : }
741 : }
742 2 : if recomputedSubtreeCount != n.subtreeCount {
743 0 : panic(fmt.Sprintf("recomputed subtree count (%d) ≠ n.subtreeCount (%d)",
744 0 : recomputedSubtreeCount, n.subtreeCount))
745 : }
746 : }
747 :
748 : // btree is an implementation of a B-Tree.
749 : //
750 : // btree stores FileMetadata in an ordered structure, allowing easy insertion,
751 : // removal, and iteration. The B-Tree stores items in order based on cmp. The
752 : // first level of the LSM uses a cmp function that compares sequence numbers.
753 : // All other levels compare using the FileMetadata.Smallest.
754 : //
755 : // Write operations are not safe for concurrent mutation by multiple
756 : // goroutines, but Read operations are.
757 : type btree struct {
758 : root *node
759 : cmp btreeCmp
760 : }
761 :
762 : // Release dereferences and clears the root node of the btree, removing all
763 : // items from the btree. In doing so, it decrements contained file counts.
764 : // It returns a slice of newly obsolete backing files, if any.
765 2 : func (t *btree) Release() (obsolete []*FileBacking) {
766 2 : if t.root != nil {
767 2 : t.root.decRef(true /* contentsToo */, &obsolete)
768 2 : t.root = nil
769 2 : }
770 2 : return obsolete
771 : }
772 :
773 : // Clone clones the btree, lazily. It does so in constant time.
774 2 : func (t *btree) Clone() btree {
775 2 : c := *t
776 2 : if c.root != nil {
777 2 : // Incrementing the reference count on the root node is sufficient to
778 2 : // ensure that no node in the cloned tree can be mutated by an actor
779 2 : // holding a reference to the original tree and vice versa. This
780 2 : // property is upheld because the root node in the receiver btree and
781 2 : // the returned btree will both necessarily have a reference count of at
782 2 : // least 2 when this method returns. All tree mutations recursively
783 2 : // acquire mutable node references (see mut) as they traverse down the
784 2 : // tree. The act of acquiring a mutable node reference performs a clone
785 2 : // if a node's reference count is greater than one. Cloning a node (see
786 2 : // clone) increases the reference count on each of its children,
787 2 : // ensuring that they have a reference count of at least 2. This, in
788 2 : // turn, ensures that any of the child nodes that are modified will also
789 2 : // be copied-on-write, recursively ensuring the immutability property
790 2 : // over the entire tree.
791 2 : c.root.incRef()
792 2 : }
793 2 : return c
794 : }
795 :
796 : // Delete removes the provided file from the tree.
797 : // It returns true if the file now has a zero reference count.
798 2 : func (t *btree) Delete(item *FileMetadata) (obsolete bool) {
799 2 : if t.root == nil || t.root.count == 0 {
800 0 : return false
801 0 : }
802 2 : if out := mut(&t.root).Remove(t.cmp, item); out != nil {
803 2 : obsolete = out.FileBacking.Unref() == 0
804 2 : }
805 2 : if invariants.Enabled {
806 2 : t.root.verifyInvariants()
807 2 : }
808 2 : if t.root.count == 0 {
809 2 : old := t.root
810 2 : if t.root.leaf {
811 2 : t.root = nil
812 2 : } else {
813 2 : t.root = t.root.children[0]
814 2 : }
815 2 : old.decRef(false /* contentsToo */, nil)
816 : }
817 2 : return obsolete
818 : }
819 :
820 : // Insert adds the given item to the tree. If a item in the tree already
821 : // equals the given one, Insert panics.
822 2 : func (t *btree) Insert(item *FileMetadata) error {
823 2 : if t.root == nil {
824 2 : t.root = newLeafNode()
825 2 : } else if t.root.count >= maxItems {
826 2 : splitLa, splitNode := mut(&t.root).split(maxItems / 2)
827 2 : newRoot := newNode()
828 2 : newRoot.count = 1
829 2 : newRoot.items[0] = splitLa
830 2 : newRoot.children[0] = t.root
831 2 : newRoot.children[1] = splitNode
832 2 : newRoot.subtreeCount = t.root.subtreeCount + splitNode.subtreeCount + 1
833 2 : t.root = newRoot
834 2 : }
835 2 : item.FileBacking.Ref()
836 2 : err := mut(&t.root).Insert(t.cmp, item)
837 2 : if invariants.Enabled {
838 2 : t.root.verifyInvariants()
839 2 : }
840 2 : return err
841 : }
842 :
843 : // Iter returns a new iterator object. It is not safe to continue using an
844 : // iterator after modifications are made to the tree. If modifications are made,
845 : // create a new iterator.
846 2 : func (t *btree) Iter() iterator {
847 2 : return iterator{r: t.root, pos: -1, cmp: t.cmp}
848 2 : }
849 :
850 : // Count returns the number of files contained within the B-Tree.
851 2 : func (t *btree) Count() int {
852 2 : if t.root == nil {
853 2 : return 0
854 2 : }
855 2 : return t.root.subtreeCount
856 : }
857 :
858 : // String returns a string description of the tree. The format is
859 : // similar to the https://en.wikipedia.org/wiki/Newick_format.
860 0 : func (t *btree) String() string {
861 0 : if t.Count() == 0 {
862 0 : return ";"
863 0 : }
864 0 : var b strings.Builder
865 0 : t.root.writeString(&b)
866 0 : return b.String()
867 : }
868 :
869 0 : func (n *node) writeString(b *strings.Builder) {
870 0 : if n.leaf {
871 0 : for i := int16(0); i < n.count; i++ {
872 0 : if i != 0 {
873 0 : b.WriteString(",")
874 0 : }
875 0 : b.WriteString(n.items[i].String())
876 : }
877 0 : return
878 : }
879 0 : for i := int16(0); i <= n.count; i++ {
880 0 : b.WriteString("(")
881 0 : n.children[i].writeString(b)
882 0 : b.WriteString(")")
883 0 : if i < n.count {
884 0 : b.WriteString(n.items[i].String())
885 0 : }
886 : }
887 : }
888 :
889 : // iterStack represents a stack of (node, pos) tuples, which captures
890 : // iteration state as an iterator descends a btree.
891 : type iterStack struct {
892 : // a contains aLen stack frames when an iterator stack is short enough.
893 : // If the iterator stack overflows the capacity of iterStackArr, the stack
894 : // is moved to s and aLen is set to -1.
895 : a iterStackArr
896 : aLen int16 // -1 when using s
897 : s []iterFrame
898 : }
899 :
900 : // Used to avoid allocations for stacks below a certain size.
901 : type iterStackArr [3]iterFrame
902 :
903 : type iterFrame struct {
904 : n *node
905 : pos int16
906 : }
907 :
908 2 : func (is *iterStack) push(f iterFrame) {
909 2 : if is.aLen == -1 {
910 1 : is.s = append(is.s, f)
911 2 : } else if int(is.aLen) == len(is.a) {
912 1 : is.s = make([]iterFrame, int(is.aLen)+1, 2*int(is.aLen))
913 1 : copy(is.s, is.a[:])
914 1 : is.s[int(is.aLen)] = f
915 1 : is.aLen = -1
916 2 : } else {
917 2 : is.a[is.aLen] = f
918 2 : is.aLen++
919 2 : }
920 : }
921 :
922 2 : func (is *iterStack) pop() iterFrame {
923 2 : if is.aLen == -1 {
924 1 : f := is.s[len(is.s)-1]
925 1 : is.s = is.s[:len(is.s)-1]
926 1 : return f
927 1 : }
928 2 : is.aLen--
929 2 : return is.a[is.aLen]
930 : }
931 :
932 2 : func (is *iterStack) len() int {
933 2 : if is.aLen == -1 {
934 1 : return len(is.s)
935 1 : }
936 2 : return int(is.aLen)
937 : }
938 :
939 2 : func (is *iterStack) clone() iterStack {
940 2 : // If the iterator is using the embedded iterStackArr, we only need to
941 2 : // copy the struct itself.
942 2 : if is.s == nil {
943 2 : return *is
944 2 : }
945 0 : clone := *is
946 0 : clone.s = make([]iterFrame, len(is.s))
947 0 : copy(clone.s, is.s)
948 0 : return clone
949 : }
950 :
951 2 : func (is *iterStack) nth(n int) (f iterFrame, ok bool) {
952 2 : if is.aLen == -1 {
953 0 : if n >= len(is.s) {
954 0 : return f, false
955 0 : }
956 0 : return is.s[n], true
957 : }
958 2 : if int16(n) >= is.aLen {
959 2 : return f, false
960 2 : }
961 2 : return is.a[n], true
962 : }
963 :
964 2 : func (is *iterStack) reset() {
965 2 : if is.aLen == -1 {
966 1 : is.s = is.s[:0]
967 2 : } else {
968 2 : is.aLen = 0
969 2 : }
970 : }
971 :
972 : // iterator is responsible for search and traversal within a btree.
973 : type iterator struct {
974 : // the root node of the B-Tree.
975 : r *node
976 : // n and pos make up the current position of the iterator.
977 : // If valid, n.items[pos] is the current value of the iterator.
978 : //
979 : // n may be nil iff i.r is nil.
980 : n *node
981 : pos int16
982 : // cmp dictates the ordering of the FileMetadata.
983 : cmp func(*FileMetadata, *FileMetadata) int
984 : // a stack of n's ancestors within the B-Tree, alongside the position
985 : // taken to arrive at n. If non-empty, the bottommost frame of the stack
986 : // will always contain the B-Tree root.
987 : s iterStack
988 : }
989 :
990 : // countLeft returns the count of files that are to the left of the current
991 : // iterator position.
992 2 : func (i *iterator) countLeft() int {
993 2 : if i.r == nil {
994 0 : return 0
995 0 : }
996 :
997 : // Each iterator has a stack of frames marking the path from the root node
998 : // to the current iterator position. All files (n.items) and all subtrees
999 : // (n.children) with indexes less than [pos] are to the left of the current
1000 : // iterator position.
1001 : //
1002 : // +------------------------+ -
1003 : // | Root pos:5 | |
1004 : // +------------------------+ | stack
1005 : // | Root/5 pos:3 | | frames
1006 : // +------------------------+ | [i.s]
1007 : // | Root/5/3 pos:9 | |
1008 : // +========================+ -
1009 : // | |
1010 : // | i.n: Root/5/3/9 i.pos:2|
1011 : // +------------------------+
1012 : //
1013 2 : var count int
1014 2 : // Walk all the ancestors in the iterator stack [i.s], tallying up all the
1015 2 : // files and subtrees to the left of the stack frame's position.
1016 2 : f, ok := i.s.nth(0)
1017 2 : for fi := 0; ok; fi++ {
1018 2 : // There are [f.pos] files contained within [f.n.items] that sort to the
1019 2 : // left of the subtree the iterator has descended.
1020 2 : count += int(f.pos)
1021 2 : // Any subtrees that fall before the stack frame's position are entirely
1022 2 : // to the left of the iterator's current position.
1023 2 : for j := int16(0); j < f.pos; j++ {
1024 2 : count += f.n.children[j].subtreeCount
1025 2 : }
1026 2 : f, ok = i.s.nth(fi + 1)
1027 : }
1028 :
1029 : // The bottommost stack frame is inlined within the iterator struct. Again,
1030 : // [i.pos] files fall to the left of the current iterator position.
1031 2 : count += int(i.pos)
1032 2 : if !i.n.leaf {
1033 2 : // NB: Unlike above, we use a `<= i.pos` comparison. The iterator is
1034 2 : // positioned at item `i.n.items[i.pos]`, which sorts after everything
1035 2 : // in the subtree at `i.n.children[i.pos]`.
1036 2 : for j := int16(0); j <= i.pos; j++ {
1037 2 : count += i.n.children[j].subtreeCount
1038 2 : }
1039 : }
1040 2 : return count
1041 : }
1042 :
1043 2 : func (i *iterator) clone() iterator {
1044 2 : c := *i
1045 2 : c.s = i.s.clone()
1046 2 : return c
1047 2 : }
1048 :
1049 2 : func (i *iterator) reset() {
1050 2 : i.n = i.r
1051 2 : i.pos = -1
1052 2 : i.s.reset()
1053 2 : }
1054 :
1055 0 : func (i iterator) String() string {
1056 0 : var buf bytes.Buffer
1057 0 : for n := 0; ; n++ {
1058 0 : f, ok := i.s.nth(n)
1059 0 : if !ok {
1060 0 : break
1061 : }
1062 0 : fmt.Fprintf(&buf, "%p: %02d/%02d\n", f.n, f.pos, f.n.count)
1063 : }
1064 0 : if i.r == nil {
1065 0 : fmt.Fprintf(&buf, "<nil>: %02d", i.pos)
1066 0 : } else {
1067 0 : fmt.Fprintf(&buf, "%p: %02d/%02d", i.n, i.pos, i.n.count)
1068 0 : }
1069 0 : return buf.String()
1070 : }
1071 :
1072 2 : func cmpIter(a, b iterator) int {
1073 2 : if a.r != b.r {
1074 0 : panic("compared iterators from different btrees")
1075 : }
1076 :
1077 : // Each iterator has a stack of frames marking the path from the root node
1078 : // to the current iterator position. We walk both paths formed by the
1079 : // iterators' stacks simultaneously, descending from the shared root node,
1080 : // always comparing nodes at the same level in the tree.
1081 : //
1082 : // If the iterators' paths ever diverge and point to different nodes, the
1083 : // iterators are not equal and we use the node positions to evaluate the
1084 : // comparison.
1085 : //
1086 : // If an iterator's stack ends, we stop descending and use its current
1087 : // node and position for the final comparison. One iterator's stack may
1088 : // end before another's if one iterator is positioned deeper in the tree.
1089 : //
1090 : // a b
1091 : // +------------------------+ +--------------------------+ -
1092 : // | Root pos:5 | = | Root pos:5 | |
1093 : // +------------------------+ +--------------------------+ | stack
1094 : // | Root/5 pos:3 | = | Root/5 pos:3 | | frames
1095 : // +------------------------+ +--------------------------+ |
1096 : // | Root/5/3 pos:9 | > | Root/5/3 pos:1 | |
1097 : // +========================+ +==========================+ -
1098 : // | | | |
1099 : // | a.n: Root/5/3/9 a.pos:2| | b.n: Root/5/3/1, b.pos:5 |
1100 : // +------------------------+ +--------------------------+
1101 :
1102 : // Initialize with the iterator's current node and position. These are
1103 : // conceptually the most-recent/current frame of the iterator stack.
1104 2 : an, apos := a.n, a.pos
1105 2 : bn, bpos := b.n, b.pos
1106 2 :
1107 2 : // aok, bok are set while traversing the iterator's path down the B-Tree.
1108 2 : // They're declared in the outer scope because they help distinguish the
1109 2 : // sentinel case when both iterators' first frame points to the last child
1110 2 : // of the root. If an iterator has no other frames in its stack, it's the
1111 2 : // end sentinel state which sorts after everything else.
1112 2 : var aok, bok bool
1113 2 : for i := 0; ; i++ {
1114 2 : var af, bf iterFrame
1115 2 : af, aok = a.s.nth(i)
1116 2 : bf, bok = b.s.nth(i)
1117 2 : if !aok || !bok {
1118 2 : if aok {
1119 2 : // Iterator a, unlike iterator b, still has a frame. Set an,
1120 2 : // apos so we compare using the frame from the stack.
1121 2 : an, apos = af.n, af.pos
1122 2 : }
1123 2 : if bok {
1124 2 : // Iterator b, unlike iterator a, still has a frame. Set bn,
1125 2 : // bpos so we compare using the frame from the stack.
1126 2 : bn, bpos = bf.n, bf.pos
1127 2 : }
1128 2 : break
1129 : }
1130 :
1131 : // aok && bok
1132 2 : if af.n != bf.n {
1133 0 : panic("nonmatching nodes during btree iterator comparison")
1134 : }
1135 2 : if v := stdcmp.Compare(af.pos, bf.pos); v != 0 {
1136 2 : return v
1137 2 : }
1138 : // Otherwise continue up both iterators' stacks (equivalently, down the
1139 : // B-Tree away from the root).
1140 : }
1141 :
1142 2 : if aok && bok {
1143 0 : panic("expected one or more stacks to have been exhausted")
1144 : }
1145 2 : if an != bn {
1146 0 : panic("nonmatching nodes during btree iterator comparison")
1147 : }
1148 2 : if v := stdcmp.Compare(apos, bpos); v != 0 {
1149 2 : return v
1150 2 : }
1151 2 : switch {
1152 2 : case aok:
1153 2 : // a is positioned at a leaf child at this position and b is at an
1154 2 : // end sentinel state.
1155 2 : return -1
1156 2 : case bok:
1157 2 : // b is positioned at a leaf child at this position and a is at an
1158 2 : // end sentinel state.
1159 2 : return +1
1160 2 : default:
1161 2 : return 0
1162 : }
1163 : }
1164 :
1165 2 : func (i *iterator) descend(n *node, pos int16) {
1166 2 : i.s.push(iterFrame{n: n, pos: pos})
1167 2 : i.n = n.children[pos]
1168 2 : i.pos = 0
1169 2 : }
1170 :
1171 : // ascend ascends up to the current node's parent and resets the position
1172 : // to the one previously set for this parent node.
1173 2 : func (i *iterator) ascend() {
1174 2 : f := i.s.pop()
1175 2 : i.n = f.n
1176 2 : i.pos = f.pos
1177 2 : }
1178 :
1179 : // seek repositions the iterator over the first file for which fn returns
1180 : // true, mirroring the semantics of the standard library's sort.Search
1181 : // function. Like sort.Search, seek requires the iterator's B-Tree to be
1182 : // ordered such that fn returns false for some (possibly empty) prefix of the
1183 : // tree's files, and then true for the (possibly empty) remainder.
1184 2 : func (i *iterator) seek(fn func(*FileMetadata) bool) {
1185 2 : i.reset()
1186 2 : if i.r == nil {
1187 0 : return
1188 0 : }
1189 :
1190 2 : for {
1191 2 : // Logic copied from sort.Search.
1192 2 : j, k := 0, int(i.n.count)
1193 2 : for j < k {
1194 2 : h := int(uint(j+k) >> 1) // avoid overflow when computing h
1195 2 :
1196 2 : // j ≤ h < k
1197 2 : if !fn(i.n.items[h]) {
1198 2 : j = h + 1 // preserves f(j-1) == false
1199 2 : } else {
1200 2 : k = h // preserves f(k) == true
1201 2 : }
1202 : }
1203 :
1204 2 : i.pos = int16(j)
1205 2 : if i.n.leaf {
1206 2 : if i.pos == i.n.count {
1207 2 : i.next()
1208 2 : }
1209 2 : return
1210 : }
1211 2 : i.descend(i.n, i.pos)
1212 : }
1213 : }
1214 :
1215 : // first seeks to the first item in the btree.
1216 2 : func (i *iterator) first() {
1217 2 : i.reset()
1218 2 : if i.r == nil {
1219 1 : return
1220 1 : }
1221 2 : for !i.n.leaf {
1222 2 : i.descend(i.n, 0)
1223 2 : }
1224 2 : i.pos = 0
1225 : }
1226 :
1227 : // last seeks to the last item in the btree.
1228 2 : func (i *iterator) last() {
1229 2 : i.reset()
1230 2 : if i.r == nil {
1231 1 : return
1232 1 : }
1233 2 : for !i.n.leaf {
1234 2 : i.descend(i.n, i.n.count)
1235 2 : }
1236 2 : i.pos = i.n.count - 1
1237 : }
1238 :
1239 : // next positions the iterator to the item immediately following
1240 : // its current position.
1241 2 : func (i *iterator) next() {
1242 2 : if i.r == nil {
1243 0 : return
1244 0 : }
1245 :
1246 2 : if i.n.leaf {
1247 2 : if i.pos < i.n.count {
1248 2 : i.pos++
1249 2 : }
1250 2 : if i.pos < i.n.count {
1251 2 : return
1252 2 : }
1253 2 : for i.s.len() > 0 && i.pos >= i.n.count {
1254 2 : i.ascend()
1255 2 : }
1256 2 : return
1257 : }
1258 :
1259 2 : i.descend(i.n, i.pos+1)
1260 2 : for !i.n.leaf {
1261 2 : i.descend(i.n, 0)
1262 2 : }
1263 2 : i.pos = 0
1264 : }
1265 :
1266 : // prev positions the iterator to the item immediately preceding
1267 : // its current position.
1268 2 : func (i *iterator) prev() {
1269 2 : if i.r == nil {
1270 0 : return
1271 0 : }
1272 :
1273 2 : if i.n.leaf {
1274 2 : i.pos--
1275 2 : if i.pos >= 0 {
1276 2 : return
1277 2 : }
1278 2 : for i.s.len() > 0 && i.pos < 0 {
1279 2 : i.ascend()
1280 2 : i.pos--
1281 2 : }
1282 2 : return
1283 : }
1284 :
1285 2 : i.descend(i.n, i.pos)
1286 2 : for !i.n.leaf {
1287 1 : i.descend(i.n, i.n.count)
1288 1 : }
1289 2 : i.pos = i.n.count - 1
1290 : }
1291 :
1292 : // valid returns whether the iterator is positioned at a valid position.
1293 2 : func (i *iterator) valid() bool {
1294 2 : return i.r != nil && i.pos >= 0 && i.pos < i.n.count
1295 2 : }
1296 :
1297 : // cur returns the item at the iterator's current position. It is illegal
1298 : // to call cur if the iterator is not valid.
1299 2 : func (i *iterator) cur() *FileMetadata {
1300 2 : if invariants.Enabled && !i.valid() {
1301 0 : panic("btree iterator.cur invoked on invalid iterator")
1302 : }
1303 2 : return i.n.items[i.pos]
1304 : }
|
