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 "leveldb/table.h"
6
7#include <map>
8#include <string>
9
10#include "db/dbformat.h"
11#include "db/memtable.h"
12#include "db/write_batch_internal.h"
13#include "leveldb/db.h"
14#include "leveldb/env.h"
15#include "leveldb/iterator.h"
16#include "leveldb/table_builder.h"
17#include "table/block.h"
18#include "table/block_builder.h"
19#include "table/format.h"
20#include "util/random.h"
21#include "util/testharness.h"
22#include "util/testutil.h"
23
24namespace leveldb {
25
26// Return reverse of "key".
27// Used to test non-lexicographic comparators.
28static std::string Reverse(const Slice& key) {
29  std::string str(key.ToString());
30  std::string rev("");
31  for (std::string::reverse_iterator rit = str.rbegin(); rit != str.rend();
32       ++rit) {
33    rev.push_back(*rit);
34  }
35  return rev;
36}
37
38namespace {
39class ReverseKeyComparator : public Comparator {
40 public:
41  const char* Name() const override {
42    return "leveldb.ReverseBytewiseComparator";
43  }
44
45  int Compare(const Slice& a, const Slice& b) const override {
46    return BytewiseComparator()->Compare(Reverse(a), Reverse(b));
47  }
48
49  void FindShortestSeparator(std::string* start,
50                             const Slice& limit) const override {
51    std::string s = Reverse(*start);
52    std::string l = Reverse(limit);
53    BytewiseComparator()->FindShortestSeparator(&s, l);
54    *start = Reverse(s);
55  }
56
57  void FindShortSuccessor(std::string* key) const override {
58    std::string s = Reverse(*key);
59    BytewiseComparator()->FindShortSuccessor(&s);
60    *key = Reverse(s);
61  }
62};
63}  // namespace
64static ReverseKeyComparator reverse_key_comparator;
65
66static void Increment(const Comparator* cmp, std::string* key) {
67  if (cmp == BytewiseComparator()) {
68    key->push_back('\0');
69  } else {
70    assert(cmp == &reverse_key_comparator);
71    std::string rev = Reverse(*key);
72    rev.push_back('\0');
73    *key = Reverse(rev);
74  }
75}
76
77// An STL comparator that uses a Comparator
78namespace {
79struct STLLessThan {
80  const Comparator* cmp;
81
82  STLLessThan() : cmp(BytewiseComparator()) {}
83  STLLessThan(const Comparator* c) : cmp(c) {}
84  bool operator()(const std::string& a, const std::string& b) const {
85    return cmp->Compare(Slice(a), Slice(b)) < 0;
86  }
87};
88}  // namespace
89
90class StringSink : public WritableFile {
91 public:
92  ~StringSink() override = default;
93
94  const std::string& contents() const { return contents_; }
95
96  Status Close() override { return Status::OK(); }
97  Status Flush() override { return Status::OK(); }
98  Status Sync() override { return Status::OK(); }
99
100  Status Append(const Slice& data) override {
101    contents_.append(data.data(), data.size());
102    return Status::OK();
103  }
104
105  std::string GetName() const override { return ""; }
106 private:
107  std::string contents_;
108};
109
110class StringSource : public RandomAccessFile {
111 public:
112  StringSource(const Slice& contents)
113      : contents_(contents.data(), contents.size()) {}
114
115  ~StringSource() override = default;
116
117  uint64_t Size() const { return contents_.size(); }
118
119  Status Read(uint64_t offset, size_t n, Slice* result,
120              char* scratch) const override {
121    if (offset >= contents_.size()) {
122      return Status::InvalidArgument("invalid Read offset");
123    }
124    if (offset + n > contents_.size()) {
125      n = contents_.size() - offset;
126    }
127    memcpy(scratch, &contents_[offset], n);
128    *result = Slice(scratch, n);
129    return Status::OK();
130  }
131
132  std::string GetName() const override { return ""; }
133 private:
134  std::string contents_;
135};
136
137typedef std::map<std::string, std::string, STLLessThan> KVMap;
138
139// Helper class for tests to unify the interface between
140// BlockBuilder/TableBuilder and Block/Table.
141class Constructor {
142 public:
143  explicit Constructor(const Comparator* cmp) : data_(STLLessThan(cmp)) {}
144  virtual ~Constructor() = default;
145
146  void Add(const std::string& key, const Slice& value) {
147    data_[key] = value.ToString();
148  }
149
150  // Finish constructing the data structure with all the keys that have
151  // been added so far.  Returns the keys in sorted order in "*keys"
152  // and stores the key/value pairs in "*kvmap"
153  void Finish(const Options& options, std::vector<std::string>* keys,
154              KVMap* kvmap) {
155    *kvmap = data_;
156    keys->clear();
157    for (const auto& kvp : data_) {
158      keys->push_back(kvp.first);
159    }
160    data_.clear();
161    Status s = FinishImpl(options, *kvmap);
162    ASSERT_TRUE(s.ok()) << s.ToString();
163  }
164
165  // Construct the data structure from the data in "data"
166  virtual Status FinishImpl(const Options& options, const KVMap& data) = 0;
167
168  virtual Iterator* NewIterator() const = 0;
169
170  const KVMap& data() const { return data_; }
171
172  virtual DB* db() const { return nullptr; }  // Overridden in DBConstructor
173
174 private:
175  KVMap data_;
176};
177
178class BlockConstructor : public Constructor {
179 public:
180  explicit BlockConstructor(const Comparator* cmp)
181      : Constructor(cmp), comparator_(cmp), block_(nullptr) {}
182  ~BlockConstructor() override { delete block_; }
183  Status FinishImpl(const Options& options, const KVMap& data) override {
184    delete block_;
185    block_ = nullptr;
186    BlockBuilder builder(&options);
187
188    for (const auto& kvp : data) {
189      builder.Add(kvp.first, kvp.second);
190    }
191    // Open the block
192    data_ = builder.Finish().ToString();
193    BlockContents contents;
194    contents.data = data_;
195    contents.cachable = false;
196    contents.heap_allocated = false;
197    block_ = new Block(contents);
198    return Status::OK();
199  }
200  Iterator* NewIterator() const override {
201    return block_->NewIterator(comparator_);
202  }
203
204 private:
205  const Comparator* const comparator_;
206  std::string data_;
207  Block* block_;
208
209  BlockConstructor();
210};
211
212class TableConstructor : public Constructor {
213 public:
214  TableConstructor(const Comparator* cmp)
215      : Constructor(cmp), source_(nullptr), table_(nullptr) {}
216  ~TableConstructor() override { Reset(); }
217  Status FinishImpl(const Options& options, const KVMap& data) override {
218    Reset();
219    StringSink sink;
220    TableBuilder builder(options, &sink);
221
222    for (const auto& kvp : data) {
223      builder.Add(kvp.first, kvp.second);
224      ASSERT_TRUE(builder.status().ok());
225    }
226    Status s = builder.Finish();
227    ASSERT_TRUE(s.ok()) << s.ToString();
228
229    ASSERT_EQ(sink.contents().size(), builder.FileSize());
230
231    // Open the table
232    source_ = new StringSource(sink.contents());
233    Options table_options;
234    table_options.comparator = options.comparator;
235    return Table::Open(table_options, source_, sink.contents().size(), &table_);
236  }
237
238  Iterator* NewIterator() const override {
239    return table_->NewIterator(ReadOptions());
240  }
241
242  uint64_t ApproximateOffsetOf(const Slice& key) const {
243    return table_->ApproximateOffsetOf(key);
244  }
245
246 private:
247  void Reset() {
248    delete table_;
249    delete source_;
250    table_ = nullptr;