131 lines
3.8 KiB
C++
131 lines
3.8 KiB
C++
// Copyright (c) 2011-present, Facebook, Inc. All rights reserved.
|
|
// This source code is licensed under both the GPLv2 (found in the
|
|
// COPYING file in the root directory) and Apache 2.0 License
|
|
// (found in the LICENSE.Apache file in the root directory).
|
|
//
|
|
// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
|
|
// Use of this source code is governed by a BSD-style license that can be
|
|
// found in the LICENSE file. See the AUTHORS file for names of contributors.
|
|
|
|
#include <algorithm>
|
|
#include <memory>
|
|
#include <stdint.h>
|
|
#include "rocksdb/comparator.h"
|
|
#include "rocksdb/slice.h"
|
|
#include "port/port.h"
|
|
#include "util/logging.h"
|
|
|
|
namespace rocksdb {
|
|
|
|
Comparator::~Comparator() { }
|
|
|
|
namespace {
|
|
class BytewiseComparatorImpl : public Comparator {
|
|
public:
|
|
BytewiseComparatorImpl() { }
|
|
|
|
virtual const char* Name() const override {
|
|
return "leveldb.BytewiseComparator";
|
|
}
|
|
|
|
virtual int Compare(const Slice& a, const Slice& b) const override {
|
|
return a.compare(b);
|
|
}
|
|
|
|
virtual bool Equal(const Slice& a, const Slice& b) const override {
|
|
return a == b;
|
|
}
|
|
|
|
virtual void FindShortestSeparator(std::string* start,
|
|
const Slice& limit) const override {
|
|
// Find length of common prefix
|
|
size_t min_length = std::min(start->size(), limit.size());
|
|
size_t diff_index = 0;
|
|
while ((diff_index < min_length) &&
|
|
((*start)[diff_index] == limit[diff_index])) {
|
|
diff_index++;
|
|
}
|
|
|
|
if (diff_index >= min_length) {
|
|
// Do not shorten if one string is a prefix of the other
|
|
} else {
|
|
uint8_t start_byte = static_cast<uint8_t>((*start)[diff_index]);
|
|
uint8_t limit_byte = static_cast<uint8_t>(limit[diff_index]);
|
|
if (start_byte >= limit_byte || (diff_index == start->size() - 1)) {
|
|
// Cannot shorten since limit is smaller than start or start is
|
|
// already the shortest possible.
|
|
return;
|
|
}
|
|
assert(start_byte < limit_byte);
|
|
|
|
if (diff_index < limit.size() - 1 || start_byte + 1 < limit_byte) {
|
|
(*start)[diff_index]++;
|
|
start->resize(diff_index + 1);
|
|
} else {
|
|
// v
|
|
// A A 1 A A A
|
|
// A A 2
|
|
//
|
|
// Incrementing the current byte will make start bigger than limit, we
|
|
// will skip this byte, and find the first non 0xFF byte in start and
|
|
// increment it.
|
|
diff_index++;
|
|
|
|
while (diff_index < start->size()) {
|
|
// Keep moving until we find the first non 0xFF byte to
|
|
// increment it
|
|
if (static_cast<uint8_t>((*start)[diff_index]) <
|
|
static_cast<uint8_t>(0xff)) {
|
|
(*start)[diff_index]++;
|
|
start->resize(diff_index + 1);
|
|
break;
|
|
}
|
|
diff_index++;
|
|
}
|
|
}
|
|
assert(Compare(*start, limit) < 0);
|
|
}
|
|
}
|
|
|
|
virtual void FindShortSuccessor(std::string* key) const override {
|
|
// Find first character that can be incremented
|
|
size_t n = key->size();
|
|
for (size_t i = 0; i < n; i++) {
|
|
const uint8_t byte = (*key)[i];
|
|
if (byte != static_cast<uint8_t>(0xff)) {
|
|
(*key)[i] = byte + 1;
|
|
key->resize(i+1);
|
|
return;
|
|
}
|
|
}
|
|
// *key is a run of 0xffs. Leave it alone.
|
|
}
|
|
};
|
|
|
|
class ReverseBytewiseComparatorImpl : public BytewiseComparatorImpl {
|
|
public:
|
|
ReverseBytewiseComparatorImpl() { }
|
|
|
|
virtual const char* Name() const override {
|
|
return "rocksdb.ReverseBytewiseComparator";
|
|
}
|
|
|
|
virtual int Compare(const Slice& a, const Slice& b) const override {
|
|
return -a.compare(b);
|
|
}
|
|
};
|
|
|
|
}// namespace
|
|
|
|
const Comparator* BytewiseComparator() {
|
|
static BytewiseComparatorImpl bytewise;
|
|
return &bytewise;
|
|
}
|
|
|
|
const Comparator* ReverseBytewiseComparator() {
|
|
static ReverseBytewiseComparatorImpl rbytewise;
|
|
return &rbytewise;
|
|
}
|
|
|
|
} // namespace rocksdb
|