Branch data Line data Source code
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_builder.h"
6 : :
7 : : #include <assert.h>
8 : :
9 : : #include "leveldb/comparator.h"
10 : : #include "leveldb/env.h"
11 : : #include "leveldb/filter_policy.h"
12 : : #include "leveldb/options.h"
13 : : #include "table/block_builder.h"
14 : : #include "table/filter_block.h"
15 : : #include "table/format.h"
16 : : #include "util/coding.h"
17 : : #include "util/crc32c.h"
18 : :
19 : : namespace leveldb {
20 : :
21 : : struct TableBuilder::Rep {
22 : 74 : Rep(const Options& opt, WritableFile* f)
23 : 74 : : options(opt),
24 : 74 : index_block_options(opt),
25 : 74 : file(f),
26 : 74 : offset(0),
27 : : data_block(&options),
28 [ + - ]: 74 : index_block(&index_block_options),
29 : 74 : num_entries(0),
30 : 74 : closed(false),
31 : 148 : filter_block(opt.filter_policy == nullptr
32 [ + - ]: 74 : ? nullptr
33 [ + - + - ]: 74 : : new FilterBlockBuilder(opt.filter_policy)),
34 [ + - + - ]: 222 : pending_index_entry(false) {
35 : 74 : index_block_options.block_restart_interval = 1;
36 [ - - ]: 74 : }
37 : :
38 : : Options options;
39 : : Options index_block_options;
40 : : WritableFile* file;
41 : : uint64_t offset;
42 : : Status status;
43 : : BlockBuilder data_block;
44 : : BlockBuilder index_block;
45 : : std::string last_key;
46 : : int64_t num_entries;
47 : : bool closed; // Either Finish() or Abandon() has been called.
48 : : FilterBlockBuilder* filter_block;
49 : :
50 : : // We do not emit the index entry for a block until we have seen the
51 : : // first key for the next data block. This allows us to use shorter
52 : : // keys in the index block. For example, consider a block boundary
53 : : // between the keys "the quick brown fox" and "the who". We can use
54 : : // "the r" as the key for the index block entry since it is >= all
55 : : // entries in the first block and < all entries in subsequent
56 : : // blocks.
57 : : //
58 : : // Invariant: r->pending_index_entry is true only if data_block is empty.
59 : : bool pending_index_entry;
60 : : BlockHandle pending_handle; // Handle to add to index block
61 : :
62 : : std::string compressed_output;
63 : : };
64 : :
65 : 74 : TableBuilder::TableBuilder(const Options& options, WritableFile* file)
66 [ + - ]: 74 : : rep_(new Rep(options, file)) {
67 [ + - ]: 74 : if (rep_->filter_block != nullptr) {
68 : 74 : rep_->filter_block->StartBlock(0);
69 : : }
70 : 74 : }
71 : :
72 : 74 : TableBuilder::~TableBuilder() {
73 [ - + ]: 74 : assert(rep_->closed); // Catch errors where caller forgot to call Finish()
74 [ + - ]: 74 : delete rep_->filter_block;
75 [ + - ]: 74 : delete rep_;
76 : 74 : }
77 : :
78 : 0 : Status TableBuilder::ChangeOptions(const Options& options) {
79 : : // Note: if more fields are added to Options, update
80 : : // this function to catch changes that should not be allowed to
81 : : // change in the middle of building a Table.
82 [ # # ]: 0 : if (options.comparator != rep_->options.comparator) {
83 : 0 : return Status::InvalidArgument("changing comparator while building table");
84 : : }
85 : :
86 : : // Note that any live BlockBuilders point to rep_->options and therefore
87 : : // will automatically pick up the updated options.
88 : 0 : rep_->options = options;
89 : 0 : rep_->index_block_options = options;
90 : 0 : rep_->index_block_options.block_restart_interval = 1;
91 : 0 : return Status::OK();
92 : : }
93 : :
94 : 28387 : void TableBuilder::Add(const Slice& key, const Slice& value) {
95 : 28387 : Rep* r = rep_;
96 [ - + ]: 28387 : assert(!r->closed);
97 [ + - ]: 28387 : if (!ok()) return;
98 [ + + ]: 28387 : if (r->num_entries > 0) {
99 [ - + - + ]: 28313 : assert(r->options.comparator->Compare(key, Slice(r->last_key)) > 0);
100 : : }
101 : :
102 [ + + ]: 28387 : if (r->pending_index_entry) {
103 [ - + ]: 345 : assert(r->data_block.empty());
104 : 345 : r->options.comparator->FindShortestSeparator(&r->last_key, key);
105 [ + - ]: 345 : std::string handle_encoding;
106 [ + - ]: 345 : r->pending_handle.EncodeTo(&handle_encoding);
107 [ - + - + : 345 : r->index_block.Add(r->last_key, Slice(handle_encoding));
+ - ]
108 : 345 : r->pending_index_entry = false;
109 : 345 : }
110 : :
111 [ + - ]: 28387 : if (r->filter_block != nullptr) {
112 : 28387 : r->filter_block->AddKey(key);
113 : : }
114 : :
115 : 28387 : r->last_key.assign(key.data(), key.size());
116 : 28387 : r->num_entries++;
117 : 28387 : r->data_block.Add(key, value);
118 : :
119 : 28387 : const size_t estimated_block_size = r->data_block.CurrentSizeEstimate();
120 [ + + ]: 28387 : if (estimated_block_size >= r->options.block_size) {
121 : 346 : Flush();
122 : : }
123 : : }
124 : :
125 : 419 : void TableBuilder::Flush() {
126 : 419 : Rep* r = rep_;
127 [ - + ]: 419 : assert(!r->closed);
128 [ + - ]: 419 : if (!ok()) return;
129 [ + + ]: 419 : if (r->data_block.empty()) return;
130 [ - + ]: 418 : assert(!r->pending_index_entry);
131 : 418 : WriteBlock(&r->data_block, &r->pending_handle);
132 [ + - ]: 418 : if (ok()) {
133 : 418 : r->pending_index_entry = true;
134 [ - + ]: 418 : r->status = r->file->Flush();
135 : : }
136 [ + - ]: 418 : if (r->filter_block != nullptr) {
137 : 418 : r->filter_block->StartBlock(r->offset);
138 : : }
139 : : }
140 : :
141 : 564 : void TableBuilder::WriteBlock(BlockBuilder* block, BlockHandle* handle) {
142 : : // File format contains a sequence of blocks where each block has:
143 : : // block_data: uint8[n]
144 : : // type: uint8
145 : : // crc: uint32
146 [ - + ]: 564 : assert(ok());
147 : 564 : Rep* r = rep_;
148 : 564 : Slice raw = block->Finish();
149 : :
150 [ + - - ]: 564 : Slice block_contents;
151 : 564 : CompressionType type = r->options.compression;
152 : : // TODO(postrelease): Support more compression options: zlib?
153 [ + - - ]: 564 : switch (type) {
154 : 564 : case kNoCompression:
155 : 564 : block_contents = raw;
156 : 564 : break;
157 : :
158 : 0 : case kSnappyCompression: {
159 : 0 : std::string* compressed = &r->compressed_output;
160 : 0 : if (port::Snappy_Compress(raw.data(), raw.size(), compressed) &&
161 : : compressed->size() < raw.size() - (raw.size() / 8u)) {
162 : : block_contents = *compressed;
163 : : } else {
164 : : // Snappy not supported, or compressed less than 12.5%, so just
165 : : // store uncompressed form
166 : 0 : block_contents = raw;
167 : 0 : type = kNoCompression;
168 : : }
169 : : break;
170 : : }
171 : : }
172 : 564 : WriteRawBlock(block_contents, type, handle);
173 : 564 : r->compressed_output.clear();
174 : 564 : block->Reset();
175 : 564 : }
176 : :
177 : 637 : void TableBuilder::WriteRawBlock(const Slice& block_contents,
178 : : CompressionType type, BlockHandle* handle) {
179 : 637 : Rep* r = rep_;
180 : 637 : handle->set_offset(r->offset);
181 : 637 : handle->set_size(block_contents.size());
182 [ - + ]: 637 : r->status = r->file->Append(block_contents);
183 [ + - ]: 637 : if (r->status.ok()) {
184 : 637 : char trailer[kBlockTrailerSize];
185 : 637 : trailer[0] = type;
186 : 637 : uint32_t crc = crc32c::Value(block_contents.data(), block_contents.size());
187 : 637 : crc = crc32c::Extend(crc, trailer, 1); // Extend crc to cover block type
188 : 637 : EncodeFixed32(trailer + 1, crc32c::Mask(crc));
189 [ - + ]: 637 : r->status = r->file->Append(Slice(trailer, kBlockTrailerSize));
190 [ + - ]: 637 : if (r->status.ok()) {
191 : 637 : r->offset += block_contents.size() + kBlockTrailerSize;
192 : : }
193 : : }
194 : 637 : }
195 : :
196 [ - + ]: 30080 : Status TableBuilder::status() const { return rep_->status; }
197 : :
198 : 73 : Status TableBuilder::Finish() {
199 : 73 : Rep* r = rep_;
200 : 73 : Flush();
201 [ - + ]: 73 : assert(!r->closed);
202 : 73 : r->closed = true;
203 : :
204 : 73 : BlockHandle filter_block_handle, metaindex_block_handle, index_block_handle;
205 : :
206 : : // Write filter block
207 [ + - + - ]: 73 : if (ok() && r->filter_block != nullptr) {
208 : 73 : WriteRawBlock(r->filter_block->Finish(), kNoCompression,
209 : : &filter_block_handle);
210 : : }
211 : :
212 : : // Write metaindex block
213 [ + - ]: 73 : if (ok()) {
214 : 73 : BlockBuilder meta_index_block(&r->options);
215 [ + - ]: 73 : if (r->filter_block != nullptr) {
216 : : // Add mapping from "filter.Name" to location of filter data
217 [ + - ]: 73 : std::string key = "filter.";
218 [ + - + - ]: 73 : key.append(r->options.filter_policy->Name());
219 [ + - ]: 73 : std::string handle_encoding;
220 [ + - ]: 73 : filter_block_handle.EncodeTo(&handle_encoding);
221 [ - + - + : 73 : meta_index_block.Add(key, handle_encoding);
+ - ]
222 : 73 : }
223 : :
224 : : // TODO(postrelease): Add stats and other meta blocks
225 [ + - ]: 73 : WriteBlock(&meta_index_block, &metaindex_block_handle);
226 : 73 : }
227 : :
228 : : // Write index block
229 [ + - ]: 73 : if (ok()) {
230 [ + - ]: 73 : if (r->pending_index_entry) {
231 : 73 : r->options.comparator->FindShortSuccessor(&r->last_key);
232 [ + - ]: 73 : std::string handle_encoding;
233 [ + - ]: 73 : r->pending_handle.EncodeTo(&handle_encoding);
234 [ - + - + : 73 : r->index_block.Add(r->last_key, Slice(handle_encoding));
+ - ]
235 : 73 : r->pending_index_entry = false;
236 : 73 : }
237 : 73 : WriteBlock(&r->index_block, &index_block_handle);
238 : : }
239 : :
240 : : // Write footer
241 [ + - ]: 73 : if (ok()) {
242 [ + - ]: 73 : Footer footer;
243 [ + - ]: 73 : footer.set_metaindex_handle(metaindex_block_handle);
244 [ + - ]: 73 : footer.set_index_handle(index_block_handle);
245 [ + - ]: 73 : std::string footer_encoding;
246 [ + - ]: 73 : footer.EncodeTo(&footer_encoding);
247 [ - + + - : 73 : r->status = r->file->Append(footer_encoding);
- + ]
248 [ + - ]: 73 : if (r->status.ok()) {
249 [ - + ]: 73 : r->offset += footer_encoding.size();
250 : : }
251 : 73 : }
252 [ - + ]: 73 : return r->status;
253 : : }
254 : :
255 : 1 : void TableBuilder::Abandon() {
256 : 1 : Rep* r = rep_;
257 [ - + ]: 1 : assert(!r->closed);
258 : 1 : r->closed = true;
259 : 1 : }
260 : :
261 : 1412 : uint64_t TableBuilder::NumEntries() const { return rep_->num_entries; }
262 : :
263 : 1474 : uint64_t TableBuilder::FileSize() const { return rep_->offset; }
264 : :
265 : : } // namespace leveldb
|
