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  
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  
70  const Comparator* BytewiseComparator() {
71    static NoDestructor<BytewiseComparatorImpl> singleton;
72    return singleton.get();
73  }
74  
75  }  // namespace leveldb