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 "leveldb/comparator.h" |
6 | |
7 | #include <algorithm> |
8 | #include <cstdint> |
9 | #include <string> |
10 | #include <type_traits> |
11 | |
12 | #include "leveldb/slice.h" |
13 | #include "util/logging.h" |
14 | #include "util/no_destructor.h" |
15 | |
16 | namespace leveldb { |
17 | |
18 | Comparator::~Comparator() = default; |
19 | |
20 | namespace { |
21 | class BytewiseComparatorImpl : public Comparator { |
22 | public: |
23 | BytewiseComparatorImpl() = default; |
24 | |
25 | const char* Name() const override { return "leveldb.BytewiseComparator"; } |
26 | |
27 | int Compare(const Slice& a, const Slice& b) const override { |
28 | return a.compare(b); |
29 | } |
30 | |
31 | void FindShortestSeparator(std::string* start, |
32 | const Slice& limit) const override { |
33 | // Find length of common prefix |
34 | size_t min_length = std::min(start->size(), limit.size()); |
35 | size_t diff_index = 0; |
36 | while ((diff_index < min_length) && |
37 | ((*start)[diff_index] == limit[diff_index])) { |
38 | diff_index++; |
39 | } |
40 | |
41 | if (diff_index >= min_length) { |
42 | // Do not shorten if one string is a prefix of the other |
43 | } else { |
44 | uint8_t diff_byte = static_cast<uint8_t>((*start)[diff_index]); |
45 | if (diff_byte < static_cast<uint8_t>(0xff) && |
46 | diff_byte + 1 < static_cast<uint8_t>(limit[diff_index])) { |
47 | (*start)[diff_index]++; |
48 | start->resize(diff_index + 1); |
49 | assert(Compare(*start, limit) < 0); |
50 | } |
51 | } |
52 | } |
53 | |
54 | void FindShortSuccessor(std::string* key) const override { |
55 | // Find first character that can be incremented |
56 | size_t n = key->size(); |
57 | for (size_t i = 0; i < n; i++) { |
58 | const uint8_t byte = (*key)[i]; |
59 | if (byte != static_cast<uint8_t>(0xff)) { |
60 | (*key)[i] = byte + 1; |
61 | key->resize(i + 1); |
62 | return; |
63 | } |
64 | } |
65 | // *key is a run of 0xffs. Leave it alone. |
66 | } |
67 | }; |
68 | } // namespace |
69 | |
70 | const Comparator* BytewiseComparator() { |
71 | static NoDestructor<BytewiseComparatorImpl> singleton; |
72 | return singleton.get(); |
73 | } |
74 | |
75 | } // namespace leveldb |
76 |