Inside Bitcoin

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(Iterator* index_iter, BlockFunction block_function,
21                   void* arg, const ReadOptions& options);
22
23  ~TwoLevelIterator() override;
24
25  void Seek(const Slice& target) override;
26  void SeekToFirst() override;
27  void SeekToLast() override;
28  void Next() override;
29  void Prev() override;
30
31  bool Valid() const override { return data_iter_.Valid(); }
32  Slice key() const override {
33    assert(Valid());
34    return data_iter_.key();
35  }
36  Slice value() const override {
37    assert(Valid());
38    return data_iter_.value();
39  }
40  Status status() const override {
41    // It'd be nice if status() returned a const Status& instead of a Status
42    if (!index_iter_.status().ok()) {
43      return index_iter_.status();
44    } else if (data_iter_.iter() != nullptr && !data_iter_.status().ok()) {
45      return data_iter_.status();
46    } else {
47      return status_;
48    }
49  }
50
51 private:
52  void SaveError(const Status& s) {
53    if (status_.ok() && !s.ok()) status_ = s;
54  }
55  void SkipEmptyDataBlocksForward();
56  void SkipEmptyDataBlocksBackward();
57  void SetDataIterator(Iterator* data_iter);
58  void InitDataBlock();
59
60  BlockFunction block_function_;
61  void* arg_;
62  const ReadOptions options_;
63  Status status_;
64  IteratorWrapper index_iter_;
65  IteratorWrapper data_iter_;  // May be nullptr
66  // If data_iter_ is non-null, then "data_block_handle_" holds the
67  // "index_value" passed to block_function_ to create the data_iter_.
68  std::string data_block_handle_;
69};
70
71TwoLevelIterator::TwoLevelIterator(Iterator* index_iter,
72                                   BlockFunction block_function, void* arg,
73                                   const ReadOptions& options)
74    : block_function_(block_function),
75      arg_(arg),
76      options_(options),
77      index_iter_(index_iter),
78      data_iter_(nullptr) {}
79
80TwoLevelIterator::~TwoLevelIterator() = default;
81
82void TwoLevelIterator::Seek(const Slice& target) {
83  index_iter_.Seek(target);
84  InitDataBlock();
85  if (data_iter_.iter() != nullptr) data_iter_.Seek(target);
86  SkipEmptyDataBlocksForward();
87}
88
89void TwoLevelIterator::SeekToFirst() {
90  index_iter_.SeekToFirst();
91  InitDataBlock();
92  if (data_iter_.iter() != nullptr) data_iter_.SeekToFirst();
93  SkipEmptyDataBlocksForward();
94}
95
96void TwoLevelIterator::SeekToLast() {
97  index_iter_.SeekToLast();
98  InitDataBlock();
99  if (data_iter_.iter() != nullptr) data_iter_.SeekToLast();
100  SkipEmptyDataBlocksBackward();
101}
102
103void TwoLevelIterator::Next() {
104  assert(Valid());
105  data_iter_.Next();
106  SkipEmptyDataBlocksForward();
107}
108
109void TwoLevelIterator::Prev() {
110  assert(Valid());
111  data_iter_.Prev();
112  SkipEmptyDataBlocksBackward();
113}
114
115void TwoLevelIterator::SkipEmptyDataBlocksForward() {
116  while (data_iter_.iter() == nullptr || !data_iter_.Valid()) {
117    // Move to next block
118    if (!index_iter_.Valid()) {
119      SetDataIterator(nullptr);
120      return;
121    }
122    index_iter_.Next();
123    InitDataBlock();
124    if (data_iter_.iter() != nullptr) data_iter_.SeekToFirst();
125  }
126}
127
128void TwoLevelIterator::SkipEmptyDataBlocksBackward() {
129  while (data_iter_.iter() == nullptr || !data_iter_.Valid()) {
130    // Move to next block
131    if (!index_iter_.Valid()) {
132      SetDataIterator(nullptr);
133      return;
134    }
135    index_iter_.Prev();
136    InitDataBlock();
137    if (data_iter_.iter() != nullptr) data_iter_.SeekToLast();
138  }
139}
140
141void TwoLevelIterator::SetDataIterator(Iterator* data_iter) {
142  if (data_iter_.iter() != nullptr) SaveError(data_iter_.status());
143  data_iter_.Set(data_iter);
144}
145
146void TwoLevelIterator::InitDataBlock() {
147  if (!index_iter_.Valid()) {
148    SetDataIterator(nullptr);
149  } else {
150    Slice handle = index_iter_.value();
151    if (data_iter_.iter() != nullptr &&
152        handle.compare(data_block_handle_) == 0) {
153      // data_iter_ is already constructed with this iterator, so
154      // no need to change anything
155    } else {
156      Iterator* iter = (*block_function_)(arg_, options_, handle);
157      data_block_handle_.assign(handle.data(), handle.size());
158      SetDataIterator(iter);
159    }
160  }
161}
162
163}  // namespace
164
165Iterator* NewTwoLevelIterator(Iterator* index_iter,
166                              BlockFunction block_function, void* arg,
167                              const ReadOptions& options) {
168  return new TwoLevelIterator(index_iter, block_function, arg, options);
169}
170
171}  // namespace leveldb
172