| // Copyright (c) 2011 The LevelDB Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. See the AUTHORS file for names of contributors. |
| |
| #include "db/memtable.h" |
| #include "db/dbformat.h" |
| #include "leveldb/comparator.h" |
| #include "leveldb/env.h" |
| #include "leveldb/iterator.h" |
| #include "util/coding.h" |
| |
| namespace leveldb { |
| |
| static Slice GetLengthPrefixedSlice(const char* data) { |
| uint32_t len; |
| const char* p = data; |
| p = GetVarint32Ptr(p, p + 5, &len); // +5: we assume "p" is not corrupted |
| return Slice(p, len); |
| } |
| |
| MemTable::MemTable(const InternalKeyComparator& cmp) |
| : comparator_(cmp), |
| refs_(0), |
| table_(comparator_, &arena_) { |
| } |
| |
| MemTable::~MemTable() { |
| assert(refs_ == 0); |
| } |
| |
| size_t MemTable::ApproximateMemoryUsage() { return arena_.MemoryUsage(); } |
| |
| int MemTable::KeyComparator::operator()(const char* aptr, const char* bptr) |
| const { |
| // Internal keys are encoded as length-prefixed strings. |
| Slice a = GetLengthPrefixedSlice(aptr); |
| Slice b = GetLengthPrefixedSlice(bptr); |
| return comparator.Compare(a, b); |
| } |
| |
| // Encode a suitable internal key target for "target" and return it. |
| // Uses *scratch as scratch space, and the returned pointer will point |
| // into this scratch space. |
| static const char* EncodeKey(std::string* scratch, const Slice& target) { |
| scratch->clear(); |
| PutVarint32(scratch, target.size()); |
| scratch->append(target.data(), target.size()); |
| return scratch->data(); |
| } |
| |
| class MemTableIterator: public Iterator { |
| public: |
| explicit MemTableIterator(MemTable* mem, MemTable::Table* table) { |
| mem_ = mem; |
| iter_ = new MemTable::Table::Iterator(table); |
| mem->Ref(); |
| } |
| virtual ~MemTableIterator() { |
| delete iter_; |
| mem_->Unref(); |
| } |
| |
| virtual bool Valid() const { return iter_->Valid(); } |
| virtual void Seek(const Slice& k) { iter_->Seek(EncodeKey(&tmp_, k)); } |
| virtual void SeekToFirst() { iter_->SeekToFirst(); } |
| virtual void SeekToLast() { iter_->SeekToLast(); } |
| virtual void Next() { iter_->Next(); } |
| virtual void Prev() { iter_->Prev(); } |
| virtual Slice key() const { return GetLengthPrefixedSlice(iter_->key()); } |
| virtual Slice value() const { |
| Slice key_slice = GetLengthPrefixedSlice(iter_->key()); |
| return GetLengthPrefixedSlice(key_slice.data() + key_slice.size()); |
| } |
| |
| virtual Status status() const { return Status::OK(); } |
| |
| private: |
| MemTable* mem_; |
| MemTable::Table::Iterator* iter_; |
| std::string tmp_; // For passing to EncodeKey |
| |
| // No copying allowed |
| MemTableIterator(const MemTableIterator&); |
| void operator=(const MemTableIterator&); |
| }; |
| |
| Iterator* MemTable::NewIterator() { |
| return new MemTableIterator(this, &table_); |
| } |
| |
| void MemTable::Add(SequenceNumber s, ValueType type, |
| const Slice& key, |
| const Slice& value) { |
| // Format of an entry is concatenation of: |
| // key_size : varint32 of internal_key.size() |
| // key bytes : char[internal_key.size()] |
| // value_size : varint32 of value.size() |
| // value bytes : char[value.size()] |
| size_t key_size = key.size(); |
| size_t val_size = value.size(); |
| size_t internal_key_size = key_size + 8; |
| const size_t encoded_len = |
| VarintLength(internal_key_size) + internal_key_size + |
| VarintLength(val_size) + val_size; |
| char* buf = arena_.Allocate(encoded_len); |
| char* p = EncodeVarint32(buf, internal_key_size); |
| memcpy(p, key.data(), key_size); |
| p += key_size; |
| EncodeFixed64(p, (s << 8) | type); |
| p += 8; |
| p = EncodeVarint32(p, val_size); |
| memcpy(p, value.data(), val_size); |
| assert((p + val_size) - buf == encoded_len); |
| table_.Insert(buf); |
| } |
| |
| } |