]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. |
2 | // This source code is licensed under the BSD-style license found in the | |
3 | // LICENSE file in the root directory of this source tree. An additional grant | |
4 | // of patent rights can be found in the PATENTS file in the same 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 <algorithm> | |
11 | #include <memory> | |
12 | #include <stdint.h> | |
13 | #include "rocksdb/comparator.h" | |
14 | #include "rocksdb/slice.h" | |
15 | #include "port/port.h" | |
16 | #include "util/logging.h" | |
17 | ||
18 | namespace rocksdb { | |
19 | ||
20 | Comparator::~Comparator() { } | |
21 | ||
22 | namespace { | |
23 | class BytewiseComparatorImpl : public Comparator { | |
24 | public: | |
25 | BytewiseComparatorImpl() { } | |
26 | ||
27 | virtual const char* Name() const override { | |
28 | return "leveldb.BytewiseComparator"; | |
29 | } | |
30 | ||
31 | virtual int Compare(const Slice& a, const Slice& b) const override { | |
32 | return a.compare(b); | |
33 | } | |
34 | ||
35 | virtual bool Equal(const Slice& a, const Slice& b) const override { | |
36 | return a == b; | |
37 | } | |
38 | ||
39 | virtual void FindShortestSeparator(std::string* start, | |
40 | const Slice& limit) const override { | |
41 | // Find length of common prefix | |
42 | size_t min_length = std::min(start->size(), limit.size()); | |
43 | size_t diff_index = 0; | |
44 | while ((diff_index < min_length) && | |
45 | ((*start)[diff_index] == limit[diff_index])) { | |
46 | diff_index++; | |
47 | } | |
48 | ||
49 | if (diff_index >= min_length) { | |
50 | // Do not shorten if one string is a prefix of the other | |
51 | } else { | |
52 | uint8_t start_byte = static_cast<uint8_t>((*start)[diff_index]); | |
53 | uint8_t limit_byte = static_cast<uint8_t>(limit[diff_index]); | |
54 | if (start_byte >= limit_byte || (diff_index == start->size() - 1)) { | |
55 | // Cannot shorten since limit is smaller than start or start is | |
56 | // already the shortest possible. | |
57 | return; | |
58 | } | |
59 | assert(start_byte < limit_byte); | |
60 | ||
61 | if (diff_index < limit.size() - 1 || start_byte + 1 < limit_byte) { | |
62 | (*start)[diff_index]++; | |
63 | start->resize(diff_index + 1); | |
64 | } else { | |
65 | // v | |
66 | // A A 1 A A A | |
67 | // A A 2 | |
68 | // | |
69 | // Incrementing the current byte will make start bigger than limit, we | |
70 | // will skip this byte, and find the first non 0xFF byte in start and | |
71 | // increment it. | |
72 | diff_index++; | |
73 | ||
74 | while (diff_index < start->size()) { | |
75 | // Keep moving until we find the first non 0xFF byte to | |
76 | // increment it | |
77 | if (static_cast<uint8_t>((*start)[diff_index]) < | |
78 | static_cast<uint8_t>(0xff)) { | |
79 | (*start)[diff_index]++; | |
80 | start->resize(diff_index + 1); | |
81 | break; | |
82 | } | |
83 | diff_index++; | |
84 | } | |
85 | } | |
86 | assert(Compare(*start, limit) < 0); | |
87 | } | |
88 | } | |
89 | ||
90 | virtual void FindShortSuccessor(std::string* key) const override { | |
91 | // Find first character that can be incremented | |
92 | size_t n = key->size(); | |
93 | for (size_t i = 0; i < n; i++) { | |
94 | const uint8_t byte = (*key)[i]; | |
95 | if (byte != static_cast<uint8_t>(0xff)) { | |
96 | (*key)[i] = byte + 1; | |
97 | key->resize(i+1); | |
98 | return; | |
99 | } | |
100 | } | |
101 | // *key is a run of 0xffs. Leave it alone. | |
102 | } | |
103 | }; | |
104 | ||
105 | class ReverseBytewiseComparatorImpl : public BytewiseComparatorImpl { | |
106 | public: | |
107 | ReverseBytewiseComparatorImpl() { } | |
108 | ||
109 | virtual const char* Name() const override { | |
110 | return "rocksdb.ReverseBytewiseComparator"; | |
111 | } | |
112 | ||
113 | virtual int Compare(const Slice& a, const Slice& b) const override { | |
114 | return -a.compare(b); | |
115 | } | |
116 | }; | |
117 | ||
118 | }// namespace | |
119 | ||
120 | const Comparator* BytewiseComparator() { | |
121 | static BytewiseComparatorImpl bytewise; | |
122 | return &bytewise; | |
123 | } | |
124 | ||
125 | const Comparator* ReverseBytewiseComparator() { | |
126 | static ReverseBytewiseComparatorImpl rbytewise; | |
127 | return &rbytewise; | |
128 | } | |
129 | ||
130 | } // namespace rocksdb |