-
Notifications
You must be signed in to change notification settings - Fork 4
/
iterator.go
113 lines (101 loc) · 3.17 KB
/
iterator.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
package iterator
import (
"go-lsm/kv"
)
// Iterator represents a common interface for all the iterators available in the system.
type Iterator interface {
Key() kv.Key
Value() kv.Value
Next() error
IsValid() bool
Close()
}
type InclusiveBoundedIteratorType = *MergeIterator
// InclusiveBoundedIterator is the final iterator encapsulating MergeIterator, and is used for scanning with kv.InclusiveKeyRange.
// It serves the following:
// 1) Returns only the latest version (/timestamp) of a key, hence it tracks the previous key.
// 2) Ensures that the iterator does not go beyond the end key of the range.
type InclusiveBoundedIterator struct {
inner InclusiveBoundedIteratorType
inclusiveEndKey kv.Key
isValid bool
previousKey kv.Key
}
// NewInclusiveBoundedIterator creates a new instance of InclusiveBoundedIterator.
func NewInclusiveBoundedIterator(iterator InclusiveBoundedIteratorType, inclusiveEndKey kv.Key) *InclusiveBoundedIterator {
inclusiveBoundedIterator := &InclusiveBoundedIterator{
inner: iterator,
inclusiveEndKey: inclusiveEndKey,
isValid: iterator.IsValid(),
}
if err := inclusiveBoundedIterator.keepLatestTimestamp(); err != nil {
panic(err)
}
return inclusiveBoundedIterator
}
// Key returns kv.Key.
func (iterator *InclusiveBoundedIterator) Key() kv.Key {
return iterator.inner.Key()
}
// Value returns kv.Value.
func (iterator *InclusiveBoundedIterator) Value() kv.Value {
return iterator.inner.Value()
}
// Next advances the iterator and keeps the latest timestamp of a key.
func (iterator *InclusiveBoundedIterator) Next() error {
if err := iterator.advance(); err != nil {
return err
}
return iterator.keepLatestTimestamp()
}
// IsValid returns true if the key referred to by the iterator is less than or equal to the end key of the range.
func (iterator *InclusiveBoundedIterator) IsValid() bool {
return iterator.isValid
}
// Close closes the inner iterator.
func (iterator *InclusiveBoundedIterator) Close() {
iterator.inner.Close()
}
// keepLatestTimestamp keeps the latest timestamp of a key.
func (iterator *InclusiveBoundedIterator) keepLatestTimestamp() error {
for {
for iterator.inner.IsValid() && iterator.inner.Key().IsRawKeyEqualTo(iterator.previousKey) {
if err := iterator.advance(); err != nil {
return err
}
}
if !iterator.inner.IsValid() {
break
}
iterator.previousKey = iterator.inner.Key()
for iterator.inner.IsValid() &&
iterator.inner.Key().IsRawKeyEqualTo(iterator.previousKey) &&
iterator.inner.Key().Timestamp() > iterator.inclusiveEndKey.Timestamp() {
if err := iterator.advance(); err != nil {
return err
}
}
if !iterator.inner.IsValid() {
break
}
if !iterator.inner.Key().IsRawKeyEqualTo(iterator.previousKey) {
continue
}
if !iterator.inner.Value().IsEmpty() {
break
}
}
return nil
}
// advance advances the iterator ahead and also sets isValid.
func (iterator *InclusiveBoundedIterator) advance() error {
if err := iterator.inner.Next(); err != nil {
return err
}
if !iterator.inner.IsValid() {
iterator.isValid = false
return nil
}
iterator.isValid = iterator.inner.Key().IsLessThanOrEqualTo(iterator.inclusiveEndKey)
return nil
}