1 // Copyright (c) 2011-present, Facebook, Inc. All rights reserved.
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).
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
10 #include "rocksdb/comparator.h"
11 #include <stdint.h>
12 #include <algorithm>
13 #include <memory>
14 #include "logging/logging.h"
15 #include "port/port.h"
16 #include "rocksdb/slice.h"
17
18 namespace ROCKSDB_NAMESPACE {
19
20 namespace {
21 class BytewiseComparatorImpl : public Comparator {
22 public:
BytewiseComparatorImpl()23 BytewiseComparatorImpl() { }
24
Name() const25 const char* Name() const override { return "leveldb.BytewiseComparator"; }
26
Compare(const Slice & a,const Slice & b) const27 int Compare(const Slice& a, const Slice& b) const override {
28 return a.compare(b);
29 }
30
Equal(const Slice & a,const Slice & b) const31 bool Equal(const Slice& a, const Slice& b) const override { return a == b; }
32
FindShortestSeparator(std::string * start,const Slice & limit) const33 void FindShortestSeparator(std::string* start,
34 const Slice& limit) const override {
35 // Find length of common prefix
36 size_t min_length = std::min(start->size(), limit.size());
37 size_t diff_index = 0;
38 while ((diff_index < min_length) &&
39 ((*start)[diff_index] == limit[diff_index])) {
40 diff_index++;
41 }
42
43 if (diff_index >= min_length) {
44 // Do not shorten if one string is a prefix of the other
45 } else {
46 uint8_t start_byte = static_cast<uint8_t>((*start)[diff_index]);
47 uint8_t limit_byte = static_cast<uint8_t>(limit[diff_index]);
48 if (start_byte >= limit_byte) {
49 // Cannot shorten since limit is smaller than start or start is
50 // already the shortest possible.
51 return;
52 }
53 assert(start_byte < limit_byte);
54
55 if (diff_index < limit.size() - 1 || start_byte + 1 < limit_byte) {
56 (*start)[diff_index]++;
57 start->resize(diff_index + 1);
58 } else {
59 // v
60 // A A 1 A A A
61 // A A 2
62 //
63 // Incrementing the current byte will make start bigger than limit, we
64 // will skip this byte, and find the first non 0xFF byte in start and
65 // increment it.
66 diff_index++;
67
68 while (diff_index < start->size()) {
69 // Keep moving until we find the first non 0xFF byte to
70 // increment it
71 if (static_cast<uint8_t>((*start)[diff_index]) <
72 static_cast<uint8_t>(0xff)) {
73 (*start)[diff_index]++;
74 start->resize(diff_index + 1);
75 break;
76 }
77 diff_index++;
78 }
79 }
80 assert(Compare(*start, limit) < 0);
81 }
82 }
83
FindShortSuccessor(std::string * key) const84 void FindShortSuccessor(std::string* key) const override {
85 // Find first character that can be incremented
86 size_t n = key->size();
87 for (size_t i = 0; i < n; i++) {
88 const uint8_t byte = (*key)[i];
89 if (byte != static_cast<uint8_t>(0xff)) {
90 (*key)[i] = byte + 1;
91 key->resize(i+1);
92 return;
93 }
94 }
95 // *key is a run of 0xffs. Leave it alone.
96 }
97
IsSameLengthImmediateSuccessor(const Slice & s,const Slice & t) const98 bool IsSameLengthImmediateSuccessor(const Slice& s,
99 const Slice& t) const override {
100 if (s.size() != t.size() || s.size() == 0) {
101 return false;
102 }
103 size_t diff_ind = s.difference_offset(t);
104 // same slice
105 if (diff_ind >= s.size()) return false;
106 uint8_t byte_s = static_cast<uint8_t>(s[diff_ind]);
107 uint8_t byte_t = static_cast<uint8_t>(t[diff_ind]);
108 // first different byte must be consecutive, and remaining bytes must be
109 // 0xff for s and 0x00 for t
110 if (byte_s != uint8_t{0xff} && byte_s + 1 == byte_t) {
111 for (size_t i = diff_ind + 1; i < s.size(); ++i) {
112 byte_s = static_cast<uint8_t>(s[i]);
113 byte_t = static_cast<uint8_t>(t[i]);
114 if (byte_s != uint8_t{0xff} || byte_t != uint8_t{0x00}) {
115 return false;
116 }
117 }
118 return true;
119 } else {
120 return false;
121 }
122 }
123
CanKeysWithDifferentByteContentsBeEqual() const124 bool CanKeysWithDifferentByteContentsBeEqual() const override {
125 return false;
126 }
127
128 using Comparator::CompareWithoutTimestamp;
CompareWithoutTimestamp(const Slice & a,bool,const Slice & b,bool) const129 int CompareWithoutTimestamp(const Slice& a, bool /*a_has_ts*/, const Slice& b,
130 bool /*b_has_ts*/) const override {
131 return a.compare(b);
132 }
133 };
134
135 class ReverseBytewiseComparatorImpl : public BytewiseComparatorImpl {
136 public:
ReverseBytewiseComparatorImpl()137 ReverseBytewiseComparatorImpl() { }
138
Name() const139 const char* Name() const override {
140 return "rocksdb.ReverseBytewiseComparator";
141 }
142
Compare(const Slice & a,const Slice & b) const143 int Compare(const Slice& a, const Slice& b) const override {
144 return -a.compare(b);
145 }
146
FindShortestSeparator(std::string * start,const Slice & limit) const147 void FindShortestSeparator(std::string* start,
148 const Slice& limit) const override {
149 // Find length of common prefix
150 size_t min_length = std::min(start->size(), limit.size());
151 size_t diff_index = 0;
152 while ((diff_index < min_length) &&
153 ((*start)[diff_index] == limit[diff_index])) {
154 diff_index++;
155 }
156
157 assert(diff_index <= min_length);
158 if (diff_index == min_length) {
159 // Do not shorten if one string is a prefix of the other
160 //
161 // We could handle cases like:
162 // V
163 // A A 2 X Y
164 // A A 2
165 // in a similar way as BytewiseComparator::FindShortestSeparator().
166 // We keep it simple by not implementing it. We can come back to it
167 // later when needed.
168 } else {
169 uint8_t start_byte = static_cast<uint8_t>((*start)[diff_index]);
170 uint8_t limit_byte = static_cast<uint8_t>(limit[diff_index]);
171 if (start_byte > limit_byte && diff_index < start->size() - 1) {
172 // Case like
173 // V
174 // A A 3 A A
175 // A A 1 B B
176 //
177 // or
178 // v
179 // A A 2 A A
180 // A A 1 B B
181 // In this case "AA2" will be good.
182 #ifndef NDEBUG
183 std::string old_start = *start;
184 #endif
185 start->resize(diff_index + 1);
186 #ifndef NDEBUG
187 assert(old_start >= *start);
188 #endif
189 assert(Slice(*start).compare(limit) > 0);
190 }
191 }
192 }
193
FindShortSuccessor(std::string *) const194 void FindShortSuccessor(std::string* /*key*/) const override {
195 // Don't do anything for simplicity.
196 }
197
CanKeysWithDifferentByteContentsBeEqual() const198 bool CanKeysWithDifferentByteContentsBeEqual() const override {
199 return false;
200 }
201
202 using Comparator::CompareWithoutTimestamp;
CompareWithoutTimestamp(const Slice & a,bool,const Slice & b,bool) const203 int CompareWithoutTimestamp(const Slice& a, bool /*a_has_ts*/, const Slice& b,
204 bool /*b_has_ts*/) const override {
205 return -a.compare(b);
206 }
207 };
208 }// namespace
209
BytewiseComparator()210 const Comparator* BytewiseComparator() {
211 static BytewiseComparatorImpl bytewise;
212 return &bytewise;
213 }
214
ReverseBytewiseComparator()215 const Comparator* ReverseBytewiseComparator() {
216 static ReverseBytewiseComparatorImpl rbytewise;
217 return &rbytewise;
218 }
219
220 } // namespace ROCKSDB_NAMESPACE
221