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 <algorithm> 6 #include <stdint.h> 7 #include "leveldb/comparator.h" 8 #include "leveldb/slice.h" 9 #include "port/port.h" 10 #include "util/logging.h" 11 12 namespace leveldb { 13 14 Comparator::~Comparator() { } 15 16 namespace { 17 class BytewiseComparatorImpl : public Comparator { 18 public: 19 BytewiseComparatorImpl() { } 20 21 virtual const char* Name() const { 22 return "leveldb.BytewiseComparator"; 23 } 24 25 virtual int Compare(const Slice& a, const Slice& b) const { 26 return a.compare(b); 27 } 28 29 virtual void FindShortestSeparator( 30 std::string* start, 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])) { 37 diff_index++; 38 } 39 40 if (diff_index >= min_length) { 41 // Do not shorten if one string is a prefix of the other 42 } else { 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); 49 } 50 } 51 } 52 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)) { 59 (*key)[i] = byte + 1; 60 key->resize(i+1); 61 return; 62 } 63 } 64 // *key is a run of 0xffs. Leave it alone. 65 } 66 }; 67 } // namespace 68 69 static port::OnceType once = LEVELDB_ONCE_INIT; 70 static const Comparator* bytewise; 71 72 static void InitModule() { 73 bytewise = new BytewiseComparatorImpl; 74 } 75 76 const Comparator* BytewiseComparator() { 77 port::InitOnce(&once, InitModule); 78 return bytewise; 79 } 80 81 } // namespace leveldb 82
