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
PackSequenceAndType(uint64_t seq,ValueType t)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
AppendInternalKey(std::string * result,const ParsedInternalKey & key)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
DebugString() const26 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
DebugString() const33 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
Name() const43 const char* InternalKeyComparator::Name() const {
44 return "leveldb.InternalKeyComparator";
45 }
46
Compare(const Slice & akey,const Slice & bkey) const47 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
FindShortestSeparator(std::string * start,const Slice & limit) const65 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
FindShortSuccessor(std::string * key) const84 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
Name() const99 const char* InternalFilterPolicy::Name() const { return user_policy_->Name(); }
100
CreateFilter(const Slice * keys,int n,std::string * dst) const101 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
KeyMayMatch(const Slice & key,const Slice & f) const113 bool InternalFilterPolicy::KeyMayMatch(const Slice& key, const Slice& f) const {
114 return user_policy_->KeyMayMatch(ExtractUserKey(key), f);
115 }
116
LookupKey(const Slice & user_key,SequenceNumber s)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