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
12namespace leveldb {
13
14namespace {
15
16typedef Iterator* (*BlockFunction)(void*, const ReadOptions&, const Slice&);
17
18class 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
76TwoLevelIterator::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
88TwoLevelIterator::~TwoLevelIterator() {
89}
90
91void 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
98void TwoLevelIterator::SeekToFirst() {
99  index_iter_.SeekToFirst();
100  InitDataBlock();
101  if (data_iter_.iter() != NULL) data_iter_.SeekToFirst();
102  SkipEmptyDataBlocksForward();
103}
104
105void TwoLevelIterator::SeekToLast() {
106  index_iter_.SeekToLast();
107  InitDataBlock();
108  if (data_iter_.iter() != NULL) data_iter_.SeekToLast();
109  SkipEmptyDataBlocksBackward();
110}
111
112void TwoLevelIterator::Next() {
113  assert(Valid());
114  data_iter_.Next();
115  SkipEmptyDataBlocksForward();
116}
117
118void TwoLevelIterator::Prev() {
119  assert(Valid());
120  data_iter_.Prev();
121  SkipEmptyDataBlocksBackward();
122}
123
124
125void 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
138void 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
151void TwoLevelIterator::SetDataIterator(Iterator* data_iter) {
152  if (data_iter_.iter() != NULL) SaveError(data_iter_.status());
153  data_iter_.Set(data_iter);
154}
155
156void 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
174Iterator* 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