1 // Copyright (c) Facebook, Inc. and its affiliates. All Rights Reserved.
2 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
3 // Use of this source code is governed by a BSD-style license that can be
4 // found in the LICENSE file. See the AUTHORS file for names of contributors.
5
6 #ifndef ROCKSDB_LITE
7
8 #include "table/plain/plain_table_reader.h"
9
10 #include <string>
11 #include <vector>
12
13 #include "db/dbformat.h"
14
15 #include "rocksdb/cache.h"
16 #include "rocksdb/comparator.h"
17 #include "rocksdb/env.h"
18 #include "rocksdb/filter_policy.h"
19 #include "rocksdb/options.h"
20 #include "rocksdb/statistics.h"
21
22 #include "table/block_based/block.h"
23 #include "table/block_based/filter_block.h"
24 #include "table/format.h"
25 #include "table/get_context.h"
26 #include "table/internal_iterator.h"
27 #include "table/meta_blocks.h"
28 #include "table/plain/plain_table_bloom.h"
29 #include "table/plain/plain_table_factory.h"
30 #include "table/plain/plain_table_key_coding.h"
31 #include "table/two_level_iterator.h"
32
33 #include "memory/arena.h"
34 #include "monitoring/histogram.h"
35 #include "monitoring/perf_context_imp.h"
36 #include "util/coding.h"
37 #include "util/dynamic_bloom.h"
38 #include "util/hash.h"
39 #include "util/stop_watch.h"
40 #include "util/string_util.h"
41
42 namespace ROCKSDB_NAMESPACE {
43
44 namespace {
45
46 // Safely getting a uint32_t element from a char array, where, starting from
47 // `base`, every 4 bytes are considered as an fixed 32 bit integer.
GetFixed32Element(const char * base,size_t offset)48 inline uint32_t GetFixed32Element(const char* base, size_t offset) {
49 return DecodeFixed32(base + offset * sizeof(uint32_t));
50 }
51 } // namespace
52
53 // Iterator to iterate IndexedTable
54 class PlainTableIterator : public InternalIterator {
55 public:
56 explicit PlainTableIterator(PlainTableReader* table, bool use_prefix_seek);
57 // No copying allowed
58 PlainTableIterator(const PlainTableIterator&) = delete;
59 void operator=(const Iterator&) = delete;
60
61 ~PlainTableIterator() override;
62
63 bool Valid() const override;
64
65 void SeekToFirst() override;
66
67 void SeekToLast() override;
68
69 void Seek(const Slice& target) override;
70
71 void SeekForPrev(const Slice& target) override;
72
73 void Next() override;
74
75 void Prev() override;
76
77 Slice key() const override;
78
79 Slice value() const override;
80
81 Status status() const override;
82
83 private:
84 PlainTableReader* table_;
85 PlainTableKeyDecoder decoder_;
86 bool use_prefix_seek_;
87 uint32_t offset_;
88 uint32_t next_offset_;
89 Slice key_;
90 Slice value_;
91 Status status_;
92 };
93
94 extern const uint64_t kPlainTableMagicNumber;
PlainTableReader(const ImmutableCFOptions & ioptions,std::unique_ptr<RandomAccessFileReader> && file,const EnvOptions & storage_options,const InternalKeyComparator & icomparator,EncodingType encoding_type,uint64_t file_size,const TableProperties * table_properties,const SliceTransform * prefix_extractor)95 PlainTableReader::PlainTableReader(
96 const ImmutableCFOptions& ioptions,
97 std::unique_ptr<RandomAccessFileReader>&& file,
98 const EnvOptions& storage_options, const InternalKeyComparator& icomparator,
99 EncodingType encoding_type, uint64_t file_size,
100 const TableProperties* table_properties,
101 const SliceTransform* prefix_extractor)
102 : internal_comparator_(icomparator),
103 encoding_type_(encoding_type),
104 full_scan_mode_(false),
105 user_key_len_(static_cast<uint32_t>(table_properties->fixed_key_len)),
106 prefix_extractor_(prefix_extractor),
107 enable_bloom_(false),
108 bloom_(6),
109 file_info_(std::move(file), storage_options,
110 static_cast<uint32_t>(table_properties->data_size)),
111 ioptions_(ioptions),
112 file_size_(file_size),
113 table_properties_(nullptr) {}
114
~PlainTableReader()115 PlainTableReader::~PlainTableReader() {
116 }
117
Open(const ImmutableCFOptions & ioptions,const EnvOptions & env_options,const InternalKeyComparator & internal_comparator,std::unique_ptr<RandomAccessFileReader> && file,uint64_t file_size,std::unique_ptr<TableReader> * table_reader,const int bloom_bits_per_key,double hash_table_ratio,size_t index_sparseness,size_t huge_page_tlb_size,bool full_scan_mode,const bool immortal_table,const SliceTransform * prefix_extractor)118 Status PlainTableReader::Open(
119 const ImmutableCFOptions& ioptions, const EnvOptions& env_options,
120 const InternalKeyComparator& internal_comparator,
121 std::unique_ptr<RandomAccessFileReader>&& file, uint64_t file_size,
122 std::unique_ptr<TableReader>* table_reader, const int bloom_bits_per_key,
123 double hash_table_ratio, size_t index_sparseness, size_t huge_page_tlb_size,
124 bool full_scan_mode, const bool immortal_table,
125 const SliceTransform* prefix_extractor) {
126 if (file_size > PlainTableIndex::kMaxFileSize) {
127 return Status::NotSupported("File is too large for PlainTableReader!");
128 }
129
130 TableProperties* props_ptr = nullptr;
131 auto s = ReadTableProperties(file.get(), file_size, kPlainTableMagicNumber,
132 ioptions, &props_ptr,
133 true /* compression_type_missing */);
134 std::shared_ptr<TableProperties> props(props_ptr);
135 if (!s.ok()) {
136 return s;
137 }
138
139 assert(hash_table_ratio >= 0.0);
140 auto& user_props = props->user_collected_properties;
141 auto prefix_extractor_in_file = props->prefix_extractor_name;
142
143 if (!full_scan_mode &&
144 !prefix_extractor_in_file.empty() /* old version sst file*/
145 && prefix_extractor_in_file != "nullptr") {
146 if (!prefix_extractor) {
147 return Status::InvalidArgument(
148 "Prefix extractor is missing when opening a PlainTable built "
149 "using a prefix extractor");
150 } else if (prefix_extractor_in_file.compare(prefix_extractor->Name()) !=
151 0) {
152 return Status::InvalidArgument(
153 "Prefix extractor given doesn't match the one used to build "
154 "PlainTable");
155 }
156 }
157
158 EncodingType encoding_type = kPlain;
159 auto encoding_type_prop =
160 user_props.find(PlainTablePropertyNames::kEncodingType);
161 if (encoding_type_prop != user_props.end()) {
162 encoding_type = static_cast<EncodingType>(
163 DecodeFixed32(encoding_type_prop->second.c_str()));
164 }
165
166 std::unique_ptr<PlainTableReader> new_reader(new PlainTableReader(
167 ioptions, std::move(file), env_options, internal_comparator,
168 encoding_type, file_size, props.get(), prefix_extractor));
169
170 s = new_reader->MmapDataIfNeeded();
171 if (!s.ok()) {
172 return s;
173 }
174
175 if (!full_scan_mode) {
176 s = new_reader->PopulateIndex(props.get(), bloom_bits_per_key,
177 hash_table_ratio, index_sparseness,
178 huge_page_tlb_size);
179 if (!s.ok()) {
180 return s;
181 }
182 } else {
183 // Flag to indicate it is a full scan mode so that none of the indexes
184 // can be used.
185 new_reader->full_scan_mode_ = true;
186 }
187 // PopulateIndex can add to the props, so don't store them until now
188 new_reader->table_properties_ = props;
189
190 if (immortal_table && new_reader->file_info_.is_mmap_mode) {
191 new_reader->dummy_cleanable_.reset(new Cleanable());
192 }
193
194 *table_reader = std::move(new_reader);
195 return s;
196 }
197
SetupForCompaction()198 void PlainTableReader::SetupForCompaction() {
199 }
200
NewIterator(const ReadOptions & options,const SliceTransform *,Arena * arena,bool,TableReaderCaller,size_t)201 InternalIterator* PlainTableReader::NewIterator(
202 const ReadOptions& options, const SliceTransform* /* prefix_extractor */,
203 Arena* arena, bool /*skip_filters*/, TableReaderCaller /*caller*/,
204 size_t /*compaction_readahead_size*/) {
205 // Not necessarily used here, but make sure this has been initialized
206 assert(table_properties_);
207
208 // Auto prefix mode is not implemented in PlainTable.
209 bool use_prefix_seek = !IsTotalOrderMode() && !options.total_order_seek &&
210 !options.auto_prefix_mode;
211 if (arena == nullptr) {
212 return new PlainTableIterator(this, use_prefix_seek);
213 } else {
214 auto mem = arena->AllocateAligned(sizeof(PlainTableIterator));
215 return new (mem) PlainTableIterator(this, use_prefix_seek);
216 }
217 }
218
PopulateIndexRecordList(PlainTableIndexBuilder * index_builder,std::vector<uint32_t> * prefix_hashes)219 Status PlainTableReader::PopulateIndexRecordList(
220 PlainTableIndexBuilder* index_builder,
221 std::vector<uint32_t>* prefix_hashes) {
222 Slice prev_key_prefix_slice;
223 std::string prev_key_prefix_buf;
224 uint32_t pos = data_start_offset_;
225
226 bool is_first_record = true;
227 Slice key_prefix_slice;
228 PlainTableKeyDecoder decoder(&file_info_, encoding_type_, user_key_len_,
229 prefix_extractor_);
230 while (pos < file_info_.data_end_offset) {
231 uint32_t key_offset = pos;
232 ParsedInternalKey key;
233 Slice value_slice;
234 bool seekable = false;
235 Status s = Next(&decoder, &pos, &key, nullptr, &value_slice, &seekable);
236 if (!s.ok()) {
237 return s;
238 }
239
240 key_prefix_slice = GetPrefix(key);
241 if (enable_bloom_) {
242 bloom_.AddHash(GetSliceHash(key.user_key));
243 } else {
244 if (is_first_record || prev_key_prefix_slice != key_prefix_slice) {
245 if (!is_first_record) {
246 prefix_hashes->push_back(GetSliceHash(prev_key_prefix_slice));
247 }
248 if (file_info_.is_mmap_mode) {
249 prev_key_prefix_slice = key_prefix_slice;
250 } else {
251 prev_key_prefix_buf = key_prefix_slice.ToString();
252 prev_key_prefix_slice = prev_key_prefix_buf;
253 }
254 }
255 }
256
257 index_builder->AddKeyPrefix(GetPrefix(key), key_offset);
258
259 if (!seekable && is_first_record) {
260 return Status::Corruption("Key for a prefix is not seekable");
261 }
262
263 is_first_record = false;
264 }
265
266 prefix_hashes->push_back(GetSliceHash(key_prefix_slice));
267 auto s = index_.InitFromRawData(index_builder->Finish());
268 return s;
269 }
270
AllocateBloom(int bloom_bits_per_key,int num_keys,size_t huge_page_tlb_size)271 void PlainTableReader::AllocateBloom(int bloom_bits_per_key, int num_keys,
272 size_t huge_page_tlb_size) {
273 uint32_t bloom_total_bits = num_keys * bloom_bits_per_key;
274 if (bloom_total_bits > 0) {
275 enable_bloom_ = true;
276 bloom_.SetTotalBits(&arena_, bloom_total_bits, ioptions_.bloom_locality,
277 huge_page_tlb_size, ioptions_.info_log);
278 }
279 }
280
FillBloom(const std::vector<uint32_t> & prefix_hashes)281 void PlainTableReader::FillBloom(const std::vector<uint32_t>& prefix_hashes) {
282 assert(bloom_.IsInitialized());
283 for (const auto prefix_hash : prefix_hashes) {
284 bloom_.AddHash(prefix_hash);
285 }
286 }
287
MmapDataIfNeeded()288 Status PlainTableReader::MmapDataIfNeeded() {
289 if (file_info_.is_mmap_mode) {
290 // Get mmapped memory.
291 return file_info_.file->Read(0, static_cast<size_t>(file_size_), &file_info_.file_data, nullptr);
292 }
293 return Status::OK();
294 }
295
PopulateIndex(TableProperties * props,int bloom_bits_per_key,double hash_table_ratio,size_t index_sparseness,size_t huge_page_tlb_size)296 Status PlainTableReader::PopulateIndex(TableProperties* props,
297 int bloom_bits_per_key,
298 double hash_table_ratio,
299 size_t index_sparseness,
300 size_t huge_page_tlb_size) {
301 assert(props != nullptr);
302
303 BlockContents index_block_contents;
304 Status s = ReadMetaBlock(file_info_.file.get(), nullptr /* prefetch_buffer */,
305 file_size_, kPlainTableMagicNumber, ioptions_,
306 PlainTableIndexBuilder::kPlainTableIndexBlock,
307 BlockType::kIndex, &index_block_contents,
308 true /* compression_type_missing */);
309
310 bool index_in_file = s.ok();
311
312 BlockContents bloom_block_contents;
313 bool bloom_in_file = false;
314 // We only need to read the bloom block if index block is in file.
315 if (index_in_file) {
316 s = ReadMetaBlock(file_info_.file.get(), nullptr /* prefetch_buffer */,
317 file_size_, kPlainTableMagicNumber, ioptions_,
318 BloomBlockBuilder::kBloomBlock, BlockType::kFilter,
319 &bloom_block_contents,
320 true /* compression_type_missing */);
321 bloom_in_file = s.ok() && bloom_block_contents.data.size() > 0;
322 }
323
324 Slice* bloom_block;
325 if (bloom_in_file) {
326 // If bloom_block_contents.allocation is not empty (which will be the case
327 // for non-mmap mode), it holds the alloated memory for the bloom block.
328 // It needs to be kept alive to keep `bloom_block` valid.
329 bloom_block_alloc_ = std::move(bloom_block_contents.allocation);
330 bloom_block = &bloom_block_contents.data;
331 } else {
332 bloom_block = nullptr;
333 }
334
335 Slice* index_block;
336 if (index_in_file) {
337 // If index_block_contents.allocation is not empty (which will be the case
338 // for non-mmap mode), it holds the alloated memory for the index block.
339 // It needs to be kept alive to keep `index_block` valid.
340 index_block_alloc_ = std::move(index_block_contents.allocation);
341 index_block = &index_block_contents.data;
342 } else {
343 index_block = nullptr;
344 }
345
346 if ((prefix_extractor_ == nullptr) && (hash_table_ratio != 0)) {
347 // moptions.prefix_extractor is requried for a hash-based look-up.
348 return Status::NotSupported(
349 "PlainTable requires a prefix extractor enable prefix hash mode.");
350 }
351
352 // First, read the whole file, for every kIndexIntervalForSamePrefixKeys rows
353 // for a prefix (starting from the first one), generate a record of (hash,
354 // offset) and append it to IndexRecordList, which is a data structure created
355 // to store them.
356
357 if (!index_in_file) {
358 // Allocate bloom filter here for total order mode.
359 if (IsTotalOrderMode()) {
360 AllocateBloom(bloom_bits_per_key,
361 static_cast<uint32_t>(props->num_entries),
362 huge_page_tlb_size);
363 }
364 } else if (bloom_in_file) {
365 enable_bloom_ = true;
366 auto num_blocks_property = props->user_collected_properties.find(
367 PlainTablePropertyNames::kNumBloomBlocks);
368
369 uint32_t num_blocks = 0;
370 if (num_blocks_property != props->user_collected_properties.end()) {
371 Slice temp_slice(num_blocks_property->second);
372 if (!GetVarint32(&temp_slice, &num_blocks)) {
373 num_blocks = 0;
374 }
375 }
376 // cast away const qualifier, because bloom_ won't be changed
377 bloom_.SetRawData(const_cast<char*>(bloom_block->data()),
378 static_cast<uint32_t>(bloom_block->size()) * 8,
379 num_blocks);
380 } else {
381 // Index in file but no bloom in file. Disable bloom filter in this case.
382 enable_bloom_ = false;
383 bloom_bits_per_key = 0;
384 }
385
386 PlainTableIndexBuilder index_builder(&arena_, ioptions_, prefix_extractor_,
387 index_sparseness, hash_table_ratio,
388 huge_page_tlb_size);
389
390 std::vector<uint32_t> prefix_hashes;
391 if (!index_in_file) {
392 // Populates _bloom if enabled (total order mode)
393 s = PopulateIndexRecordList(&index_builder, &prefix_hashes);
394 if (!s.ok()) {
395 return s;
396 }
397 } else {
398 s = index_.InitFromRawData(*index_block);
399 if (!s.ok()) {
400 return s;
401 }
402 }
403
404 if (!index_in_file) {
405 if (!IsTotalOrderMode()) {
406 // Calculated bloom filter size and allocate memory for
407 // bloom filter based on the number of prefixes, then fill it.
408 AllocateBloom(bloom_bits_per_key, index_.GetNumPrefixes(),
409 huge_page_tlb_size);
410 if (enable_bloom_) {
411 FillBloom(prefix_hashes);
412 }
413 }
414 }
415
416 // Fill two table properties.
417 if (!index_in_file) {
418 props->user_collected_properties["plain_table_hash_table_size"] =
419 ToString(index_.GetIndexSize() * PlainTableIndex::kOffsetLen);
420 props->user_collected_properties["plain_table_sub_index_size"] =
421 ToString(index_.GetSubIndexSize());
422 } else {
423 props->user_collected_properties["plain_table_hash_table_size"] =
424 ToString(0);
425 props->user_collected_properties["plain_table_sub_index_size"] =
426 ToString(0);
427 }
428
429 return Status::OK();
430 }
431
GetOffset(PlainTableKeyDecoder * decoder,const Slice & target,const Slice & prefix,uint32_t prefix_hash,bool & prefix_matched,uint32_t * offset) const432 Status PlainTableReader::GetOffset(PlainTableKeyDecoder* decoder,
433 const Slice& target, const Slice& prefix,
434 uint32_t prefix_hash, bool& prefix_matched,
435 uint32_t* offset) const {
436 prefix_matched = false;
437 uint32_t prefix_index_offset;
438 auto res = index_.GetOffset(prefix_hash, &prefix_index_offset);
439 if (res == PlainTableIndex::kNoPrefixForBucket) {
440 *offset = file_info_.data_end_offset;
441 return Status::OK();
442 } else if (res == PlainTableIndex::kDirectToFile) {
443 *offset = prefix_index_offset;
444 return Status::OK();
445 }
446
447 // point to sub-index, need to do a binary search
448 uint32_t upper_bound;
449 const char* base_ptr =
450 index_.GetSubIndexBasePtrAndUpperBound(prefix_index_offset, &upper_bound);
451 uint32_t low = 0;
452 uint32_t high = upper_bound;
453 ParsedInternalKey mid_key;
454 ParsedInternalKey parsed_target;
455 if (!ParseInternalKey(target, &parsed_target)) {
456 return Status::Corruption(Slice());
457 }
458
459 // The key is between [low, high). Do a binary search between it.
460 while (high - low > 1) {
461 uint32_t mid = (high + low) / 2;
462 uint32_t file_offset = GetFixed32Element(base_ptr, mid);
463 uint32_t tmp;
464 Status s = decoder->NextKeyNoValue(file_offset, &mid_key, nullptr, &tmp);
465 if (!s.ok()) {
466 return s;
467 }
468 int cmp_result = internal_comparator_.Compare(mid_key, parsed_target);
469 if (cmp_result < 0) {
470 low = mid;
471 } else {
472 if (cmp_result == 0) {
473 // Happen to have found the exact key or target is smaller than the
474 // first key after base_offset.
475 prefix_matched = true;
476 *offset = file_offset;
477 return Status::OK();
478 } else {
479 high = mid;
480 }
481 }
482 }
483 // Both of the key at the position low or low+1 could share the same
484 // prefix as target. We need to rule out one of them to avoid to go
485 // to the wrong prefix.
486 ParsedInternalKey low_key;
487 uint32_t tmp;
488 uint32_t low_key_offset = GetFixed32Element(base_ptr, low);
489 Status s = decoder->NextKeyNoValue(low_key_offset, &low_key, nullptr, &tmp);
490 if (!s.ok()) {
491 return s;
492 }
493
494 if (GetPrefix(low_key) == prefix) {
495 prefix_matched = true;
496 *offset = low_key_offset;
497 } else if (low + 1 < upper_bound) {
498 // There is possible a next prefix, return it
499 prefix_matched = false;
500 *offset = GetFixed32Element(base_ptr, low + 1);
501 } else {
502 // target is larger than a key of the last prefix in this bucket
503 // but with a different prefix. Key does not exist.
504 *offset = file_info_.data_end_offset;
505 }
506 return Status::OK();
507 }
508
MatchBloom(uint32_t hash) const509 bool PlainTableReader::MatchBloom(uint32_t hash) const {
510 if (!enable_bloom_) {
511 return true;
512 }
513
514 if (bloom_.MayContainHash(hash)) {
515 PERF_COUNTER_ADD(bloom_sst_hit_count, 1);
516 return true;
517 } else {
518 PERF_COUNTER_ADD(bloom_sst_miss_count, 1);
519 return false;
520 }
521 }
522
Next(PlainTableKeyDecoder * decoder,uint32_t * offset,ParsedInternalKey * parsed_key,Slice * internal_key,Slice * value,bool * seekable) const523 Status PlainTableReader::Next(PlainTableKeyDecoder* decoder, uint32_t* offset,
524 ParsedInternalKey* parsed_key,
525 Slice* internal_key, Slice* value,
526 bool* seekable) const {
527 if (*offset == file_info_.data_end_offset) {
528 *offset = file_info_.data_end_offset;
529 return Status::OK();
530 }
531
532 if (*offset > file_info_.data_end_offset) {
533 return Status::Corruption("Offset is out of file size");
534 }
535
536 uint32_t bytes_read;
537 Status s = decoder->NextKey(*offset, parsed_key, internal_key, value,
538 &bytes_read, seekable);
539 if (!s.ok()) {
540 return s;
541 }
542 *offset = *offset + bytes_read;
543 return Status::OK();
544 }
545
Prepare(const Slice & target)546 void PlainTableReader::Prepare(const Slice& target) {
547 if (enable_bloom_) {
548 uint32_t prefix_hash = GetSliceHash(GetPrefix(target));
549 bloom_.Prefetch(prefix_hash);
550 }
551 }
552
Get(const ReadOptions &,const Slice & target,GetContext * get_context,const SliceTransform *,bool)553 Status PlainTableReader::Get(const ReadOptions& /*ro*/, const Slice& target,
554 GetContext* get_context,
555 const SliceTransform* /* prefix_extractor */,
556 bool /*skip_filters*/) {
557 // Check bloom filter first.
558 Slice prefix_slice;
559 uint32_t prefix_hash;
560 if (IsTotalOrderMode()) {
561 if (full_scan_mode_) {
562 status_ =
563 Status::InvalidArgument("Get() is not allowed in full scan mode.");
564 }
565 // Match whole user key for bloom filter check.
566 if (!MatchBloom(GetSliceHash(GetUserKey(target)))) {
567 return Status::OK();
568 }
569 // in total order mode, there is only one bucket 0, and we always use empty
570 // prefix.
571 prefix_slice = Slice();
572 prefix_hash = 0;
573 } else {
574 prefix_slice = GetPrefix(target);
575 prefix_hash = GetSliceHash(prefix_slice);
576 if (!MatchBloom(prefix_hash)) {
577 return Status::OK();
578 }
579 }
580 uint32_t offset;
581 bool prefix_match;
582 PlainTableKeyDecoder decoder(&file_info_, encoding_type_, user_key_len_,
583 prefix_extractor_);
584 Status s = GetOffset(&decoder, target, prefix_slice, prefix_hash,
585 prefix_match, &offset);
586
587 if (!s.ok()) {
588 return s;
589 }
590 ParsedInternalKey found_key;
591 ParsedInternalKey parsed_target;
592 if (!ParseInternalKey(target, &parsed_target)) {
593 return Status::Corruption(Slice());
594 }
595 Slice found_value;
596 while (offset < file_info_.data_end_offset) {
597 s = Next(&decoder, &offset, &found_key, nullptr, &found_value);
598 if (!s.ok()) {
599 return s;
600 }
601 if (!prefix_match) {
602 // Need to verify prefix for the first key found if it is not yet
603 // checked.
604 if (GetPrefix(found_key) != prefix_slice) {
605 return Status::OK();
606 }
607 prefix_match = true;
608 }
609 // TODO(ljin): since we know the key comparison result here,
610 // can we enable the fast path?
611 if (internal_comparator_.Compare(found_key, parsed_target) >= 0) {
612 bool dont_care __attribute__((__unused__));
613 if (!get_context->SaveValue(found_key, found_value, &dont_care,
614 dummy_cleanable_.get())) {
615 break;
616 }
617 }
618 }
619 return Status::OK();
620 }
621
ApproximateOffsetOf(const Slice &,TableReaderCaller)622 uint64_t PlainTableReader::ApproximateOffsetOf(const Slice& /*key*/,
623 TableReaderCaller /*caller*/) {
624 return 0;
625 }
626
ApproximateSize(const Slice &,const Slice &,TableReaderCaller)627 uint64_t PlainTableReader::ApproximateSize(const Slice& /*start*/,
628 const Slice& /*end*/,
629 TableReaderCaller /*caller*/) {
630 return 0;
631 }
632
PlainTableIterator(PlainTableReader * table,bool use_prefix_seek)633 PlainTableIterator::PlainTableIterator(PlainTableReader* table,
634 bool use_prefix_seek)
635 : table_(table),
636 decoder_(&table_->file_info_, table_->encoding_type_,
637 table_->user_key_len_, table_->prefix_extractor_),
638 use_prefix_seek_(use_prefix_seek) {
639 next_offset_ = offset_ = table_->file_info_.data_end_offset;
640 }
641
~PlainTableIterator()642 PlainTableIterator::~PlainTableIterator() {
643 }
644
Valid() const645 bool PlainTableIterator::Valid() const {
646 return offset_ < table_->file_info_.data_end_offset &&
647 offset_ >= table_->data_start_offset_;
648 }
649
SeekToFirst()650 void PlainTableIterator::SeekToFirst() {
651 status_ = Status::OK();
652 next_offset_ = table_->data_start_offset_;
653 if (next_offset_ >= table_->file_info_.data_end_offset) {
654 next_offset_ = offset_ = table_->file_info_.data_end_offset;
655 } else {
656 Next();
657 }
658 }
659
SeekToLast()660 void PlainTableIterator::SeekToLast() {
661 assert(false);
662 status_ = Status::NotSupported("SeekToLast() is not supported in PlainTable");
663 next_offset_ = offset_ = table_->file_info_.data_end_offset;
664 }
665
Seek(const Slice & target)666 void PlainTableIterator::Seek(const Slice& target) {
667 if (use_prefix_seek_ != !table_->IsTotalOrderMode()) {
668 // This check is done here instead of NewIterator() to permit creating an
669 // iterator with total_order_seek = true even if we won't be able to Seek()
670 // it. This is needed for compaction: it creates iterator with
671 // total_order_seek = true but usually never does Seek() on it,
672 // only SeekToFirst().
673 status_ =
674 Status::InvalidArgument(
675 "total_order_seek not implemented for PlainTable.");
676 offset_ = next_offset_ = table_->file_info_.data_end_offset;
677 return;
678 }
679
680 // If the user doesn't set prefix seek option and we are not able to do a
681 // total Seek(). assert failure.
682 if (table_->IsTotalOrderMode()) {
683 if (table_->full_scan_mode_) {
684 status_ =
685 Status::InvalidArgument("Seek() is not allowed in full scan mode.");
686 offset_ = next_offset_ = table_->file_info_.data_end_offset;
687 return;
688 } else if (table_->GetIndexSize() > 1) {
689 assert(false);
690 status_ = Status::NotSupported(
691 "PlainTable cannot issue non-prefix seek unless in total order "
692 "mode.");
693 offset_ = next_offset_ = table_->file_info_.data_end_offset;
694 return;
695 }
696 }
697
698 Slice prefix_slice = table_->GetPrefix(target);
699 uint32_t prefix_hash = 0;
700 // Bloom filter is ignored in total-order mode.
701 if (!table_->IsTotalOrderMode()) {
702 prefix_hash = GetSliceHash(prefix_slice);
703 if (!table_->MatchBloom(prefix_hash)) {
704 status_ = Status::OK();
705 offset_ = next_offset_ = table_->file_info_.data_end_offset;
706 return;
707 }
708 }
709 bool prefix_match;
710 status_ = table_->GetOffset(&decoder_, target, prefix_slice, prefix_hash,
711 prefix_match, &next_offset_);
712 if (!status_.ok()) {
713 offset_ = next_offset_ = table_->file_info_.data_end_offset;
714 return;
715 }
716
717 if (next_offset_ < table_->file_info_.data_end_offset) {
718 for (Next(); status_.ok() && Valid(); Next()) {
719 if (!prefix_match) {
720 // Need to verify the first key's prefix
721 if (table_->GetPrefix(key()) != prefix_slice) {
722 offset_ = next_offset_ = table_->file_info_.data_end_offset;
723 break;
724 }
725 prefix_match = true;
726 }
727 if (table_->internal_comparator_.Compare(key(), target) >= 0) {
728 break;
729 }
730 }
731 } else {
732 offset_ = table_->file_info_.data_end_offset;
733 }
734 }
735
SeekForPrev(const Slice &)736 void PlainTableIterator::SeekForPrev(const Slice& /*target*/) {
737 assert(false);
738 status_ =
739 Status::NotSupported("SeekForPrev() is not supported in PlainTable");
740 offset_ = next_offset_ = table_->file_info_.data_end_offset;
741 }
742
Next()743 void PlainTableIterator::Next() {
744 offset_ = next_offset_;
745 if (offset_ < table_->file_info_.data_end_offset) {
746 Slice tmp_slice;
747 ParsedInternalKey parsed_key;
748 status_ =
749 table_->Next(&decoder_, &next_offset_, &parsed_key, &key_, &value_);
750 if (!status_.ok()) {
751 offset_ = next_offset_ = table_->file_info_.data_end_offset;
752 }
753 }
754 }
755
Prev()756 void PlainTableIterator::Prev() {
757 assert(false);
758 }
759
key() const760 Slice PlainTableIterator::key() const {
761 assert(Valid());
762 return key_;
763 }
764
value() const765 Slice PlainTableIterator::value() const {
766 assert(Valid());
767 return value_;
768 }
769
status() const770 Status PlainTableIterator::status() const {
771 return status_;
772 }
773
774 } // namespace ROCKSDB_NAMESPACE
775 #endif // ROCKSDB_LITE
776