]>
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 | ||
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: | |
11fdf7f2 | 23 | virtual ~Comparator() {} |
7c673cae FG |
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. | |
494da23a TL |
58 | virtual void FindShortestSeparator(std::string* start, |
59 | const Slice& limit) const = 0; | |
7c673cae FG |
60 | |
61 | // Changes *key to a short string >= *key. | |
62 | // Simple comparator implementations may return with *key unchanged, | |
63 | // i.e., an implementation of this method that does nothing is correct. | |
64 | virtual void FindShortSuccessor(std::string* key) const = 0; | |
11fdf7f2 TL |
65 | |
66 | // if it is a wrapped comparator, may return the root one. | |
67 | // return itself it is not wrapped. | |
68 | virtual const Comparator* GetRootComparator() const { return this; } | |
69 | ||
70 | // given two keys, determine if t is the successor of s | |
71 | virtual bool IsSameLengthImmediateSuccessor(const Slice& /*s*/, | |
72 | const Slice& /*t*/) const { | |
73 | return false; | |
74 | } | |
75 | ||
76 | // return true if two keys with different byte sequences can be regarded | |
77 | // as equal by this comparator. | |
78 | // The major use case is to determine if DataBlockHashIndex is compatible | |
79 | // with the customized comparator. | |
80 | virtual bool CanKeysWithDifferentByteContentsBeEqual() const { return true; } | |
7c673cae FG |
81 | }; |
82 | ||
83 | // Return a builtin comparator that uses lexicographic byte-wise | |
84 | // ordering. The result remains the property of this module and | |
85 | // must not be deleted. | |
86 | extern const Comparator* BytewiseComparator(); | |
87 | ||
88 | // Return a builtin comparator that uses reverse lexicographic byte-wise | |
89 | // ordering. | |
90 | extern const Comparator* ReverseBytewiseComparator(); | |
91 | ||
92 | } // namespace rocksdb |