comparator.cc raw

   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
  76