Line data Source code
1 : // Copyright 2018 The LevelDB-Go and Pebble Authors. All rights reserved. Use
2 : // of this source code is governed by a BSD-style license that can be found in
3 : // the LICENSE file.
4 :
5 : package sstable
6 :
7 : import (
8 : "encoding/binary"
9 : "sort"
10 : "unsafe"
11 :
12 : "github.com/cockroachdb/pebble/internal/base"
13 : )
14 :
15 : type rawBlockWriter struct {
16 : blockWriter
17 : }
18 :
19 2 : func (w *rawBlockWriter) add(key InternalKey, value []byte) {
20 2 : w.curKey, w.prevKey = w.prevKey, w.curKey
21 2 :
22 2 : size := len(key.UserKey)
23 2 : if cap(w.curKey) < size {
24 2 : w.curKey = make([]byte, 0, size*2)
25 2 : }
26 2 : w.curKey = w.curKey[:size]
27 2 : copy(w.curKey, key.UserKey)
28 2 :
29 2 : w.storeWithOptionalValuePrefix(
30 2 : size, value, len(key.UserKey), false, 0, false)
31 : }
32 :
33 : // rawBlockIter is an iterator over a single block of data. Unlike blockIter,
34 : // keys are stored in "raw" format (i.e. not as internal keys). Note that there
35 : // is significant similarity between this code and the code in blockIter. Yet
36 : // reducing duplication is difficult due to the blockIter being performance
37 : // critical. rawBlockIter must only be used for blocks where the value is
38 : // stored together with the key.
39 : type rawBlockIter struct {
40 : cmp Compare
41 : offset int32
42 : nextOffset int32
43 : restarts int32
44 : numRestarts int32
45 : ptr unsafe.Pointer
46 : data []byte
47 : key, val []byte
48 : ikey InternalKey
49 : cached []blockEntry
50 : cachedBuf []byte
51 : }
52 :
53 2 : func newRawBlockIter(cmp Compare, block block) (*rawBlockIter, error) {
54 2 : i := &rawBlockIter{}
55 2 : return i, i.init(cmp, block)
56 2 : }
57 :
58 2 : func (i *rawBlockIter) init(cmp Compare, block block) error {
59 2 : numRestarts := int32(binary.LittleEndian.Uint32(block[len(block)-4:]))
60 2 : if numRestarts == 0 {
61 0 : return base.CorruptionErrorf("pebble/table: invalid table (block has no restart points)")
62 0 : }
63 2 : i.cmp = cmp
64 2 : i.restarts = int32(len(block)) - 4*(1+numRestarts)
65 2 : i.numRestarts = numRestarts
66 2 : i.ptr = unsafe.Pointer(&block[0])
67 2 : i.data = block
68 2 : if i.key == nil {
69 2 : i.key = make([]byte, 0, 256)
70 2 : } else {
71 0 : i.key = i.key[:0]
72 0 : }
73 2 : i.val = nil
74 2 : i.clearCache()
75 2 : return nil
76 : }
77 :
78 2 : func (i *rawBlockIter) readEntry() {
79 2 : ptr := unsafe.Pointer(uintptr(i.ptr) + uintptr(i.offset))
80 2 : shared, ptr := decodeVarint(ptr)
81 2 : unshared, ptr := decodeVarint(ptr)
82 2 : value, ptr := decodeVarint(ptr)
83 2 : i.key = append(i.key[:shared], getBytes(ptr, int(unshared))...)
84 2 : i.key = i.key[:len(i.key):len(i.key)]
85 2 : ptr = unsafe.Pointer(uintptr(ptr) + uintptr(unshared))
86 2 : i.val = getBytes(ptr, int(value))
87 2 : i.nextOffset = int32(uintptr(ptr)-uintptr(i.ptr)) + int32(value)
88 2 : }
89 :
90 2 : func (i *rawBlockIter) loadEntry() {
91 2 : i.readEntry()
92 2 : i.ikey.UserKey = i.key
93 2 : }
94 :
95 2 : func (i *rawBlockIter) clearCache() {
96 2 : i.cached = i.cached[:0]
97 2 : i.cachedBuf = i.cachedBuf[:0]
98 2 : }
99 :
100 1 : func (i *rawBlockIter) cacheEntry() {
101 1 : var valStart int32
102 1 : valSize := int32(len(i.val))
103 1 : if valSize > 0 {
104 0 : valStart = int32(uintptr(unsafe.Pointer(&i.val[0])) - uintptr(i.ptr))
105 0 : }
106 :
107 1 : i.cached = append(i.cached, blockEntry{
108 1 : offset: i.offset,
109 1 : keyStart: int32(len(i.cachedBuf)),
110 1 : keyEnd: int32(len(i.cachedBuf) + len(i.key)),
111 1 : valStart: valStart,
112 1 : valSize: valSize,
113 1 : })
114 1 : i.cachedBuf = append(i.cachedBuf, i.key...)
115 : }
116 :
117 : // SeekGE implements internalIterator.SeekGE, as documented in the pebble
118 : // package.
119 1 : func (i *rawBlockIter) SeekGE(key []byte) bool {
120 1 : // Find the index of the smallest restart point whose key is > the key
121 1 : // sought; index will be numRestarts if there is no such restart point.
122 1 : i.offset = 0
123 1 : index := sort.Search(int(i.numRestarts), func(j int) bool {
124 1 : offset := int32(binary.LittleEndian.Uint32(i.data[int(i.restarts)+4*j:]))
125 1 : // For a restart point, there are 0 bytes shared with the previous key.
126 1 : // The varint encoding of 0 occupies 1 byte.
127 1 : ptr := unsafe.Pointer(uintptr(i.ptr) + uintptr(offset+1))
128 1 : // Decode the key at that restart point, and compare it to the key sought.
129 1 : v1, ptr := decodeVarint(ptr)
130 1 : _, ptr = decodeVarint(ptr)
131 1 : s := getBytes(ptr, int(v1))
132 1 : return i.cmp(key, s) < 0
133 1 : })
134 :
135 : // Since keys are strictly increasing, if index > 0 then the restart point at
136 : // index-1 will be the largest whose key is <= the key sought. If index ==
137 : // 0, then all keys in this block are larger than the key sought, and offset
138 : // remains at zero.
139 1 : if index > 0 {
140 1 : i.offset = int32(binary.LittleEndian.Uint32(i.data[int(i.restarts)+4*(index-1):]))
141 1 : }
142 1 : i.loadEntry()
143 1 :
144 1 : // Iterate from that restart point to somewhere >= the key sought.
145 1 : for valid := i.Valid(); valid; valid = i.Next() {
146 1 : if i.cmp(key, i.key) <= 0 {
147 1 : break
148 : }
149 : }
150 1 : return i.Valid()
151 : }
152 :
153 : // First implements internalIterator.First, as documented in the pebble
154 : // package.
155 2 : func (i *rawBlockIter) First() bool {
156 2 : i.offset = 0
157 2 : i.loadEntry()
158 2 : return i.Valid()
159 2 : }
160 :
161 : // Last implements internalIterator.Last, as documented in the pebble package.
162 1 : func (i *rawBlockIter) Last() bool {
163 1 : // Seek forward from the last restart point.
164 1 : i.offset = int32(binary.LittleEndian.Uint32(i.data[i.restarts+4*(i.numRestarts-1):]))
165 1 :
166 1 : i.readEntry()
167 1 : i.clearCache()
168 1 : i.cacheEntry()
169 1 :
170 1 : for i.nextOffset < i.restarts {
171 1 : i.offset = i.nextOffset
172 1 : i.readEntry()
173 1 : i.cacheEntry()
174 1 : }
175 :
176 1 : i.ikey.UserKey = i.key
177 1 : return i.Valid()
178 : }
179 :
180 : // Next implements internalIterator.Next, as documented in the pebble
181 : // package.
182 2 : func (i *rawBlockIter) Next() bool {
183 2 : i.offset = i.nextOffset
184 2 : if !i.Valid() {
185 2 : return false
186 2 : }
187 2 : i.loadEntry()
188 2 : return true
189 : }
190 :
191 : // Prev implements internalIterator.Prev, as documented in the pebble
192 : // package.
193 1 : func (i *rawBlockIter) Prev() bool {
194 1 : if n := len(i.cached) - 1; n > 0 && i.cached[n].offset == i.offset {
195 1 : i.nextOffset = i.offset
196 1 : e := &i.cached[n-1]
197 1 : i.offset = e.offset
198 1 : i.val = getBytes(unsafe.Pointer(uintptr(i.ptr)+uintptr(e.valStart)), int(e.valSize))
199 1 : i.ikey.UserKey = i.cachedBuf[e.keyStart:e.keyEnd]
200 1 : i.cached = i.cached[:n]
201 1 : return true
202 1 : }
203 :
204 1 : if i.offset == 0 {
205 1 : i.offset = -1
206 1 : i.nextOffset = 0
207 1 : return false
208 1 : }
209 :
210 0 : targetOffset := i.offset
211 0 : index := sort.Search(int(i.numRestarts), func(j int) bool {
212 0 : offset := int32(binary.LittleEndian.Uint32(i.data[int(i.restarts)+4*j:]))
213 0 : return offset >= targetOffset
214 0 : })
215 0 : i.offset = 0
216 0 : if index > 0 {
217 0 : i.offset = int32(binary.LittleEndian.Uint32(i.data[int(i.restarts)+4*(index-1):]))
218 0 : }
219 :
220 0 : i.readEntry()
221 0 : i.clearCache()
222 0 : i.cacheEntry()
223 0 :
224 0 : for i.nextOffset < targetOffset {
225 0 : i.offset = i.nextOffset
226 0 : i.readEntry()
227 0 : i.cacheEntry()
228 0 : }
229 :
230 0 : i.ikey.UserKey = i.key
231 0 : return true
232 : }
233 :
234 : // Key implements internalIterator.Key, as documented in the pebble package.
235 2 : func (i *rawBlockIter) Key() InternalKey {
236 2 : return i.ikey
237 2 : }
238 :
239 : // Value implements internalIterator.Value, as documented in the pebble
240 : // package.
241 2 : func (i *rawBlockIter) Value() []byte {
242 2 : return i.val
243 2 : }
244 :
245 : // Valid implements internalIterator.Valid, as documented in the pebble
246 : // package.
247 2 : func (i *rawBlockIter) Valid() bool {
248 2 : return i.offset >= 0 && i.offset < i.restarts
249 2 : }
250 :
251 : // Error implements internalIterator.Error, as documented in the pebble
252 : // package.
253 0 : func (i *rawBlockIter) Error() error {
254 0 : return nil
255 0 : }
256 :
257 : // Close implements internalIterator.Close, as documented in the pebble
258 : // package.
259 2 : func (i *rawBlockIter) Close() error {
260 2 : i.val = nil
261 2 : return nil
262 2 : }
|
