// 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/dbformat.h" #include #include #include "port/port.h" #include "util/coding.h" namespace leveldb { static uint64_t PackSequenceAndTypeAndTtlAndLookup( uint64_t seq, ValueType t, bool havettl, bool islookup) { assert(seq <= kMaxSequenceNumber); assert(t <= kValueTypeForSeek); return (seq << 8) | (islookup << 2) | (havettl << 1) | t; } //下面有两个调这个函数的没改,也许也要修改标志位? static uint64_t PackSequenceAndType(uint64_t seq, ValueType t) { assert(seq <= kMaxSequenceNumber); assert(t <= kValueTypeForSeek); return (seq << 8) | t; } void AppendInternalKey(std::string* result, const ParsedInternalKey& key) { result->append(key.user_key.data(), key.user_key.size()); if(key.deadTime != 0) PutFixed64(result, key.deadTime); PutFixed64(result, PackSequenceAndTypeAndTtlAndLookup( key.sequence, key.type, (key.deadTime != 0), false)); } std::string ParsedInternalKey::DebugString() const { std::ostringstream ss; ss << '\'' << EscapeString(user_key.ToString()) << "' @ " << sequence << " : " << static_cast(type); return ss.str(); } std::string InternalKey::DebugString() const { ParsedInternalKey parsed; if (ParseInternalKey(rep_, &parsed)) { return parsed.DebugString(); } std::ostringstream ss; ss << "(bad)" << EscapeString(rep_); return ss.str(); } const char* InternalKeyComparator::Name() const { return "leveldb.InternalKeyComparator"; } int InternalKeyComparator::Compare(const Slice& akey, const Slice& bkey) const { // Order by: // increasing user key (according to user-supplied comparator) // decreasing sequence number // decreasing type (though sequence# should be enough to disambiguate) //目前看调用时都是a为node, b为key,万一有不是的,逻辑还得补充 //for debug // std::string a = ExtractUserKey(akey).ToString(); // std::string b = ExtractUserKey(bkey).ToString(); int r = user_comparator_->Compare(ExtractUserKey(akey), ExtractUserKey(bkey)); if (r == 0) { const uint64_t atag = DecodeFixed64(akey.data() + akey.size() - 8); const uint64_t btag = DecodeFixed64(bkey.data() + bkey.size() - 8); const uint64_t aseq = atag >> 8; const uint64_t bseq = btag >> 8; if (aseq > bseq) { r = -1; return r; } const uint64_t atime = DecodeFixed64(akey.data() + akey.size() - 16); const uint64_t btime = DecodeFixed64(bkey.data() + bkey.size() - 16); //原本应该找到了,新加判断 // if((btag & 0b100) && (atag & 0b10)){ //一个是查询键,另一个有ttl // const uint64_t atime = DecodeFixed64(akey.data() + akey.size() - 16); // const uint64_t btime = DecodeFixed64(bkey.data() + bkey.size() - 16); // std::cout<<"atime:"<FindShortestSeparator(&tmp, user_limit); if (tmp.size() < user_start.size() && user_comparator_->Compare(user_start, tmp) < 0) { // User key has become shorter physically, but larger logically. // Tack on the earliest possible number to the shortened user key. PutFixed64(&tmp, PackSequenceAndType(kMaxSequenceNumber, kValueTypeForSeek)); assert(this->Compare(*start, tmp) < 0); assert(this->Compare(tmp, limit) < 0); start->swap(tmp); } } void InternalKeyComparator::FindShortSuccessor(std::string* key) const { Slice user_key = ExtractUserKey(*key); std::string tmp(user_key.data(), user_key.size()); user_comparator_->FindShortSuccessor(&tmp); if (tmp.size() < user_key.size() && user_comparator_->Compare(user_key, tmp) < 0) { // User key has become shorter physically, but larger logically. // Tack on the earliest possible number to the shortened user key. PutFixed64(&tmp, PackSequenceAndType(kMaxSequenceNumber, kValueTypeForSeek)); assert(this->Compare(*key, tmp) < 0); key->swap(tmp); } } const char* InternalFilterPolicy::Name() const { return user_policy_->Name(); } void InternalFilterPolicy::CreateFilter(const Slice* keys, int n, std::string* dst) const { // We rely on the fact that the code in table.cc does not mind us // adjusting keys[]. Slice* mkey = const_cast(keys); for (int i = 0; i < n; i++) { mkey[i] = ExtractUserKey(keys[i]); // TODO(sanjay): Suppress dups? } user_policy_->CreateFilter(keys, n, dst); } bool InternalFilterPolicy::KeyMayMatch(const Slice& key, const Slice& f) const { return user_policy_->KeyMayMatch(ExtractUserKey(key), f); } LookupKey::LookupKey(const Slice& user_key, SequenceNumber s, uint64_t nowTime) { size_t usize = user_key.size(); size_t needed = usize + 21; // A conservative estimate char* dst; if (needed <= sizeof(space_)) { dst = space_; } else { dst = new char[needed]; } start_ = dst; dst = EncodeVarint32(dst, usize + 16); kstart_ = dst; std::memcpy(dst, user_key.data(), usize); dst += usize; EncodeFixed64(dst, nowTime); dst += 8; // EncodeFixed64(dst, PackSequenceAndTypeAndTtlAndLookup(s, kValueTypeForSeek, 0, true)); EncodeFixed64(dst, PackSequenceAndTypeAndTtlAndLookup(s, kValueTypeForSeek, 1, false)); dst += 8; end_ = dst; printf("lookupkey tag:%lx\n",PackSequenceAndTypeAndTtlAndLookup(s, kValueTypeForSeek, 1, false)); } } // namespace leveldb