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