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 : 6057561 : static uint64_t PackSequenceAndType(uint64_t seq, ValueType t) {
17 [ - + ]: 6057561 : assert(seq <= kMaxSequenceNumber);
18 [ - + ]: 6057561 : assert(t <= kValueTypeForSeek);
19 : 6057561 : return (seq << 8) | t;
20 : : }
21 : :
22 : 4886 : void AppendInternalKey(std::string* result, const ParsedInternalKey& key) {
23 : 4886 : result->append(key.user_key.data(), key.user_key.size());
24 : 4886 : PutFixed64(result, PackSequenceAndType(key.sequence, key.type));
25 : 4886 : }
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 : : }
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 : : }
47 : :
48 : 144313855 : 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 : 144313855 : int r = user_comparator_->Compare(ExtractUserKey(akey), ExtractUserKey(bkey));
54 [ + + ]: 144313855 : if (r == 0) {
55 [ + + ]: 799963 : const uint64_t anum = DecodeFixed64(akey.data() + akey.size() - 8);
56 : 799963 : const uint64_t bnum = DecodeFixed64(bkey.data() + bkey.size() - 8);
57 [ + + ]: 799963 : if (anum > bnum) {
58 : : r = -1;
59 [ + + ]: 719835 : } else if (anum < bnum) {
60 : 710905 : r = +1;
61 : : }
62 : : }
63 : 144313855 : return r;
64 : : }
65 : :
66 : 8319 : void InternalKeyComparator::FindShortestSeparator(std::string* start,
67 : : const Slice& limit) const {
68 : : // Attempt to shorten the user portion of the key
69 [ - + ]: 8319 : Slice user_start = ExtractUserKey(*start);
70 : 8319 : Slice user_limit = ExtractUserKey(limit);
71 : 8319 : std::string tmp(user_start.data(), user_start.size());
72 [ + - ]: 8319 : user_comparator_->FindShortestSeparator(&tmp, user_limit);
73 [ - + + + : 13542 : if (tmp.size() < user_start.size() &&
+ - ]
74 [ + - ]: 5223 : 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 [ + - ]: 5223 : PutFixed64(&tmp,
78 : : PackSequenceAndType(kMaxSequenceNumber, kValueTypeForSeek));
79 [ - + - + : 5223 : assert(this->Compare(*start, tmp) < 0);
+ - - + ]
80 [ - + + - : 5223 : assert(this->Compare(tmp, limit) < 0);
- + ]
81 : 5223 : start->swap(tmp);
82 : : }
83 : 8319 : }
84 : :
85 : 2028 : void InternalKeyComparator::FindShortSuccessor(std::string* key) const {
86 [ - + ]: 2028 : Slice user_key = ExtractUserKey(*key);
87 : 2028 : std::string tmp(user_key.data(), user_key.size());
88 [ + - ]: 2028 : user_comparator_->FindShortSuccessor(&tmp);
89 [ - + + + : 2304 : if (tmp.size() < user_key.size() &&
+ - ]
90 [ + - ]: 276 : 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 [ + - ]: 276 : PutFixed64(&tmp,
94 : : PackSequenceAndType(kMaxSequenceNumber, kValueTypeForSeek));
95 [ - + - + : 276 : assert(this->Compare(*key, tmp) < 0);
+ - - + ]
96 : 276 : key->swap(tmp);
97 : : }
98 : 2028 : }
99 : :
100 : 6172 : const char* InternalFilterPolicy::Name() const { return user_policy_->Name(); }
101 : :
102 : 10347 : void InternalFilterPolicy::CreateFilter(const Slice* keys, int n,
103 : : std::string* dst) const {
104 : : // We rely on the fact that the code in table.cc does not mind us
105 : : // adjusting keys[].
106 : 10347 : Slice* mkey = const_cast<Slice*>(keys);
107 [ + + ]: 381315 : for (int i = 0; i < n; i++) {
108 : 370968 : mkey[i] = ExtractUserKey(keys[i]);
109 : : // TODO(sanjay): Suppress dups?
110 : : }
111 : 10347 : user_policy_->CreateFilter(keys, n, dst);
112 : 10347 : }
113 : :
114 : 2216827 : bool InternalFilterPolicy::KeyMayMatch(const Slice& key, const Slice& f) const {
115 : 2216827 : return user_policy_->KeyMayMatch(ExtractUserKey(key), f);
116 : : }
117 : :
118 : 6047176 : LookupKey::LookupKey(const Slice& user_key, SequenceNumber s) {
119 [ + - ]: 6047176 : size_t usize = user_key.size();
120 : 6047176 : size_t needed = usize + 13; // A conservative estimate
121 : 6047176 : char* dst;
122 [ + - ]: 6047176 : if (needed <= sizeof(space_)) {
123 : 6047176 : dst = space_;
124 : : } else {
125 : 0 : dst = new char[needed];
126 : : }
127 : 6047176 : start_ = dst;
128 : 6047176 : dst = EncodeVarint32(dst, usize + 8);
129 : 6047176 : kstart_ = dst;
130 : 6047176 : memcpy(dst, user_key.data(), usize);
131 : 6047176 : dst += usize;
132 : 6047176 : EncodeFixed64(dst, PackSequenceAndType(s, kValueTypeForSeek));
133 : 6047176 : dst += 8;
134 : 6047176 : end_ = dst;
135 : 6047176 : }
136 : :
137 : : } // namespace leveldb
|
