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