-
Notifications
You must be signed in to change notification settings - Fork 3.5k
/
memiterator.go
137 lines (117 loc) · 2.73 KB
/
memiterator.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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
package internal
import (
"bytes"
"errors"
"github.com/cosmos/cosmos-sdk/store/types"
"github.com/tidwall/btree"
)
var _ types.Iterator = (*memIterator)(nil)
// memIterator iterates over iterKVCache items.
// if key is nil, means it was deleted.
// Implements Iterator.
type memIterator struct {
iter btree.GenericIter[item]
start []byte
end []byte
ascending bool
lastKey []byte
deleted map[string]struct{}
valid bool
}
func NewMemIterator(start, end []byte, items *BTree, deleted map[string]struct{}, ascending bool) *memIterator {
iter := items.tree.Iter()
var valid bool
if ascending {
if start != nil {
valid = iter.Seek(newItem(start, nil))
} else {
valid = iter.First()
}
} else {
if end != nil {
valid = iter.Seek(newItem(end, nil))
if !valid {
valid = iter.Last()
} else {
// end is exclusive
valid = iter.Prev()
}
} else {
valid = iter.Last()
}
}
mi := &memIterator{
iter: iter,
start: start,
end: end,
ascending: ascending,
lastKey: nil,
deleted: deleted,
valid: valid,
}
if mi.valid {
mi.valid = mi.keyInRange(mi.Key())
}
return mi
}
func (mi *memIterator) Domain() (start []byte, end []byte) {
return mi.start, mi.end
}
func (mi *memIterator) Close() error {
mi.iter.Release()
return nil
}
func (mi *memIterator) Error() error {
if !mi.Valid() {
return errors.New("invalid memIterator")
}
return nil
}
func (mi *memIterator) Valid() bool {
return mi.valid
}
func (mi *memIterator) Next() {
mi.assertValid()
if mi.ascending {
mi.valid = mi.iter.Next()
} else {
mi.valid = mi.iter.Prev()
}
if mi.valid {
mi.valid = mi.keyInRange(mi.Key())
}
}
func (mi *memIterator) keyInRange(key []byte) bool {
if mi.ascending && mi.end != nil && bytes.Compare(key, mi.end) >= 0 {
return false
}
if !mi.ascending && mi.start != nil && bytes.Compare(key, mi.start) < 0 {
return false
}
return true
}
func (mi *memIterator) Key() []byte {
return mi.iter.Item().key
}
func (mi *memIterator) Value() []byte {
item := mi.iter.Item()
key := item.key
// We need to handle the case where deleted is modified and includes our current key
// We handle this by maintaining a lastKey object in the iterator.
// If the current key is the same as the last key (and last key is not nil / the start)
// then we are calling value on the same thing as last time.
// Therefore we don't check the mi.deleted to see if this key is included in there.
if _, ok := mi.deleted[string(key)]; ok {
if mi.lastKey == nil || !bytes.Equal(key, mi.lastKey) {
// not re-calling on old last key
return nil
}
}
mi.lastKey = key
return item.value
}
func (mi *memIterator) assertValid() {
if err := mi.Error(); err != nil {
panic(err)
}
}