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