1179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Copyright (c) 2011 The LevelDB Authors. All rights reserved. 2179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// Use of this source code is governed by a BSD-style license that can be 3179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org// found in the LICENSE file. See the AUTHORS file for names of contributors. 4179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 551f892d349df9ed408f5a0e6e012667e5eae5f8bgabor@google.com#include <algorithm> 6179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include <stdint.h> 7fbd97aa4c5325eace57d24b89845b9581bac9324jorlow@chromium.org#include "leveldb/comparator.h" 8fbd97aa4c5325eace57d24b89845b9581bac9324jorlow@chromium.org#include "leveldb/slice.h" 9158f767acaed4c39cbb3ee8128fe896e155ec40csanjay@google.com#include "port/port.h" 10179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org#include "util/logging.h" 11179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 12179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgnamespace leveldb { 13179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 14179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgComparator::~Comparator() { } 15179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 16179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgnamespace { 17179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgclass BytewiseComparatorImpl : public Comparator { 18179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org public: 19179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org BytewiseComparatorImpl() { } 20179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 21179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual const char* Name() const { 22179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return "leveldb.BytewiseComparator"; 23179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 24179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 25179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual int Compare(const Slice& a, const Slice& b) const { 26179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return a.compare(b); 27179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 28179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 29179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual void FindShortestSeparator( 30179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org std::string* start, 31179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const Slice& limit) const { 32179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Find length of common prefix 33179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org size_t min_length = std::min(start->size(), limit.size()); 34179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org size_t diff_index = 0; 35179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org while ((diff_index < min_length) && 36179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org ((*start)[diff_index] == limit[diff_index])) { 37179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org diff_index++; 38179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 39179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 40179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (diff_index >= min_length) { 41179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Do not shorten if one string is a prefix of the other 42179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } else { 43179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org uint8_t diff_byte = static_cast<uint8_t>((*start)[diff_index]); 44179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (diff_byte < static_cast<uint8_t>(0xff) && 45179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org diff_byte + 1 < static_cast<uint8_t>(limit[diff_index])) { 46179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org (*start)[diff_index]++; 47179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org start->resize(diff_index + 1); 48179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org assert(Compare(*start, limit) < 0); 49179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 50179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 51179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 52179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 53179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org virtual void FindShortSuccessor(std::string* key) const { 54179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // Find first character that can be incremented 55179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org size_t n = key->size(); 561511be6edb54b6ade2bfad94256f76bc191e92ecdgrogan@chromium.org for (size_t i = 0; i < n; i++) { 57179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org const uint8_t byte = (*key)[i]; 58179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org if (byte != static_cast<uint8_t>(0xff)) { 59179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org (*key)[i] = byte + 1; 60179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org key->resize(i+1); 61179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org return; 62179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 63179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 64179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org // *key is a run of 0xffs. Leave it alone. 65179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org } 66179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org}; 6745b9940be332834440bd5299419f396e38085ebehans@chromium.org} // namespace 68ac271d8b01dd3a1b6d57b1a4a0e0d28e00f67780hans@chromium.org 69158f767acaed4c39cbb3ee8128fe896e155ec40csanjay@google.comstatic port::OnceType once = LEVELDB_ONCE_INIT; 70158f767acaed4c39cbb3ee8128fe896e155ec40csanjay@google.comstatic const Comparator* bytewise; 71158f767acaed4c39cbb3ee8128fe896e155ec40csanjay@google.com 72158f767acaed4c39cbb3ee8128fe896e155ec40csanjay@google.comstatic void InitModule() { 73158f767acaed4c39cbb3ee8128fe896e155ec40csanjay@google.com bytewise = new BytewiseComparatorImpl; 74158f767acaed4c39cbb3ee8128fe896e155ec40csanjay@google.com} 75179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 76179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.orgconst Comparator* BytewiseComparator() { 77158f767acaed4c39cbb3ee8128fe896e155ec40csanjay@google.com port::InitOnce(&once, InitModule); 78ac271d8b01dd3a1b6d57b1a4a0e0d28e00f67780hans@chromium.org return bytewise; 79179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org} 80179be588c25dccaa963df9c9c104fc6229435483jorlow@chromium.org 8145b9940be332834440bd5299419f396e38085ebehans@chromium.org} // namespace leveldb 82