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