Branch data Line data Source code
# 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/dbformat.h"
# 6 : :
# 7 : : #include <stdio.h>
# 8 : :
# 9 : : #include <sstream>
# 10 : :
# 11 : : #include "port/port.h"
# 12 : : #include "util/coding.h"
# 13 : :
# 14 : : namespace leveldb {
# 15 : :
# 16 : 10088484 : static uint64_t PackSequenceAndType(uint64_t seq, ValueType t) {
# 17 : 10088484 : assert(seq <= kMaxSequenceNumber);
# 18 : 0 : assert(t <= kValueTypeForSeek);
# 19 : 0 : return (seq << 8) | t;
# 20 : 10088484 : }
# 21 : :
# 22 : 2950 : void AppendInternalKey(std::string* result, const ParsedInternalKey& key) {
# 23 : 2950 : result->append(key.user_key.data(), key.user_key.size());
# 24 : 2950 : PutFixed64(result, PackSequenceAndType(key.sequence, key.type));
# 25 : 2950 : }
# 26 : :
# 27 : 0 : std::string ParsedInternalKey::DebugString() const {
# 28 : 0 : std::ostringstream ss;
# 29 : 0 : ss << '\'' << EscapeString(user_key.ToString()) << "' @ " << sequence << " : "
# 30 : 0 : << static_cast<int>(type);
# 31 : 0 : return ss.str();
# 32 : 0 : }
# 33 : :
# 34 : 0 : std::string InternalKey::DebugString() const {
# 35 : 0 : ParsedInternalKey parsed;
# 36 [ # # ]: 0 : if (ParseInternalKey(rep_, &parsed)) {
# 37 : 0 : return parsed.DebugString();
# 38 : 0 : }
# 39 : 0 : std::ostringstream ss;
# 40 : 0 : ss << "(bad)" << EscapeString(rep_);
# 41 : 0 : return ss.str();
# 42 : 0 : }
# 43 : :
# 44 : 0 : const char* InternalKeyComparator::Name() const {
# 45 : 0 : return "leveldb.InternalKeyComparator";
# 46 : 0 : }
# 47 : :
# 48 : 257958810 : int InternalKeyComparator::Compare(const Slice& akey, const Slice& bkey) const {
# 49 : : // Order by:
# 50 : : // increasing user key (according to user-supplied comparator)
# 51 : : // decreasing sequence number
# 52 : : // decreasing type (though sequence# should be enough to disambiguate)
# 53 : 257958810 : int r = user_comparator_->Compare(ExtractUserKey(akey), ExtractUserKey(bkey));
# 54 [ + + ]: 257958810 : if (r == 0) {
# 55 : 1012265 : const uint64_t anum = DecodeFixed64(akey.data() + akey.size() - 8);
# 56 : 1012265 : const uint64_t bnum = DecodeFixed64(bkey.data() + bkey.size() - 8);
# 57 [ + + ]: 1012265 : if (anum > bnum) {
# 58 : 67278 : r = -1;
# 59 [ + + ]: 944987 : } else if (anum < bnum) {
# 60 : 931892 : r = +1;
# 61 : 931892 : }
# 62 : 1012265 : }
# 63 : 257958810 : return r;
# 64 : 257958810 : }
# 65 : :
# 66 : : void InternalKeyComparator::FindShortestSeparator(std::string* start,
# 67 : 3571 : const Slice& limit) const {
# 68 : : // Attempt to shorten the user portion of the key
# 69 : 3571 : Slice user_start = ExtractUserKey(*start);
# 70 : 3571 : Slice user_limit = ExtractUserKey(limit);
# 71 : 3571 : std::string tmp(user_start.data(), user_start.size());
# 72 : 3571 : user_comparator_->FindShortestSeparator(&tmp, user_limit);
# 73 [ + + ][ + + ]: 3571 : if (tmp.size() < user_start.size() &&
# 74 [ + - ]: 3571 : user_comparator_->Compare(user_start, tmp) < 0) {
# 75 : : // User key has become shorter physically, but larger logically.
# 76 : : // Tack on the earliest possible number to the shortened user key.
# 77 : 1532 : PutFixed64(&tmp,
# 78 : 1532 : PackSequenceAndType(kMaxSequenceNumber, kValueTypeForSeek));
# 79 : 1532 : assert(this->Compare(*start, tmp) < 0);
# 80 : 0 : assert(this->Compare(tmp, limit) < 0);
# 81 : 0 : start->swap(tmp);
# 82 : 1532 : }
# 83 : 3571 : }
# 84 : :
# 85 : 1077 : void InternalKeyComparator::FindShortSuccessor(std::string* key) const {
# 86 : 1077 : Slice user_key = ExtractUserKey(*key);
# 87 : 1077 : std::string tmp(user_key.data(), user_key.size());
# 88 : 1077 : user_comparator_->FindShortSuccessor(&tmp);
# 89 [ + + ][ + + ]: 1077 : if (tmp.size() < user_key.size() &&
# 90 [ + - ]: 1077 : user_comparator_->Compare(user_key, tmp) < 0) {
# 91 : : // User key has become shorter physically, but larger logically.
# 92 : : // Tack on the earliest possible number to the shortened user key.
# 93 : 73 : PutFixed64(&tmp,
# 94 : 73 : PackSequenceAndType(kMaxSequenceNumber, kValueTypeForSeek));
# 95 : 73 : assert(this->Compare(*key, tmp) < 0);
# 96 : 0 : key->swap(tmp);
# 97 : 73 : }
# 98 : 1077 : }
# 99 : :
# 100 : 3000 : const char* InternalFilterPolicy::Name() const { return user_policy_->Name(); }
# 101 : :
# 102 : : void InternalFilterPolicy::CreateFilter(const Slice* keys, int n,
# 103 : 4648 : std::string* dst) const {
# 104 : : // We rely on the fact that the code in table.cc does not mind us
# 105 : : // adjusting keys[].
# 106 : 4648 : Slice* mkey = const_cast<Slice*>(keys);
# 107 [ + + ]: 201265 : for (int i = 0; i < n; i++) {
# 108 : 196617 : mkey[i] = ExtractUserKey(keys[i]);
# 109 : : // TODO(sanjay): Suppress dups?
# 110 : 196617 : }
# 111 : 4648 : user_policy_->CreateFilter(keys, n, dst);
# 112 : 4648 : }
# 113 : :
# 114 : 3382960 : bool InternalFilterPolicy::KeyMayMatch(const Slice& key, const Slice& f) const {
# 115 : 3382960 : return user_policy_->KeyMayMatch(ExtractUserKey(key), f);
# 116 : 3382960 : }
# 117 : :
# 118 : 10083933 : LookupKey::LookupKey(const Slice& user_key, SequenceNumber s) {
# 119 : 10083933 : size_t usize = user_key.size();
# 120 : 10083933 : size_t needed = usize + 13; // A conservative estimate
# 121 : 10083933 : char* dst;
# 122 [ + - ]: 10083933 : if (needed <= sizeof(space_)) {
# 123 : 10083933 : dst = space_;
# 124 : 10083933 : } else {
# 125 : 0 : dst = new char[needed];
# 126 : 0 : }
# 127 : 10083933 : start_ = dst;
# 128 : 10083933 : dst = EncodeVarint32(dst, usize + 8);
# 129 : 10083933 : kstart_ = dst;
# 130 : 10083933 : memcpy(dst, user_key.data(), usize);
# 131 : 10083933 : dst += usize;
# 132 : 10083933 : EncodeFixed64(dst, PackSequenceAndType(s, kValueTypeForSeek));
# 133 : 10083933 : dst += 8;
# 134 : 10083933 : end_ = dst;
# 135 : 10083933 : }
# 136 : :
# 137 : : } // namespace leveldb
|
