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 // BlockBuilder generates blocks where keys are prefix-compressed:
6 //
7 // When we store a key, we drop the prefix shared with the previous
8 // string. This helps reduce the space requirement significantly.
9 // Furthermore, once every K keys, we do not apply the prefix
10 // compression and store the entire key. We call this a "restart
11 // point". The tail end of the block stores the offsets of all of the
12 // restart points, and can be used to do a binary search when looking
13 // for a particular key. Values are stored as-is (without compression)
14 // immediately following the corresponding key.
15 //
16 // An entry for a particular key-value pair has the form:
17 // shared_bytes: varint32
18 // unshared_bytes: varint32
19 // value_length: varint32
20 // key_delta: char[unshared_bytes]
21 // value: char[value_length]
22 // shared_bytes == 0 for restart points.
23 //
24 // The trailer of the block has the form:
25 // restarts: uint32[num_restarts]
26 // num_restarts: uint32
27 // restarts[i] contains the offset within the block of the ith restart point.
28
29 #include "table/block_builder.h"
30
31 #include <algorithm>
32 #include <assert.h>
33 #include "leveldb/comparator.h"
34 #include "leveldb/table_builder.h"
35 #include "util/coding.h"
36
37 namespace leveldb {
38
BlockBuilder(const Options * options)39 BlockBuilder::BlockBuilder(const Options* options)
40 : options_(options),
41 restarts_(),
42 counter_(0),
43 finished_(false) {
44 assert(options->block_restart_interval >= 1);
45 restarts_.push_back(0); // First restart point is at offset 0
46 }
47
Reset()48 void BlockBuilder::Reset() {
49 buffer_.clear();
50 restarts_.clear();
51 restarts_.push_back(0); // First restart point is at offset 0
52 counter_ = 0;
53 finished_ = false;
54 last_key_.clear();
55 }
56
CurrentSizeEstimate() const57 size_t BlockBuilder::CurrentSizeEstimate() const {
58 return (buffer_.size() + // Raw data buffer
59 restarts_.size() * sizeof(uint32_t) + // Restart array
60 sizeof(uint32_t)); // Restart array length
61 }
62
Finish()63 Slice BlockBuilder::Finish() {
64 // Append restart array
65 for (size_t i = 0; i < restarts_.size(); i++) {
66 PutFixed32(&buffer_, restarts_[i]);
67 }
68 PutFixed32(&buffer_, restarts_.size());
69 finished_ = true;
70 return Slice(buffer_);
71 }
72
Add(const Slice & key,const Slice & value)73 void BlockBuilder::Add(const Slice& key, const Slice& value) {
74 Slice last_key_piece(last_key_);
75 assert(!finished_);
76 assert(counter_ <= options_->block_restart_interval);
77 assert(buffer_.empty() // No values yet?
78 || options_->comparator->Compare(key, last_key_piece) > 0);
79 size_t shared = 0;
80 if (counter_ < options_->block_restart_interval) {
81 // See how much sharing to do with previous string
82 const size_t min_length = std::min(last_key_piece.size(), key.size());
83 while ((shared < min_length) && (last_key_piece[shared] == key[shared])) {
84 shared++;
85 }
86 } else {
87 // Restart compression
88 restarts_.push_back(buffer_.size());
89 counter_ = 0;
90 }
91 const size_t non_shared = key.size() - shared;
92
93 // Add "<shared><non_shared><value_size>" to buffer_
94 PutVarint32(&buffer_, shared);
95 PutVarint32(&buffer_, non_shared);
96 PutVarint32(&buffer_, value.size());
97
98 // Add string delta to buffer_ followed by value
99 buffer_.append(key.data() + shared, non_shared);
100 buffer_.append(value.data(), value.size());
101
102 // Update state
103 last_key_.resize(shared);
104 last_key_.append(key.data() + shared, non_shared);
105 assert(Slice(last_key_) == key);
106 counter_++;
107 }
108
109 } // namespace leveldb
110