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