]> git.proxmox.com Git - ceph.git/blame - ceph/src/rocksdb/util/comparator.cc
add subtree-ish sources for 12.0.3
[ceph.git] / ceph / src / rocksdb / util / comparator.cc
CommitLineData
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
18namespace rocksdb {
19
20Comparator::~Comparator() { }
21
22namespace {
23class 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
105class 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
120const Comparator* BytewiseComparator() {
121 static BytewiseComparatorImpl bytewise;
122 return &bytewise;
123}
124
125const Comparator* ReverseBytewiseComparator() {
126 static ReverseBytewiseComparatorImpl rbytewise;
127 return &rbytewise;
128}
129
130} // namespace rocksdb