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

   1 // Copyright (c) 2011-present, Facebook, Inc.  All rights reserved.
   2 // This source code is licensed under the BSD-style license found in the
   3 // LICENSE file in the root directory of this source tree. An additional grant
   4 // of patent rights can be found in the PATENTS file in the same 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 #ifndef STORAGE_ROCKSDB_INCLUDE_COMPARATOR_H_
  10 #define STORAGE_ROCKSDB_INCLUDE_COMPARATOR_H_
  11
  12 #include <string>
  13
  14 namespace rocksdb {
  15
  16 class Slice;
  17
  18 // A Comparator object provides a total order across slices that are
  19 // used as keys in an sstable or a database.  A Comparator implementation
  20 // must be thread-safe since rocksdb may invoke its methods concurrently
  21 // from multiple threads.
  22 class Comparator {
  23  public:
  24   virtual ~Comparator();
  25
  26   // Three-way comparison.  Returns value:
  27   //   < 0 iff "a" < "b",
  28   //   == 0 iff "a" == "b",
  29   //   > 0 iff "a" > "b"
  30   virtual int Compare(const Slice& a, const Slice& b) const = 0;
  31
  32   // Compares two slices for equality. The following invariant should always
  33   // hold (and is the default implementation):
  34   //   Equal(a, b) iff Compare(a, b) == 0
  35   // Overwrite only if equality comparisons can be done more efficiently than
  36   // three-way comparisons.
  37   virtual bool Equal(const Slice& a, const Slice& b) const {
  38     return Compare(a, b) == 0;
  39   }
  40
  41   // The name of the comparator.  Used to check for comparator
  42   // mismatches (i.e., a DB created with one comparator is
  43   // accessed using a different comparator.
  44   //
  45   // The client of this package should switch to a new name whenever
  46   // the comparator implementation changes in a way that will cause
  47   // the relative ordering of any two keys to change.
  48   //
  49   // Names starting with "rocksdb." are reserved and should not be used
  50   // by any clients of this package.
  51   virtual const char* Name() const = 0;
  52
  53   // Advanced functions: these are used to reduce the space requirements
  54   // for internal data structures like index blocks.
  55
  56   // If *start < limit, changes *start to a short string in [start,limit).
  57   // Simple comparator implementations may return with *start unchanged,
  58   // i.e., an implementation of this method that does nothing is correct.
  59   virtual void FindShortestSeparator(
  60       std::string* start,
  61       const Slice& limit) const = 0;
  62
  63   // Changes *key to a short string >= *key.
  64   // Simple comparator implementations may return with *key unchanged,
  65   // i.e., an implementation of this method that does nothing is correct.
  66   virtual void FindShortSuccessor(std::string* key) const = 0;
  67 };
  68
  69 // Return a builtin comparator that uses lexicographic byte-wise
  70 // ordering.  The result remains the property of this module and
  71 // must not be deleted.
  72 extern const Comparator* BytewiseComparator();
  73
  74 // Return a builtin comparator that uses reverse lexicographic byte-wise
  75 // ordering.
  76 extern const Comparator* ReverseBytewiseComparator();
  77
  78 }  // namespace rocksdb
  79
  80 #endif  // STORAGE_ROCKSDB_INCLUDE_COMPARATOR_H_