src/leveldb/table/two_level_iterator.cc

   1 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file. See the AUTHORS file for names of contributors.
   4
   5 #include "table/two_level_iterator.h"
   6
   7 #include "leveldb/table.h"
   8 #include "table/block.h"
   9 #include "table/format.h"
  10 #include "table/iterator_wrapper.h"
  11
  12 namespace leveldb {
  13
  14 namespace {
  15
  16 typedef Iterator* (*BlockFunction)(void*, const ReadOptions&, const Slice&);
  17
  18 class TwoLevelIterator: public Iterator {
  19  public:
  20   TwoLevelIterator(
  21     Iterator* index_iter,
  22     BlockFunction block_function,
  23     void* arg,
  24     const ReadOptions& options);
  25
  26   virtual ~TwoLevelIterator();
  27
  28   virtual void Seek(const Slice& target);
  29   virtual void SeekToFirst();
  30   virtual void SeekToLast();
  31   virtual void Next();
  32   virtual void Prev();
  33
  34   virtual bool Valid() const {
  35     return data_iter_.Valid();
  36   }
  37   virtual Slice key() const {
  38     assert(Valid());
  39     return data_iter_.key();
  40   }
  41   virtual Slice value() const {
  42     assert(Valid());
  43     return data_iter_.value();
  44   }
  45   virtual Status status() const {
  46     // It'd be nice if status() returned a const Status& instead of a Status
  47     if (!index_iter_.status().ok()) {
  48       return index_iter_.status();
  49     } else if (data_iter_.iter() != NULL && !data_iter_.status().ok()) {
  50       return data_iter_.status();
  51     } else {
  52       return status_;
  53     }
  54   }
  55
  56  private:
  57   void SaveError(const Status& s) {
  58     if (status_.ok() && !s.ok()) status_ = s;
  59   }
  60   void SkipEmptyDataBlocksForward();
  61   void SkipEmptyDataBlocksBackward();
  62   void SetDataIterator(Iterator* data_iter);
  63   void InitDataBlock();
  64
  65   BlockFunction block_function_;
  66   void* arg_;
  67   const ReadOptions options_;
  68   Status status_;
  69   IteratorWrapper index_iter_;
  70   IteratorWrapper data_iter_; // May be NULL
  71   // If data_iter_ is non-NULL, then "data_block_handle_" holds the
  72   // "index_value" passed to block_function_ to create the data_iter_.
  73   std::string data_block_handle_;
  74 };
  75
  76 TwoLevelIterator::TwoLevelIterator(
  77     Iterator* index_iter,
  78     BlockFunction block_function,
  79     void* arg,
  80     const ReadOptions& options)
  81     : block_function_(block_function),
  82       arg_(arg),
  83       options_(options),
  84       index_iter_(index_iter),
  85       data_iter_(NULL) {
  86 }
  87
  88 TwoLevelIterator::~TwoLevelIterator() {
  89 }
  90
  91 void TwoLevelIterator::Seek(const Slice& target) {
  92   index_iter_.Seek(target);
  93   InitDataBlock();
  94   if (data_iter_.iter() != NULL) data_iter_.Seek(target);
  95   SkipEmptyDataBlocksForward();
  96 }
  97
  98 void TwoLevelIterator::SeekToFirst() {
  99   index_iter_.SeekToFirst();
 100   InitDataBlock();
 101   if (data_iter_.iter() != NULL) data_iter_.SeekToFirst();
 102   SkipEmptyDataBlocksForward();
 103 }
 104
 105 void TwoLevelIterator::SeekToLast() {
 106   index_iter_.SeekToLast();
 107   InitDataBlock();
 108   if (data_iter_.iter() != NULL) data_iter_.SeekToLast();
 109   SkipEmptyDataBlocksBackward();
 110 }
 111
 112 void TwoLevelIterator::Next() {
 113   assert(Valid());
 114   data_iter_.Next();
 115   SkipEmptyDataBlocksForward();
 116 }
 117
 118 void TwoLevelIterator::Prev() {
 119   assert(Valid());
 120   data_iter_.Prev();
 121   SkipEmptyDataBlocksBackward();
 122 }
 123
 124
 125 void TwoLevelIterator::SkipEmptyDataBlocksForward() {
 126   while (data_iter_.iter() == NULL || !data_iter_.Valid()) {
 127     // Move to next block
 128     if (!index_iter_.Valid()) {
 129       SetDataIterator(NULL);
 130       return;
 131     }
 132     index_iter_.Next();
 133     InitDataBlock();
 134     if (data_iter_.iter() != NULL) data_iter_.SeekToFirst();
 135   }
 136 }
 137
 138 void TwoLevelIterator::SkipEmptyDataBlocksBackward() {
 139   while (data_iter_.iter() == NULL || !data_iter_.Valid()) {
 140     // Move to next block
 141     if (!index_iter_.Valid()) {
 142       SetDataIterator(NULL);
 143       return;
 144     }
 145     index_iter_.Prev();
 146     InitDataBlock();
 147     if (data_iter_.iter() != NULL) data_iter_.SeekToLast();
 148   }
 149 }
 150
 151 void TwoLevelIterator::SetDataIterator(Iterator* data_iter) {
 152   if (data_iter_.iter() != NULL) SaveError(data_iter_.status());
 153   data_iter_.Set(data_iter);
 154 }
 155
 156 void TwoLevelIterator::InitDataBlock() {
 157   if (!index_iter_.Valid()) {
 158     SetDataIterator(NULL);
 159   } else {
 160     Slice handle = index_iter_.value();
 161     if (data_iter_.iter() != NULL && handle.compare(data_block_handle_) == 0) {
 162       // data_iter_ is already constructed with this iterator, so
 163       // no need to change anything
 164     } else {
 165       Iterator* iter = (*block_function_)(arg_, options_, handle);
 166       data_block_handle_.assign(handle.data(), handle.size());
 167       SetDataIterator(iter);
 168     }
 169   }
 170 }
 171
 172 }  // namespace
 173
 174 Iterator* NewTwoLevelIterator(
 175     Iterator* index_iter,
 176     BlockFunction block_function,
 177     void* arg,
 178     const ReadOptions& options) {
 179   return new TwoLevelIterator(index_iter, block_function, arg, options);
 180 }
 181
 182 }  // namespace leveldb