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