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
16namespace leveldb {
17
18Comparator::~Comparator() = default;
19
20namespace {
21class 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
70const Comparator* BytewiseComparator() {
71 static NoDestructor<BytewiseComparatorImpl> singleton;
72 return singleton.get();
73}
74
75} // namespace leveldb
76