1179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Copyright (c) 2011 The LevelDB Authors. All rights reserved. 2179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Use of this source code is governed by a BSD-style license that can be 3179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// found in the LICENSE file. See the AUTHORS file for names of contributors. 4179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 5179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "db/memtable.h" 6179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "db/dbformat.h" 7fbd97aa4c5325eace57d24b89845b9581bac9324jorlow@chromium.org#include "leveldb/comparator.h" 8fbd97aa4c5325eace57d24b89845b9581bac9324jorlow@chromium.org#include "leveldb/env.h" 9fbd97aa4c5325eace57d24b89845b9581bac9324jorlow@chromium.org#include "leveldb/iterator.h" 10179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "util/coding.h" 11179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 12179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgnamespace leveldb { 13179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 14179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgstatic Slice GetLengthPrefixedSlice(const char* data) { 15179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org uint32_t len; 16179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const char* p = data; 17179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org p = GetVarint32Ptr(p, p + 5, &len); // +5: we assume "p" is not corrupted 18179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return Slice(p, len); 19179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 20179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 21179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgMemTable::MemTable(const InternalKeyComparator& cmp) 22179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org : comparator_(cmp), 23a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org refs_(0), 24179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org table_(comparator_, &arena_) { 25179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 26179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 27179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgMemTable::~MemTable() { 28a5b4129c0a8c01158cde2244a5811f15b9d45ec0dgrogan@chromium.org assert(refs_ == 0); 29179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 30179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 31179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgsize_t MemTable::ApproximateMemoryUsage() { return arena_.MemoryUsage(); } 32179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 33179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgint MemTable::KeyComparator::operator()(const char* aptr, const char* bptr) 34179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const { 35179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Internal keys are encoded as length-prefixed strings. 36179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Slice a = GetLengthPrefixedSlice(aptr); 37179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org Slice b = GetLengthPrefixedSlice(bptr); 38179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return comparator.Compare(a, b); 39179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 40179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 41179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Encode a suitable internal key target for "target" and return it. 42179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Uses *scratch as scratch space, and the returned pointer will point 43179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// into this scratch space. 44179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgstatic const char* EncodeKey(std::string* scratch, const Slice& target) { 45179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org scratch->clear(); 46179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org PutVarint32(scratch, target.size()); 47179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org scratch->append(target.data(), target.size()); 48179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return scratch->data(); 49179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 50179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 51179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgclass MemTableIterator: public Iterator { 52179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org public: 53c6ac22e779e5135e494ddeb1d8e2b6008e9b619edgrogan@chromium.org explicit MemTableIterator(MemTable::Table* table) : iter_(table) { } 54c6ac22e779e5135e494ddeb1d8e2b6008e9b619edgrogan@chromium.org 55c6ac22e779e5135e494ddeb1d8e2b6008e9b619edgrogan@chromium.org virtual bool Valid() const { return iter_.Valid(); } 56c6ac22e779e5135e494ddeb1d8e2b6008e9b619edgrogan@chromium.org virtual void Seek(const Slice& k) { iter_.Seek(EncodeKey(&tmp_, k)); } 57c6ac22e779e5135e494ddeb1d8e2b6008e9b619edgrogan@chromium.org virtual void SeekToFirst() { iter_.SeekToFirst(); } 58c6ac22e779e5135e494ddeb1d8e2b6008e9b619edgrogan@chromium.org virtual void SeekToLast() { iter_.SeekToLast(); } 59c6ac22e779e5135e494ddeb1d8e2b6008e9b619edgrogan@chromium.org virtual void Next() { iter_.Next(); } 60c6ac22e779e5135e494ddeb1d8e2b6008e9b619edgrogan@chromium.org virtual void Prev() { iter_.Prev(); } 61c6ac22e779e5135e494ddeb1d8e2b6008e9b619edgrogan@chromium.org virtual Slice key() const { return GetLengthPrefixedSlice(iter_.key()); } 62179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual Slice value() const { 63c6ac22e779e5135e494ddeb1d8e2b6008e9b619edgrogan@chromium.org Slice key_slice = GetLengthPrefixedSlice(iter_.key()); 64179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return GetLengthPrefixedSlice(key_slice.data() + key_slice.size()); 65179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 66179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 67179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual Status status() const { return Status::OK(); } 68179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 69179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org private: 70c6ac22e779e5135e494ddeb1d8e2b6008e9b619edgrogan@chromium.org MemTable::Table::Iterator iter_; 71179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::string tmp_; // For passing to EncodeKey 72179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 73179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // No copying allowed 74179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org MemTableIterator(const MemTableIterator&); 75179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org void operator=(const MemTableIterator&); 76179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org}; 77179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 78179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgIterator* MemTable::NewIterator() { 79c6ac22e779e5135e494ddeb1d8e2b6008e9b619edgrogan@chromium.org return new MemTableIterator(&table_); 80179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 81179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 82179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgvoid MemTable::Add(SequenceNumber s, ValueType type, 83179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const Slice& key, 84179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const Slice& value) { 85179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Format of an entry is concatenation of: 86179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // key_size : varint32 of internal_key.size() 87179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // key bytes : char[internal_key.size()] 88179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // value_size : varint32 of value.size() 89179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // value bytes : char[value.size()] 90179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org size_t key_size = key.size(); 91179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org size_t val_size = value.size(); 92179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org size_t internal_key_size = key_size + 8; 93179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const size_t encoded_len = 94179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org VarintLength(internal_key_size) + internal_key_size + 95179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org VarintLength(val_size) + val_size; 96179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org char* buf = arena_.Allocate(encoded_len); 97179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org char* p = EncodeVarint32(buf, internal_key_size); 98179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org memcpy(p, key.data(), key_size); 99179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org p += key_size; 100179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org EncodeFixed64(p, (s << 8) | type); 101179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org p += 8; 102179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org p = EncodeVarint32(p, val_size); 103179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org memcpy(p, value.data(), val_size); 104179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org assert((p + val_size) - buf == encoded_len); 105179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org table_.Insert(buf); 106179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 107179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 1088cd4ab8303620197cf24282ae8639060efbb326egabor@google.combool MemTable::Get(const LookupKey& key, std::string* value, Status* s) { 1098cd4ab8303620197cf24282ae8639060efbb326egabor@google.com Slice memkey = key.memtable_key(); 1108cd4ab8303620197cf24282ae8639060efbb326egabor@google.com Table::Iterator iter(&table_); 1118cd4ab8303620197cf24282ae8639060efbb326egabor@google.com iter.Seek(memkey.data()); 1128cd4ab8303620197cf24282ae8639060efbb326egabor@google.com if (iter.Valid()) { 1138cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // entry format is: 1148cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // klength varint32 1158cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // userkey char[klength] 1168cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // tag uint64 1178cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // vlength varint32 1188cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // value char[vlength] 1198cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // Check that it belongs to same user key. We do not check the 1208cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // sequence number since the Seek() call above should have skipped 1218cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // all entries with overly large sequence numbers. 1228cd4ab8303620197cf24282ae8639060efbb326egabor@google.com const char* entry = iter.key(); 1238cd4ab8303620197cf24282ae8639060efbb326egabor@google.com uint32_t key_length; 1248cd4ab8303620197cf24282ae8639060efbb326egabor@google.com const char* key_ptr = GetVarint32Ptr(entry, entry+5, &key_length); 1258cd4ab8303620197cf24282ae8639060efbb326egabor@google.com if (comparator_.comparator.user_comparator()->Compare( 1268cd4ab8303620197cf24282ae8639060efbb326egabor@google.com Slice(key_ptr, key_length - 8), 1278cd4ab8303620197cf24282ae8639060efbb326egabor@google.com key.user_key()) == 0) { 1288cd4ab8303620197cf24282ae8639060efbb326egabor@google.com // Correct user key 1298cd4ab8303620197cf24282ae8639060efbb326egabor@google.com const uint64_t tag = DecodeFixed64(key_ptr + key_length - 8); 1308cd4ab8303620197cf24282ae8639060efbb326egabor@google.com switch (static_cast<ValueType>(tag & 0xff)) { 1318cd4ab8303620197cf24282ae8639060efbb326egabor@google.com case kTypeValue: { 1328cd4ab8303620197cf24282ae8639060efbb326egabor@google.com Slice v = GetLengthPrefixedSlice(key_ptr + key_length); 1338cd4ab8303620197cf24282ae8639060efbb326egabor@google.com value->assign(v.data(), v.size()); 1348cd4ab8303620197cf24282ae8639060efbb326egabor@google.com return true; 1358cd4ab8303620197cf24282ae8639060efbb326egabor@google.com } 1368cd4ab8303620197cf24282ae8639060efbb326egabor@google.com case kTypeDeletion: 1378cd4ab8303620197cf24282ae8639060efbb326egabor@google.com *s = Status::NotFound(Slice()); 1388cd4ab8303620197cf24282ae8639060efbb326egabor@google.com return true; 1398cd4ab8303620197cf24282ae8639060efbb326egabor@google.com } 1408cd4ab8303620197cf24282ae8639060efbb326egabor@google.com } 1418cd4ab8303620197cf24282ae8639060efbb326egabor@google.com } 1428cd4ab8303620197cf24282ae8639060efbb326egabor@google.com return false; 1438cd4ab8303620197cf24282ae8639060efbb326egabor@google.com} 1448cd4ab8303620197cf24282ae8639060efbb326egabor@google.com 14545b9940be332834440bd5299419f396e38085ebehans@chromium.org} // namespace leveldb 146