1 | // Copyright (c) 2012 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 | // A database can be configured with a custom FilterPolicy object. |
6 | // This object is responsible for creating a small filter from a set |
7 | // of keys. These filters are stored in leveldb and are consulted |
8 | // automatically by leveldb to decide whether or not to read some |
9 | // information from disk. In many cases, a filter can cut down the |
10 | // number of disk seeks form a handful to a single disk seek per |
11 | // DB::Get() call. |
12 | // |
13 | // Most people will want to use the builtin bloom filter support (see |
14 | // NewBloomFilterPolicy() below). |
15 | |
16 | #ifndef STORAGE_LEVELDB_INCLUDE_FILTER_POLICY_H_ |
17 | #define STORAGE_LEVELDB_INCLUDE_FILTER_POLICY_H_ |
18 | |
19 | #include <string> |
20 | |
21 | #include "leveldb/export.h" |
22 | |
23 | namespace leveldb { |
24 | |
25 | class Slice; |
26 | |
27 | class LEVELDB_EXPORT FilterPolicy { |
28 | public: |
29 | virtual ~FilterPolicy(); |
30 | |
31 | // Return the name of this policy. Note that if the filter encoding |
32 | // changes in an incompatible way, the name returned by this method |
33 | // must be changed. Otherwise, old incompatible filters may be |
34 | // passed to methods of this type. |
35 | virtual const char* Name() const = 0; |
36 | |
37 | // keys[0,n-1] contains a list of keys (potentially with duplicates) |
38 | // that are ordered according to the user supplied comparator. |
39 | // Append a filter that summarizes keys[0,n-1] to *dst. |
40 | // |
41 | // Warning: do not change the initial contents of *dst. Instead, |
42 | // append the newly constructed filter to *dst. |
43 | virtual void CreateFilter(const Slice* keys, int n, |
44 | std::string* dst) const = 0; |
45 | |
46 | // "filter" contains the data appended by a preceding call to |
47 | // CreateFilter() on this class. This method must return true if |
48 | // the key was in the list of keys passed to CreateFilter(). |
49 | // This method may return true or false if the key was not on the |
50 | // list, but it should aim to return false with a high probability. |
51 | virtual bool KeyMayMatch(const Slice& key, const Slice& filter) const = 0; |
52 | }; |
53 | |
54 | // Return a new filter policy that uses a bloom filter with approximately |
55 | // the specified number of bits per key. A good value for bits_per_key |
56 | // is 10, which yields a filter with ~ 1% false positive rate. |
57 | // |
58 | // Callers must delete the result after any database that is using the |
59 | // result has been closed. |
60 | // |
61 | // Note: if you are using a custom comparator that ignores some parts |
62 | // of the keys being compared, you must not use NewBloomFilterPolicy() |
63 | // and must provide your own FilterPolicy that also ignores the |
64 | // corresponding parts of the keys. For example, if the comparator |
65 | // ignores trailing spaces, it would be incorrect to use a |
66 | // FilterPolicy (like NewBloomFilterPolicy) that does not ignore |
67 | // trailing spaces in keys. |
68 | LEVELDB_EXPORT const FilterPolicy* NewBloomFilterPolicy(int bits_per_key); |
69 | |
70 | } // namespace leveldb |
71 | |
72 | #endif // STORAGE_LEVELDB_INCLUDE_FILTER_POLICY_H_ |
73 | |