| OLD | NEW |
|---|
| (Empty) |
| 1 /* | |
| 2 * Copyright (C) 2011 Apple Inc. All rights reserved. | |
| 3 * | |
| 4 * Redistribution and use in source and binary forms, with or without | |
| 5 * modification, are permitted provided that the following conditions | |
| 6 * are met: | |
| 7 * 1. Redistributions of source code must retain the above copyright | |
| 8 * notice, this list of conditions and the following disclaimer. | |
| 9 * 2. Redistributions in binary form must reproduce the above copyright | |
| 10 * notice, this list of conditions and the following disclaimer in the | |
| 11 * documentation and/or other materials provided with the distribution. | |
| 12 * | |
| 13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS'' | |
| 14 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, | |
| 15 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR | |
| 16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS | |
| 17 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR | |
| 18 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF | |
| 19 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS | |
| 20 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN | |
| 21 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | |
| 22 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF | |
| 23 * THE POSSIBILITY OF SUCH DAMAGE. | |
| 24 */ | |
| 25 | |
| 26 #ifndef BloomFilter_h | |
| 27 #define BloomFilter_h | |
| 28 | |
| 29 #include "platform/wtf/Allocator.h" | |
| 30 #include "platform/wtf/Compiler.h" | |
| 31 #include "platform/wtf/text/AtomicString.h" | |
| 32 | |
| 33 namespace WTF { | |
| 34 | |
| 35 // Counting bloom filter with k=2 and 8 bit counters. Uses 2^keyBits bytes of | |
| 36 // memory. False positive rate is approximately (1-e^(-2n/m))^2, where n is | |
| 37 // the number of unique keys and m is the table size (==2^keyBits). | |
| 38 template <unsigned keyBits> | |
| 39 class BloomFilter { | |
| 40 USING_FAST_MALLOC(BloomFilter); | |
| 41 | |
| 42 public: | |
| 43 static_assert(keyBits <= 16, "bloom filter key size check"); | |
| 44 | |
| 45 static const size_t tableSize = 1 << keyBits; | |
| 46 static const unsigned keyMask = (1 << keyBits) - 1; | |
| 47 static uint8_t maximumCount() { return std::numeric_limits<uint8_t>::max(); } | |
| 48 | |
| 49 BloomFilter() { clear(); } | |
| 50 | |
| 51 void add(unsigned hash); | |
| 52 void remove(unsigned hash); | |
| 53 | |
| 54 // The filter may give false positives (claim it may contain a key it doesn't) | |
| 55 // but never false negatives (claim it doesn't contain a key it does). | |
| 56 bool mayContain(unsigned hash) const { | |
| 57 return firstSlot(hash) && secondSlot(hash); | |
| 58 } | |
| 59 | |
| 60 // The filter must be cleared before reuse even if all keys are removed. | |
| 61 // Otherwise overflowed keys will stick around. | |
| 62 void clear(); | |
| 63 | |
| 64 void add(const AtomicString& string) { add(string.impl()->existingHash()); } | |
| 65 void add(const String& string) { add(string.impl()->hash()); } | |
| 66 void remove(const AtomicString& string) { | |
| 67 remove(string.impl()->existingHash()); | |
| 68 } | |
| 69 void remove(const String& string) { remove(string.impl()->hash()); } | |
| 70 | |
| 71 bool mayContain(const AtomicString& string) const { | |
| 72 return mayContain(string.impl()->existingHash()); | |
| 73 } | |
| 74 bool mayContain(const String& string) const { | |
| 75 return mayContain(string.impl()->hash()); | |
| 76 } | |
| 77 | |
| 78 #if DCHECK_IS_ON() | |
| 79 // Slow. | |
| 80 bool likelyEmpty() const; | |
| 81 bool isClear() const; | |
| 82 #endif | |
| 83 | |
| 84 private: | |
| 85 uint8_t& firstSlot(unsigned hash) { return m_table[hash & keyMask]; } | |
| 86 uint8_t& secondSlot(unsigned hash) { return m_table[(hash >> 16) & keyMask]; } | |
| 87 const uint8_t& firstSlot(unsigned hash) const { | |
| 88 return m_table[hash & keyMask]; | |
| 89 } | |
| 90 const uint8_t& secondSlot(unsigned hash) const { | |
| 91 return m_table[(hash >> 16) & keyMask]; | |
| 92 } | |
| 93 | |
| 94 uint8_t m_table[tableSize]; | |
| 95 }; | |
| 96 | |
| 97 template <unsigned keyBits> | |
| 98 inline void BloomFilter<keyBits>::add(unsigned hash) { | |
| 99 uint8_t& first = firstSlot(hash); | |
| 100 uint8_t& second = secondSlot(hash); | |
| 101 if (LIKELY(first < maximumCount())) | |
| 102 ++first; | |
| 103 if (LIKELY(second < maximumCount())) | |
| 104 ++second; | |
| 105 } | |
| 106 | |
| 107 template <unsigned keyBits> | |
| 108 inline void BloomFilter<keyBits>::remove(unsigned hash) { | |
| 109 uint8_t& first = firstSlot(hash); | |
| 110 uint8_t& second = secondSlot(hash); | |
| 111 DCHECK(first); | |
| 112 DCHECK(second); | |
| 113 // In case of an overflow, the slot sticks in the table until clear(). | |
| 114 if (LIKELY(first < maximumCount())) | |
| 115 --first; | |
| 116 if (LIKELY(second < maximumCount())) | |
| 117 --second; | |
| 118 } | |
| 119 | |
| 120 template <unsigned keyBits> | |
| 121 inline void BloomFilter<keyBits>::clear() { | |
| 122 memset(m_table, 0, tableSize); | |
| 123 } | |
| 124 | |
| 125 #if DCHECK_IS_ON() | |
| 126 template <unsigned keyBits> | |
| 127 bool BloomFilter<keyBits>::likelyEmpty() const { | |
| 128 for (size_t n = 0; n < tableSize; ++n) { | |
| 129 if (m_table[n] && m_table[n] != maximumCount()) | |
| 130 return false; | |
| 131 } | |
| 132 return true; | |
| 133 } | |
| 134 | |
| 135 template <unsigned keyBits> | |
| 136 bool BloomFilter<keyBits>::isClear() const { | |
| 137 for (size_t n = 0; n < tableSize; ++n) { | |
| 138 if (m_table[n]) | |
| 139 return false; | |
| 140 } | |
| 141 return true; | |
| 142 } | |
| 143 #endif | |
| 144 | |
| 145 } // namespace WTF | |
| 146 | |
| 147 using WTF::BloomFilter; | |
| 148 | |
| 149 #endif | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2774333002:
Revert "Move files in wtf/ to platform/wtf/" (Closed)
