]>
Commit | Line | Data |
---|---|---|
7c673cae | 1 | // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. |
11fdf7f2 TL |
2 | // This source code is licensed under both the GPLv2 (found in the |
3 | // COPYING file in the root directory) and Apache 2.0 License | |
4 | // (found in the LICENSE.Apache file in the root directory). | |
7c673cae FG |
5 | // |
6 | // Copyright (c) 2011 The LevelDB Authors. All rights reserved. | |
7 | // Use of this source code is governed by a BSD-style license that can be | |
8 | // found in the LICENSE file. See the AUTHORS file for names of contributors. | |
9 | #include "db/dbformat.h" | |
10 | ||
7c673cae | 11 | #include <stdio.h> |
f67539c2 | 12 | #include <cinttypes> |
7c673cae FG |
13 | #include "monitoring/perf_context_imp.h" |
14 | #include "port/port.h" | |
15 | #include "util/coding.h" | |
16 | #include "util/string_util.h" | |
17 | ||
f67539c2 | 18 | namespace ROCKSDB_NAMESPACE { |
7c673cae FG |
19 | |
20 | // kValueTypeForSeek defines the ValueType that should be passed when | |
21 | // constructing a ParsedInternalKey object for seeking to a particular | |
22 | // sequence number (since we sort sequence numbers in decreasing order | |
23 | // and the value type is embedded as the low 8 bits in the sequence | |
24 | // number in internal keys, we need to use the highest-numbered | |
25 | // ValueType, not the lowest). | |
20effc67 | 26 | const ValueType kValueTypeForSeek = kTypeDeletionWithTimestamp; |
7c673cae FG |
27 | const ValueType kValueTypeForSeekForPrev = kTypeDeletion; |
28 | ||
11fdf7f2 TL |
29 | EntryType GetEntryType(ValueType value_type) { |
30 | switch (value_type) { | |
31 | case kTypeValue: | |
32 | return kEntryPut; | |
33 | case kTypeDeletion: | |
34 | return kEntryDelete; | |
20effc67 TL |
35 | case kTypeDeletionWithTimestamp: |
36 | return kEntryDeleteWithTimestamp; | |
11fdf7f2 TL |
37 | case kTypeSingleDeletion: |
38 | return kEntrySingleDelete; | |
39 | case kTypeMerge: | |
40 | return kEntryMerge; | |
41 | case kTypeRangeDeletion: | |
42 | return kEntryRangeDeletion; | |
43 | case kTypeBlobIndex: | |
44 | return kEntryBlobIndex; | |
45 | default: | |
46 | return kEntryOther; | |
47 | } | |
48 | } | |
49 | ||
50 | bool ParseFullKey(const Slice& internal_key, FullKey* fkey) { | |
51 | ParsedInternalKey ikey; | |
20effc67 TL |
52 | if (!ParseInternalKey(internal_key, &ikey, false /*log_err_key */) |
53 | .ok()) { // TODO | |
11fdf7f2 TL |
54 | return false; |
55 | } | |
56 | fkey->user_key = ikey.user_key; | |
57 | fkey->sequence = ikey.sequence; | |
58 | fkey->type = GetEntryType(ikey.type); | |
59 | return true; | |
60 | } | |
61 | ||
7c673cae FG |
62 | void AppendInternalKey(std::string* result, const ParsedInternalKey& key) { |
63 | result->append(key.user_key.data(), key.user_key.size()); | |
64 | PutFixed64(result, PackSequenceAndType(key.sequence, key.type)); | |
65 | } | |
66 | ||
20effc67 TL |
67 | void AppendInternalKeyWithDifferentTimestamp(std::string* result, |
68 | const ParsedInternalKey& key, | |
69 | const Slice& ts) { | |
70 | assert(key.user_key.size() >= ts.size()); | |
71 | result->append(key.user_key.data(), key.user_key.size() - ts.size()); | |
72 | result->append(ts.data(), ts.size()); | |
73 | PutFixed64(result, PackSequenceAndType(key.sequence, key.type)); | |
74 | } | |
75 | ||
7c673cae FG |
76 | void AppendInternalKeyFooter(std::string* result, SequenceNumber s, |
77 | ValueType t) { | |
78 | PutFixed64(result, PackSequenceAndType(s, t)); | |
79 | } | |
80 | ||
20effc67 TL |
81 | std::string ParsedInternalKey::DebugString(bool log_err_key, bool hex) const { |
82 | std::string result = "'"; | |
83 | if (log_err_key) { | |
84 | result += user_key.ToString(hex); | |
85 | } else { | |
86 | result += "<redacted>"; | |
87 | } | |
88 | ||
7c673cae FG |
89 | char buf[50]; |
90 | snprintf(buf, sizeof(buf), "' seq:%" PRIu64 ", type:%d", sequence, | |
91 | static_cast<int>(type)); | |
20effc67 | 92 | |
7c673cae FG |
93 | result += buf; |
94 | return result; | |
95 | } | |
96 | ||
97 | std::string InternalKey::DebugString(bool hex) const { | |
98 | std::string result; | |
99 | ParsedInternalKey parsed; | |
20effc67 TL |
100 | if (ParseInternalKey(rep_, &parsed, false /* log_err_key */).ok()) { |
101 | result = parsed.DebugString(true /* log_err_key */, hex); // TODO | |
7c673cae FG |
102 | } else { |
103 | result = "(bad)"; | |
104 | result.append(EscapeString(rep_)); | |
105 | } | |
106 | return result; | |
107 | } | |
108 | ||
20effc67 TL |
109 | const char* InternalKeyComparator::Name() const { |
110 | if (name_.empty()) { | |
111 | return "rocksdb.anonymous.InternalKeyComparator"; | |
112 | } | |
113 | return name_.c_str(); | |
114 | } | |
7c673cae | 115 | |
7c673cae FG |
116 | int InternalKeyComparator::Compare(const ParsedInternalKey& a, |
117 | const ParsedInternalKey& b) const { | |
118 | // Order by: | |
119 | // increasing user key (according to user-supplied comparator) | |
120 | // decreasing sequence number | |
121 | // decreasing type (though sequence# should be enough to disambiguate) | |
494da23a | 122 | int r = user_comparator_.Compare(a.user_key, b.user_key); |
7c673cae FG |
123 | if (r == 0) { |
124 | if (a.sequence > b.sequence) { | |
125 | r = -1; | |
126 | } else if (a.sequence < b.sequence) { | |
127 | r = +1; | |
128 | } else if (a.type > b.type) { | |
129 | r = -1; | |
130 | } else if (a.type < b.type) { | |
131 | r = +1; | |
132 | } | |
133 | } | |
134 | return r; | |
135 | } | |
136 | ||
494da23a TL |
137 | void InternalKeyComparator::FindShortestSeparator(std::string* start, |
138 | const Slice& limit) const { | |
7c673cae FG |
139 | // Attempt to shorten the user portion of the key |
140 | Slice user_start = ExtractUserKey(*start); | |
141 | Slice user_limit = ExtractUserKey(limit); | |
142 | std::string tmp(user_start.data(), user_start.size()); | |
494da23a | 143 | user_comparator_.FindShortestSeparator(&tmp, user_limit); |
11fdf7f2 | 144 | if (tmp.size() <= user_start.size() && |
494da23a | 145 | user_comparator_.Compare(user_start, tmp) < 0) { |
7c673cae FG |
146 | // User key has become shorter physically, but larger logically. |
147 | // Tack on the earliest possible number to the shortened user key. | |
494da23a TL |
148 | PutFixed64(&tmp, |
149 | PackSequenceAndType(kMaxSequenceNumber, kValueTypeForSeek)); | |
7c673cae FG |
150 | assert(this->Compare(*start, tmp) < 0); |
151 | assert(this->Compare(tmp, limit) < 0); | |
152 | start->swap(tmp); | |
153 | } | |
154 | } | |
155 | ||
156 | void InternalKeyComparator::FindShortSuccessor(std::string* key) const { | |
157 | Slice user_key = ExtractUserKey(*key); | |
158 | std::string tmp(user_key.data(), user_key.size()); | |
494da23a | 159 | user_comparator_.FindShortSuccessor(&tmp); |
11fdf7f2 | 160 | if (tmp.size() <= user_key.size() && |
494da23a | 161 | user_comparator_.Compare(user_key, tmp) < 0) { |
7c673cae FG |
162 | // User key has become shorter physically, but larger logically. |
163 | // Tack on the earliest possible number to the shortened user key. | |
494da23a TL |
164 | PutFixed64(&tmp, |
165 | PackSequenceAndType(kMaxSequenceNumber, kValueTypeForSeek)); | |
7c673cae FG |
166 | assert(this->Compare(*key, tmp) < 0); |
167 | key->swap(tmp); | |
168 | } | |
169 | } | |
170 | ||
f67539c2 TL |
171 | LookupKey::LookupKey(const Slice& _user_key, SequenceNumber s, |
172 | const Slice* ts) { | |
7c673cae | 173 | size_t usize = _user_key.size(); |
f67539c2 TL |
174 | size_t ts_sz = (nullptr == ts) ? 0 : ts->size(); |
175 | size_t needed = usize + ts_sz + 13; // A conservative estimate | |
7c673cae FG |
176 | char* dst; |
177 | if (needed <= sizeof(space_)) { | |
178 | dst = space_; | |
179 | } else { | |
180 | dst = new char[needed]; | |
181 | } | |
182 | start_ = dst; | |
183 | // NOTE: We don't support users keys of more than 2GB :) | |
f67539c2 | 184 | dst = EncodeVarint32(dst, static_cast<uint32_t>(usize + ts_sz + 8)); |
7c673cae FG |
185 | kstart_ = dst; |
186 | memcpy(dst, _user_key.data(), usize); | |
187 | dst += usize; | |
f67539c2 TL |
188 | if (nullptr != ts) { |
189 | memcpy(dst, ts->data(), ts_sz); | |
190 | dst += ts_sz; | |
191 | } | |
7c673cae FG |
192 | EncodeFixed64(dst, PackSequenceAndType(s, kValueTypeForSeek)); |
193 | dst += 8; | |
194 | end_ = dst; | |
195 | } | |
196 | ||
11fdf7f2 TL |
197 | void IterKey::EnlargeBuffer(size_t key_size) { |
198 | // If size is smaller than buffer size, continue using current buffer, | |
199 | // or the static allocated one, as default | |
200 | assert(key_size > buf_size_); | |
201 | // Need to enlarge the buffer. | |
202 | ResetBuffer(); | |
203 | buf_ = new char[key_size]; | |
204 | buf_size_ = key_size; | |
205 | } | |
f67539c2 | 206 | } // namespace ROCKSDB_NAMESPACE |