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
  10 #include <stddef.h>
  11 #include <stdio.h>
  12
  13 using mozilla::BloomFilter;
  14
  15 class FilterChecker
  16 {
  17 public:
  18   explicit FilterChecker(uint32_t aHash) : mHash(aHash) { }
  19
  20   uint32_t hash() const { return mHash; }
  21
  22 private:
  23   uint32_t mHash;
  24 };
  25
  26 int
  27 main()
  28 {
  29   BloomFilter<12, FilterChecker>* filter = new BloomFilter<12, FilterChecker>();
  30   MOZ_RELEASE_ASSERT(filter);
  31
  32   FilterChecker one(1);
  33   FilterChecker two(0x20000);
  34   FilterChecker many(0x10000);
  35   FilterChecker multiple(0x20001);
  36
  37   filter->add(&one);
  38   MOZ_RELEASE_ASSERT(filter->mightContain(&one),
  39              "Filter should contain 'one'");
  40
  41   MOZ_RELEASE_ASSERT(!filter->mightContain(&multiple),
  42              "Filter claims to contain 'multiple' when it should not");
  43
  44   MOZ_RELEASE_ASSERT(filter->mightContain(&many),
  45              "Filter should contain 'many' (false positive)");
  46
  47   filter->add(&two);
  48   MOZ_RELEASE_ASSERT(filter->mightContain(&multiple),
  49              "Filter should contain 'multiple' (false positive)");
  50
  51   // Test basic removals
  52   filter->remove(&two);
  53   MOZ_RELEASE_ASSERT(!filter->mightContain(&multiple),
  54              "Filter claims to contain 'multiple' when it should not after two "
  55              "was removed");
  56
  57   // Test multiple addition/removal
  58   const size_t FILTER_SIZE = 255;
  59   for (size_t i = 0; i < FILTER_SIZE - 1; ++i) {
  60     filter->add(&two);
  61   }
  62   MOZ_RELEASE_ASSERT(filter->mightContain(&multiple),
  63              "Filter should contain 'multiple' after 'two' added lots of times "
  64              "(false positive)");
  65
  66   for (size_t i = 0; i < FILTER_SIZE - 1; ++i) {
  67     filter->remove(&two);
  68   }
  69   MOZ_RELEASE_ASSERT(!filter->mightContain(&multiple),
  70              "Filter claims to contain 'multiple' when it should not after two "
  71              "was removed lots of times");
  72
  73   // Test overflowing the filter buckets
  74   for (size_t i = 0; i < FILTER_SIZE + 1; ++i) {
  75     filter->add(&two);
  76   }
  77   MOZ_RELEASE_ASSERT(filter->mightContain(&multiple),
  78              "Filter should contain 'multiple' after 'two' added lots more "
  79              "times (false positive)");
  80
  81   for (size_t i = 0; i < FILTER_SIZE + 1; ++i) {
  82     filter->remove(&two);
  83   }
  84   MOZ_RELEASE_ASSERT(filter->mightContain(&multiple),
  85              "Filter claims to not contain 'multiple' even though we should "
  86              "have run out of space in the buckets (false positive)");
  87   MOZ_RELEASE_ASSERT(filter->mightContain(&two),
  88              "Filter claims to not contain 'two' even though we should have "
  89              "run out of space in the buckets (false positive)");
  90
  91   filter->remove(&one);
  92
  93   MOZ_RELEASE_ASSERT(!filter->mightContain(&one),
  94              "Filter should not contain 'one', because we didn't overflow its "
  95              "bucket");
  96
  97   filter->clear();
  98
  99   MOZ_RELEASE_ASSERT(!filter->mightContain(&multiple),
 100              "clear() failed to work");
 101
 102   return 0;
 103 }