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