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_