OLD | NEW |
1 // Copyright 2017 The Chromium Authors. All rights reserved. | 1 /* |
2 // Use of this source code is governed by a BSD-style license that can be | 2 * Copyright (C) 2011 Apple Inc. All rights reserved. |
3 // found in the LICENSE file. | 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 */ |
4 | 25 |
5 #include "platform/wtf/BloomFilter.h" | 26 #ifndef BloomFilter_h |
| 27 #define BloomFilter_h |
6 | 28 |
7 // The contents of this header was moved to platform/wtf as part of | 29 #include "wtf/Allocator.h" |
8 // WTF migration project. See the following post for details: | 30 #include "wtf/Compiler.h" |
9 // https://groups.google.com/a/chromium.org/d/msg/blink-dev/tLdAZCTlcAA/bYXVT8gY
CAAJ | 31 #include "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 |