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 #include "rocksdb/rocksdb_namespace.h"
  14
  15 namespace ROCKSDB_NAMESPACE {
  16
  17 class Slice;
  18
  19 // A Comparator object provides a total order across slices that are
  20 // used as keys in an sstable or a database.  A Comparator implementation
  21 // must be thread-safe since rocksdb may invoke its methods concurrently
  22 // from multiple threads.
  23 class Comparator {
  24  public:
  25   Comparator() : timestamp_size_(0) {}
  26
  27   Comparator(size_t ts_sz) : timestamp_size_(ts_sz) {}
  28
  29   Comparator(const Comparator& orig) : timestamp_size_(orig.timestamp_size_) {}
  30
  31   Comparator& operator=(const Comparator& rhs) {
  32     if (this != &rhs) {
  33       timestamp_size_ = rhs.timestamp_size_;
  34     }
  35     return *this;
  36   }
  37
  38   virtual ~Comparator() {}
  39
  40   static const char* Type() { return "Comparator"; }
  41   // Three-way comparison.  Returns value:
  42   //   < 0 iff "a" < "b",
  43   //   == 0 iff "a" == "b",
  44   //   > 0 iff "a" > "b"
  45   virtual int Compare(const Slice& a, const Slice& b) const = 0;
  46
  47   // Compares two slices for equality. The following invariant should always
  48   // hold (and is the default implementation):
  49   //   Equal(a, b) iff Compare(a, b) == 0
  50   // Overwrite only if equality comparisons can be done more efficiently than
  51   // three-way comparisons.
  52   virtual bool Equal(const Slice& a, const Slice& b) const {
  53     return Compare(a, b) == 0;
  54   }
  55
  56   // The name of the comparator.  Used to check for comparator
  57   // mismatches (i.e., a DB created with one comparator is
  58   // accessed using a different comparator.
  59   //
  60   // The client of this package should switch to a new name whenever
  61   // the comparator implementation changes in a way that will cause
  62   // the relative ordering of any two keys to change.
  63   //
  64   // Names starting with "rocksdb." are reserved and should not be used
  65   // by any clients of this package.
  66   virtual const char* Name() const = 0;
  67
  68   // Advanced functions: these are used to reduce the space requirements
  69   // for internal data structures like index blocks.
  70
  71   // If *start < limit, changes *start to a short string in [start,limit).
  72   // Simple comparator implementations may return with *start unchanged,
  73   // i.e., an implementation of this method that does nothing is correct.
  74   virtual void FindShortestSeparator(std::string* start,
  75                                      const Slice& limit) const = 0;
  76
  77   // Changes *key to a short string >= *key.
  78   // Simple comparator implementations may return with *key unchanged,
  79   // i.e., an implementation of this method that does nothing is correct.
  80   virtual void FindShortSuccessor(std::string* key) const = 0;
  81
  82   // if it is a wrapped comparator, may return the root one.
  83   // return itself it is not wrapped.
  84   virtual const Comparator* GetRootComparator() const { return this; }
  85
  86   // given two keys, determine if t is the successor of s
  87   virtual bool IsSameLengthImmediateSuccessor(const Slice& /*s*/,
  88                                               const Slice& /*t*/) const {
  89     return false;
  90   }
  91
  92   // return true if two keys with different byte sequences can be regarded
  93   // as equal by this comparator.
  94   // The major use case is to determine if DataBlockHashIndex is compatible
  95   // with the customized comparator.
  96   virtual bool CanKeysWithDifferentByteContentsBeEqual() const { return true; }
  97
  98   inline size_t timestamp_size() const { return timestamp_size_; }
  99
 100   virtual int CompareWithoutTimestamp(const Slice& a, const Slice& b) const {
 101     return Compare(a, b);
 102   }
 103
 104   virtual int CompareTimestamp(const Slice& /*ts1*/,
 105                                const Slice& /*ts2*/) const {
 106     return 0;
 107   }
 108
 109  private:
 110   size_t timestamp_size_;
 111 };
 112
 113 // Return a builtin comparator that uses lexicographic byte-wise
 114 // ordering.  The result remains the property of this module and
 115 // must not be deleted.
 116 extern const Comparator* BytewiseComparator();
 117
 118 // Return a builtin comparator that uses reverse lexicographic byte-wise
 119 // ordering.
 120 extern const Comparator* ReverseBytewiseComparator();
 121
 122 }  // namespace ROCKSDB_NAMESPACE