Branch data Line data Source code
# 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 : 10645 : Comparator::~Comparator() = default; # 19 : : # 20 : : namespace { # 21 : : class BytewiseComparatorImpl : public Comparator { # 22 : : public: # 23 : 628 : BytewiseComparatorImpl() = default; # 24 : : # 25 : 4161 : const char* Name() const override { return "leveldb.BytewiseComparator"; } # 26 : : # 27 : 203189328 : int Compare(const Slice& a, const Slice& b) const override { # 28 : 203189328 : return a.compare(b); # 29 : 203189328 : } # 30 : : # 31 : : void FindShortestSeparator(std::string* start, # 32 : 2841 : const Slice& limit) const override { # 33 : : // Find length of common prefix # 34 : 2841 : size_t min_length = std::min(start->size(), limit.size()); # 35 : 2841 : size_t diff_index = 0; # 36 [ + + ]: 22192 : while ((diff_index < min_length) && # 37 [ + + ]: 22192 : ((*start)[diff_index] == limit[diff_index])) { # 38 : 19351 : diff_index++; # 39 : 19351 : } # 40 : : # 41 [ + + ]: 2841 : if (diff_index >= min_length) { # 42 : : // Do not shorten if one string is a prefix of the other # 43 : 2370 : } else { # 44 : 2370 : uint8_t diff_byte = static_cast<uint8_t>((*start)[diff_index]); # 45 [ + - ]: 2370 : if (diff_byte < static_cast<uint8_t>(0xff) && # 46 [ + + ]: 2370 : diff_byte + 1 < static_cast<uint8_t>(limit[diff_index])) { # 47 : 1602 : (*start)[diff_index]++; # 48 : 1602 : start->resize(diff_index + 1); # 49 : 1602 : assert(Compare(*start, limit) < 0); # 50 : 1602 : } # 51 : 2370 : } # 52 : 2841 : } # 53 : : # 54 : 842 : void FindShortSuccessor(std::string* key) const override { # 55 : : // Find first character that can be incremented # 56 : 842 : size_t n = key->size(); # 57 [ + - ]: 842 : for (size_t i = 0; i < n; i++) { # 58 : 842 : const uint8_t byte = (*key)[i]; # 59 [ + - ]: 842 : if (byte != static_cast<uint8_t>(0xff)) { # 60 : 842 : (*key)[i] = byte + 1; # 61 : 842 : key->resize(i + 1); # 62 : 842 : return; # 63 : 842 : } # 64 : 842 : } # 65 : : // *key is a run of 0xffs. Leave it alone. # 66 : 842 : } # 67 : : }; # 68 : : } // namespace # 69 : : # 70 : 6160 : const Comparator* BytewiseComparator() { # 71 : 6160 : static NoDestructor<BytewiseComparatorImpl> singleton; # 72 : 6160 : return singleton.get(); # 73 : 6160 : } # 74 : : # 75 : : } // namespace leveldb