Embedded Template Library 1.0
Loading...
Searching...
No Matches
bloom_filter.h
Go to the documentation of this file.
1
2
3/******************************************************************************
4The MIT License(MIT)
5
6Embedded Template Library.
7https://github.com/ETLCPP/etl
8https://www.etlcpp.com
9
10Copyright(c) 2014 John Wellbelove
11
12Permission is hereby granted, free of charge, to any person obtaining a copy
13of this software and associated documentation files(the "Software"), to deal
14in the Software without restriction, including without limitation the rights
15to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
16copies of the Software, and to permit persons to whom the Software is
17furnished to do so, subject to the following conditions :
18
19The above copyright notice and this permission notice shall be included in all
20copies or substantial portions of the Software.
21
22THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
23IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
24FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
25AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
26LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
27OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
28SOFTWARE.
29******************************************************************************/
30
31#ifndef ETL_BLOOM_FILTER_INCLUDED
32#define ETL_BLOOM_FILTER_INCLUDED
33
34#include "platform.h"
35#include "parameter_type.h"
36#include "bitset.h"
37#include "type_traits.h"
38#include "binary.h"
39#include "log.h"
40#include "power.h"
41
45
46namespace etl
47{
48 namespace private_bloom_filter
49 {
50 // Placeholder null hash for defaulted template parameters.
51 struct null_hash
52 {
53 template <typename T>
54 size_t operator ()(T)
55 {
56 return 0;
57 }
58 };
59 }
60
61 //***************************************************************************
71 //***************************************************************************
72 template <size_t Desired_Width,
73 typename THash1,
77 {
78 private:
79
82
83 public:
84
85 enum
86 {
87 // Make the most efficient use of the bitset.
89 };
90
91 //***************************************************************************
93 //***************************************************************************
94 void clear()
95 {
96 flags.reset();
97 }
98
99 //***************************************************************************
102 //***************************************************************************
103 void add(parameter_t key)
104 {
106
108 {
110 }
111
113 {
115 }
116 }
117
118 //***************************************************************************
122 //***************************************************************************
123 bool exists(parameter_t key) const
124 {
125 bool exists1 = flags[get_hash<THash1>(key)];
126 bool exists2 = true;
127 bool exists3 = true;
128
129 // Do we have a second hash?
131 {
133 }
134
135 // Do we have a third hash?
137 {
139 }
140
141 return exists1 && exists2 && exists3;
142 }
143
144 //***************************************************************************
146 //***************************************************************************
147 size_t width() const
148 {
149 return WIDTH;
150 }
151
152 //***************************************************************************
154 //***************************************************************************
155 size_t usage() const
156 {
157 return (100 * count()) / WIDTH;
158 }
159
160 //***************************************************************************
162 //***************************************************************************
163 size_t count() const
164 {
165 return flags.count();
166 }
167
168 private:
169
170 //***************************************************************************
174 //***************************************************************************
175 template <typename THash>
176 size_t get_hash(parameter_t key) const
177 {
178 size_t hash = THash()(key);
179
180 // Fold the hash down to fit the width.
182 }
183
185 etl::bitset<WIDTH> flags;
186 };
187}
188
189#endif
190
Definition flags.h:53
ETL_CONSTEXPR14 flags< T, MASK > & set() ETL_NOEXCEPT
Set the bits.
Definition flags.h:102
ETL_CONSTEXPR14 flags< T, MASK > & reset() ETL_NOEXCEPT
Reset the bit at the pattern.
Definition flags.h:157
Bitset forward declaration.
Definition bitset_legacy.h:1130
size_t width() const
Returns the width of the Bloom filter.
Definition bloom_filter.h:147
size_t count() const
Returns the number of filter flags set.
Definition bloom_filter.h:163
void clear()
Clears the bloom filter of all entries.
Definition bloom_filter.h:94
bool exists(parameter_t key) const
Definition bloom_filter.h:123
size_t usage() const
Returns the percentage of usage. Range 0 to 100.
Definition bloom_filter.h:155
void add(parameter_t key)
Definition bloom_filter.h:103
Definition bloom_filter.h:77
is_same
Definition type_traits_generator.h:1036
bitset_ext
Definition absolute.h:38
pair holds two objects of arbitrary type
Definition utility.h:164
Definition bloom_filter.h:52