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             : #include "db/memtable.h"
       6             : #include "db/dbformat.h"
       7             : #include "leveldb/comparator.h"
       8             : #include "leveldb/env.h"
       9             : #include "leveldb/iterator.h"
      10             : #include "util/coding.h"
      11             : 
      12             : namespace leveldb {
      13             : 
      14             : static Slice GetLengthPrefixedSlice(const char* data) {
      15             :   uint32_t len;
      16      766904 :   const char* p = data;
      17      766904 :   p = GetVarint32Ptr(p, p + 5, &len);  // +5: we assume "p" is not corrupted
      18      766904 :   return Slice(p, len);
      19             : }
      20             : 
      21         359 : MemTable::MemTable(const InternalKeyComparator& cmp)
      22             :     : comparator_(cmp),
      23             :       refs_(0),
      24        1436 :       table_(comparator_, &arena_) {
      25         359 : }
      26             : 
      27        1077 : MemTable::~MemTable() {
      28         359 :   assert(refs_ == 0);
      29         359 : }
      30             : 
      31        1668 : size_t MemTable::ApproximateMemoryUsage() { return arena_.MemoryUsage(); }
      32             : 
      33      358314 : int MemTable::KeyComparator::operator()(const char* aptr, const char* bptr)
      34             :     const {
      35             :   // Internal keys are encoded as length-prefixed strings.
      36      358314 :   Slice a = GetLengthPrefixedSlice(aptr);
      37      358314 :   Slice b = GetLengthPrefixedSlice(bptr);
      38      358314 :   return comparator.Compare(a, b);
      39             : }
      40             : 
      41             : // Encode a suitable internal key target for "target" and return it.
      42             : // Uses *scratch as scratch space, and the returned pointer will point
      43             : // into this scratch space.
      44          93 : static const char* EncodeKey(std::string* scratch, const Slice& target) {
      45             :   scratch->clear();
      46          93 :   PutVarint32(scratch, target.size());
      47          93 :   scratch->append(target.data(), target.size());
      48          93 :   return scratch->data();
      49             : }
      50             : 
      51         822 : class MemTableIterator: public Iterator {
      52             :  public:
      53         548 :   explicit MemTableIterator(MemTable::Table* table) : iter_(table) { }
      54             : 
      55       34332 :   virtual bool Valid() const { return iter_.Valid(); }
      56         186 :   virtual void Seek(const Slice& k) { iter_.Seek(EncodeKey(&tmp_, k)); }
      57         362 :   virtual void SeekToFirst() { iter_.SeekToFirst(); }
      58           0 :   virtual void SeekToLast() { iter_.SeekToLast(); }
      59       16718 :   virtual void Next() { iter_.Next(); }
      60           0 :   virtual void Prev() { iter_.Prev(); }
      61       50499 :   virtual Slice key() const { return GetLengthPrefixedSlice(iter_.key()); }
      62       16718 :   virtual Slice value() const {
      63       50154 :     Slice key_slice = GetLengthPrefixedSlice(iter_.key());
      64       33436 :     return GetLengthPrefixedSlice(key_slice.data() + key_slice.size());
      65             :   }
      66             : 
      67         230 :   virtual Status status() const { return Status::OK(); }
      68             : 
      69             :  private:
      70             :   MemTable::Table::Iterator iter_;
      71             :   std::string tmp_;       // For passing to EncodeKey
      72             : 
      73             :   // No copying allowed
      74             :   MemTableIterator(const MemTableIterator&);
      75             :   void operator=(const MemTableIterator&);
      76             : };
      77             : 
      78         274 : Iterator* MemTable::NewIterator() {
      79         548 :   return new MemTableIterator(&table_);
      80             : }
      81             : 
      82       28549 : void MemTable::Add(SequenceNumber s, ValueType type,
      83             :                    const Slice& key,
      84             :                    const Slice& value) {
      85             :   // Format of an entry is concatenation of:
      86             :   //  key_size     : varint32 of internal_key.size()
      87             :   //  key bytes    : char[internal_key.size()]
      88             :   //  value_size   : varint32 of value.size()
      89             :   //  value bytes  : char[value.size()]
      90       28549 :   size_t key_size = key.size();
      91       28549 :   size_t val_size = value.size();
      92       28549 :   size_t internal_key_size = key_size + 8;
      93             :   const size_t encoded_len =
      94       57098 :       VarintLength(internal_key_size) + internal_key_size +
      95       57098 :       VarintLength(val_size) + val_size;
      96       28549 :   char* buf = arena_.Allocate(encoded_len);
      97       28549 :   char* p = EncodeVarint32(buf, internal_key_size);
      98       28549 :   memcpy(p, key.data(), key_size);
      99       28549 :   p += key_size;
     100       28549 :   EncodeFixed64(p, (s << 8) | type);
     101       28549 :   p += 8;
     102       28549 :   p = EncodeVarint32(p, val_size);
     103       28549 :   memcpy(p, value.data(), val_size);
     104       28549 :   assert((p + val_size) - buf == encoded_len);
     105       28549 :   table_.Insert(buf);
     106       28549 : }
     107             : 
     108       36658 : bool MemTable::Get(const LookupKey& key, std::string* value, Status* s) {
     109       73316 :   Slice memkey = key.memtable_key();
     110       36658 :   Table::Iterator iter(&table_);
     111       73316 :   iter.Seek(memkey.data());
     112       36658 :   if (iter.Valid()) {
     113             :     // entry format is:
     114             :     //    klength  varint32
     115             :     //    userkey  char[klength]
     116             :     //    tag      uint64
     117             :     //    vlength  varint32
     118             :     //    value    char[vlength]
     119             :     // Check that it belongs to same user key.  We do not check the
     120             :     // sequence number since the Seek() call above should have skipped
     121             :     // all entries with overly large sequence numbers.
     122           7 :     const char* entry = iter.key();
     123             :     uint32_t key_length;
     124           7 :     const char* key_ptr = GetVarint32Ptr(entry, entry+5, &key_length);
     125          14 :     if (comparator_.comparator.user_comparator()->Compare(
     126           7 :             Slice(key_ptr, key_length - 8),
     127          28 :             key.user_key()) == 0) {
     128             :       // Correct user key
     129          14 :       const uint64_t tag = DecodeFixed64(key_ptr + key_length - 8);
     130           7 :       switch (static_cast<ValueType>(tag & 0xff)) {
     131             :         case kTypeValue: {
     132          14 :           Slice v = GetLengthPrefixedSlice(key_ptr + key_length);
     133           7 :           value->assign(v.data(), v.size());
     134             :           return true;
     135             :         }
     136             :         case kTypeDeletion:
     137           0 :           *s = Status::NotFound(Slice());
     138           0 :           return true;
     139             :       }
     140             :     }
     141             :   }
     142             :   return false;
     143             : }
     144             : 
     145             : }  // namespace leveldb