Line data    Source code

       1             : /*
       2             :  * Copyright 2017 Dgraph Labs, Inc. and Contributors
       3             :  * Modifications copyright (C) 2017 Andy Kimball and Contributors
       4             :  *
       5             :  * Licensed under the Apache License, Version 2.0 (the "License");
       6             :  * you may not use this file except in compliance with the License.
       7             :  * You may obtain a copy of the License at
       8             :  *
       9             :  *     http://www.apache.org/licenses/LICENSE-2.0
      10             :  *
      11             :  * Unless required by applicable law or agreed to in writing, software
      12             :  * distributed under the License is distributed on an "AS IS" BASIS,
      13             :  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
      14             :  * See the License for the specific language governing permissions and
      15             :  * limitations under the License.
      16             :  */
      17             : 
      18             : package batchskl
      19             : 
      20             : import "github.com/cockroachdb/pebble/internal/base"
      21             : 
      22             : type splice struct {
      23             :         prev uint32
      24             :         next uint32
      25             : }
      26             : 
      27             : // Iterator is an iterator over the skiplist object. Use Skiplist.NewIter
      28             : // to construct an iterator. The current state of the iterator can be cloned
      29             : // by simply value copying the struct.
      30             : type Iterator struct {
      31             :         list  *Skiplist
      32             :         nd    uint32
      33             :         key   base.InternalKey
      34             :         lower []byte
      35             :         upper []byte
      36             :         // {lower,upper}Node are lazily populated with the offset of an arbitrary
      37             :         // node that is beyond the lower and upper bound respectively. Once
      38             :         // populated, [lower|upper]Node may be used to detect when iteration has
      39             :         // reached a bound without performing a key comparison. This may be
      40             :         // beneficial when performing repeated SeekGEs with TrySeekUsingNext and an
      41             :         // upper bound set. Once the upper bound has been met, no additional key
      42             :         // comparisons are necessary.
      43             :         //
      44             :         // Note that {lower,upper}Node may be zero if the iterator has not yet
      45             :         // encountered a node beyond the respective bound. No valid node may ever
      46             :         // have a zero offset because the skiplist head sentinel node is always
      47             :         // allocated first, ensuring all other nodes have non-zero offsets.
      48             :         lowerNode uint32
      49             :         upperNode uint32
      50             : }
      51             : 
      52             : // Close resets the iterator.
      53           1 : func (it *Iterator) Close() error {
      54           1 :         *it = Iterator{}
      55           1 :         return nil
      56           1 : }
      57             : 
      58             : // SeekGE moves the iterator to the first entry whose key is greater than or
      59             : // equal to the given key. Returns true if the iterator is pointing at a valid
      60             : // entry and false otherwise. Note that SeekGE only checks the upper bound. It
      61             : // is up to the caller to ensure that key is greater than or equal to the lower
      62             : // bound.
      63           1 : func (it *Iterator) SeekGE(key []byte, flags base.SeekGEFlags) *base.InternalKey {
      64           1 :         if flags.TrySeekUsingNext() {
      65           1 :                 if it.nd == it.list.tail || it.nd == it.upperNode {
      66           1 :                         // Iterator is done.
      67           1 :                         return nil
      68           1 :                 }
      69           1 :                 less := it.list.cmp(it.key.UserKey, key) < 0
      70           1 :                 // Arbitrary constant. By measuring the seek cost as a function of the
      71           1 :                 // number of elements in the skip list, and fitting to a model, we
      72           1 :                 // could adjust the number of nexts based on the current size of the
      73           1 :                 // skip list.
      74           1 :                 const numNexts = 5
      75           1 :                 for i := 0; less && i < numNexts; i++ {
      76           1 :                         k := it.Next()
      77           1 :                         if k == nil {
      78           1 :                                 // Iterator is done.
      79           1 :                                 return nil
      80           1 :                         }
      81           1 :                         less = it.list.cmp(k.UserKey, key) < 0
      82             :                 }
      83           1 :                 if !less {
      84           1 :                         return &it.key
      85           1 :                 }
      86             :         }
      87             : 
      88           1 :         _, it.nd = it.seekForBaseSplice(key, it.list.abbreviatedKey(key))
      89           1 :         if it.nd == it.list.tail || it.nd == it.upperNode {
      90           1 :                 return nil
      91           1 :         }
      92           1 :         nodeKey := it.list.getKey(it.nd)
      93           1 :         if it.upper != nil && it.list.cmp(it.upper, nodeKey.UserKey) <= 0 {
      94           1 :                 it.upperNode = it.nd
      95           1 :                 return nil
      96           1 :         }
      97           1 :         it.key = nodeKey
      98           1 :         return &it.key
      99             : }
     100             : 
     101             : // SeekLT moves the iterator to the last entry whose key is less the given
     102             : // key. Returns true if the iterator is pointing at a valid entry and false
     103             : // otherwise. Note that SeekLT only checks the lower bound. It is up to the
     104             : // caller to ensure that key is less than the upper bound.
     105           1 : func (it *Iterator) SeekLT(key []byte) *base.InternalKey {
     106           1 :         it.nd, _ = it.seekForBaseSplice(key, it.list.abbreviatedKey(key))
     107           1 :         if it.nd == it.list.head || it.nd == it.lowerNode {
     108           1 :                 return nil
     109           1 :         }
     110           1 :         nodeKey := it.list.getKey(it.nd)
     111           1 :         if it.lower != nil && it.list.cmp(it.lower, nodeKey.UserKey) > 0 {
     112           1 :                 it.lowerNode = it.nd
     113           1 :                 return nil
     114           1 :         }
     115           1 :         it.key = nodeKey
     116           1 :         return &it.key
     117             : }
     118             : 
     119             : // First seeks position at the first entry in list. Final state of iterator is
     120             : // Valid() iff list is not empty. Note that First only checks the upper
     121             : // bound. It is up to the caller to ensure that key is greater than or equal to
     122             : // the lower bound (e.g. via a call to SeekGE(lower)).
     123           1 : func (it *Iterator) First() *base.InternalKey {
     124           1 :         it.nd = it.list.getNext(it.list.head, 0)
     125           1 :         if it.nd == it.list.tail || it.nd == it.upperNode {
     126           1 :                 return nil
     127           1 :         }
     128           1 :         nodeKey := it.list.getKey(it.nd)
     129           1 :         if it.upper != nil && it.list.cmp(it.upper, nodeKey.UserKey) <= 0 {
     130           0 :                 it.upperNode = it.nd
     131           0 :                 return nil
     132           0 :         }
     133           1 :         it.key = nodeKey
     134           1 :         return &it.key
     135             : }
     136             : 
     137             : // Last seeks position at the last entry in list. Final state of iterator is
     138             : // Valid() iff list is not empty. Note that Last only checks the lower
     139             : // bound. It is up to the caller to ensure that key is less than the upper
     140             : // bound (e.g. via a call to SeekLT(upper)).
     141           1 : func (it *Iterator) Last() *base.InternalKey {
     142           1 :         it.nd = it.list.getPrev(it.list.tail, 0)
     143           1 :         if it.nd == it.list.head || it.nd == it.lowerNode {
     144           1 :                 return nil
     145           1 :         }
     146           1 :         nodeKey := it.list.getKey(it.nd)
     147           1 :         if it.lower != nil && it.list.cmp(it.lower, nodeKey.UserKey) > 0 {
     148           0 :                 it.lowerNode = it.nd
     149           0 :                 return nil
     150           0 :         }
     151           1 :         it.key = nodeKey
     152           1 :         return &it.key
     153             : }
     154             : 
     155             : // Next advances to the next position. If there are no following nodes, then
     156             : // Valid() will be false after this call.
     157           1 : func (it *Iterator) Next() *base.InternalKey {
     158           1 :         it.nd = it.list.getNext(it.nd, 0)
     159           1 :         if it.nd == it.list.tail || it.nd == it.upperNode {
     160           1 :                 return nil
     161           1 :         }
     162           1 :         nodeKey := it.list.getKey(it.nd)
     163           1 :         if it.upper != nil && it.list.cmp(it.upper, nodeKey.UserKey) <= 0 {
     164           1 :                 it.upperNode = it.nd
     165           1 :                 return nil
     166           1 :         }
     167           1 :         it.key = nodeKey
     168           1 :         return &it.key
     169             : }
     170             : 
     171             : // Prev moves to the previous position. If there are no previous nodes, then
     172             : // Valid() will be false after this call.
     173           1 : func (it *Iterator) Prev() *base.InternalKey {
     174           1 :         it.nd = it.list.getPrev(it.nd, 0)
     175           1 :         if it.nd == it.list.head || it.nd == it.lowerNode {
     176           1 :                 return nil
     177           1 :         }
     178           1 :         nodeKey := it.list.getKey(it.nd)
     179           1 :         if it.lower != nil && it.list.cmp(it.lower, nodeKey.UserKey) > 0 {
     180           0 :                 it.lowerNode = it.nd
     181           0 :                 return nil
     182           0 :         }
     183           1 :         it.key = nodeKey
     184           1 :         return &it.key
     185             : }
     186             : 
     187             : // KeyInfo returns the offset of the start of the record, the start of the key,
     188             : // and the end of the key.
     189           1 : func (it *Iterator) KeyInfo() (offset, keyStart, keyEnd uint32) {
     190           1 :         n := it.list.node(it.nd)
     191           1 :         return n.offset, n.keyStart, n.keyEnd
     192           1 : }
     193             : 
     194           0 : func (it *Iterator) String() string {
     195           0 :         return "batch"
     196           0 : }
     197             : 
     198             : // SetBounds sets the lower and upper bounds for the iterator. Note that the
     199             : // result of Next and Prev will be undefined until the iterator has been
     200             : // repositioned with SeekGE, SeekLT, First, or Last.
     201           1 : func (it *Iterator) SetBounds(lower, upper []byte) {
     202           1 :         it.lower = lower
     203           1 :         it.upper = upper
     204           1 :         it.lowerNode = 0
     205           1 :         it.upperNode = 0
     206           1 : }
     207             : 
     208           1 : func (it *Iterator) seekForBaseSplice(key []byte, abbreviatedKey uint64) (prev, next uint32) {
     209           1 :         prev = it.list.head
     210           1 :         for level := it.list.height - 1; ; level-- {
     211           1 :                 prev, next = it.list.findSpliceForLevel(key, abbreviatedKey, level, prev)
     212           1 :                 if level == 0 {
     213           1 :                         break
     214             :                 }
     215             :         }
     216             : 
     217           1 :         return
     218             : }