]>
Commit | Line | Data |
---|---|---|
11fdf7f2 TL |
1 | // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. |
2 | // This source code is licensed under both the GPLv2 (found in the | |
3 | // COPYING file in the root directory) and Apache 2.0 License | |
4 | // (found in the LICENSE.Apache file in the root directory). | |
5 | // Copyright (c) 2012 The LevelDB Authors. All rights reserved. | |
6 | // Use of this source code is governed by a BSD-style license that can be | |
7 | // found in the LICENSE file. See the AUTHORS file for names of contributors. | |
8 | ||
9 | #pragma once | |
10 | ||
11 | #include <memory> | |
12 | #include <string> | |
13 | #include <vector> | |
14 | ||
15 | #include "rocksdb/filter_policy.h" | |
16 | ||
17 | namespace rocksdb { | |
18 | ||
19 | class Slice; | |
20 | ||
21 | class FullFilterBitsBuilder : public FilterBitsBuilder { | |
22 | public: | |
23 | explicit FullFilterBitsBuilder(const size_t bits_per_key, | |
24 | const size_t num_probes); | |
25 | ||
26 | ~FullFilterBitsBuilder(); | |
27 | ||
28 | virtual void AddKey(const Slice& key) override; | |
29 | ||
30 | // Create a filter that for hashes [0, n-1], the filter is allocated here | |
31 | // When creating filter, it is ensured that | |
32 | // total_bits = num_lines * CACHE_LINE_SIZE * 8 | |
33 | // dst len is >= 5, 1 for num_probes, 4 for num_lines | |
34 | // Then total_bits = (len - 5) * 8, and cache_line_size could be calculated | |
35 | // +----------------------------------------------------------------+ | |
36 | // | filter data with length total_bits/8 | | |
37 | // +----------------------------------------------------------------+ | |
38 | // | | | |
39 | // | ... | | |
40 | // | | | |
41 | // +----------------------------------------------------------------+ | |
42 | // | ... | num_probes : 1 byte | num_lines : 4 bytes | | |
43 | // +----------------------------------------------------------------+ | |
44 | virtual Slice Finish(std::unique_ptr<const char[]>* buf) override; | |
45 | ||
46 | // Calculate num of entries fit into a space. | |
47 | virtual int CalculateNumEntry(const uint32_t space) override; | |
48 | ||
49 | // Calculate space for new filter. This is reverse of CalculateNumEntry. | |
50 | uint32_t CalculateSpace(const int num_entry, uint32_t* total_bits, | |
51 | uint32_t* num_lines); | |
52 | ||
53 | private: | |
54 | friend class FullFilterBlockTest_DuplicateEntries_Test; | |
55 | size_t bits_per_key_; | |
56 | size_t num_probes_; | |
57 | std::vector<uint32_t> hash_entries_; | |
58 | ||
59 | // Get totalbits that optimized for cpu cache line | |
60 | uint32_t GetTotalBitsForLocality(uint32_t total_bits); | |
61 | ||
62 | // Reserve space for new filter | |
63 | char* ReserveSpace(const int num_entry, uint32_t* total_bits, | |
64 | uint32_t* num_lines); | |
65 | ||
66 | // Assuming single threaded access to this function. | |
67 | void AddHash(uint32_t h, char* data, uint32_t num_lines, uint32_t total_bits); | |
68 | ||
69 | // No Copy allowed | |
70 | FullFilterBitsBuilder(const FullFilterBitsBuilder&); | |
71 | void operator=(const FullFilterBitsBuilder&); | |
72 | }; | |
73 | ||
74 | } // namespace rocksdb |