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