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