Embedded Template Library 1.0
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,
74 typename THash2 = private_bloom_filter::null_hash,
75 typename THash3 = private_bloom_filter::null_hash>
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 {
105 flags.set(get_hash<THash1>(key));
106
108 {
109 flags.set(get_hash<THash2>(key));
110 }
111
113 {
114 flags.set(get_hash<THash3>(key));
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 {
132 exists2 = flags[get_hash<THash2>(key)];
133 }
134
135 // Do we have a third hash?
137 {
138 exists3 = flags[get_hash<THash3>(key)];
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.
181 return fold_bits<size_t, etl::log2<WIDTH>::value>(hash);
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
Definition: bitset_legacy.h:1102
size_t width() const
Returns the width of the Bloom filter.
Definition: bloom_filter.h:147
size_t usage() const
Returns the percentage of usage. Range 0 to 100.
Definition: bloom_filter.h:155
bool exists(parameter_t key) const
Definition: bloom_filter.h:123
void clear()
Clears the bloom filter of all entries.
Definition: bloom_filter.h:94
size_t count() const
Returns the number of filter flags set.
Definition: bloom_filter.h:163
void add(parameter_t key)
Definition: bloom_filter.h:103
Definition: bloom_filter.h:77
is_same
Definition: type_traits_generator.h:1041
bitset_ext
Definition: absolute.h:38
etl::conditional< etl::is_fundamental< T >::value||etl::is_pointer< T >::value, T, constT & >::type type
By default fundamental and pointer types are passed by value.
Definition: parameter_type.h:48
Definition: bloom_filter.h:52