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