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.
7 #include "leveldb/comparator.h"
8 #include "leveldb/slice.h"
10 #include "util/logging.h"
14 Comparator::~Comparator() { }
17 class BytewiseComparatorImpl : public Comparator {
19 BytewiseComparatorImpl() { }
21 virtual const char* Name() const {
22 return "leveldb.BytewiseComparator";
25 virtual int Compare(const Slice& a, const Slice& b) const {
29 virtual void FindShortestSeparator(
31 const Slice& limit) const {
32 // Find length of common prefix
33 size_t min_length = std::min(start->size(), limit.size());
34 size_t diff_index = 0;
35 while ((diff_index < min_length) &&
36 ((*start)[diff_index] == limit[diff_index])) {
40 if (diff_index >= min_length) {
41 // Do not shorten if one string is a prefix of the other
43 uint8_t diff_byte = static_cast<uint8_t>((*start)[diff_index]);
44 if (diff_byte < static_cast<uint8_t>(0xff) &&
45 diff_byte + 1 < static_cast<uint8_t>(limit[diff_index])) {
46 (*start)[diff_index]++;
47 start->resize(diff_index + 1);
48 assert(Compare(*start, limit) < 0);
53 virtual void FindShortSuccessor(std::string* key) const {
54 // Find first character that can be incremented
55 size_t n = key->size();
56 for (size_t i = 0; i < n; i++) {
57 const uint8_t byte = (*key)[i];
58 if (byte != static_cast<uint8_t>(0xff)) {
64 // *key is a run of 0xffs. Leave it alone.
69 static port::OnceType once = LEVELDB_ONCE_INIT;
70 static const Comparator* bytewise;
72 static void InitModule() {
73 bytewise = new BytewiseComparatorImpl;
76 const Comparator* BytewiseComparator() {
77 port::InitOnce(&once, InitModule);
81 } // namespace leveldb