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 filter block is stored near the end of a Table file. It contains
6 // filters (e.g., bloom filters) for all data blocks in the table combined
7 // into a single filter block.
8 9 #ifndef STORAGE_LEVELDB_TABLE_FILTER_BLOCK_H_
10 #define STORAGE_LEVELDB_TABLE_FILTER_BLOCK_H_
11 12 #include <stddef.h>
13 #include <stdint.h>
14 15 #include <string>
16 #include <vector>
17 18 #include "leveldb/slice.h"
19 #include "util/hash.h"
20 21 namespace leveldb {
22 23 class FilterPolicy;
24 25 // A FilterBlockBuilder is used to construct all of the filters for a
26 // particular Table. It generates a single string which is stored as
27 // a special block in the Table.
28 //
29 // The sequence of calls to FilterBlockBuilder must match the regexp:
30 // (StartBlock AddKey*)* Finish
31 class FilterBlockBuilder {
32 public:
33 explicit FilterBlockBuilder(const FilterPolicy*);
34 35 FilterBlockBuilder(const FilterBlockBuilder&) = delete;
36 FilterBlockBuilder& operator=(const FilterBlockBuilder&) = delete;
37 38 void StartBlock(uint64_t block_offset);
39 void AddKey(const Slice& key);
40 Slice Finish();
41 42 private:
43 void GenerateFilter();
44 45 const FilterPolicy* policy_;
46 std::string keys_; // Flattened key contents
47 std::vector<size_t> start_; // Starting index in keys_ of each key
48 std::string result_; // Filter data computed so far
49 std::vector<Slice> tmp_keys_; // policy_->CreateFilter() argument
50 std::vector<uint32_t> filter_offsets_;
51 };
52 53 class FilterBlockReader {
54 public:
55 // REQUIRES: "contents" and *policy must stay live while *this is live.
56 FilterBlockReader(const FilterPolicy* policy, const Slice& contents);
57 bool KeyMayMatch(uint64_t block_offset, const Slice& key);
58 59 private:
60 const FilterPolicy* policy_;
61 const char* data_; // Pointer to filter data (at block-start)
62 const char* offset_; // Pointer to beginning of offset array (at block-end)
63 size_t num_; // Number of entries in offset array
64 size_t base_lg_; // Encoding parameter (see kFilterBaseLg in .cc file)
65 };
66 67 } // namespace leveldb
68 69 #endif // STORAGE_LEVELDB_TABLE_FILTER_BLOCK_H_
70