1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/mfbt/tests/TestBloomFilter.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,102 @@
1.4 +/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
1.5 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.6 + * License, v. 2.0. If a copy of the MPL was not distributed with this file,
1.7 + * You can obtain one at http://mozilla.org/MPL/2.0/. */
1.8 +
1.9 +#include "mozilla/Assertions.h"
1.10 +#include "mozilla/BloomFilter.h"
1.11 +
1.12 +#include <stddef.h>
1.13 +#include <stdio.h>
1.14 +
1.15 +using mozilla::BloomFilter;
1.16 +
1.17 +class FilterChecker
1.18 +{
1.19 + public:
1.20 + FilterChecker(uint32_t hash) : mHash(hash) { }
1.21 +
1.22 + uint32_t hash() const { return mHash; }
1.23 +
1.24 + private:
1.25 + uint32_t mHash;
1.26 +};
1.27 +
1.28 +int
1.29 +main()
1.30 +{
1.31 + BloomFilter<12, FilterChecker> *filter = new BloomFilter<12, FilterChecker>();
1.32 + MOZ_RELEASE_ASSERT(filter);
1.33 +
1.34 + FilterChecker one(1);
1.35 + FilterChecker two(0x20000);
1.36 + FilterChecker many(0x10000);
1.37 + FilterChecker multiple(0x20001);
1.38 +
1.39 + filter->add(&one);
1.40 + MOZ_RELEASE_ASSERT(filter->mightContain(&one),
1.41 + "Filter should contain 'one'");
1.42 +
1.43 + MOZ_RELEASE_ASSERT(!filter->mightContain(&multiple),
1.44 + "Filter claims to contain 'multiple' when it should not");
1.45 +
1.46 + MOZ_RELEASE_ASSERT(filter->mightContain(&many),
1.47 + "Filter should contain 'many' (false positive)");
1.48 +
1.49 + filter->add(&two);
1.50 + MOZ_RELEASE_ASSERT(filter->mightContain(&multiple),
1.51 + "Filter should contain 'multiple' (false positive)");
1.52 +
1.53 + // Test basic removals
1.54 + filter->remove(&two);
1.55 + MOZ_RELEASE_ASSERT(!filter->mightContain(&multiple),
1.56 + "Filter claims to contain 'multiple' when it should not after two "
1.57 + "was removed");
1.58 +
1.59 + // Test multiple addition/removal
1.60 + const size_t FILTER_SIZE = 255;
1.61 + for (size_t i = 0; i < FILTER_SIZE - 1; ++i)
1.62 + filter->add(&two);
1.63 +
1.64 + MOZ_RELEASE_ASSERT(filter->mightContain(&multiple),
1.65 + "Filter should contain 'multiple' after 'two' added lots of times "
1.66 + "(false positive)");
1.67 +
1.68 + for (size_t i = 0; i < FILTER_SIZE - 1; ++i)
1.69 + filter->remove(&two);
1.70 +
1.71 + MOZ_RELEASE_ASSERT(!filter->mightContain(&multiple),
1.72 + "Filter claims to contain 'multiple' when it should not after two "
1.73 + "was removed lots of times");
1.74 +
1.75 + // Test overflowing the filter buckets
1.76 + for (size_t i = 0; i < FILTER_SIZE + 1; ++i)
1.77 + filter->add(&two);
1.78 +
1.79 + MOZ_RELEASE_ASSERT(filter->mightContain(&multiple),
1.80 + "Filter should contain 'multiple' after 'two' added lots more "
1.81 + "times (false positive)");
1.82 +
1.83 + for (size_t i = 0; i < FILTER_SIZE + 1; ++i)
1.84 + filter->remove(&two);
1.85 +
1.86 + MOZ_RELEASE_ASSERT(filter->mightContain(&multiple),
1.87 + "Filter claims to not contain 'multiple' even though we should "
1.88 + "have run out of space in the buckets (false positive)");
1.89 + MOZ_RELEASE_ASSERT(filter->mightContain(&two),
1.90 + "Filter claims to not contain 'two' even though we should have "
1.91 + "run out of space in the buckets (false positive)");
1.92 +
1.93 + filter->remove(&one);
1.94 +
1.95 + MOZ_RELEASE_ASSERT(!filter->mightContain(&one),
1.96 + "Filter should not contain 'one', because we didn't overflow its "
1.97 + "bucket");
1.98 +
1.99 + filter->clear();
1.100 +
1.101 + MOZ_RELEASE_ASSERT(!filter->mightContain(&multiple),
1.102 + "clear() failed to work");
1.103 +
1.104 + return 0;
1.105 +}
