OLD | NEW |
1 /* | 1 /* |
2 * Copyright (C) 2011 Apple Inc. All rights reserved. | 2 * Copyright (C) 2011 Apple Inc. All rights reserved. |
3 * | 3 * |
4 * Redistribution and use in source and binary forms, with or without | 4 * Redistribution and use in source and binary forms, with or without |
5 * modification, are permitted provided that the following conditions | 5 * modification, are permitted provided that the following conditions |
6 * are met: | 6 * are met: |
7 * 1. Redistributions of source code must retain the above copyright | 7 * 1. Redistributions of source code must retain the above copyright |
8 * notice, this list of conditions and the following disclaimer. | 8 * notice, this list of conditions and the following disclaimer. |
9 * 2. Redistributions in binary form must reproduce the above copyright | 9 * 2. Redistributions in binary form must reproduce the above copyright |
10 * notice, this list of conditions and the following disclaimer in the | 10 * notice, this list of conditions and the following disclaimer in the |
(...skipping 19 matching lines...) Expand all Loading... |
30 #include "wtf/text/AtomicString.h" | 30 #include "wtf/text/AtomicString.h" |
31 | 31 |
32 namespace WTF { | 32 namespace WTF { |
33 | 33 |
34 // Counting bloom filter with k=2 and 8 bit counters. Uses 2^keyBits bytes of me
mory. | 34 // Counting bloom filter with k=2 and 8 bit counters. Uses 2^keyBits bytes of me
mory. |
35 // False positive rate is approximately (1-e^(-2n/m))^2, where n is the number o
f unique | 35 // False positive rate is approximately (1-e^(-2n/m))^2, where n is the number o
f unique |
36 // keys and m is the table size (==2^keyBits). | 36 // keys and m is the table size (==2^keyBits). |
37 template <unsigned keyBits> | 37 template <unsigned keyBits> |
38 class BloomFilter { | 38 class BloomFilter { |
39 public: | 39 public: |
40 COMPILE_ASSERT(keyBits <= 16, bloom_filter_key_size); | 40 static_assert(keyBits <= 16, "bloom filter key size check"); |
41 | 41 |
42 static const size_t tableSize = 1 << keyBits; | 42 static const size_t tableSize = 1 << keyBits; |
43 static const unsigned keyMask = (1 << keyBits) - 1; | 43 static const unsigned keyMask = (1 << keyBits) - 1; |
44 static uint8_t maximumCount() { return std::numeric_limits<uint8_t>::max();
} | 44 static uint8_t maximumCount() { return std::numeric_limits<uint8_t>::max();
} |
45 | 45 |
46 BloomFilter() { clear(); } | 46 BloomFilter() { clear(); } |
47 | 47 |
48 void add(unsigned hash); | 48 void add(unsigned hash); |
49 void remove(unsigned hash); | 49 void remove(unsigned hash); |
50 | 50 |
(...skipping 79 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
130 } | 130 } |
131 return true; | 131 return true; |
132 } | 132 } |
133 #endif | 133 #endif |
134 | 134 |
135 } | 135 } |
136 | 136 |
137 using WTF::BloomFilter; | 137 using WTF::BloomFilter; |
138 | 138 |
139 #endif | 139 #endif |
OLD | NEW |