Leveldb源码分析--10

6 SSTable之4

Table导出了一个返回Iterator的接口，通过Iterator对象，调用者就可以遍历Table的内容，它简单的返回了一个TwoLevelIterator对象。见函数实现：

Iterator* NewIterator(const ReadOptions&options) const;
{
    return NewTwoLevelIterator(
          rep_->index_block->NewIterator(rep_->options.comparator),
          &Table::BlockReader,const_cast<Table*>(this), options);
}
// 函数NewTwoLevelIterator创建了一个TwoLevelIterator对象：
Iterator* NewTwoLevelIterator(
    Iterator* index_iter,BlockFunction block_function,
    void* arg, constReadOptions& options) {
  return newTwoLevelIterator(index_iter, block_function, arg, options);
}

这里有一个函数指针BlockFunction，类型为：
typedef Iterator* (*BlockFunction)(void*, const ReadOptions&, constSlice&);
为什么叫TwoLevelIterator呢，下面就来看看。
它也是Iterator的子类，之所以叫two level应该是不仅可以迭代其中存储的对象，它还接受了一个函数BlockFunction，可以遍历存储的对象，可见它是专门为Table定制的。
我们已经知道各种Block的存储格式都是相同的，但是各自block data存储的k/v又互不相同，于是我们就需要一个途径，能够在使用同一个方式遍历不同的block时，又能解析这些k/v。这就是BlockFunction，它又返回了一个针对block data的Iterator。Block和block data存储的k/v对的key是统一的。
先来看类的主要成员变量：

  BlockFunction block_function_; // block操作函数
  void* arg_;  // BlockFunction的自定义参数
  const ReadOptions options_; // BlockFunction的read option参数
  Status status_;  // 当前状态
  IteratorWrapper index_iter_; // 遍历block的迭代器
  IteratorWrapper data_iter_; // May be NULL-遍历block data的迭代器
  // 如果data_iter_ != NULL，data_block_handle_保存的是传递给
  // block_function_的index value，以用来创建data_iter_
  std::string data_block_handle_;

下面分析一下对于Iterator几个接口的实现。
S1 对于其Key和Value接口都是返回的data_iter_对应的key和value：

  virtual bool Valid() const {
    return data_iter_.Valid();
  }
  virtual Slice key() const {
    assert(Valid());
    return data_iter_.key();
  }
  virtual Slice value() const {
    assert(Valid());
    return data_iter_.value();
  }

S2 在分析Seek系函数之前，有必要先了解下面这几个函数的用途。

  void InitDataBlock();
  void SetDataIterator(Iterator*data_iter); //设置date_iter_ = data_iter
  voidSkipEmptyDataBlocksForward();
  voidSkipEmptyDataBlocksBackward();

S2.1首先是InitDataBlock()，它是根据index_iter来初始化data_iter，当定位到新的block时，需要更新data Iterator，指向该block中k/v对的合适位置，函数如下：

  if (!index_iter_.Valid()) SetDataIterator(NULL);// index_iter非法
  else {
    Slice handle =index_iter_.value();
    if (data_iter_.iter() != NULL&& handle.compare(data_block_handle_) == 0) {
      //data_iter已经在该block data上了，无须改变
    } else { // 根据handle数据定位data iter
      Iterator* iter =(*block_function_)(arg_, options_, handle);
      data_block_handle_.assign(handle.data(), handle.size());
      SetDataIterator(iter);
    }
  }

S2.2 SkipEmptyDataBlocksForward，向前跳过空的datablock，函数实现如下：

  while (data_iter_.iter() == NULL|| !data_iter_.Valid()) { // 跳到下一个block
    if (!index_iter_.Valid()) { // 如果index iter非法，设置data iteration为NULL
      SetDataIterator(NULL);
      return;
    }
    index_iter_.Next();
    InitDataBlock();
    if (data_iter_.iter() != NULL)data_iter_.SeekToFirst(); // 跳转到开始
  }

S2.3 SkipEmptyDataBlocksBackward，向后跳过空的datablock，函数实现如下：

  while (data_iter_.iter() == NULL|| !data_iter_.Valid()) { // 跳到前一个block
    if (!index_iter_.Valid()) { // 如果index iter非法，设置data iteration为NULL
      SetDataIterator(NULL);
      return;
    }
    index_iter_.Prev();
    InitDataBlock();
    if (data_iter_.iter() != NULL)data_iter_.SeekToLast();// 跳转到开始
  }

S3 了解了几个跳转的辅助函数，再来看Seek系接口。

void TwoLevelIterator::Seek(const Slice& target) {
  index_iter_.Seek(target);
  InitDataBlock(); // 根据index iter设置data iter
  if (data_iter_.iter() != NULL)data_iter_.Seek(target); // 调整data iter跳转到target
  SkipEmptyDataBlocksForward(); // 调整iter