/Users/deen/code/yugabyte-db/src/yb/rocksdb/table/block_based_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 | | // Copyright (c) 2012 The LevelDB Authors. All rights reserved. |
21 | | // Use of this source code is governed by a BSD-style license that can be |
22 | | // found in the LICENSE file. See the AUTHORS file for names of contributors. |
23 | | // |
24 | | // A filter block is stored near the end of a Table file. It contains |
25 | | // filters (e.g., bloom filters) for all data blocks in the table combined |
26 | | // into a single filter block. |
27 | | |
28 | | #pragma once |
29 | | |
30 | | #include <stddef.h> |
31 | | #include <stdint.h> |
32 | | |
33 | | #include <memory> |
34 | | #include <string> |
35 | | #include <vector> |
36 | | |
37 | | #include "yb/rocksdb/options.h" |
38 | | #include "yb/rocksdb/slice_transform.h" |
39 | | #include "yb/rocksdb/table/filter_block.h" |
40 | | #include "yb/rocksdb/table/format.h" |
41 | | #include "yb/rocksdb/util/hash.h" |
42 | | |
43 | | #include "yb/util/slice.h" |
44 | | |
45 | | namespace rocksdb { |
46 | | |
47 | | |
48 | | // A BlockBasedFilterBlockBuilder is used to construct all of the filters for a |
49 | | // particular Table. It generates a single string which is stored as |
50 | | // a special block in the Table. |
51 | | // |
52 | | // The sequence of calls to BlockBasedFilterBlockBuilder must match the regexp: |
53 | | // (StartBlock Add*)* Finish |
54 | | class BlockBasedFilterBlockBuilder : public FilterBlockBuilder { |
55 | | public: |
56 | | BlockBasedFilterBlockBuilder(const SliceTransform* prefix_extractor, |
57 | | const BlockBasedTableOptions& table_opt); |
58 | | |
59 | | virtual void StartBlock(uint64_t block_offset) override; |
60 | | virtual void Add(const Slice& key) override; |
61 | | virtual Slice Finish() override; |
62 | 1.24M | virtual bool ShouldFlush() const override { return false; } |
63 | | |
64 | | private: |
65 | | void AddKey(const Slice& key); |
66 | | void AddPrefix(const Slice& key); |
67 | | void GenerateFilter(); |
68 | | |
69 | | // important: all of these might point to invalid addresses |
70 | | // at the time of destruction of this filter block. destructor |
71 | | // should NOT dereference them. |
72 | | const FilterPolicy* policy_; |
73 | | const SliceTransform* prefix_extractor_; |
74 | | bool whole_key_filtering_; |
75 | | |
76 | | size_t prev_prefix_start_; // the position of the last appended prefix |
77 | | // to "entries_". |
78 | | size_t prev_prefix_size_; // the length of the last appended prefix to |
79 | | // "entries_". |
80 | | std::string entries_; // Flattened entry contents |
81 | | std::vector<size_t> start_; // Starting index in entries_ of each entry |
82 | | std::string result_; // Filter data computed so far |
83 | | std::vector<Slice> tmp_entries_; // policy_->CreateFilter() argument |
84 | | std::vector<uint32_t> filter_offsets_; |
85 | | |
86 | | // No copying allowed |
87 | | BlockBasedFilterBlockBuilder(const BlockBasedFilterBlockBuilder&); |
88 | | void operator=(const BlockBasedFilterBlockBuilder&); |
89 | | }; |
90 | | |
91 | | // A FilterBlockReader is used to parse filter from SST table. |
92 | | // KeyMayMatch and PrefixMayMatch would trigger filter checking |
93 | | class BlockBasedFilterBlockReader : public FilterBlockReader { |
94 | | public: |
95 | | // REQUIRES: "contents" and *policy must stay live while *this is live. |
96 | | BlockBasedFilterBlockReader(const SliceTransform* prefix_extractor, |
97 | | const BlockBasedTableOptions& table_opt, |
98 | | bool whole_key_filtering, |
99 | | BlockContents&& contents); |
100 | | virtual bool KeyMayMatch(const Slice& key, |
101 | | uint64_t block_offset = kNotValid) override; |
102 | | virtual bool PrefixMayMatch(const Slice& prefix, |
103 | | uint64_t block_offset = kNotValid) override; |
104 | | virtual size_t ApproximateMemoryUsage() const override; |
105 | | |
106 | | // convert this object to a human readable form |
107 | | std::string ToString() const override; |
108 | | |
109 | | private: |
110 | | const FilterPolicy* policy_; |
111 | | const SliceTransform* prefix_extractor_; |
112 | | bool whole_key_filtering_; |
113 | | const char* data_; // Pointer to filter data (at block-start) |
114 | | const char* offset_; // Pointer to beginning of offset array (at block-end) |
115 | | size_t num_; // Number of entries in offset array |
116 | | size_t base_lg_; // Encoding parameter (see kFilterBaseLg in .cc file) |
117 | | BlockContents contents_; |
118 | | |
119 | | bool MayMatch(const Slice& entry, uint64_t block_offset); |
120 | | |
121 | | // No copying allowed |
122 | | BlockBasedFilterBlockReader(const BlockBasedFilterBlockReader&); |
123 | | void operator=(const BlockBasedFilterBlockReader&); |
124 | | }; |
125 | | } // namespace rocksdb |