/* * Copyright (C) 2011, 2015 Apple Inc. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS'' * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF * THE POSSIBILITY OF SUCH DAMAGE. */ #ifdef UNSAFE_BUFFERS_BUILD // TODO(crbug.com/351564777): Remove this and convert code to safer constructs. #pragma allow_unsafe_buffers #endif #ifndef THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_BLOOM_FILTER_H_ #define THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_BLOOM_FILTER_H_ #include "base/check_op.h" #include "base/dcheck_is_on.h" #include "third_party/blink/renderer/platform/wtf/allocator/allocator.h" namespace WTF { // Bloom filter with k=2. Uses 2^keyBits/8 bytes of memory. // False positive rate is approximately (1-e^(-2n/m))^2, where n is the number // of unique keys and m is the table size (==2^keyBits). template <unsigned keyBits> class BloomFilter { … }; template <unsigned keyBits> inline bool BloomFilter<keyBits>::MayContain(unsigned hash) const { … } template <unsigned keyBits> inline void BloomFilter<keyBits>::Add(unsigned hash) { … } template <unsigned keyBits> inline void BloomFilter<keyBits>::Clear() { … } template <unsigned keyBits> inline void BloomFilter<keyBits>::Merge(const BloomFilter<keyBits>& other) { … } template <unsigned keyBits> inline size_t BloomFilter<keyBits>::BitArrayIndex(unsigned key) { … } template <unsigned keyBits> inline unsigned BloomFilter<keyBits>::BitMask(unsigned key) { … } template <unsigned keyBits> bool BloomFilter<keyBits>::IsBitSet(unsigned key) const { … } template <unsigned keyBits> void BloomFilter<keyBits>::SetBit(unsigned key) { … } // Counting bloom filter with k=2 and 8 bit counters. Uses 2^keyBits bytes of // memory. False positive rate is approximately (1-e^(-2n/m))^2, where n is // the number of unique keys and m is the table size (==2^keyBits). template <unsigned keyBits> class CountingBloomFilter { … }; template <unsigned keyBits> inline void CountingBloomFilter<keyBits>::Add(unsigned hash) { … } template <unsigned keyBits> inline void CountingBloomFilter<keyBits>::Remove(unsigned hash) { … } template <unsigned keyBits> inline void CountingBloomFilter<keyBits>::Clear() { … } #if DCHECK_IS_ON() template <unsigned keyBits> bool CountingBloomFilter<keyBits>::LikelyEmpty() const { … } template <unsigned keyBits> bool CountingBloomFilter<keyBits>::IsClear() const { … } #endif } // namespace WTF CountingBloomFilter; #endif // THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_BLOOM_FILTER_H_
Codebase Browser
chromium