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