mfbt/tests/TestBloomFilter.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
   3 /* This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this file,
   5  * You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #include "mozilla/Assertions.h"
   8 #include "mozilla/BloomFilter.h"
   9 #include "mozilla/UniquePtr.h"
  10
  11 #include <stddef.h>
  12 #include <stdint.h>
  13
  14 using mozilla::BitBloomFilter;
  15 using mozilla::CountingBloomFilter;
  16
  17 class FilterChecker {
  18  public:
  19   explicit FilterChecker(uint32_t aHash) : mHash(aHash) {}
  20
  21   uint32_t hash() const { return mHash; }
  22
  23  private:
  24   uint32_t mHash;
  25 };
  26
  27 void testBitBloomFilter() {
  28   const mozilla::UniquePtr filter =
  29       mozilla::MakeUnique<BitBloomFilter<12, FilterChecker>>();
  30   MOZ_RELEASE_ASSERT(filter);
  31
  32   FilterChecker one(1);
  33   FilterChecker two(0x20000);
  34
  35   filter->add(&one);
  36   MOZ_RELEASE_ASSERT(filter->mightContain(&one), "Filter should contain 'one'");
  37
  38   MOZ_RELEASE_ASSERT(!filter->mightContain(&two),
  39                      "Filter claims to contain 'two' when it should not");
  40
  41   // Test multiple addition
  42   filter->add(&two);
  43   MOZ_RELEASE_ASSERT(filter->mightContain(&two),
  44                      "Filter should contain 'two' after 'two' is added");
  45   filter->add(&two);
  46   MOZ_RELEASE_ASSERT(filter->mightContain(&two),
  47                      "Filter should contain 'two' after 'two' is added again");
  48
  49   filter->clear();
  50
  51   MOZ_RELEASE_ASSERT(!filter->mightContain(&one), "clear() failed to work");
  52   MOZ_RELEASE_ASSERT(!filter->mightContain(&two), "clear() failed to work");
  53 }
  54
  55 void testCountingBloomFilter() {
  56   const mozilla::UniquePtr filter =
  57       mozilla::MakeUnique<CountingBloomFilter<12, FilterChecker>>();
  58   MOZ_RELEASE_ASSERT(filter);
  59
  60   FilterChecker one(1);
  61   FilterChecker two(0x20000);
  62   FilterChecker many(0x10000);
  63   FilterChecker multiple(0x20001);
  64
  65   filter->add(&one);
  66   MOZ_RELEASE_ASSERT(filter->mightContain(&one), "Filter should contain 'one'");
  67
  68   MOZ_RELEASE_ASSERT(!filter->mightContain(&multiple),
  69                      "Filter claims to contain 'multiple' when it should not");
  70
  71   MOZ_RELEASE_ASSERT(filter->mightContain(&many),
  72                      "Filter should contain 'many' (false positive)");
  73
  74   filter->add(&two);
  75   MOZ_RELEASE_ASSERT(filter->mightContain(&multiple),
  76                      "Filter should contain 'multiple' (false positive)");
  77
  78   // Test basic removals
  79   filter->remove(&two);
  80   MOZ_RELEASE_ASSERT(
  81       !filter->mightContain(&multiple),
  82       "Filter claims to contain 'multiple' when it should not after two "
  83       "was removed");
  84
  85   // Test multiple addition/removal
  86   const size_t FILTER_SIZE = 255;
  87   for (size_t i = 0; i < FILTER_SIZE - 1; ++i) {
  88     filter->add(&two);
  89   }
  90   MOZ_RELEASE_ASSERT(
  91       filter->mightContain(&multiple),
  92       "Filter should contain 'multiple' after 'two' added lots of times "
  93       "(false positive)");
  94
  95   for (size_t i = 0; i < FILTER_SIZE - 1; ++i) {
  96     filter->remove(&two);
  97   }
  98   MOZ_RELEASE_ASSERT(
  99       !filter->mightContain(&multiple),
 100       "Filter claims to contain 'multiple' when it should not after two "
 101       "was removed lots of times");
 102
 103   // Test overflowing the filter buckets
 104   for (size_t i = 0; i < FILTER_SIZE + 1; ++i) {
 105     filter->add(&two);
 106   }
 107   MOZ_RELEASE_ASSERT(
 108       filter->mightContain(&multiple),
 109       "Filter should contain 'multiple' after 'two' added lots more "
 110       "times (false positive)");
 111
 112   for (size_t i = 0; i < FILTER_SIZE + 1; ++i) {
 113     filter->remove(&two);
 114   }
 115   MOZ_RELEASE_ASSERT(
 116       filter->mightContain(&multiple),
 117       "Filter claims to not contain 'multiple' even though we should "
 118       "have run out of space in the buckets (false positive)");
 119   MOZ_RELEASE_ASSERT(
 120       filter->mightContain(&two),
 121       "Filter claims to not contain 'two' even though we should have "
 122       "run out of space in the buckets (false positive)");
 123
 124   filter->remove(&one);
 125
 126   MOZ_RELEASE_ASSERT(
 127       !filter->mightContain(&one),
 128       "Filter should not contain 'one', because we didn't overflow its "
 129       "bucket");
 130
 131   filter->clear();
 132
 133   MOZ_RELEASE_ASSERT(!filter->mightContain(&multiple),
 134                      "clear() failed to work");
 135 }
 136
 137 int main() {
 138   testBitBloomFilter();
 139   testCountingBloomFilter();
 140
 141   return 0;
 142 }