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.
15 #include "rocksdb/filter_policy.h"
21 class FullFilterBitsBuilder
: public FilterBitsBuilder
{
23 explicit FullFilterBitsBuilder(const size_t bits_per_key
,
24 const size_t num_probes
);
26 ~FullFilterBitsBuilder();
28 virtual void AddKey(const Slice
& key
) override
;
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 // +----------------------------------------------------------------+
41 // +----------------------------------------------------------------+
42 // | ... | num_probes : 1 byte | num_lines : 4 bytes |
43 // +----------------------------------------------------------------+
44 virtual Slice
Finish(std::unique_ptr
<const char[]>* buf
) override
;
46 // Calculate num of entries fit into a space.
47 virtual int CalculateNumEntry(const uint32_t space
) override
;
49 // Calculate space for new filter. This is reverse of CalculateNumEntry.
50 uint32_t CalculateSpace(const int num_entry
, uint32_t* total_bits
,
54 friend class FullFilterBlockTest_DuplicateEntries_Test
;
57 std::vector
<uint32_t> hash_entries_
;
59 // Get totalbits that optimized for cpu cache line
60 uint32_t GetTotalBitsForLocality(uint32_t total_bits
);
62 // Reserve space for new filter
63 char* ReserveSpace(const int num_entry
, uint32_t* total_bits
,
66 // Assuming single threaded access to this function.
67 void AddHash(uint32_t h
, char* data
, uint32_t num_lines
, uint32_t total_bits
);
70 FullFilterBitsBuilder(const FullFilterBitsBuilder
&);
71 void operator=(const FullFilterBitsBuilder
&);
74 } // namespace rocksdb