/Users/deen/code/yugabyte-db/src/yb/rocksdb/table/fixed_size_filter_block.h
Line | Count | Source |
1 | | // Copyright (c) YugaByte, Inc. |
2 | | // |
3 | | // Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except |
4 | | // in compliance with the License. You may obtain a copy of the License at |
5 | | // |
6 | | // http://www.apache.org/licenses/LICENSE-2.0 |
7 | | // |
8 | | // Unless required by applicable law or agreed to in writing, software distributed under the License |
9 | | // is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express |
10 | | // or implied. See the License for the specific language governing permissions and limitations |
11 | | // under the License. |
12 | | // |
13 | | |
14 | | #ifndef YB_ROCKSDB_TABLE_FIXED_SIZE_FILTER_BLOCK_H |
15 | | #define YB_ROCKSDB_TABLE_FIXED_SIZE_FILTER_BLOCK_H |
16 | | |
17 | | #include <stddef.h> |
18 | | #include <stdint.h> |
19 | | |
20 | | #include <memory> |
21 | | #include <string> |
22 | | #include <vector> |
23 | | |
24 | | #include "yb/rocksdb/filter_policy.h" |
25 | | #include "yb/rocksdb/options.h" |
26 | | #include "yb/rocksdb/slice_transform.h" |
27 | | #include "yb/rocksdb/table/filter_block.h" |
28 | | #include "yb/rocksdb/table/format.h" |
29 | | #include "yb/rocksdb/util/hash.h" |
30 | | |
31 | | #include "yb/util/slice.h" |
32 | | |
33 | | namespace rocksdb { |
34 | | |
35 | | // A fixed size Bloom filter divides the Bloom Filter into blocks of fixed size |
36 | | // in which each block holds the information of a range of keys. |
37 | | // Each Bloom filter block is built as keys are inserted into the block. |
38 | | // As long as the terminating condition is reached, the Bloom filter block is flushed into disk |
39 | | // and its offset being written to the index block. |
40 | | |
41 | | // Since FixedSizeFilterBlockBuilder does not buffer any key, |
42 | | // FixedSizeFilterBlockBuilder treats each insertion independently |
43 | | // and won't check for duplicate keys. |
44 | | |
45 | | // The sequence of calls to FixedSizeFilterBlockBuilder must match the regexp: |
46 | | // (StartBlock Add* Finish)* |
47 | | class FixedSizeFilterBlockBuilder : public FilterBlockBuilder { |
48 | | public: |
49 | | FixedSizeFilterBlockBuilder(const SliceTransform* prefix_extractor, |
50 | | const BlockBasedTableOptions& table_opt); |
51 | | |
52 | 3.11k | ~FixedSizeFilterBlockBuilder() { |
53 | 3.11k | results_.clear(); |
54 | 3.11k | } |
55 | | |
56 | | // No copying allowed |
57 | | FixedSizeFilterBlockBuilder(const FixedSizeFilterBlockBuilder&) = delete; |
58 | | void operator=(const FixedSizeFilterBlockBuilder&) = delete; |
59 | | |
60 | | virtual void StartBlock(uint64_t block_offset) override; |
61 | | virtual void Add(const Slice& key) override; |
62 | | virtual bool ShouldFlush() const override; |
63 | | virtual Slice Finish() override; |
64 | | |
65 | | private: |
66 | | void AddKey(const Slice& key); |
67 | | void AddPrefix(const Slice& key); |
68 | | |
69 | | // Important: all of these might point to invalid addresses at the time of destruction of this |
70 | | // filter block. Destructor should NOT dereference them. |
71 | | const FilterPolicy* policy_; |
72 | | const SliceTransform* prefix_extractor_; |
73 | | bool whole_key_filtering_; |
74 | | |
75 | | std::unique_ptr<FilterBitsBuilder> bits_builder_; // writer to the results |
76 | | std::unique_ptr<const char[]> active_block_data_; |
77 | | std::vector<std::unique_ptr<const char[]>> results_; |
78 | | }; |
79 | | |
80 | | // A FilterBlockReader will attempt to read the block associated with the keys of interest. |
81 | | // KeyMayMatch and PrefixMayMatch would trigger filter checking. |
82 | | class FixedSizeFilterBlockReader : public FilterBlockReader { |
83 | | public: |
84 | | // REQUIRES: "contents" and *policy must stay live while *this is live. |
85 | | FixedSizeFilterBlockReader(const SliceTransform* prefix_extractor, |
86 | | const BlockBasedTableOptions& table_opt, |
87 | | bool whole_key_filtering, |
88 | | BlockContents&& contents); |
89 | | FixedSizeFilterBlockReader(const FixedSizeFilterBlockReader&) = delete; |
90 | | void operator=(const FixedSizeFilterBlockReader&) = delete; |
91 | | |
92 | | virtual bool KeyMayMatch(const Slice& key, |
93 | | uint64_t block_offset = 0) override; |
94 | | virtual bool PrefixMayMatch(const Slice& prefix, |
95 | | uint64_t block_offset = 0) override; |
96 | | virtual size_t ApproximateMemoryUsage() const override; |
97 | | |
98 | | // convert this object to a human readable form |
99 | | std::string ToString() const override; |
100 | | |
101 | | private: |
102 | | const FilterPolicy* policy_; |
103 | | const SliceTransform* prefix_extractor_; |
104 | | bool whole_key_filtering_; |
105 | | std::unique_ptr<FilterBitsReader> reader_; |
106 | | BlockContents contents_; |
107 | | |
108 | | // Checks whether entry is present in filter. Entry could be any binary data, but used here for |
109 | | // either key or key prefix when calling from corresponding public methods. |
110 | | bool MayMatch(const Slice& entry); |
111 | | |
112 | | }; |
113 | | } // namespace rocksdb |
114 | | |
115 | | #endif // YB_ROCKSDB_TABLE_FIXED_SIZE_FILTER_BLOCK_H |