code.vuplus.com Git - vuplus_webkit/blob - Source/JavaScriptCore/wtf/BloomFilter.h

   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 <wtf/AlwaysInline.h>
  30 #include <wtf/text/AtomicString.h>
  31
  32 namespace WTF {
  33
  34 // Counting bloom filter with k=2 and 8 bit counters. Uses 2^keyBits bytes of memory.
  35 // False positive rate is approximately (1-e^(-2n/m))^2, where n is the number of unique
  36 // keys and m is the table size (==2^keyBits).
  37 template <unsigned keyBits>
  38 class BloomFilter {
  39 public:
  40     COMPILE_ASSERT(keyBits <= 16, bloom_filter_key_size);
  41
  42     static const size_t tableSize = 1 << keyBits;
  43     static const unsigned keyMask = (1 << keyBits) - 1;
  44     static uint8_t maximumCount() { return std::numeric_limits<uint8_t>::max(); }
  45
  46     BloomFilter() { clear(); }
  47
  48     void add(unsigned hash);
  49     void remove(unsigned hash);
  50
  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).
  53     bool mayContain(unsigned hash) const { return firstSlot(hash) && secondSlot(hash); }
  54
  55     // The filter must be cleared before reuse even if all keys are removed.
  56     // Otherwise overflowed keys will stick around.
  57     void clear();
  58
  59     void add(const AtomicString& string) { add(string.impl()->existingHash()); }
  60     void add(const String& string) { add(string.impl()->hash()); }
  61     void remove(const AtomicString& string) { remove(string.impl()->existingHash()); }
  62     void remove(const String& string) { remove(string.impl()->hash()); }
  63
  64     bool mayContain(const AtomicString& string) const { return mayContain(string.impl()->existingHash()); }
  65     bool mayContain(const String& string) const { return mayContain(string.impl()->hash()); }
  66
  67 #if !ASSERT_DISABLED
  68     // Slow.
  69     bool likelyEmpty() const;
  70     bool isClear() const;
  71 #endif
  72
  73 private:
  74     uint8_t& firstSlot(unsigned hash) { return m_table[hash & 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 & keyMask]; }
  77     const uint8_t& secondSlot(unsigned hash) const { return m_table[(hash >> 16) & keyMask]; }
  78
  79     uint8_t m_table[tableSize];
  80 };
  81
  82 template <unsigned keyBits>
  83 inline void BloomFilter<keyBits>::add(unsigned hash)
  84 {
  85     uint8_t& first = firstSlot(hash);
  86     uint8_t& second = secondSlot(hash);
  87     if (LIKELY(first < maximumCount()))
  88         ++first;
  89     if (LIKELY(second < maximumCount()))
  90         ++second;
  91 }
  92
  93 template <unsigned keyBits>
  94 inline void BloomFilter<keyBits>::remove(unsigned hash)
  95 {
  96     uint8_t& first = firstSlot(hash);
  97     uint8_t& second = secondSlot(hash);
  98     ASSERT(first);
  99     ASSERT(second);
 100     // In case of an overflow, the slot sticks in the table until clear().
 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>::clear()
 109 {
 110     memset(m_table, 0, tableSize);
 111 }
 112
 113 #if !ASSERT_DISABLED
 114 template <unsigned keyBits>
 115 bool BloomFilter<keyBits>::likelyEmpty() const
 116 {
 117     for (size_t n = 0; n < tableSize; ++n) {
 118         if (m_table[n] && m_table[n] != maximumCount())
 119             return false;
 120     }
 121     return true;
 122 }
 123
 124 template <unsigned keyBits>
 125 bool BloomFilter<keyBits>::isClear() const
 126 {
 127     for (size_t n = 0; n < tableSize; ++n) {
 128         if (m_table[n])
 129             return false;
 130     }
 131     return true;
 132 }
 133 #endif
 134
 135 }
 136
 137 using WTF::BloomFilter;
 138
 139 #endif