ceph/src/rocksdb/util/comparator.cc

   1 //  Copyright (c) 2011-present, Facebook, Inc.  All rights reserved.
   2 //  This source code is licensed under both the GPLv2 (found in the
   3 //  COPYING file in the root directory) and Apache 2.0 License
   4 //  (found in the LICENSE.Apache file in the root directory).
   5 //
   6 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
   7 // Use of this source code is governed by a BSD-style license that can be
   8 // found in the LICENSE file. See the AUTHORS file for names of contributors.
   9
  10 #include "rocksdb/comparator.h"
  11 #include <stdint.h>
  12 #include <algorithm>
  13 #include <memory>
  14 #include "logging/logging.h"
  15 #include "port/port.h"
  16 #include "rocksdb/slice.h"
  17
  18 namespace ROCKSDB_NAMESPACE {
  19
  20 namespace {
  21 class BytewiseComparatorImpl : public Comparator {
  22  public:
  23   BytewiseComparatorImpl() { }
  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   bool Equal(const Slice& a, const Slice& b) const override { return a == b; }
  32
  33   void FindShortestSeparator(std::string* start,
  34                              const Slice& limit) const override {
  35     // Find length of common prefix
  36     size_t min_length = std::min(start->size(), limit.size());
  37     size_t diff_index = 0;
  38     while ((diff_index < min_length) &&
  39            ((*start)[diff_index] == limit[diff_index])) {
  40       diff_index++;
  41     }
  42
  43     if (diff_index >= min_length) {
  44       // Do not shorten if one string is a prefix of the other
  45     } else {
  46       uint8_t start_byte = static_cast<uint8_t>((*start)[diff_index]);
  47       uint8_t limit_byte = static_cast<uint8_t>(limit[diff_index]);
  48       if (start_byte >= limit_byte) {
  49         // Cannot shorten since limit is smaller than start or start is
  50         // already the shortest possible.
  51         return;
  52       }
  53       assert(start_byte < limit_byte);
  54
  55       if (diff_index < limit.size() - 1 || start_byte + 1 < limit_byte) {
  56         (*start)[diff_index]++;
  57         start->resize(diff_index + 1);
  58       } else {
  59         //     v
  60         // A A 1 A A A
  61         // A A 2
  62         //
  63         // Incrementing the current byte will make start bigger than limit, we
  64         // will skip this byte, and find the first non 0xFF byte in start and
  65         // increment it.
  66         diff_index++;
  67
  68         while (diff_index < start->size()) {
  69           // Keep moving until we find the first non 0xFF byte to
  70           // increment it
  71           if (static_cast<uint8_t>((*start)[diff_index]) <
  72               static_cast<uint8_t>(0xff)) {
  73             (*start)[diff_index]++;
  74             start->resize(diff_index + 1);
  75             break;
  76           }
  77           diff_index++;
  78         }
  79       }
  80       assert(Compare(*start, limit) < 0);
  81     }
  82   }
  83
  84   void FindShortSuccessor(std::string* key) const override {
  85     // Find first character that can be incremented
  86     size_t n = key->size();
  87     for (size_t i = 0; i < n; i++) {
  88       const uint8_t byte = (*key)[i];
  89       if (byte != static_cast<uint8_t>(0xff)) {
  90         (*key)[i] = byte + 1;
  91         key->resize(i+1);
  92         return;
  93       }
  94     }
  95     // *key is a run of 0xffs.  Leave it alone.
  96   }
  97
  98   bool IsSameLengthImmediateSuccessor(const Slice& s,
  99                                       const Slice& t) const override {
 100     if (s.size() != t.size() || s.size() == 0) {
 101       return false;
 102     }
 103     size_t diff_ind = s.difference_offset(t);
 104     // same slice
 105     if (diff_ind >= s.size()) return false;
 106     uint8_t byte_s = static_cast<uint8_t>(s[diff_ind]);
 107     uint8_t byte_t = static_cast<uint8_t>(t[diff_ind]);
 108     // first different byte must be consecutive, and remaining bytes must be
 109     // 0xff for s and 0x00 for t
 110     if (byte_s != uint8_t{0xff} && byte_s + 1 == byte_t) {
 111       for (size_t i = diff_ind + 1; i < s.size(); ++i) {
 112         byte_s = static_cast<uint8_t>(s[i]);
 113         byte_t = static_cast<uint8_t>(t[i]);
 114         if (byte_s != uint8_t{0xff} || byte_t != uint8_t{0x00}) {
 115           return false;
 116         }
 117       }
 118       return true;
 119     } else {
 120       return false;
 121     }
 122   }
 123
 124   bool CanKeysWithDifferentByteContentsBeEqual() const override {
 125     return false;
 126   }
 127
 128   int CompareWithoutTimestamp(const Slice& a, const Slice& b) const override {
 129     return a.compare(b);
 130   }
 131 };
 132
 133 class ReverseBytewiseComparatorImpl : public BytewiseComparatorImpl {
 134  public:
 135   ReverseBytewiseComparatorImpl() { }
 136
 137   const char* Name() const override {
 138     return "rocksdb.ReverseBytewiseComparator";
 139   }
 140
 141   int Compare(const Slice& a, const Slice& b) const override {
 142     return -a.compare(b);
 143   }
 144
 145   void FindShortestSeparator(std::string* start,
 146                              const Slice& limit) const override {
 147     // Find length of common prefix
 148     size_t min_length = std::min(start->size(), limit.size());
 149     size_t diff_index = 0;
 150     while ((diff_index < min_length) &&
 151            ((*start)[diff_index] == limit[diff_index])) {
 152       diff_index++;
 153     }
 154
 155     assert(diff_index <= min_length);
 156     if (diff_index == min_length) {
 157       // Do not shorten if one string is a prefix of the other
 158       //
 159       // We could handle cases like:
 160       //     V
 161       // A A 2 X Y
 162       // A A 2
 163       // in a similar way as BytewiseComparator::FindShortestSeparator().
 164       // We keep it simple by not implementing it. We can come back to it
 165       // later when needed.
 166     } else {
 167       uint8_t start_byte = static_cast<uint8_t>((*start)[diff_index]);
 168       uint8_t limit_byte = static_cast<uint8_t>(limit[diff_index]);
 169       if (start_byte > limit_byte && diff_index < start->size() - 1) {
 170         // Case like
 171         //     V
 172         // A A 3 A A
 173         // A A 1 B B
 174         //
 175         // or
 176         //     v
 177         // A A 2 A A
 178         // A A 1 B B
 179         // In this case "AA2" will be good.
 180 #ifndef NDEBUG
 181         std::string old_start = *start;
 182 #endif
 183         start->resize(diff_index + 1);
 184 #ifndef NDEBUG
 185         assert(old_start >= *start);
 186 #endif
 187         assert(Slice(*start).compare(limit) > 0);
 188       }
 189     }
 190   }
 191
 192   void FindShortSuccessor(std::string* /*key*/) const override {
 193     // Don't do anything for simplicity.
 194   }
 195
 196   bool CanKeysWithDifferentByteContentsBeEqual() const override {
 197     return false;
 198   }
 199
 200   int CompareWithoutTimestamp(const Slice& a, const Slice& b) const override {
 201     return -a.compare(b);
 202   }
 203 };
 204 }// namespace
 205
 206 const Comparator* BytewiseComparator() {
 207   static BytewiseComparatorImpl bytewise;
 208   return &bytewise;
 209 }
 210
 211 const Comparator* ReverseBytewiseComparator() {
 212   static ReverseBytewiseComparatorImpl rbytewise;
 213   return &rbytewise;
 214 }
 215
 216 }  // namespace ROCKSDB_NAMESPACE