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 : 251283234 : static Slice GetLengthPrefixedSlice(const char* data) {
15 : 251283234 : uint32_t len;
16 : 251283234 : const char* p = data;
17 : 251283234 : p = GetVarint32Ptr(p, p + 5, &len); // +5: we assume "p" is not corrupted
18 : 251283234 : return Slice(p, len);
19 : : }
20 : :
21 : 4583 : MemTable::MemTable(const InternalKeyComparator& comparator)
22 [ + - + - ]: 9166 : : comparator_(comparator), refs_(0), table_(comparator_, &arena_) {}
23 : :
24 [ - + ]: 4582 : MemTable::~MemTable() { assert(refs_ == 0); }
25 : :
26 : 54828 : size_t MemTable::ApproximateMemoryUsage() { return arena_.MemoryUsage(); }
27 : :
28 : 124650354 : int MemTable::KeyComparator::operator()(const char* aptr,
29 : : const char* bptr) const {
30 : : // Internal keys are encoded as length-prefixed strings.
31 : 124650354 : Slice a = GetLengthPrefixedSlice(aptr);
32 : 124650354 : Slice b = GetLengthPrefixedSlice(bptr);
33 : 124650354 : return comparator.Compare(a, b);
34 : : }
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 : 4491 : static const char* EncodeKey(std::string* scratch, const Slice& target) {
40 : 4491 : scratch->clear();
41 : 4491 : PutVarint32(scratch, target.size());
42 : 4491 : scratch->append(target.data(), target.size());
43 : 4491 : return scratch->data();
44 : : }
45 : :
46 : : class MemTableIterator : public Iterator {
47 : : public:
48 : 6769 : explicit MemTableIterator(MemTable::Table* table) : iter_(table) {}
49 : :
50 : : MemTableIterator(const MemTableIterator&) = delete;
51 : : MemTableIterator& operator=(const MemTableIterator&) = delete;
52 : :
53 : 13538 : ~MemTableIterator() override = default;
54 : :
55 : 589283 : bool Valid() const override { return iter_.Valid(); }
56 : 4491 : void Seek(const Slice& k) override { iter_.Seek(EncodeKey(&tmp_, k)); }
57 : 2280 : void SeekToFirst() override { iter_.SeekToFirst(); }
58 : 0 : void SeekToLast() override { iter_.SeekToLast(); }
59 : 539485 : void Next() override { iter_.Next(); }
60 : 0 : void Prev() override { iter_.Prev(); }
61 : 618065 : Slice key() const override { return GetLengthPrefixedSlice(iter_.key()); }
62 : 655370 : Slice value() const override {
63 : 655370 : Slice key_slice = GetLengthPrefixedSlice(iter_.key());
64 : 655370 : return GetLengthPrefixedSlice(key_slice.data() + key_slice.size());
65 : : }
66 : :
67 : 1736 : 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 [ + - ]: 6769 : Iterator* MemTable::NewIterator() { return new MemTableIterator(&table_); }
75 : :
76 : 722975 : void MemTable::Add(SequenceNumber s, ValueType type, const Slice& key,
77 : : 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 : 722975 : size_t key_size = key.size();
84 : 722975 : size_t val_size = value.size();
85 : 722975 : size_t internal_key_size = key_size + 8;
86 : 722975 : const size_t encoded_len = VarintLength(internal_key_size) +
87 : 722975 : internal_key_size + VarintLength(val_size) +
88 : 722975 : val_size;
89 : 722975 : char* buf = arena_.Allocate(encoded_len);
90 : 722975 : char* p = EncodeVarint32(buf, internal_key_size);
91 : 722975 : memcpy(p, key.data(), key_size);
92 : 722975 : p += key_size;
93 : 722975 : EncodeFixed64(p, (s << 8) | type);
94 : 722975 : p += 8;
95 : 722975 : p = EncodeVarint32(p, val_size);
96 [ - + ]: 722975 : memcpy(p, value.data(), val_size);
97 [ - + ]: 722975 : assert(p + val_size == buf + encoded_len);
98 : 722975 : table_.Insert(buf);
99 : 722975 : }
100 : :
101 : 6051081 : bool MemTable::Get(const LookupKey& key, std::string* value, Status* s) {
102 : 6051081 : Slice memkey = key.memtable_key();
103 : 6051081 : Table::Iterator iter(&table_);
104 : 6051081 : iter.Seek(memkey.data());
105 [ + + ]: 6051081 : 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 : 5261142 : const char* entry = iter.key();
116 : 5261142 : uint32_t key_length;
117 : 5261142 : const char* key_ptr = GetVarint32Ptr(entry, entry + 5, &key_length);
118 [ + + ]: 5261142 : if (comparator_.comparator.user_comparator()->Compare(
119 : 5261142 : Slice(key_ptr, key_length - 8), key.user_key()) == 0) {
120 : : // Correct user key
121 : 171485 : const uint64_t tag = DecodeFixed64(key_ptr + key_length - 8);
122 [ + + - ]: 171485 : switch (static_cast<ValueType>(tag & 0xff)) {
123 : 53721 : case kTypeValue: {
124 : 53721 : Slice v = GetLengthPrefixedSlice(key_ptr + key_length);
125 : 53721 : value->assign(v.data(), v.size());
126 : 53721 : return true;
127 : : }
128 : 117764 : case kTypeDeletion:
129 [ - + ]: 117764 : *s = Status::NotFound(Slice());
130 : 117764 : return true;
131 : : }
132 : : }
133 : : }
134 : : return false;
135 : : }
136 : :
137 : : } // namespace leveldb
|
