/Users/deen/code/yugabyte-db/src/yb/rocksdb/util/comparator.cc
Line | Count | Source (jump to first uncovered line) |
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 | | // The following only applies to changes made to this file as part of YugaByte development. |
7 | | // |
8 | | // Portions Copyright (c) YugaByte, Inc. |
9 | | // |
10 | | // Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except |
11 | | // in compliance with the License. You may obtain a copy of the License at |
12 | | // |
13 | | // http://www.apache.org/licenses/LICENSE-2.0 |
14 | | // |
15 | | // Unless required by applicable law or agreed to in writing, software distributed under the License |
16 | | // is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express |
17 | | // or implied. See the License for the specific language governing permissions and limitations |
18 | | // under the License. |
19 | | // |
20 | | // Copyright (c) 2011 The LevelDB Authors. All rights reserved. |
21 | | // Use of this source code is governed by a BSD-style license that can be |
22 | | // found in the LICENSE file. See the AUTHORS file for names of contributors. |
23 | | #include <stdint.h> |
24 | | |
25 | | #include <memory> |
26 | | |
27 | | #include <glog/logging.h> |
28 | | |
29 | | #include "yb/rocksdb/comparator.h" |
30 | | #include "yb/util/slice.h" |
31 | | |
32 | | namespace rocksdb { |
33 | | |
34 | 1.39M | Comparator::~Comparator() { } |
35 | | |
36 | | namespace { |
37 | | class BytewiseComparatorImpl : public Comparator { |
38 | | public: |
39 | 10.6k | BytewiseComparatorImpl() { } |
40 | | |
41 | 3.31M | const char* Name() const override { |
42 | 3.31M | return "leveldb.BytewiseComparator"; |
43 | 3.31M | } |
44 | | |
45 | 11.9G | int Compare(const Slice& a, const Slice& b) const override { |
46 | 11.9G | return a.compare(b); |
47 | 11.9G | } |
48 | | |
49 | 139M | bool Equal(const Slice& a, const Slice& b) const override { |
50 | 139M | return a == b; |
51 | 139M | } |
52 | | |
53 | 2.46M | virtual void FindShortestSeparator(std::string* start, const Slice& limit) const override { |
54 | 2.46M | const uint8_t* start_bytes = pointer_cast<const uint8_t*>(start->data()); |
55 | 2.46M | const uint8_t* limit_bytes = limit.data(); |
56 | | // Find length of common prefix |
57 | 2.46M | size_t min_length = std::min(start->size(), limit.size()); |
58 | 2.46M | size_t diff_index = 0; |
59 | 125M | while ((diff_index < min_length) && |
60 | 125M | (start_bytes[diff_index] == limit_bytes[diff_index])) { |
61 | 122M | diff_index++; |
62 | 122M | } |
63 | | |
64 | 2.46M | if (diff_index >= min_length) { |
65 | | // Do not shorten if one string is a prefix of the other |
66 | 2.46M | } else { |
67 | 2.46M | uint8_t start_byte = start_bytes[diff_index]; |
68 | 2.46M | uint8_t limit_byte = limit_bytes[diff_index]; |
69 | 2.46M | if (start_byte > limit_byte) { |
70 | | // Cannot shorten since limit is smaller than start. |
71 | 2 | return; |
72 | 2 | } |
73 | 2.46M | DCHECK_LT(start_byte, limit_byte); |
74 | | |
75 | 2.46M | if (diff_index == limit.size() - 1 && start_byte + 1 == limit_byte) { |
76 | | // v |
77 | | // A A 1 A A A |
78 | | // A A 2 |
79 | | // |
80 | | // Incrementing the current byte will make start bigger than limit, we |
81 | | // will skip this byte, and find the first non 0xFF byte in start and |
82 | | // increment it. |
83 | 1.16M | ++diff_index; |
84 | 1.16M | while (diff_index < start->size() && start_bytes[diff_index] == 0xffU) { ++diff_index; } |
85 | 1.16M | if (diff_index == start->size()) { |
86 | 1.16M | return; |
87 | 1.16M | } |
88 | 1.29M | } |
89 | 1.29M | (*start)[diff_index]++; |
90 | 1.29M | start->resize(diff_index + 1); |
91 | 1.29M | DCHECK_LT(Compare(*start, limit), 0); |
92 | 1.29M | } |
93 | 2.46M | } |
94 | | |
95 | 68.6k | void FindShortSuccessor(std::string* key) const override { |
96 | | // Find first character that can be incremented |
97 | 68.6k | size_t n = key->size(); |
98 | 78.2k | for (size_t i = 0; i < n; i++) { |
99 | 77.3k | const uint8_t byte = (*key)[i]; |
100 | 77.3k | if (byte != static_cast<uint8_t>(0xff)) { |
101 | 67.7k | (*key)[i] = byte + 1; |
102 | 67.7k | key->resize(i+1); |
103 | 67.7k | return; |
104 | 67.7k | } |
105 | 77.3k | } |
106 | | // *key is a run of 0xffs. Leave it alone. |
107 | 68.6k | } |
108 | | }; |
109 | | |
110 | | class ReverseBytewiseComparatorImpl : public BytewiseComparatorImpl { |
111 | | public: |
112 | 3 | ReverseBytewiseComparatorImpl() { } |
113 | | |
114 | 0 | const char* Name() const override { |
115 | 0 | return "rocksdb.ReverseBytewiseComparator"; |
116 | 0 | } |
117 | | |
118 | 83 | int Compare(const Slice& a, const Slice& b) const override { |
119 | 83 | return -a.compare(b); |
120 | 83 | } |
121 | | }; |
122 | | |
123 | | } // namespace |
124 | | |
125 | 69.9M | const ComparatorPtr& SharedBytewiseComparator() { |
126 | | // Comparator should be shared ptr, because we use shared_from_this to store it in index reader. |
127 | 69.9M | static ComparatorPtr bytewise = std::make_shared<BytewiseComparatorImpl>(); |
128 | 69.9M | return bytewise; |
129 | 69.9M | } |
130 | | |
131 | 69.9M | const Comparator* BytewiseComparator() { |
132 | | // Comparator should be shared ptr, because we use shared_from_this to store it in index reader. |
133 | 69.9M | return SharedBytewiseComparator().get(); |
134 | 69.9M | } |
135 | | |
136 | 4 | const Comparator* ReverseBytewiseComparator() { |
137 | 4 | static ComparatorPtr rbytewise = std::make_shared<ReverseBytewiseComparatorImpl>(); |
138 | 4 | return rbytewise.get(); |
139 | 4 | } |
140 | | |
141 | | class Uint64ComparatorImpl : public Comparator { |
142 | | public: |
143 | 1 | Uint64ComparatorImpl() { } |
144 | | |
145 | 76 | const char* Name() const override { |
146 | 76 | return "rocksdb.Uint64Comparator"; |
147 | 76 | } |
148 | | |
149 | 516k | int Compare(const Slice& a, const Slice& b) const override { |
150 | 516k | assert(a.size() == sizeof(uint64_t) && b.size() == sizeof(uint64_t)); |
151 | 516k | const uint64_t* left = reinterpret_cast<const uint64_t*>(a.data()); |
152 | 516k | const uint64_t* right = reinterpret_cast<const uint64_t*>(b.data()); |
153 | 516k | if (*left == *right) { |
154 | 81.3k | return 0; |
155 | 434k | } else if (*left < *right) { |
156 | 303k | return -1; |
157 | 131k | } else { |
158 | 131k | return 1; |
159 | 131k | } |
160 | 516k | } |
161 | | |
162 | | virtual void FindShortestSeparator(std::string* start, |
163 | 0 | const Slice& limit) const override { |
164 | 0 | return; |
165 | 0 | } |
166 | | |
167 | 45 | void FindShortSuccessor(std::string* key) const override { |
168 | 45 | return; |
169 | 45 | } |
170 | | }; |
171 | | |
172 | 1 | const Comparator* Uint64Comparator() { |
173 | 1 | static ComparatorPtr uint64comparator = std::make_shared<Uint64ComparatorImpl>(); |
174 | 1 | return uint64comparator.get(); |
175 | 1 | } |
176 | | |
177 | | } // namespace rocksdb |