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 namespace leveldb { 22 23 class Slice; 24 25 class FilterPolicy { 26 public: 27 virtual ~FilterPolicy(); 28 29 // Return the name of this policy. Note that if the filter encoding 30 // changes in an incompatible way, the name returned by this method 31 // must be changed. Otherwise, old incompatible filters may be 32 // passed to methods of this type. 33 virtual const char* Name() const = 0; 34 35 // keys[0,n-1] contains a list of keys (potentially with duplicates) 36 // that are ordered according to the user supplied comparator. 37 // Append a filter that summarizes keys[0,n-1] to *dst. 38 // 39 // Warning: do not change the initial contents of *dst. Instead, 40 // append the newly constructed filter to *dst. 41 virtual void CreateFilter(const Slice* keys, int n, std::string* dst) 42 const = 0; 43 44 // "filter" contains the data appended by a preceding call to 45 // CreateFilter() on this class. This method must return true if 46 // the key was in the list of keys passed to CreateFilter(). 47 // This method may return true or false if the key was not on the 48 // list, but it should aim to return false with a high probability. 49 virtual bool KeyMayMatch(const Slice& key, const Slice& filter) const = 0; 50 }; 51 52 // Return a new filter policy that uses a bloom filter with approximately 53 // the specified number of bits per key. A good value for bits_per_key 54 // is 10, which yields a filter with ~ 1% false positive rate. 55 // 56 // Callers must delete the result after any database that is using the 57 // result has been closed. 58 // 59 // Note: if you are using a custom comparator that ignores some parts 60 // of the keys being compared, you must not use NewBloomFilterPolicy() 61 // and must provide your own FilterPolicy that also ignores the 62 // corresponding parts of the keys. For example, if the comparator 63 // ignores trailing spaces, it would be incorrect to use a 64 // FilterPolicy (like NewBloomFilterPolicy) that does not ignore 65 // trailing spaces in keys. 66 extern const FilterPolicy* NewBloomFilterPolicy(int bits_per_key); 67 68 } 69 70 #endif // STORAGE_LEVELDB_INCLUDE_FILTER_POLICY_H_ 71