作者: 韩晨旭 10225101440 李畅 10225102463

138 lignes
4.8 KiB

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