]>
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). | |
11fdf7f2 | 26 | const ValueType kValueTypeForSeek = kTypeBlobIndex; |
7c673cae FG |
27 | const ValueType kValueTypeForSeekForPrev = kTypeDeletion; |
28 | ||
29 | uint64_t PackSequenceAndType(uint64_t seq, ValueType t) { | |
30 | assert(seq <= kMaxSequenceNumber); | |
31 | assert(IsExtendedValueType(t)); | |
32 | return (seq << 8) | t; | |
33 | } | |
34 | ||
11fdf7f2 TL |
35 | EntryType GetEntryType(ValueType value_type) { |
36 | switch (value_type) { | |
37 | case kTypeValue: | |
38 | return kEntryPut; | |
39 | case kTypeDeletion: | |
40 | return kEntryDelete; | |
41 | case kTypeSingleDeletion: | |
42 | return kEntrySingleDelete; | |
43 | case kTypeMerge: | |
44 | return kEntryMerge; | |
45 | case kTypeRangeDeletion: | |
46 | return kEntryRangeDeletion; | |
47 | case kTypeBlobIndex: | |
48 | return kEntryBlobIndex; | |
49 | default: | |
50 | return kEntryOther; | |
51 | } | |
52 | } | |
53 | ||
54 | bool ParseFullKey(const Slice& internal_key, FullKey* fkey) { | |
55 | ParsedInternalKey ikey; | |
56 | if (!ParseInternalKey(internal_key, &ikey)) { | |
57 | return false; | |
58 | } | |
59 | fkey->user_key = ikey.user_key; | |
60 | fkey->sequence = ikey.sequence; | |
61 | fkey->type = GetEntryType(ikey.type); | |
62 | return true; | |
63 | } | |
64 | ||
7c673cae FG |
65 | void UnPackSequenceAndType(uint64_t packed, uint64_t* seq, ValueType* t) { |
66 | *seq = packed >> 8; | |
67 | *t = static_cast<ValueType>(packed & 0xff); | |
68 | ||
69 | assert(*seq <= kMaxSequenceNumber); | |
70 | assert(IsExtendedValueType(*t)); | |
71 | } | |
72 | ||
73 | void AppendInternalKey(std::string* result, const ParsedInternalKey& key) { | |
74 | result->append(key.user_key.data(), key.user_key.size()); | |
75 | PutFixed64(result, PackSequenceAndType(key.sequence, key.type)); | |
76 | } | |
77 | ||
78 | void AppendInternalKeyFooter(std::string* result, SequenceNumber s, | |
79 | ValueType t) { | |
80 | PutFixed64(result, PackSequenceAndType(s, t)); | |
81 | } | |
82 | ||
83 | std::string ParsedInternalKey::DebugString(bool hex) const { | |
84 | char buf[50]; | |
85 | snprintf(buf, sizeof(buf), "' seq:%" PRIu64 ", type:%d", sequence, | |
86 | static_cast<int>(type)); | |
87 | std::string result = "'"; | |
88 | result += user_key.ToString(hex); | |
89 | result += buf; | |
90 | return result; | |
91 | } | |
92 | ||
93 | std::string InternalKey::DebugString(bool hex) const { | |
94 | std::string result; | |
95 | ParsedInternalKey parsed; | |
96 | if (ParseInternalKey(rep_, &parsed)) { | |
97 | result = parsed.DebugString(hex); | |
98 | } else { | |
99 | result = "(bad)"; | |
100 | result.append(EscapeString(rep_)); | |
101 | } | |
102 | return result; | |
103 | } | |
104 | ||
494da23a | 105 | const char* InternalKeyComparator::Name() const { return name_.c_str(); } |
7c673cae | 106 | |
7c673cae FG |
107 | int InternalKeyComparator::Compare(const ParsedInternalKey& a, |
108 | const ParsedInternalKey& b) const { | |
109 | // Order by: | |
110 | // increasing user key (according to user-supplied comparator) | |
111 | // decreasing sequence number | |
112 | // decreasing type (though sequence# should be enough to disambiguate) | |
494da23a | 113 | int r = user_comparator_.Compare(a.user_key, b.user_key); |
7c673cae FG |
114 | if (r == 0) { |
115 | if (a.sequence > b.sequence) { | |
116 | r = -1; | |
117 | } else if (a.sequence < b.sequence) { | |
118 | r = +1; | |
119 | } else if (a.type > b.type) { | |
120 | r = -1; | |
121 | } else if (a.type < b.type) { | |
122 | r = +1; | |
123 | } | |
124 | } | |
125 | return r; | |
126 | } | |
127 | ||
494da23a TL |
128 | void InternalKeyComparator::FindShortestSeparator(std::string* start, |
129 | const Slice& limit) const { | |
7c673cae FG |
130 | // Attempt to shorten the user portion of the key |
131 | Slice user_start = ExtractUserKey(*start); | |
132 | Slice user_limit = ExtractUserKey(limit); | |
133 | std::string tmp(user_start.data(), user_start.size()); | |
494da23a | 134 | user_comparator_.FindShortestSeparator(&tmp, user_limit); |
11fdf7f2 | 135 | if (tmp.size() <= user_start.size() && |
494da23a | 136 | user_comparator_.Compare(user_start, tmp) < 0) { |
7c673cae FG |
137 | // User key has become shorter physically, but larger logically. |
138 | // Tack on the earliest possible number to the shortened user key. | |
494da23a TL |
139 | PutFixed64(&tmp, |
140 | PackSequenceAndType(kMaxSequenceNumber, kValueTypeForSeek)); | |
7c673cae FG |
141 | assert(this->Compare(*start, tmp) < 0); |
142 | assert(this->Compare(tmp, limit) < 0); | |
143 | start->swap(tmp); | |
144 | } | |
145 | } | |
146 | ||
147 | void InternalKeyComparator::FindShortSuccessor(std::string* key) const { | |
148 | Slice user_key = ExtractUserKey(*key); | |
149 | std::string tmp(user_key.data(), user_key.size()); | |
494da23a | 150 | user_comparator_.FindShortSuccessor(&tmp); |
11fdf7f2 | 151 | if (tmp.size() <= user_key.size() && |
494da23a | 152 | user_comparator_.Compare(user_key, tmp) < 0) { |
7c673cae FG |
153 | // User key has become shorter physically, but larger logically. |
154 | // Tack on the earliest possible number to the shortened user key. | |
494da23a TL |
155 | PutFixed64(&tmp, |
156 | PackSequenceAndType(kMaxSequenceNumber, kValueTypeForSeek)); | |
7c673cae FG |
157 | assert(this->Compare(*key, tmp) < 0); |
158 | key->swap(tmp); | |
159 | } | |
160 | } | |
161 | ||
f67539c2 TL |
162 | LookupKey::LookupKey(const Slice& _user_key, SequenceNumber s, |
163 | const Slice* ts) { | |
7c673cae | 164 | size_t usize = _user_key.size(); |
f67539c2 TL |
165 | size_t ts_sz = (nullptr == ts) ? 0 : ts->size(); |
166 | size_t needed = usize + ts_sz + 13; // A conservative estimate | |
7c673cae FG |
167 | char* dst; |
168 | if (needed <= sizeof(space_)) { | |
169 | dst = space_; | |
170 | } else { | |
171 | dst = new char[needed]; | |
172 | } | |
173 | start_ = dst; | |
174 | // NOTE: We don't support users keys of more than 2GB :) | |
f67539c2 | 175 | dst = EncodeVarint32(dst, static_cast<uint32_t>(usize + ts_sz + 8)); |
7c673cae FG |
176 | kstart_ = dst; |
177 | memcpy(dst, _user_key.data(), usize); | |
178 | dst += usize; | |
f67539c2 TL |
179 | if (nullptr != ts) { |
180 | memcpy(dst, ts->data(), ts_sz); | |
181 | dst += ts_sz; | |
182 | } | |
7c673cae FG |
183 | EncodeFixed64(dst, PackSequenceAndType(s, kValueTypeForSeek)); |
184 | dst += 8; | |
185 | end_ = dst; | |
186 | } | |
187 | ||
11fdf7f2 TL |
188 | void IterKey::EnlargeBuffer(size_t key_size) { |
189 | // If size is smaller than buffer size, continue using current buffer, | |
190 | // or the static allocated one, as default | |
191 | assert(key_size > buf_size_); | |
192 | // Need to enlarge the buffer. | |
193 | ResetBuffer(); | |
194 | buf_ = new char[key_size]; | |
195 | buf_size_ = key_size; | |
196 | } | |
f67539c2 | 197 | } // namespace ROCKSDB_NAMESPACE |