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.
5
// BlockBuilder generates blocks where keys are prefix-compressed:
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.
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.
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.
29
#include "table/block_builder.h"
33
#include "leveldb/comparator.h"
34
#include "leveldb/table_builder.h"
35
#include "util/coding.h"
39
BlockBuilder::BlockBuilder(const Options* options)
44
assert(options->block_restart_interval >= 1);
45
restarts_.push_back(0); // First restart point is at offset 0
48
void BlockBuilder::Reset() {
51
restarts_.push_back(0); // First restart point is at offset 0
57
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
63
Slice BlockBuilder::Finish() {
64
// Append restart array
65
for (size_t i = 0; i < restarts_.size(); i++) {
66
PutFixed32(&buffer_, restarts_[i]);
68
PutFixed32(&buffer_, restarts_.size());
70
return Slice(buffer_);
73
void BlockBuilder::Add(const Slice& key, const Slice& value) {
74
Slice last_key_piece(last_key_);
76
assert(counter_ <= options_->block_restart_interval);
77
assert(buffer_.empty() // No values yet?
78
|| options_->comparator->Compare(key, last_key_piece) > 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])) {
87
// Restart compression
88
restarts_.push_back(buffer_.size());
91
const size_t non_shared = key.size() - shared;
93
// Add "<shared><non_shared><value_size>" to buffer_
94
PutVarint32(&buffer_, shared);
95
PutVarint32(&buffer_, non_shared);
96
PutVarint32(&buffer_, value.size());
98
// Add string delta to buffer_ followed by value
99
buffer_.append(key.data() + shared, non_shared);
100
buffer_.append(value.data(), value.size());
103
last_key_.resize(shared);
104
last_key_.append(key.data() + shared, non_shared);
105
assert(Slice(last_key_) == key);
109
} // namespace leveldb
added
removed
cppForSwig/leveldb/table/block_builder.cc
