Line data    Source code

       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        1565 : Comparator::~Comparator() { }
      15             : 
      16             : namespace {
      17           0 : class BytewiseComparatorImpl : public Comparator {
      18             :  public:
      19         190 :   BytewiseComparatorImpl() { }
      20             : 
      21         617 :   virtual const char* Name() const {
      22         617 :     return "leveldb.BytewiseComparator";
      23             :   }
      24             : 
      25      664881 :   virtual int Compare(const Slice& a, const Slice& b) const {
      26      665244 :     return a.compare(b);
      27             :   }
      28             : 
      29         395 :   virtual void FindShortestSeparator(
      30             :       std::string* start,
      31             :       const Slice& limit) const {
      32             :     // Find length of common prefix
      33        1185 :     size_t min_length = std::min(start->size(), limit.size());
      34         395 :     size_t diff_index = 0;
      35        2239 :     while ((diff_index < min_length) &&
      36         922 :            ((*start)[diff_index] == limit[diff_index])) {
      37         527 :       diff_index++;
      38             :     }
      39             : 
      40         395 :     if (diff_index >= min_length) {
      41             :       // Do not shorten if one string is a prefix of the other
      42             :     } else {
      43         395 :       uint8_t diff_byte = static_cast<uint8_t>((*start)[diff_index]);
      44         790 :       if (diff_byte < static_cast<uint8_t>(0xff) &&
      45         395 :           diff_byte + 1 < static_cast<uint8_t>(limit[diff_index])) {
      46         363 :         (*start)[diff_index]++;
      47         363 :         start->resize(diff_index + 1);
      48         726 :         assert(Compare(*start, limit) < 0);
      49             :       }
      50             :     }
      51         395 :   }
      52             : 
      53         122 :   virtual void FindShortSuccessor(std::string* key) const {
      54             :     // Find first character that can be incremented
      55         122 :     size_t n = key->size();
      56         122 :     for (size_t i = 0; i < n; i++) {
      57         122 :       const uint8_t byte = (*key)[i];
      58         122 :       if (byte != static_cast<uint8_t>(0xff)) {
      59         122 :         (*key)[i] = byte + 1;
      60         122 :         key->resize(i+1);
      61         122 :         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          95 : static void InitModule() {
      73         190 :   bytewise = new BytewiseComparatorImpl;
      74          95 : }
      75             : 
      76         808 : const Comparator* BytewiseComparator() {
      77         808 :   port::InitOnce(&once, InitModule);
      78         808 :   return bytewise;
      79             : }
      80             : 
      81             : }  // namespace leveldb