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:
Comparator()25   Comparator() : timestamp_size_(0) {}
26 
Comparator(size_t ts_sz)27   Comparator(size_t ts_sz) : timestamp_size_(ts_sz) {}
28 
Comparator(const Comparator & orig)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 
~Comparator()38   virtual ~Comparator() {}
39 
Type()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   // Note that Compare(a, b) also compares timestamp if timestamp size is
46   // non-zero. For the same user key with different timestamps, larger (newer)
47   // timestamp comes first.
48   virtual int Compare(const Slice& a, const Slice& b) const = 0;
49 
50   // Compares two slices for equality. The following invariant should always
51   // hold (and is the default implementation):
52   //   Equal(a, b) iff Compare(a, b) == 0
53   // Overwrite only if equality comparisons can be done more efficiently than
54   // three-way comparisons.
Equal(const Slice & a,const Slice & b)55   virtual bool Equal(const Slice& a, const Slice& b) const {
56     return Compare(a, b) == 0;
57   }
58 
59   // The name of the comparator.  Used to check for comparator
60   // mismatches (i.e., a DB created with one comparator is
61   // accessed using a different comparator.
62   //
63   // The client of this package should switch to a new name whenever
64   // the comparator implementation changes in a way that will cause
65   // the relative ordering of any two keys to change.
66   //
67   // Names starting with "rocksdb." are reserved and should not be used
68   // by any clients of this package.
69   virtual const char* Name() const = 0;
70 
71   // Advanced functions: these are used to reduce the space requirements
72   // for internal data structures like index blocks.
73 
74   // If *start < limit, changes *start to a short string in [start,limit).
75   // Simple comparator implementations may return with *start unchanged,
76   // i.e., an implementation of this method that does nothing is correct.
77   virtual void FindShortestSeparator(std::string* start,
78                                      const Slice& limit) const = 0;
79 
80   // Changes *key to a short string >= *key.
81   // Simple comparator implementations may return with *key unchanged,
82   // i.e., an implementation of this method that does nothing is correct.
83   virtual void FindShortSuccessor(std::string* key) const = 0;
84 
85   // if it is a wrapped comparator, may return the root one.
86   // return itself it is not wrapped.
GetRootComparator()87   virtual const Comparator* GetRootComparator() const { return this; }
88 
89   // given two keys, determine if t is the successor of s
IsSameLengthImmediateSuccessor(const Slice &,const Slice &)90   virtual bool IsSameLengthImmediateSuccessor(const Slice& /*s*/,
91                                               const Slice& /*t*/) const {
92     return false;
93   }
94 
95   // return true if two keys with different byte sequences can be regarded
96   // as equal by this comparator.
97   // The major use case is to determine if DataBlockHashIndex is compatible
98   // with the customized comparator.
CanKeysWithDifferentByteContentsBeEqual()99   virtual bool CanKeysWithDifferentByteContentsBeEqual() const { return true; }
100 
timestamp_size()101   inline size_t timestamp_size() const { return timestamp_size_; }
102 
CompareWithoutTimestamp(const Slice & a,const Slice & b)103   int CompareWithoutTimestamp(const Slice& a, const Slice& b) const {
104     return CompareWithoutTimestamp(a, /*a_has_ts=*/true, b, /*b_has_ts=*/true);
105   }
106 
107   // For two events e1 and e2 whose timestamps are t1 and t2 respectively,
108   // Returns value:
109   // < 0  iff t1 < t2
110   // == 0 iff t1 == t2
111   // > 0  iff t1 > t2
112   // Note that an all-zero byte array will be the smallest (oldest) timestamp
113   // of the same length.
CompareTimestamp(const Slice &,const Slice &)114   virtual int CompareTimestamp(const Slice& /*ts1*/,
115                                const Slice& /*ts2*/) const {
116     return 0;
117   }
118 
CompareWithoutTimestamp(const Slice & a,bool,const Slice & b,bool)119   virtual int CompareWithoutTimestamp(const Slice& a, bool /*a_has_ts*/,
120                                       const Slice& b, bool /*b_has_ts*/) const {
121     return Compare(a, b);
122   }
123 
124  private:
125   size_t timestamp_size_;
126 };
127 
128 // Return a builtin comparator that uses lexicographic byte-wise
129 // ordering.  The result remains the property of this module and
130 // must not be deleted.
131 extern const Comparator* BytewiseComparator();
132 
133 // Return a builtin comparator that uses reverse lexicographic byte-wise
134 // ordering.
135 extern const Comparator* ReverseBytewiseComparator();
136 
137 }  // namespace ROCKSDB_NAMESPACE
138