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 1 : func (w *rawBlockWriter) add(key InternalKey, value []byte) {
20 1 : w.curKey, w.prevKey = w.prevKey, w.curKey
21 1 :
22 1 : size := len(key.UserKey)
23 1 : if cap(w.curKey) < size {
24 1 : w.curKey = make([]byte, 0, size*2)
25 1 : }
26 1 : w.curKey = w.curKey[:size]
27 1 : copy(w.curKey, key.UserKey)
28 1 :
29 1 : w.storeWithOptionalValuePrefix(
30 1 : 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 1 : func newRawBlockIter(cmp Compare, block block) (*rawBlockIter, error) {
54 1 : i := &rawBlockIter{}
55 1 : return i, i.init(cmp, block)
56 1 : }
57 :
58 1 : func (i *rawBlockIter) init(cmp Compare, block block) error {
59 1 : numRestarts := int32(binary.LittleEndian.Uint32(block[len(block)-4:]))
60 1 : if numRestarts == 0 {
61 0 : return base.CorruptionErrorf("pebble/table: invalid table (block has no restart points)")
62 0 : }
63 1 : i.cmp = cmp
64 1 : i.restarts = int32(len(block)) - 4*(1+numRestarts)
65 1 : i.numRestarts = numRestarts
66 1 : i.ptr = unsafe.Pointer(&block[0])
67 1 : i.data = block
68 1 : if i.key == nil {
69 1 : i.key = make([]byte, 0, 256)
70 1 : } else {
71 0 : i.key = i.key[:0]
72 0 : }
73 1 : i.val = nil
74 1 : i.clearCache()
75 1 : return nil
76 : }
77 :
78 1 : func (i *rawBlockIter) readEntry() {
79 1 : ptr := unsafe.Pointer(uintptr(i.ptr) + uintptr(i.offset))
80 1 : shared, ptr := decodeVarint(ptr)
81 1 : unshared, ptr := decodeVarint(ptr)
82 1 : value, ptr := decodeVarint(ptr)
83 1 : i.key = append(i.key[:shared], getBytes(ptr, int(unshared))...)
84 1 : i.key = i.key[:len(i.key):len(i.key)]
85 1 : ptr = unsafe.Pointer(uintptr(ptr) + uintptr(unshared))
86 1 : i.val = getBytes(ptr, int(value))
87 1 : i.nextOffset = int32(uintptr(ptr)-uintptr(i.ptr)) + int32(value)
88 1 : }
89 :
90 1 : func (i *rawBlockIter) loadEntry() {
91 1 : i.readEntry()
92 1 : i.ikey.UserKey = i.key
93 1 : }
94 :
95 1 : func (i *rawBlockIter) clearCache() {
96 1 : i.cached = i.cached[:0]
97 1 : i.cachedBuf = i.cachedBuf[:0]
98 1 : }
99 :
100 0 : func (i *rawBlockIter) cacheEntry() {
101 0 : var valStart int32
102 0 : valSize := int32(len(i.val))
103 0 : if valSize > 0 {
104 0 : valStart = int32(uintptr(unsafe.Pointer(&i.val[0])) - uintptr(i.ptr))
105 0 : }
106 :
107 0 : i.cached = append(i.cached, blockEntry{
108 0 : offset: i.offset,
109 0 : keyStart: int32(len(i.cachedBuf)),
110 0 : keyEnd: int32(len(i.cachedBuf) + len(i.key)),
111 0 : valStart: valStart,
112 0 : valSize: valSize,
113 0 : })
114 0 : i.cachedBuf = append(i.cachedBuf, i.key...)
115 : }
116 :
117 : // SeekGE implements internalIterator.SeekGE, as documented in the pebble
118 : // package.
119 0 : func (i *rawBlockIter) SeekGE(key []byte) bool {
120 0 : // Find the index of the smallest restart point whose key is > the key
121 0 : // sought; index will be numRestarts if there is no such restart point.
122 0 : i.offset = 0
123 0 : index := sort.Search(int(i.numRestarts), func(j int) bool {
124 0 : offset := int32(binary.LittleEndian.Uint32(i.data[int(i.restarts)+4*j:]))
125 0 : // For a restart point, there are 0 bytes shared with the previous key.
126 0 : // The varint encoding of 0 occupies 1 byte.
127 0 : ptr := unsafe.Pointer(uintptr(i.ptr) + uintptr(offset+1))
128 0 : // Decode the key at that restart point, and compare it to the key sought.
129 0 : v1, ptr := decodeVarint(ptr)
130 0 : _, ptr = decodeVarint(ptr)
131 0 : s := getBytes(ptr, int(v1))
132 0 : return i.cmp(key, s) < 0
133 0 : })
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 0 : if index > 0 {
140 0 : i.offset = int32(binary.LittleEndian.Uint32(i.data[int(i.restarts)+4*(index-1):]))
141 0 : }
142 0 : i.loadEntry()
143 0 :
144 0 : // Iterate from that restart point to somewhere >= the key sought.
145 0 : for valid := i.Valid(); valid; valid = i.Next() {
146 0 : if i.cmp(key, i.key) <= 0 {
147 0 : break
148 : }
149 : }
150 0 : return i.Valid()
151 : }
152 :
153 : // First implements internalIterator.First, as documented in the pebble
154 : // package.
155 1 : func (i *rawBlockIter) First() bool {
156 1 : i.offset = 0
157 1 : i.loadEntry()
158 1 : return i.Valid()
159 1 : }
160 :
161 : // Last implements internalIterator.Last, as documented in the pebble package.
162 0 : func (i *rawBlockIter) Last() bool {
163 0 : // Seek forward from the last restart point.
164 0 : i.offset = int32(binary.LittleEndian.Uint32(i.data[i.restarts+4*(i.numRestarts-1):]))
165 0 :
166 0 : i.readEntry()
167 0 : i.clearCache()
168 0 : i.cacheEntry()
169 0 :
170 0 : for i.nextOffset < i.restarts {
171 0 : i.offset = i.nextOffset
172 0 : i.readEntry()
173 0 : i.cacheEntry()
174 0 : }
175 :
176 0 : i.ikey.UserKey = i.key
177 0 : return i.Valid()
178 : }
179 :
180 : // Next implements internalIterator.Next, as documented in the pebble
181 : // package.
182 1 : func (i *rawBlockIter) Next() bool {
183 1 : i.offset = i.nextOffset
184 1 : if !i.Valid() {
185 1 : return false
186 1 : }
187 1 : i.loadEntry()
188 1 : return true
189 : }
190 :
191 : // Prev implements internalIterator.Prev, as documented in the pebble
192 : // package.
193 0 : func (i *rawBlockIter) Prev() bool {
194 0 : if n := len(i.cached) - 1; n > 0 && i.cached[n].offset == i.offset {
195 0 : i.nextOffset = i.offset
196 0 : e := &i.cached[n-1]
197 0 : i.offset = e.offset
198 0 : i.val = getBytes(unsafe.Pointer(uintptr(i.ptr)+uintptr(e.valStart)), int(e.valSize))
199 0 : i.ikey.UserKey = i.cachedBuf[e.keyStart:e.keyEnd]
200 0 : i.cached = i.cached[:n]
201 0 : return true
202 0 : }
203 :
204 0 : if i.offset == 0 {
205 0 : i.offset = -1
206 0 : i.nextOffset = 0
207 0 : return false
208 0 : }
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 1 : func (i *rawBlockIter) Key() InternalKey {
236 1 : return i.ikey
237 1 : }
238 :
239 : // Value implements internalIterator.Value, as documented in the pebble
240 : // package.
241 1 : func (i *rawBlockIter) Value() []byte {
242 1 : return i.val
243 1 : }
244 :
245 : // Valid implements internalIterator.Valid, as documented in the pebble
246 : // package.
247 1 : func (i *rawBlockIter) Valid() bool {
248 1 : return i.offset >= 0 && i.offset < i.restarts
249 1 : }
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 1 : func (i *rawBlockIter) Close() error {
260 1 : i.val = nil
261 1 : return nil
262 1 : }
|
