Home | History | Annotate | Download | only in table 
      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
    183