]>
Commit | Line | Data |
---|---|---|
7c673cae | 1 | // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. |
11fdf7f2 TL |
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). | |
7c673cae FG |
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 | ||
11fdf7f2 | 9 | #pragma once |
7c673cae FG |
10 | |
11 | #include <string> | |
12 | ||
1e59de90 | 13 | #include "rocksdb/customizable.h" |
f67539c2 TL |
14 | #include "rocksdb/rocksdb_namespace.h" |
15 | ||
16 | namespace ROCKSDB_NAMESPACE { | |
7c673cae FG |
17 | |
18 | class Slice; | |
19 | ||
1e59de90 TL |
20 | // The general interface for comparing two Slices are defined for both of |
21 | // Comparator and some internal data structures. | |
22 | class CompareInterface { | |
23 | public: | |
24 | virtual ~CompareInterface() {} | |
25 | ||
26 | // Three-way comparison. Returns value: | |
27 | // < 0 iff "a" < "b", | |
28 | // == 0 iff "a" == "b", | |
29 | // > 0 iff "a" > "b" | |
30 | // Note that Compare(a, b) also compares timestamp if timestamp size is | |
31 | // non-zero. For the same user key with different timestamps, larger (newer) | |
32 | // timestamp comes first. | |
33 | virtual int Compare(const Slice& a, const Slice& b) const = 0; | |
34 | }; | |
35 | ||
7c673cae FG |
36 | // A Comparator object provides a total order across slices that are |
37 | // used as keys in an sstable or a database. A Comparator implementation | |
38 | // must be thread-safe since rocksdb may invoke its methods concurrently | |
39 | // from multiple threads. | |
1e59de90 TL |
40 | // |
41 | // Exceptions MUST NOT propagate out of overridden functions into RocksDB, | |
42 | // because RocksDB is not exception-safe. This could cause undefined behavior | |
43 | // including data loss, unreported corruption, deadlocks, and more. | |
44 | class Comparator : public Customizable, public CompareInterface { | |
7c673cae | 45 | public: |
f67539c2 TL |
46 | Comparator() : timestamp_size_(0) {} |
47 | ||
48 | Comparator(size_t ts_sz) : timestamp_size_(ts_sz) {} | |
49 | ||
50 | Comparator(const Comparator& orig) : timestamp_size_(orig.timestamp_size_) {} | |
51 | ||
52 | Comparator& operator=(const Comparator& rhs) { | |
53 | if (this != &rhs) { | |
54 | timestamp_size_ = rhs.timestamp_size_; | |
55 | } | |
56 | return *this; | |
57 | } | |
58 | ||
1e59de90 | 59 | ~Comparator() override {} |
7c673cae | 60 | |
1e59de90 TL |
61 | static Status CreateFromString(const ConfigOptions& opts, |
62 | const std::string& id, | |
63 | const Comparator** comp); | |
f67539c2 | 64 | static const char* Type() { return "Comparator"; } |
7c673cae FG |
65 | |
66 | // The name of the comparator. Used to check for comparator | |
67 | // mismatches (i.e., a DB created with one comparator is | |
68 | // accessed using a different comparator. | |
69 | // | |
70 | // The client of this package should switch to a new name whenever | |
71 | // the comparator implementation changes in a way that will cause | |
72 | // the relative ordering of any two keys to change. | |
73 | // | |
74 | // Names starting with "rocksdb." are reserved and should not be used | |
75 | // by any clients of this package. | |
1e59de90 TL |
76 | const char* Name() const override = 0; |
77 | ||
78 | // Compares two slices for equality. The following invariant should always | |
79 | // hold (and is the default implementation): | |
80 | // Equal(a, b) iff Compare(a, b) == 0 | |
81 | // Overwrite only if equality comparisons can be done more efficiently than | |
82 | // three-way comparisons. | |
83 | virtual bool Equal(const Slice& a, const Slice& b) const { | |
84 | return Compare(a, b) == 0; | |
85 | } | |
7c673cae FG |
86 | |
87 | // Advanced functions: these are used to reduce the space requirements | |
88 | // for internal data structures like index blocks. | |
89 | ||
90 | // If *start < limit, changes *start to a short string in [start,limit). | |
91 | // Simple comparator implementations may return with *start unchanged, | |
92 | // i.e., an implementation of this method that does nothing is correct. | |
494da23a TL |
93 | virtual void FindShortestSeparator(std::string* start, |
94 | const Slice& limit) const = 0; | |
7c673cae FG |
95 | |
96 | // Changes *key to a short string >= *key. | |
97 | // Simple comparator implementations may return with *key unchanged, | |
98 | // i.e., an implementation of this method that does nothing is correct. | |
99 | virtual void FindShortSuccessor(std::string* key) const = 0; | |
11fdf7f2 | 100 | |
11fdf7f2 | 101 | // given two keys, determine if t is the successor of s |
1e59de90 TL |
102 | // BUG: only return true if no other keys starting with `t` are ordered |
103 | // before `t`. Otherwise, the auto_prefix_mode can omit entries within | |
104 | // iterator bounds that have same prefix as upper bound but different | |
105 | // prefix from seek key. | |
11fdf7f2 TL |
106 | virtual bool IsSameLengthImmediateSuccessor(const Slice& /*s*/, |
107 | const Slice& /*t*/) const { | |
108 | return false; | |
109 | } | |
110 | ||
111 | // return true if two keys with different byte sequences can be regarded | |
112 | // as equal by this comparator. | |
113 | // The major use case is to determine if DataBlockHashIndex is compatible | |
114 | // with the customized comparator. | |
115 | virtual bool CanKeysWithDifferentByteContentsBeEqual() const { return true; } | |
f67539c2 | 116 | |
1e59de90 TL |
117 | // if it is a wrapped comparator, may return the root one. |
118 | // return itself it is not wrapped. | |
119 | virtual const Comparator* GetRootComparator() const { return this; } | |
120 | ||
f67539c2 TL |
121 | inline size_t timestamp_size() const { return timestamp_size_; } |
122 | ||
20effc67 TL |
123 | int CompareWithoutTimestamp(const Slice& a, const Slice& b) const { |
124 | return CompareWithoutTimestamp(a, /*a_has_ts=*/true, b, /*b_has_ts=*/true); | |
f67539c2 TL |
125 | } |
126 | ||
20effc67 TL |
127 | // For two events e1 and e2 whose timestamps are t1 and t2 respectively, |
128 | // Returns value: | |
129 | // < 0 iff t1 < t2 | |
130 | // == 0 iff t1 == t2 | |
131 | // > 0 iff t1 > t2 | |
132 | // Note that an all-zero byte array will be the smallest (oldest) timestamp | |
1e59de90 TL |
133 | // of the same length, and a byte array with all bits 1 will be the largest. |
134 | // In the future, we can extend Comparator so that subclasses can specify | |
135 | // both largest and smallest timestamps. | |
f67539c2 TL |
136 | virtual int CompareTimestamp(const Slice& /*ts1*/, |
137 | const Slice& /*ts2*/) const { | |
138 | return 0; | |
139 | } | |
140 | ||
20effc67 TL |
141 | virtual int CompareWithoutTimestamp(const Slice& a, bool /*a_has_ts*/, |
142 | const Slice& b, bool /*b_has_ts*/) const { | |
143 | return Compare(a, b); | |
144 | } | |
145 | ||
1e59de90 TL |
146 | virtual bool EqualWithoutTimestamp(const Slice& a, const Slice& b) const { |
147 | return 0 == | |
148 | CompareWithoutTimestamp(a, /*a_has_ts=*/true, b, /*b_has_ts=*/true); | |
149 | } | |
150 | ||
f67539c2 TL |
151 | private: |
152 | size_t timestamp_size_; | |
7c673cae FG |
153 | }; |
154 | ||
155 | // Return a builtin comparator that uses lexicographic byte-wise | |
156 | // ordering. The result remains the property of this module and | |
157 | // must not be deleted. | |
158 | extern const Comparator* BytewiseComparator(); | |
159 | ||
160 | // Return a builtin comparator that uses reverse lexicographic byte-wise | |
161 | // ordering. | |
162 | extern const Comparator* ReverseBytewiseComparator(); | |
163 | ||
f67539c2 | 164 | } // namespace ROCKSDB_NAMESPACE |