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 0 : // Iterator is done. 79 0 : return nil 80 0 : } 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 0 : func (it *Iterator) SetBounds(lower, upper []byte) { 202 0 : it.lower = lower 203 0 : it.upper = upper 204 0 : } 205 : 206 1 : func (it *Iterator) seekForBaseSplice(key []byte, abbreviatedKey uint64) (prev, next uint32) { 207 1 : prev = it.list.head 208 1 : for level := it.list.height - 1; ; level-- { 209 1 : prev, next = it.list.findSpliceForLevel(key, abbreviatedKey, level, prev) 210 1 : if level == 0 { 211 1 : break 212 : } 213 : } 214 : 215 1 : return 216 : }