| 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 |