src/leveldb/table/block_builder.cc

   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
  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
  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
  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
  61 }
  62
  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
  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