199a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com// Copyright (c) 2012 The LevelDB Authors. All rights reserved. 299a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com// Use of this source code is governed by a BSD-style license that can be 399a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com// found in the LICENSE file. See the AUTHORS file for names of contributors. 499a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com// 599a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com// A filter block is stored near the end of a Table file. It contains 699a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com// filters (e.g., bloom filters) for all data blocks in the table combined 799a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com// into a single filter block. 899a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 999a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com#ifndef STORAGE_LEVELDB_TABLE_FILTER_BLOCK_H_ 1099a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com#define STORAGE_LEVELDB_TABLE_FILTER_BLOCK_H_ 1199a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 1299a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com#include <stddef.h> 1399a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com#include <stdint.h> 1499a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com#include <string> 1599a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com#include <vector> 1699a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com#include "leveldb/slice.h" 1799a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com#include "util/hash.h" 1899a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 1999a7585544fc162a5f8dd39a6add00776a981efesanjay@google.comnamespace leveldb { 2099a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 2199a7585544fc162a5f8dd39a6add00776a981efesanjay@google.comclass FilterPolicy; 2299a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 2399a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com// A FilterBlockBuilder is used to construct all of the filters for a 2499a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com// particular Table. It generates a single string which is stored as 2599a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com// a special block in the Table. 2699a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com// 2799a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com// The sequence of calls to FilterBlockBuilder must match the regexp: 2899a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com// (StartBlock AddKey*)* Finish 2999a7585544fc162a5f8dd39a6add00776a981efesanjay@google.comclass FilterBlockBuilder { 3099a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com public: 3199a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com explicit FilterBlockBuilder(const FilterPolicy*); 3299a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 3399a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com void StartBlock(uint64_t block_offset); 3499a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com void AddKey(const Slice& key); 3599a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com Slice Finish(); 3699a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 3799a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com private: 3899a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com void GenerateFilter(); 3999a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 4099a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com const FilterPolicy* policy_; 4199a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com std::string keys_; // Flattened key contents 4299a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com std::vector<size_t> start_; // Starting index in keys_ of each key 4399a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com std::string result_; // Filter data computed so far 4499a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com std::vector<Slice> tmp_keys_; // policy_->CreateFilter() argument 4599a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com std::vector<uint32_t> filter_offsets_; 4699a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 4799a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com // No copying allowed 4899a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com FilterBlockBuilder(const FilterBlockBuilder&); 4999a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com void operator=(const FilterBlockBuilder&); 5099a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com}; 5199a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 5299a7585544fc162a5f8dd39a6add00776a981efesanjay@google.comclass FilterBlockReader { 5399a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com public: 5499a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com // REQUIRES: "contents" and *policy must stay live while *this is live. 5599a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com FilterBlockReader(const FilterPolicy* policy, const Slice& contents); 5699a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com bool KeyMayMatch(uint64_t block_offset, const Slice& key); 5799a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 5899a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com private: 5999a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com const FilterPolicy* policy_; 6099a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com const char* data_; // Pointer to filter data (at block-start) 6199a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com const char* offset_; // Pointer to beginning of offset array (at block-end) 6299a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com size_t num_; // Number of entries in offset array 6399a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com size_t base_lg_; // Encoding parameter (see kFilterBaseLg in .cc file) 6499a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com}; 6599a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 6699a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com} 6799a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com 6899a7585544fc162a5f8dd39a6add00776a981efesanjay@google.com#endif // STORAGE_LEVELDB_TABLE_FILTER_BLOCK_H_ 69