Inside Bitcoin

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