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