1 /*
2  * Authored by Alex Hultman, 2018-2019.
3  * Intellectual property of third-party.
4 
5  * Licensed under the Apache License, Version 2.0 (the "License");
6  * you may not use this file except in compliance with the License.
7  * You may obtain a copy of the License at
8 
9  *     http://www.apache.org/licenses/LICENSE-2.0
10 
11  * Unless required by applicable law or agreed to in writing, software
12  * distributed under the License is distributed on an "AS IS" BASIS,
13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and
15  * limitations under the License.
16  */
17 
18 #ifndef UWS_BLOOMFILTER_H
19 #define UWS_BLOOMFILTER_H
20 
21 /* This filter has a decently low amount of false positives for the
22  * standard and non-standard common request headers */
23 
24 #include <string_view>
25 #include <bitset>
26 
27 namespace uWS {
28 
29 struct BloomFilter {
30 private:
31     std::bitset<512> filter;
32 
hash1BloomFilter33     unsigned int hash1(std::string_view key) {
34         return ((size_t)key[key.length() - 1] - (key.length() << 3)) & 511;
35     }
36 
hash2BloomFilter37     unsigned int hash2(std::string_view key) {
38         return (((size_t)key[0] + (key.length() << 4)) & 511);
39     }
40 
hash3BloomFilter41     unsigned int hash3(std::string_view key) {
42         return ((unsigned int)key[key.length() - 2] - 97 - (key.length() << 5)) & 511;
43     }
44 
45 public:
mightHaveBloomFilter46     bool mightHave(std::string_view key) {
47         return filter.test(hash1(key)) && filter.test(hash2(key)) && (key.length() < 2 || filter.test(hash3(key)));
48     }
49 
addBloomFilter50     void add(std::string_view key) {
51         filter.set(hash1(key));
52         filter.set(hash2(key));
53         if (key.length() >= 2) {
54             filter.set(hash3(key));
55         }
56     }
57 
resetBloomFilter58     void reset() {
59         filter.reset();
60     }
61 };
62 
63 }
64 
65 #endif // UWS_BLOOMFILTER_H