1// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file. See the AUTHORS file for names of contributors.
4
5#ifndef STORAGE_LEVELDB_INCLUDE_COMPARATOR_H_
6#define STORAGE_LEVELDB_INCLUDE_COMPARATOR_H_
7
8#include <string>
9
10namespace leveldb {
11
12class Slice;
13
14// A Comparator object provides a total order across slices that are
15// used as keys in an sstable or a database.  A Comparator implementation
16// must be thread-safe since leveldb may invoke its methods concurrently
17// from multiple threads.
18class Comparator {
19 public:
20  virtual ~Comparator();
21
22  // Three-way comparison.  Returns value:
23  //   < 0 iff "a" < "b",
24  //   == 0 iff "a" == "b",
25  //   > 0 iff "a" > "b"
26  virtual int Compare(const Slice& a, const Slice& b) const = 0;
27
28  // The name of the comparator.  Used to check for comparator
29  // mismatches (i.e., a DB created with one comparator is
30  // accessed using a different comparator.
31  //
32  // The client of this package should switch to a new name whenever
33  // the comparator implementation changes in a way that will cause
34  // the relative ordering of any two keys to change.
35  //
36  // Names starting with "leveldb." are reserved and should not be used
37  // by any clients of this package.
38  virtual const char* Name() const = 0;
39
40  // Advanced functions: these are used to reduce the space requirements
41  // for internal data structures like index blocks.
42
43  // If *start < limit, changes *start to a short string in [start,limit).
44  // Simple comparator implementations may return with *start unchanged,
45  // i.e., an implementation of this method that does nothing is correct.
46  virtual void FindShortestSeparator(
47      std::string* start,
48      const Slice& limit) const = 0;
49
50  // Changes *key to a short string >= *key.
51  // Simple comparator implementations may return with *key unchanged,
52  // i.e., an implementation of this method that does nothing is correct.
53  virtual void FindShortSuccessor(std::string* key) const = 0;
54};
55
56// Return a builtin comparator that uses lexicographic byte-wise
57// ordering.  The result remains the property of this module and
58// must not be deleted.
59extern const Comparator* BytewiseComparator();
60
61}  // namespace leveldb
62
63#endif  // STORAGE_LEVELDB_INCLUDE_COMPARATOR_H_
64