diff options
author | Matt A. Tobin <mattatobin@localhost.localdomain> | 2018-02-02 04:16:08 -0500 |
---|---|---|
committer | Matt A. Tobin <mattatobin@localhost.localdomain> | 2018-02-02 04:16:08 -0500 |
commit | 5f8de423f190bbb79a62f804151bc24824fa32d8 (patch) | |
tree | 10027f336435511475e392454359edea8e25895d /mfbt/tests/TestBloomFilter.cpp | |
parent | 49ee0794b5d912db1f95dce6eb52d781dc210db5 (diff) | |
download | UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar.gz UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar.lz UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar.xz UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.zip |
Add m-esr52 at 52.6.0
Diffstat (limited to 'mfbt/tests/TestBloomFilter.cpp')
-rw-r--r-- | mfbt/tests/TestBloomFilter.cpp | 103 |
1 files changed, 103 insertions, 0 deletions
diff --git a/mfbt/tests/TestBloomFilter.cpp b/mfbt/tests/TestBloomFilter.cpp new file mode 100644 index 000000000..42e8b821e --- /dev/null +++ b/mfbt/tests/TestBloomFilter.cpp @@ -0,0 +1,103 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* vim: set ts=8 sts=2 et sw=2 tw=80: */ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this file, + * You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include "mozilla/Assertions.h" +#include "mozilla/BloomFilter.h" + +#include <stddef.h> +#include <stdio.h> + +using mozilla::BloomFilter; + +class FilterChecker +{ +public: + explicit FilterChecker(uint32_t aHash) : mHash(aHash) { } + + uint32_t hash() const { return mHash; } + +private: + uint32_t mHash; +}; + +int +main() +{ + BloomFilter<12, FilterChecker>* filter = new BloomFilter<12, FilterChecker>(); + MOZ_RELEASE_ASSERT(filter); + + FilterChecker one(1); + FilterChecker two(0x20000); + FilterChecker many(0x10000); + FilterChecker multiple(0x20001); + + filter->add(&one); + MOZ_RELEASE_ASSERT(filter->mightContain(&one), + "Filter should contain 'one'"); + + MOZ_RELEASE_ASSERT(!filter->mightContain(&multiple), + "Filter claims to contain 'multiple' when it should not"); + + MOZ_RELEASE_ASSERT(filter->mightContain(&many), + "Filter should contain 'many' (false positive)"); + + filter->add(&two); + MOZ_RELEASE_ASSERT(filter->mightContain(&multiple), + "Filter should contain 'multiple' (false positive)"); + + // Test basic removals + filter->remove(&two); + MOZ_RELEASE_ASSERT(!filter->mightContain(&multiple), + "Filter claims to contain 'multiple' when it should not after two " + "was removed"); + + // Test multiple addition/removal + const size_t FILTER_SIZE = 255; + for (size_t i = 0; i < FILTER_SIZE - 1; ++i) { + filter->add(&two); + } + MOZ_RELEASE_ASSERT(filter->mightContain(&multiple), + "Filter should contain 'multiple' after 'two' added lots of times " + "(false positive)"); + + for (size_t i = 0; i < FILTER_SIZE - 1; ++i) { + filter->remove(&two); + } + MOZ_RELEASE_ASSERT(!filter->mightContain(&multiple), + "Filter claims to contain 'multiple' when it should not after two " + "was removed lots of times"); + + // Test overflowing the filter buckets + for (size_t i = 0; i < FILTER_SIZE + 1; ++i) { + filter->add(&two); + } + MOZ_RELEASE_ASSERT(filter->mightContain(&multiple), + "Filter should contain 'multiple' after 'two' added lots more " + "times (false positive)"); + + for (size_t i = 0; i < FILTER_SIZE + 1; ++i) { + filter->remove(&two); + } + MOZ_RELEASE_ASSERT(filter->mightContain(&multiple), + "Filter claims to not contain 'multiple' even though we should " + "have run out of space in the buckets (false positive)"); + MOZ_RELEASE_ASSERT(filter->mightContain(&two), + "Filter claims to not contain 'two' even though we should have " + "run out of space in the buckets (false positive)"); + + filter->remove(&one); + + MOZ_RELEASE_ASSERT(!filter->mightContain(&one), + "Filter should not contain 'one', because we didn't overflow its " + "bucket"); + + filter->clear(); + + MOZ_RELEASE_ASSERT(!filter->mightContain(&multiple), + "clear() failed to work"); + + return 0; +} |