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             : }
      37             : 
      38             : // Close resets the iterator.
      39           2 : func (it *Iterator) Close() error {
      40           2 :         it.list = nil
      41           2 :         it.nd = 0
      42           2 :         return nil
      43           2 : }
      44             : 
      45             : // SeekGE moves the iterator to the first entry whose key is greater than or
      46             : // equal to the given key. Returns true if the iterator is pointing at a valid
      47             : // entry and false otherwise. Note that SeekGE only checks the upper bound. It
      48             : // is up to the caller to ensure that key is greater than or equal to the lower
      49             : // bound.
      50           2 : func (it *Iterator) SeekGE(key []byte, flags base.SeekGEFlags) *base.InternalKey {
      51           2 :         if flags.TrySeekUsingNext() {
      52           1 :                 if it.nd == it.list.tail {
      53           1 :                         // Iterator is done.
      54           1 :                         return nil
      55           1 :                 }
      56           1 :                 less := it.list.cmp(it.key.UserKey, key) < 0
      57           1 :                 // Arbitrary constant. By measuring the seek cost as a function of the
      58           1 :                 // number of elements in the skip list, and fitting to a model, we
      59           1 :                 // could adjust the number of nexts based on the current size of the
      60           1 :                 // skip list.
      61           1 :                 const numNexts = 5
      62           1 :                 for i := 0; less && i < numNexts; i++ {
      63           1 :                         k := it.Next()
      64           1 :                         if k == nil {
      65           0 :                                 // Iterator is done.
      66           0 :                                 return nil
      67           0 :                         }
      68           1 :                         less = it.list.cmp(k.UserKey, key) < 0
      69             :                 }
      70           1 :                 if !less {
      71           1 :                         return &it.key
      72           1 :                 }
      73             :         }
      74             : 
      75           2 :         _, it.nd = it.seekForBaseSplice(key, it.list.abbreviatedKey(key))
      76           2 :         if it.nd == it.list.tail {
      77           2 :                 return nil
      78           2 :         }
      79           2 :         nodeKey := it.list.getKey(it.nd)
      80           2 :         if it.upper != nil && it.list.cmp(it.upper, nodeKey.UserKey) <= 0 {
      81           2 :                 it.nd = it.list.tail
      82           2 :                 return nil
      83           2 :         }
      84           2 :         it.key = nodeKey
      85           2 :         return &it.key
      86             : }
      87             : 
      88             : // SeekLT moves the iterator to the last entry whose key is less the given
      89             : // key. Returns true if the iterator is pointing at a valid entry and false
      90             : // otherwise. Note that SeekLT only checks the lower bound. It is up to the
      91             : // caller to ensure that key is less than the upper bound.
      92           2 : func (it *Iterator) SeekLT(key []byte) *base.InternalKey {
      93           2 :         it.nd, _ = it.seekForBaseSplice(key, it.list.abbreviatedKey(key))
      94           2 :         if it.nd == it.list.head {
      95           2 :                 return nil
      96           2 :         }
      97           2 :         nodeKey := it.list.getKey(it.nd)
      98           2 :         if it.lower != nil && it.list.cmp(it.lower, nodeKey.UserKey) > 0 {
      99           2 :                 it.nd = it.list.head
     100           2 :                 return nil
     101           2 :         }
     102           2 :         it.key = nodeKey
     103           2 :         return &it.key
     104             : }
     105             : 
     106             : // First seeks position at the first entry in list. Final state of iterator is
     107             : // Valid() iff list is not empty. Note that First only checks the upper
     108             : // bound. It is up to the caller to ensure that key is greater than or equal to
     109             : // the lower bound (e.g. via a call to SeekGE(lower)).
     110           2 : func (it *Iterator) First() *base.InternalKey {
     111           2 :         it.nd = it.list.getNext(it.list.head, 0)
     112           2 :         if it.nd == it.list.tail {
     113           2 :                 return nil
     114           2 :         }
     115           2 :         nodeKey := it.list.getKey(it.nd)
     116           2 :         if it.upper != nil && it.list.cmp(it.upper, nodeKey.UserKey) <= 0 {
     117           0 :                 it.nd = it.list.tail
     118           0 :                 return nil
     119           0 :         }
     120           2 :         it.key = nodeKey
     121           2 :         return &it.key
     122             : }
     123             : 
     124             : // Last seeks position at the last entry in list. Final state of iterator is
     125             : // Valid() iff list is not empty. Note that Last only checks the lower
     126             : // bound. It is up to the caller to ensure that key is less than the upper
     127             : // bound (e.g. via a call to SeekLT(upper)).
     128           2 : func (it *Iterator) Last() *base.InternalKey {
     129           2 :         it.nd = it.list.getPrev(it.list.tail, 0)
     130           2 :         if it.nd == it.list.head {
     131           2 :                 return nil
     132           2 :         }
     133           2 :         nodeKey := it.list.getKey(it.nd)
     134           2 :         if it.lower != nil && it.list.cmp(it.lower, nodeKey.UserKey) > 0 {
     135           0 :                 it.nd = it.list.head
     136           0 :                 return nil
     137           0 :         }
     138           2 :         it.key = nodeKey
     139           2 :         return &it.key
     140             : }
     141             : 
     142             : // Next advances to the next position. If there are no following nodes, then
     143             : // Valid() will be false after this call.
     144           2 : func (it *Iterator) Next() *base.InternalKey {
     145           2 :         it.nd = it.list.getNext(it.nd, 0)
     146           2 :         if it.nd == it.list.tail {
     147           2 :                 return nil
     148           2 :         }
     149           2 :         nodeKey := it.list.getKey(it.nd)
     150           2 :         if it.upper != nil && it.list.cmp(it.upper, nodeKey.UserKey) <= 0 {
     151           2 :                 it.nd = it.list.tail
     152           2 :                 return nil
     153           2 :         }
     154           2 :         it.key = nodeKey
     155           2 :         return &it.key
     156             : }
     157             : 
     158             : // Prev moves to the previous position. If there are no previous nodes, then
     159             : // Valid() will be false after this call.
     160           2 : func (it *Iterator) Prev() *base.InternalKey {
     161           2 :         it.nd = it.list.getPrev(it.nd, 0)
     162           2 :         if it.nd == it.list.head {
     163           2 :                 return nil
     164           2 :         }
     165           1 :         nodeKey := it.list.getKey(it.nd)
     166           1 :         if it.lower != nil && it.list.cmp(it.lower, nodeKey.UserKey) > 0 {
     167           1 :                 it.nd = it.list.head
     168           1 :                 return nil
     169           1 :         }
     170           1 :         it.key = nodeKey
     171           1 :         return &it.key
     172             : }
     173             : 
     174             : // Key returns the key at the current position.
     175           1 : func (it *Iterator) Key() *base.InternalKey {
     176           1 :         return &it.key
     177           1 : }
     178             : 
     179             : // KeyInfo returns the offset of the start of the record, the start of the key,
     180             : // and the end of the key.
     181           2 : func (it *Iterator) KeyInfo() (offset, keyStart, keyEnd uint32) {
     182           2 :         n := it.list.node(it.nd)
     183           2 :         return n.offset, n.keyStart, n.keyEnd
     184           2 : }
     185             : 
     186             : // Head true iff the iterator is positioned at the sentinel head node.
     187           0 : func (it *Iterator) Head() bool {
     188           0 :         return it.nd == it.list.head
     189           0 : }
     190             : 
     191             : // Tail true iff the iterator is positioned at the sentinel tail node.
     192           0 : func (it *Iterator) Tail() bool {
     193           0 :         return it.nd == it.list.tail
     194           0 : }
     195             : 
     196             : // Valid returns nil iff the iterator is positioned at a valid node.
     197           1 : func (it *Iterator) Valid() bool {
     198           1 :         return it.list != nil && it.nd != it.list.head && it.nd != it.list.tail
     199           1 : }
     200             : 
     201           0 : func (it *Iterator) String() string {
     202           0 :         return "batch"
     203           0 : }
     204             : 
     205             : // SetBounds sets the lower and upper bounds for the iterator. Note that the
     206             : // result of Next and Prev will be undefined until the iterator has been
     207             : // repositioned with SeekGE, SeekLT, First, or Last.
     208           1 : func (it *Iterator) SetBounds(lower, upper []byte) {
     209           1 :         it.lower = lower
     210           1 :         it.upper = upper
     211           1 : }
     212             : 
     213           2 : func (it *Iterator) seekForBaseSplice(key []byte, abbreviatedKey uint64) (prev, next uint32) {
     214           2 :         prev = it.list.head
     215           2 :         for level := it.list.height - 1; ; level-- {
     216           2 :                 prev, next = it.list.findSpliceForLevel(key, abbreviatedKey, level, prev)
     217           2 :                 if level == 0 {
     218           2 :                         break
     219             :                 }
     220             :         }
     221             : 
     222           2 :         return
     223             : }