text: // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
  // Use of this source code is governed by a BSD-style license that can be
  // found in the LICENSE file. See the AUTHORS file for names of contributors.
  
  #include <algorithm>
  #include <stdint.h>
  #include "leveldb/comparator.h"
  #include "leveldb/slice.h"
  #include "port/port.h"
  #include "util/logging.h"
  
  namespace leveldb {
  
  Comparator::~Comparator() { }
  
  namespace {
  class BytewiseComparatorImpl : public Comparator {
   public:
    BytewiseComparatorImpl() { }
  
    virtual const char* Name() const {
      return "leveldb.BytewiseComparator";
    }
  
    virtual int Compare(const Slice& a, const Slice& b) const {
      return a.compare(b);
    }
  
    virtual void FindShortestSeparator(
        std::string* start,
        const Slice& limit) const {
      // Find length of common prefix
      size_t min_length = std::min<size_t>(start->size(), limit.size());
      size_t diff_index = 0;
      while ((diff_index < min_length) &&
             ((*start)[diff_index] == limit[diff_index])) {
        diff_index++;
      }
  
      if (diff_index >= min_length) {
        // Do not shorten if one string is a prefix of the other
      } else {
        uint8_t diff_byte = static_cast<uint8_t>((*start)[diff_index]);
        if (diff_byte < static_cast<uint8_t>(0xff) &&
            diff_byte + 1 < static_cast<uint8_t>(limit[diff_index])) {
          (*start)[diff_index]++;
          start->resize(diff_index + 1);
          assert(Compare(*start, limit) < 0);
        }
      }
    }
  
    virtual void FindShortSuccessor(std::string* key) const {
      // Find first character that can be incremented
      size_t n = key->size();
      for (size_t i = 0; i < n; i++) {
        const uint8_t byte = (*key)[i];
        if (byte != static_cast<uint8_t>(0xff)) {
          (*key)[i] = byte + 1;
          key->resize(i+1);
          return;
        }
      }
      // *key is a run of 0xffs.  Leave it alone.
    }
  };
  }  // namespace
  
  static port::OnceType once = LEVELDB_ONCE_INIT;
  static const Comparator* bytewise;
  
  static void InitModule() {
    bytewise = new BytewiseComparatorImpl;
  }
  
  const Comparator* BytewiseComparator() {
    port::InitOnce(&once, InitModule);
    return bytewise;
  }
  
  }  // namespace leveldb
  