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 <algorithm>
  11 #include <memory>
  12 #include <stdint.h>
  13 #include "rocksdb/comparator.h"
  14 #include "rocksdb/slice.h"
  15 #include "port/port.h"
  16 #include "util/logging.h"
  17
  18 namespace rocksdb {
  19
  20 namespace {
  21 class BytewiseComparatorImpl : public Comparator {
  22  public:
  23   BytewiseComparatorImpl() { }
  24
  25   virtual const char* Name() const override {
  26     return "leveldb.BytewiseComparator";
  27   }
  28
  29   virtual int Compare(const Slice& a, const Slice& b) const override {
  30     return a.compare(b);
  31   }
  32
  33   virtual bool Equal(const Slice& a, const Slice& b) const override {
  34     return a == b;
  35   }
  36
  37   virtual void FindShortestSeparator(std::string* start,
  38                                      const Slice& limit) const override {
  39     // Find length of common prefix
  40     size_t min_length = std::min(start->size(), limit.size());
  41     size_t diff_index = 0;
  42     while ((diff_index < min_length) &&
  43            ((*start)[diff_index] == limit[diff_index])) {
  44       diff_index++;
  45     }
  46
  47     if (diff_index >= min_length) {
  48       // Do not shorten if one string is a prefix of the other
  49     } else {
  50       uint8_t start_byte = static_cast<uint8_t>((*start)[diff_index]);
  51       uint8_t limit_byte = static_cast<uint8_t>(limit[diff_index]);
  52       if (start_byte >= limit_byte) {
  53         // Cannot shorten since limit is smaller than start or start is
  54         // already the shortest possible.
  55         return;
  56       }
  57       assert(start_byte < limit_byte);
  58
  59       if (diff_index < limit.size() - 1 || start_byte + 1 < limit_byte) {
  60         (*start)[diff_index]++;
  61         start->resize(diff_index + 1);
  62       } else {
  63         //     v
  64         // A A 1 A A A
  65         // A A 2
  66         //
  67         // Incrementing the current byte will make start bigger than limit, we
  68         // will skip this byte, and find the first non 0xFF byte in start and
  69         // increment it.
  70         diff_index++;
  71
  72         while (diff_index < start->size()) {
  73           // Keep moving until we find the first non 0xFF byte to
  74           // increment it
  75           if (static_cast<uint8_t>((*start)[diff_index]) <
  76               static_cast<uint8_t>(0xff)) {
  77             (*start)[diff_index]++;
  78             start->resize(diff_index + 1);
  79             break;
  80           }
  81           diff_index++;
  82         }
  83       }
  84       assert(Compare(*start, limit) < 0);
  85     }
  86   }
  87
  88   virtual void FindShortSuccessor(std::string* key) const override {
  89     // Find first character that can be incremented
  90     size_t n = key->size();
  91     for (size_t i = 0; i < n; i++) {
  92       const uint8_t byte = (*key)[i];
  93       if (byte != static_cast<uint8_t>(0xff)) {
  94         (*key)[i] = byte + 1;
  95         key->resize(i+1);
  96         return;
  97       }
  98     }
  99     // *key is a run of 0xffs.  Leave it alone.
 100   }
 101
 102   virtual bool IsSameLengthImmediateSuccessor(const Slice& s,
 103                                               const Slice& t) const override {
 104     if (s.size() != t.size() || s.size() == 0) {
 105       return false;
 106     }
 107     size_t diff_ind = s.difference_offset(t);
 108     // same slice
 109     if (diff_ind >= s.size()) return false;
 110     uint8_t byte_s = static_cast<uint8_t>(s[diff_ind]);
 111     uint8_t byte_t = static_cast<uint8_t>(t[diff_ind]);
 112     // first different byte must be consecutive, and remaining bytes must be
 113     // 0xff for s and 0x00 for t
 114     if (byte_s != uint8_t{0xff} && byte_s + 1 == byte_t) {
 115       for (size_t i = diff_ind + 1; i < s.size(); ++i) {
 116         byte_s = static_cast<uint8_t>(s[i]);
 117         byte_t = static_cast<uint8_t>(t[i]);
 118         if (byte_s != uint8_t{0xff} || byte_t != uint8_t{0x00}) {
 119           return false;
 120         }
 121       }
 122       return true;
 123     } else {
 124       return false;
 125     }
 126   }
 127
 128   virtual bool CanKeysWithDifferentByteContentsBeEqual() const override {
 129     return false;
 130   }
 131 };
 132
 133 class ReverseBytewiseComparatorImpl : public BytewiseComparatorImpl {
 134  public:
 135   ReverseBytewiseComparatorImpl() { }
 136
 137   virtual const char* Name() const override {
 138     return "rocksdb.ReverseBytewiseComparator";
 139   }
 140
 141   virtual 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   virtual bool CanKeysWithDifferentByteContentsBeEqual() const override {
 197     return false;
 198   }
 199 };
 200 }// namespace
 201
 202 const Comparator* BytewiseComparator() {
 203   static BytewiseComparatorImpl bytewise;
 204   return &bytewise;
 205 }
 206
 207 const Comparator* ReverseBytewiseComparator() {
 208   static ReverseBytewiseComparatorImpl rbytewise;
 209   return &rbytewise;
 210 }
 211
 212 }  // namespace rocksdb