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 
Name() const25   const char* Name() const override { return "leveldb.BytewiseComparator"; }
26 
Compare(const Slice & a,const Slice & b) const27   int Compare(const Slice& a, const Slice& b) const override {
28     return a.compare(b);
29   }
30 
FindShortestSeparator(std::string * start,const Slice & limit) const31   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 
FindShortSuccessor(std::string * key) const54   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 
BytewiseComparator()70 const Comparator* BytewiseComparator() {
71   static NoDestructor<BytewiseComparatorImpl> singleton;
72   return singleton.get();
73 }
74 
75 }  // namespace leveldb
76