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 14 matching lines...) Expand all Loading... |
25 | 25 |
26 #ifndef BloomFilter_h | 26 #ifndef BloomFilter_h |
27 #define BloomFilter_h | 27 #define BloomFilter_h |
28 | 28 |
29 #include "wtf/Compiler.h" | 29 #include "wtf/Compiler.h" |
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 COMPILE_ASSERT(keyBits <= 16, bloom_filter_key_size); |
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 |
51 // The filter may give false positives (claim it may contain a key it doesn'
t) | 51 // The filter may give false positives (claim it may contain a key it doesn'
t) |
52 // but never false negatives (claim it doesn't contain a key it does). | 52 // but never false negatives (claim it doesn't contain a key it does). |
53 bool mayContain(unsigned hash) const { return firstSlot(hash) && secondSlot(
hash); } | 53 bool mayContain(unsigned hash) const { return firstSlot(hash) && secondSlot(
hash); } |
54 | 54 |
55 // The filter must be cleared before reuse even if all keys are removed. | 55 // The filter must be cleared before reuse even if all keys are removed. |
56 // Otherwise overflowed keys will stick around. | 56 // Otherwise overflowed keys will stick around. |
57 void clear(); | 57 void clear(); |
58 | 58 |
59 void add(const AtomicString& string) { add(string.impl()->existingHash()); } | 59 void add(const AtomicString& string) { add(string.impl()->existingHash()); } |
60 void add(const String& string) { add(string.impl()->hash()); } | 60 void add(const String& string) { add(string.impl()->hash()); } |
61 void remove(const AtomicString& string) { remove(string.impl()->existingHash
()); } | 61 void remove(const AtomicString& string) { remove(string.impl()->existingHash
()); } |
62 void remove(const String& string) { remove(string.impl()->hash()); } | 62 void remove(const String& string) { remove(string.impl()->hash()); } |
63 | 63 |
64 bool mayContain(const AtomicString& string) const { return mayContain(string
.impl()->existingHash()); } | 64 bool mayContain(const AtomicString& string) const { return mayContain(string
.impl()->existingHash()); } |
65 bool mayContain(const String& string) const { return mayContain(string.impl(
)->hash()); } | 65 bool mayContain(const String& string) const { return mayContain(string.impl(
)->hash()); } |
66 | 66 |
67 #if !ASSERT_DISABLED | 67 #if !ASSERT_DISABLED |
68 // Slow. | 68 // Slow. |
69 bool likelyEmpty() const; | 69 bool likelyEmpty() const; |
70 bool isClear() const; | 70 bool isClear() const; |
71 #endif | 71 #endif |
72 | 72 |
73 private: | 73 private: |
74 uint8_t& firstSlot(unsigned hash) { return m_table[hash & keyMask]; } | 74 uint8_t& firstSlot(unsigned hash) { return m_table[hash & keyMask]; } |
75 uint8_t& secondSlot(unsigned hash) { return m_table[(hash >> 16) & keyMask];
} | 75 uint8_t& secondSlot(unsigned hash) { return m_table[(hash >> 16) & keyMask];
} |
76 const uint8_t& firstSlot(unsigned hash) const { return m_table[hash & keyMas
k]; } | 76 const uint8_t& firstSlot(unsigned hash) const { return m_table[hash & keyMas
k]; } |
77 const uint8_t& secondSlot(unsigned hash) const { return m_table[(hash >> 16)
& keyMask]; } | 77 const uint8_t& secondSlot(unsigned hash) const { return m_table[(hash >> 16)
& keyMask]; } |
78 | 78 |
79 uint8_t m_table[tableSize]; | 79 uint8_t m_table[tableSize]; |
80 }; | 80 }; |
81 | 81 |
82 template <unsigned keyBits> | 82 template <unsigned keyBits> |
83 inline void BloomFilter<keyBits>::add(unsigned hash) | 83 inline void BloomFilter<keyBits>::add(unsigned hash) |
84 { | 84 { |
85 uint8_t& first = firstSlot(hash); | 85 uint8_t& first = firstSlot(hash); |
86 uint8_t& second = secondSlot(hash); | 86 uint8_t& second = secondSlot(hash); |
87 if (LIKELY(first < maximumCount())) | 87 if (LIKELY(first < maximumCount())) |
88 ++first; | 88 ++first; |
89 if (LIKELY(second < maximumCount())) | 89 if (LIKELY(second < maximumCount())) |
90 ++second; | 90 ++second; |
91 } | 91 } |
92 | 92 |
93 template <unsigned keyBits> | 93 template <unsigned keyBits> |
94 inline void BloomFilter<keyBits>::remove(unsigned hash) | 94 inline void BloomFilter<keyBits>::remove(unsigned hash) |
95 { | 95 { |
96 uint8_t& first = firstSlot(hash); | 96 uint8_t& first = firstSlot(hash); |
97 uint8_t& second = secondSlot(hash); | 97 uint8_t& second = secondSlot(hash); |
98 ASSERT(first); | 98 ASSERT(first); |
99 ASSERT(second); | 99 ASSERT(second); |
100 // In case of an overflow, the slot sticks in the table until clear(). | 100 // In case of an overflow, the slot sticks in the table until clear(). |
101 if (LIKELY(first < maximumCount())) | 101 if (LIKELY(first < maximumCount())) |
102 --first; | 102 --first; |
103 if (LIKELY(second < maximumCount())) | 103 if (LIKELY(second < maximumCount())) |
104 --second; | 104 --second; |
105 } | 105 } |
106 | 106 |
107 template <unsigned keyBits> | 107 template <unsigned keyBits> |
108 inline void BloomFilter<keyBits>::clear() | 108 inline void BloomFilter<keyBits>::clear() |
109 { | 109 { |
110 memset(m_table, 0, tableSize); | 110 memset(m_table, 0, tableSize); |
111 } | 111 } |
112 | 112 |
113 #if !ASSERT_DISABLED | 113 #if !ASSERT_DISABLED |
114 template <unsigned keyBits> | 114 template <unsigned keyBits> |
115 bool BloomFilter<keyBits>::likelyEmpty() const | 115 bool BloomFilter<keyBits>::likelyEmpty() const |
116 { | 116 { |
(...skipping 13 matching lines...) Expand all 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 |