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// 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 <assert.h>
32
33#include <algorithm>
34
35#include "leveldb/comparator.h"
36#include "leveldb/options.h"
37#include "util/coding.h"
38
39namespace leveldb {
40
41BlockBuilder::BlockBuilder(const Options* options)
42    : options_(options), restarts_(), counter_(0), finished_(false) {
43  assert(options->block_restart_interval >= 1);
44  restarts_.push_back(0);  // First restart point is at offset 0
45}
46
47void BlockBuilder::Reset() {
48  buffer_.clear();
49  restarts_.clear();
50  restarts_.push_back(0);  // First restart point is at offset 0
51  counter_ = 0;
52  finished_ = false;
53  last_key_.clear();
54}
55
56size_t BlockBuilder::CurrentSizeEstimate() const {
57  return (buffer_.size() +                       // Raw data buffer
58          restarts_.size() * sizeof(uint32_t) +  // Restart array
59          sizeof(uint32_t));                     // Restart array length
60}
61
62Slice BlockBuilder::Finish() {
63  // Append restart array
64  for (size_t i = 0; i < restarts_.size(); i++) {
65    PutFixed32(&buffer_, restarts_[i]);
66  }
67  PutFixed32(&buffer_, restarts_.size());
68  finished_ = true;
69  return Slice(buffer_);
70}
71
72void BlockBuilder::Add(const Slice& key, const Slice& value) {
73  Slice last_key_piece(last_key_);
74  assert(!finished_);
75  assert(counter_ <= options_->block_restart_interval);
76  assert(buffer_.empty()  // No values yet?
77         || options_->comparator->Compare(key, last_key_piece) > 0);
78  size_t shared = 0;
79  if (counter_ < options_->block_restart_interval) {
80    // See how much sharing to do with previous string
81    const size_t min_length = std::min(last_key_piece.size(), key.size());
82    while ((shared < min_length) && (last_key_piece[shared] == key[shared])) {
83      shared++;
84    }
85  } else {
86    // Restart compression
87    restarts_.push_back(buffer_.size());
88    counter_ = 0;
89  }
90  const size_t non_shared = key.size() - shared;
91
92  // Add "<shared><non_shared><value_size>" to buffer_
93  PutVarint32(&buffer_, shared);
94  PutVarint32(&buffer_, non_shared);
95  PutVarint32(&buffer_, value.size());
96
97  // Add string delta to buffer_ followed by value
98  buffer_.append(key.data() + shared, non_shared);
99  buffer_.append(value.data(), value.size());
100
101  // Update state
102  last_key_.resize(shared);
103  last_key_.append(key.data() + shared, non_shared);
104  assert(Slice(last_key_) == key);
105  counter_++;
106}
107
108}  // namespace leveldb
109