1179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Copyright (c) 2011 The LevelDB Authors. All rights reserved. 2179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Use of this source code is governed by a BSD-style license that can be 3179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// found in the LICENSE file. See the AUTHORS file for names of contributors. 4179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 5fbd97aa4c5325eace57d24b89845b9581bac9324jorlow@chromium.org#include "leveldb/table.h" 6179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 7fbd97aa4c5325eace57d24b89845b9581bac9324jorlow@chromium.org#include "leveldb/cache.h" 899a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com#include "leveldb/comparator.h" 9fbd97aa4c5325eace57d24b89845b9581bac9324jorlow@chromium.org#include "leveldb/env.h" 1099a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com#include "leveldb/filter_policy.h" 1199a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com#include "leveldb/options.h" 12179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "table/block.h" 1399a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com#include "table/filter_block.h" 14179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "table/format.h" 15179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "table/two_level_iterator.h" 16179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "util/coding.h" 17179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 18179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgnamespace leveldb { 19179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 20179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgstruct Table::Rep { 21179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ~Rep() { 2299a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com delete filter; 2399a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com delete [] filter_data; 24179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org delete index_block; 25179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 26179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 27179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Options options; 28179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Status status; 29179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org RandomAccessFile* file; 30179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org uint64_t cache_id; 3199a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com FilterBlockReader* filter; 3299a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com const char* filter_data; 33179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 34179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org BlockHandle metaindex_handle; // Handle to metaindex_block: saved from footer 35179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Block* index_block; 36179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org}; 37179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 38179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgStatus Table::Open(const Options& options, 39179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org RandomAccessFile* file, 40f85ede82f8c27a00c3120f67fbab89b2a89fe987jorlow@chromium.org uint64_t size, 41179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Table** table) { 42179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org *table = NULL; 43179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (size < Footer::kEncodedLength) { 44179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return Status::InvalidArgument("file is too short to be an sstable"); 45179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 46179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 47179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org char footer_space[Footer::kEncodedLength]; 48179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Slice footer_input; 49179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Status s = file->Read(size - Footer::kEncodedLength, Footer::kEncodedLength, 50179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org &footer_input, footer_space); 51179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (!s.ok()) return s; 52179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 53179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Footer footer; 54179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org s = footer.DecodeFrom(&footer_input); 55179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (!s.ok()) return s; 56179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 57179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Read the index block 5899a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com BlockContents contents; 59179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Block* index_block = NULL; 60179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (s.ok()) { 6199a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com s = ReadBlock(file, ReadOptions(), footer.index_handle(), &contents); 6299a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com if (s.ok()) { 6399a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com index_block = new Block(contents); 6499a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com } 65179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 66179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 67179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (s.ok()) { 68179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // We've successfully read the footer and the index block: we're 69179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // ready to serve requests. 70179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Rep* rep = new Table::Rep; 71179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org rep->options = options; 72179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org rep->file = file; 73179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org rep->metaindex_handle = footer.metaindex_handle(); 74179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org rep->index_block = index_block; 75179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org rep->cache_id = (options.block_cache ? options.block_cache->NewId() : 0); 7699a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com rep->filter_data = NULL; 7799a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com rep->filter = NULL; 78179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org *table = new Table(rep); 7999a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com (*table)->ReadMeta(footer); 80179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else { 81179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (index_block) delete index_block; 82179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 83179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 84179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return s; 85179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 86179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 8799a7585544fc162a5f8dd39a6add00776a981efesanjay@google.comvoid Table::ReadMeta(const Footer& footer) { 8899a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com if (rep_->options.filter_policy == NULL) { 8999a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com return; // Do not need any metadata 9099a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com } 9199a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 9299a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com // TODO(sanjay): Skip this if footer.metaindex_handle() size indicates 9399a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com // it is an empty block. 9499a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com ReadOptions opt; 9599a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com BlockContents contents; 9699a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com if (!ReadBlock(rep_->file, opt, footer.metaindex_handle(), &contents).ok()) { 9799a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com // Do not propagate errors since meta info is not needed for operation 9899a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com return; 9999a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com } 10099a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com Block* meta = new Block(contents); 10199a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 10299a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com Iterator* iter = meta->NewIterator(BytewiseComparator()); 10399a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com std::string key = "filter."; 10499a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com key.append(rep_->options.filter_policy->Name()); 10599a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com iter->Seek(key); 10699a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com if (iter->Valid() && iter->key() == Slice(key)) { 10799a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com ReadFilter(iter->value()); 10899a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com } 10999a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com delete iter; 11099a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com delete meta; 11199a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com} 11299a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 11399a7585544fc162a5f8dd39a6add00776a981efesanjay@google.comvoid Table::ReadFilter(const Slice& filter_handle_value) { 11499a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com Slice v = filter_handle_value; 11599a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com BlockHandle filter_handle; 11699a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com if (!filter_handle.DecodeFrom(&v).ok()) { 11799a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com return; 11899a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com } 11999a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 12099a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com // We might want to unify with ReadBlock() if we start 12199a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com // requiring checksum verification in Table::Open. 12299a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com ReadOptions opt; 12399a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com BlockContents block; 12499a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com if (!ReadBlock(rep_->file, opt, filter_handle, &block).ok()) { 12599a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com return; 12699a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com } 12799a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com if (block.heap_allocated) { 12899a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com rep_->filter_data = block.data.data(); // Will need to delete later 12999a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com } 13099a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com rep_->filter = new FilterBlockReader(rep_->options.filter_policy, block.data); 13199a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com} 13299a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 133179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgTable::~Table() { 134179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org delete rep_; 135179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 136179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 137179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgstatic void DeleteBlock(void* arg, void* ignored) { 138179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org delete reinterpret_cast<Block*>(arg); 139179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 140179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 141179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgstatic void DeleteCachedBlock(const Slice& key, void* value) { 142179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Block* block = reinterpret_cast<Block*>(value); 143179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org delete block; 144179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 145179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 146179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgstatic void ReleaseBlock(void* arg, void* h) { 147179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Cache* cache = reinterpret_cast<Cache*>(arg); 148179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Cache::Handle* handle = reinterpret_cast<Cache::Handle*>(h); 149179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org cache->Release(handle); 150179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 151179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 152179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Convert an index iterator value (i.e., an encoded BlockHandle) 153179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// into an iterator over the contents of the corresponding block. 154179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgIterator* Table::BlockReader(void* arg, 155179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const ReadOptions& options, 156179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const Slice& index_value) { 157179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Table* table = reinterpret_cast<Table*>(arg); 158179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Cache* block_cache = table->rep_->options.block_cache; 159179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Block* block = NULL; 160179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Cache::Handle* cache_handle = NULL; 161179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 162179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org BlockHandle handle; 163179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Slice input = index_value; 164179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Status s = handle.DecodeFrom(&input); 165179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // We intentionally allow extra stuff in index_value so that we 166179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // can add more features in the future. 167179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 168179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (s.ok()) { 16999a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com BlockContents contents; 170179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (block_cache != NULL) { 171179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org char cache_key_buffer[16]; 172179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org EncodeFixed64(cache_key_buffer, table->rep_->cache_id); 173179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org EncodeFixed64(cache_key_buffer+8, handle.offset()); 174179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Slice key(cache_key_buffer, sizeof(cache_key_buffer)); 175179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org cache_handle = block_cache->Lookup(key); 176179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (cache_handle != NULL) { 177179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org block = reinterpret_cast<Block*>(block_cache->Value(cache_handle)); 178179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else { 17999a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com s = ReadBlock(table->rep_->file, options, handle, &contents); 18099a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com if (s.ok()) { 18199a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com block = new Block(contents); 18299a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com if (contents.cachable && options.fill_cache) { 18399a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com cache_handle = block_cache->Insert( 18499a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com key, block, block->size(), &DeleteCachedBlock); 18599a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com } 186179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 187179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 188179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else { 18999a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com s = ReadBlock(table->rep_->file, options, handle, &contents); 19099a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com if (s.ok()) { 19199a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com block = new Block(contents); 19299a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com } 193179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 194179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 195179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 196179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Iterator* iter; 197179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (block != NULL) { 198179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org iter = block->NewIterator(table->rep_->options.comparator); 199179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (cache_handle == NULL) { 200179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org iter->RegisterCleanup(&DeleteBlock, block, NULL); 201179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else { 202179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org iter->RegisterCleanup(&ReleaseBlock, block_cache, cache_handle); 203179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 204179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else { 205179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org iter = NewErrorIterator(s); 206179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 207179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return iter; 208179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 209179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 210179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgIterator* Table::NewIterator(const ReadOptions& options) const { 211179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return NewTwoLevelIterator( 212179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org rep_->index_block->NewIterator(rep_->options.comparator), 213179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org &Table::BlockReader, const_cast<Table*>(this), options); 214179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 215179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 21699a7585544fc162a5f8dd39a6add00776a981efesanjay@google.comStatus Table::InternalGet(const ReadOptions& options, const Slice& k, 21799a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com void* arg, 21899a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com void (*saver)(void*, const Slice&, const Slice&)) { 21999a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com Status s; 22099a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com Iterator* iiter = rep_->index_block->NewIterator(rep_->options.comparator); 22199a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com iiter->Seek(k); 22299a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com if (iiter->Valid()) { 22399a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com Slice handle_value = iiter->value(); 22499a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com FilterBlockReader* filter = rep_->filter; 22599a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com BlockHandle handle; 22699a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com if (filter != NULL && 22799a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com handle.DecodeFrom(&handle_value).ok() && 22899a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com !filter->KeyMayMatch(handle.offset(), k)) { 22999a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com // Not found 23099a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com } else { 23199a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com Iterator* block_iter = BlockReader(this, options, iiter->value()); 23299a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com block_iter->Seek(k); 23399a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com if (block_iter->Valid()) { 23499a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com (*saver)(arg, block_iter->key(), block_iter->value()); 23599a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com } 23699a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com s = block_iter->status(); 23799a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com delete block_iter; 23899a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com } 23999a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com } 24099a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com if (s.ok()) { 24199a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com s = iiter->status(); 24299a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com } 24399a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com delete iiter; 24499a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com return s; 24599a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com} 24699a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 24799a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 248179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orguint64_t Table::ApproximateOffsetOf(const Slice& key) const { 249179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Iterator* index_iter = 250179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org rep_->index_block->NewIterator(rep_->options.comparator); 251179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org index_iter->Seek(key); 252179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org uint64_t result; 253179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (index_iter->Valid()) { 254179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org BlockHandle handle; 255179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Slice input = index_iter->value(); 256179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Status s = handle.DecodeFrom(&input); 257179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (s.ok()) { 258179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org result = handle.offset(); 259179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else { 260179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Strange: we can't decode the block handle in the index block. 261179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // We'll just return the offset of the metaindex block, which is 262179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // close to the whole file size for this case. 263179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org result = rep_->metaindex_handle.offset(); 264179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 265179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else { 266179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // key is past the last key in the file. Approximate the offset 267179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // by returning the offset of the metaindex block (which is 268179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // right near the end of the file). 269179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org result = rep_->metaindex_handle.offset(); 270179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 271179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org delete index_iter; 272179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return result; 273179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 274179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 27545b9940be332834440bd5299419f396e38085ebehans@chromium.org} // namespace leveldb 276