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