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
23namespace leveldb {
24
25class Slice;
26
27class 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.
68LEVELDB_EXPORT const FilterPolicy* NewBloomFilterPolicy(int bits_per_key);
69
70} // namespace leveldb
71
72#endif // STORAGE_LEVELDB_INCLUDE_FILTER_POLICY_H_
73