mfbt/tests/TestBloomFilter.cpp

   1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* This Source Code Form is subject to the terms of the Mozilla Public
   3  * License, v. 2.0. If a copy of the MPL was not distributed with this file,
   4  * You can obtain one at http://mozilla.org/MPL/2.0/. */
   5
   6 #include "mozilla/Assertions.h"
   7 #include "mozilla/BloomFilter.h"
   8
   9 #include <stddef.h>
  10 #include <stdio.h>
  11
  12 using mozilla::BloomFilter;
  13
  14 class FilterChecker
  15 {
  16   public:
  17     FilterChecker(uint32_t hash) : mHash(hash) { }
  18
  19     uint32_t hash() const { return mHash; }
  20
  21   private:
  22     uint32_t mHash;
  23 };
  24
  25 int
  26 main()
  27 {
  28   BloomFilter<12, FilterChecker> *filter = new BloomFilter<12, FilterChecker>();
  29   MOZ_ASSERT(filter);
  30
  31   FilterChecker one(1);
  32   FilterChecker two(0x20000);
  33   FilterChecker many(0x10000);
  34   FilterChecker multiple(0x20001);
  35
  36   filter->add(&one);
  37   MOZ_ASSERT(filter->mightContain(&one),
  38              "Filter should contain 'one'");
  39
  40   MOZ_ASSERT(!filter->mightContain(&multiple),
  41              "Filter claims to contain 'multiple' when it should not");
  42
  43   MOZ_ASSERT(filter->mightContain(&many),
  44              "Filter should contain 'many' (false positive)");
  45
  46   filter->add(&two);
  47   MOZ_ASSERT(filter->mightContain(&multiple),
  48              "Filter should contain 'multiple' (false positive)");
  49
  50   // Test basic removals
  51   filter->remove(&two);
  52   MOZ_ASSERT(!filter->mightContain(&multiple),
  53              "Filter claims to contain 'multiple' when it should not after two "
  54              "was removed");
  55
  56   // Test multiple addition/removal
  57   const size_t FILTER_SIZE = 255;
  58   for (size_t i = 0; i < FILTER_SIZE - 1; ++i)
  59     filter->add(&two);
  60
  61   MOZ_ASSERT(filter->mightContain(&multiple),
  62              "Filter should contain 'multiple' after 'two' added lots of times "
  63              "(false positive)");
  64
  65   for (size_t i = 0; i < FILTER_SIZE - 1; ++i)
  66     filter->remove(&two);
  67
  68   MOZ_ASSERT(!filter->mightContain(&multiple),
  69              "Filter claims to contain 'multiple' when it should not after two "
  70              "was removed lots of times");
  71
  72   // Test overflowing the filter buckets
  73   for (size_t i = 0; i < FILTER_SIZE + 1; ++i)
  74     filter->add(&two);
  75
  76   MOZ_ASSERT(filter->mightContain(&multiple),
  77              "Filter should contain 'multiple' after 'two' added lots more "
  78              "times (false positive)");
  79
  80   for (size_t i = 0; i < FILTER_SIZE + 1; ++i)
  81     filter->remove(&two);
  82
  83   MOZ_ASSERT(filter->mightContain(&multiple),
  84              "Filter claims to not contain 'multiple' even though we should "
  85              "have run out of space in the buckets (false positive)");
  86   MOZ_ASSERT(filter->mightContain(&two),
  87              "Filter claims to not contain 'two' even though we should have "
  88              "run out of space in the buckets (false positive)");
  89
  90   filter->remove(&one);
  91
  92   MOZ_ASSERT(!filter->mightContain(&one),
  93              "Filter should not contain 'one', because we didn't overflow its "
  94              "bucket");
  95
  96   filter->clear();
  97
  98   MOZ_ASSERT(!filter->mightContain(&multiple),
  99              "clear() failed to work");
 100
 101   return 0;
 102 }