src/leveldb/util/comparator.cc

   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