/Users/deen/code/yugabyte-db/src/yb/rocksdb/table/full_filter_block.h
Line | Count | Source |
1 | | // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. |
2 | | // This source code is licensed under the BSD-style license found in the |
3 | | // LICENSE file in the root directory of this source tree. An additional grant |
4 | | // of patent rights can be found in the PATENTS file in the same directory. |
5 | | // |
6 | | // The following only applies to changes made to this file as part of YugaByte development. |
7 | | // |
8 | | // Portions Copyright (c) YugaByte, Inc. |
9 | | // |
10 | | // Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except |
11 | | // in compliance with the License. You may obtain a copy of the License at |
12 | | // |
13 | | // http://www.apache.org/licenses/LICENSE-2.0 |
14 | | // |
15 | | // Unless required by applicable law or agreed to in writing, software distributed under the License |
16 | | // is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express |
17 | | // or implied. See the License for the specific language governing permissions and limitations |
18 | | // under the License. |
19 | | // |
20 | | |
21 | | #pragma once |
22 | | |
23 | | #include <stddef.h> |
24 | | #include <stdint.h> |
25 | | |
26 | | #include <memory> |
27 | | #include <string> |
28 | | #include <vector> |
29 | | |
30 | | #include "yb/rocksdb/filter_policy.h" |
31 | | #include "yb/rocksdb/options.h" |
32 | | #include "yb/rocksdb/slice_transform.h" |
33 | | #include "yb/rocksdb/table/filter_block.h" |
34 | | #include "yb/rocksdb/table/format.h" |
35 | | #include "yb/rocksdb/util/hash.h" |
36 | | |
37 | | #include "yb/util/slice.h" |
38 | | |
39 | | namespace rocksdb { |
40 | | |
41 | | class FilterPolicy; |
42 | | class FilterBitsBuilder; |
43 | | class FilterBitsReader; |
44 | | |
45 | | // A FullFilterBlockBuilder is used to construct a full filter for a |
46 | | // particular Table. It generates a single string which is stored as |
47 | | // a special block in the Table. |
48 | | // The format of full filter block is: |
49 | | // +----------------------------------------------------------------+ |
50 | | // | full filter for all keys in sst file | |
51 | | // +----------------------------------------------------------------+ |
52 | | // The full filter can be very large. At the end of it, we put |
53 | | // num_probes: how many hash functions are used in bloom filter |
54 | | // |
55 | | class FullFilterBlockBuilder : public FilterBlockBuilder { |
56 | | public: |
57 | | explicit FullFilterBlockBuilder(const SliceTransform* prefix_extractor, |
58 | | bool whole_key_filtering, |
59 | | FilterBitsBuilder* filter_bits_builder); |
60 | | // bits_builder is created in filter_policy, it should be passed in here |
61 | | // directly. and be deleted here |
62 | 3.45k | ~FullFilterBlockBuilder() {} |
63 | | |
64 | 3.45k | virtual void StartBlock(uint64_t block_offset) override {} |
65 | | virtual void Add(const Slice& key) override; |
66 | | virtual Slice Finish() override; |
67 | 516k | virtual bool ShouldFlush() const override { return false; } |
68 | | |
69 | | private: |
70 | | // important: all of these might point to invalid addresses |
71 | | // at the time of destruction of this filter block. destructor |
72 | | // should NOT dereference them. |
73 | | const SliceTransform* prefix_extractor_; |
74 | | bool whole_key_filtering_; |
75 | | |
76 | | uint32_t num_added_; |
77 | | std::unique_ptr<FilterBitsBuilder> filter_bits_builder_; |
78 | | std::unique_ptr<const char[]> filter_data_; |
79 | | |
80 | | void AddKey(const Slice& key); |
81 | | void AddPrefix(const Slice& key); |
82 | | |
83 | | // No copying allowed |
84 | | FullFilterBlockBuilder(const FullFilterBlockBuilder&); |
85 | | void operator=(const FullFilterBlockBuilder&); |
86 | | }; |
87 | | |
88 | | // A FilterBlockReader is used to parse filter from SST table. |
89 | | // KeyMayMatch and PrefixMayMatch would trigger filter checking |
90 | | class FullFilterBlockReader : public FilterBlockReader { |
91 | | public: |
92 | | // REQUIRES: "contents" and filter_bits_reader must stay live |
93 | | // while *this is live. |
94 | | explicit FullFilterBlockReader(const SliceTransform* prefix_extractor, |
95 | | bool whole_key_filtering, |
96 | | const Slice& contents, |
97 | | FilterBitsReader* filter_bits_reader); |
98 | | explicit FullFilterBlockReader(const SliceTransform* prefix_extractor, |
99 | | bool whole_key_filtering, |
100 | | BlockContents&& contents, |
101 | | FilterBitsReader* filter_bits_reader); |
102 | | |
103 | | // bits_reader is created in filter_policy, it should be passed in here |
104 | | // directly. and be deleted here |
105 | 4.00k | ~FullFilterBlockReader() {} |
106 | | |
107 | | virtual bool KeyMayMatch(const Slice& key, |
108 | | uint64_t block_offset = kNotValid) override; |
109 | | virtual bool PrefixMayMatch(const Slice& prefix, |
110 | | uint64_t block_offset = kNotValid) override; |
111 | | virtual size_t ApproximateMemoryUsage() const override; |
112 | | |
113 | | private: |
114 | | const SliceTransform* prefix_extractor_; |
115 | | bool whole_key_filtering_; |
116 | | |
117 | | std::unique_ptr<FilterBitsReader> filter_bits_reader_; |
118 | | Slice contents_; |
119 | | BlockContents block_contents_; |
120 | | std::unique_ptr<const char[]> filter_data_; |
121 | | |
122 | | bool MayMatch(const Slice& entry); |
123 | | |
124 | | // No copying allowed |
125 | | FullFilterBlockReader(const FullFilterBlockReader&); |
126 | | void operator=(const FullFilterBlockReader&); |
127 | | }; |
128 | | |
129 | | } // namespace rocksdb |