ceph/src/rocksdb/include/rocksdb/comparator.h

   1 // Copyright (c) 2011-present, Facebook, Inc.  All rights reserved.
   2 //  This source code is licensed under both the GPLv2 (found in the
   3 //  COPYING file in the root directory) and Apache 2.0 License
   4 //  (found in the LICENSE.Apache file in the root directory).
   5 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
   6 // Use of this source code is governed by a BSD-style license that can be
   7 // found in the LICENSE file. See the AUTHORS file for names of contributors.
   8
   9 #pragma once
  10
  11 #include <string>
  12
  13 namespace rocksdb {
  14
  15 class Slice;
  16
  17 // A Comparator object provides a total order across slices that are
  18 // used as keys in an sstable or a database.  A Comparator implementation
  19 // must be thread-safe since rocksdb may invoke its methods concurrently
  20 // from multiple threads.
  21 class Comparator {
  22  public:
  23   virtual ~Comparator() {}
  24
  25   // Three-way comparison.  Returns value:
  26   //   < 0 iff "a" < "b",
  27   //   == 0 iff "a" == "b",
  28   //   > 0 iff "a" > "b"
  29   virtual int Compare(const Slice& a, const Slice& b) const = 0;
  30
  31   // Compares two slices for equality. The following invariant should always
  32   // hold (and is the default implementation):
  33   //   Equal(a, b) iff Compare(a, b) == 0
  34   // Overwrite only if equality comparisons can be done more efficiently than
  35   // three-way comparisons.
  36   virtual bool Equal(const Slice& a, const Slice& b) const {
  37     return Compare(a, b) == 0;
  38   }
  39
  40   // The name of the comparator.  Used to check for comparator
  41   // mismatches (i.e., a DB created with one comparator is
  42   // accessed using a different comparator.
  43   //
  44   // The client of this package should switch to a new name whenever
  45   // the comparator implementation changes in a way that will cause
  46   // the relative ordering of any two keys to change.
  47   //
  48   // Names starting with "rocksdb." are reserved and should not be used
  49   // by any clients of this package.
  50   virtual const char* Name() const = 0;
  51
  52   // Advanced functions: these are used to reduce the space requirements
  53   // for internal data structures like index blocks.
  54
  55   // If *start < limit, changes *start to a short string in [start,limit).
  56   // Simple comparator implementations may return with *start unchanged,
  57   // i.e., an implementation of this method that does nothing is correct.
  58   virtual void FindShortestSeparator(
  59       std::string* start,
  60       const Slice& limit) const = 0;
  61
  62   // Changes *key to a short string >= *key.
  63   // Simple comparator implementations may return with *key unchanged,
  64   // i.e., an implementation of this method that does nothing is correct.
  65   virtual void FindShortSuccessor(std::string* key) const = 0;
  66
  67   // if it is a wrapped comparator, may return the root one.
  68   // return itself it is not wrapped.
  69   virtual const Comparator* GetRootComparator() const { return this; }
  70
  71   // given two keys, determine if t is the successor of s
  72   virtual bool IsSameLengthImmediateSuccessor(const Slice& /*s*/,
  73                                               const Slice& /*t*/) const {
  74     return false;
  75   }
  76
  77   // return true if two keys with different byte sequences can be regarded
  78   // as equal by this comparator.
  79   // The major use case is to determine if DataBlockHashIndex is compatible
  80   // with the customized comparator.
  81   virtual bool CanKeysWithDifferentByteContentsBeEqual() const { return true; }
  82 };
  83
  84 // Return a builtin comparator that uses lexicographic byte-wise
  85 // ordering.  The result remains the property of this module and
  86 // must not be deleted.
  87 extern const Comparator* BytewiseComparator();
  88
  89 // Return a builtin comparator that uses reverse lexicographic byte-wise
  90 // ordering.
  91 extern const Comparator* ReverseBytewiseComparator();
  92
  93 }  // namespace rocksdb