The Tor Browser: mfbt/tests/TestBloomFilter.cpp@6474c204b198

Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.

     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/. */

     6 #include "mozilla/Assertions.h"

     7 #include "mozilla/BloomFilter.h"

     9 #include <stddef.h>

    10 #include <stdio.h>

    12 using mozilla::BloomFilter;

    14 class FilterChecker

    15 {

    16   public:

    17     FilterChecker(uint32_t hash) : mHash(hash) { }

    19     uint32_t hash() const { return mHash; }

    21   private:

    22     uint32_t mHash;

    23 };

    25 int

    26 main()

    27 {

    28   BloomFilter<12, FilterChecker> *filter = new BloomFilter<12, FilterChecker>();

    29   MOZ_RELEASE_ASSERT(filter);

    31   FilterChecker one(1);

    32   FilterChecker two(0x20000);

    33   FilterChecker many(0x10000);

    34   FilterChecker multiple(0x20001);

    36   filter->add(&one);

    37   MOZ_RELEASE_ASSERT(filter->mightContain(&one),

    38              "Filter should contain 'one'");

    40   MOZ_RELEASE_ASSERT(!filter->mightContain(&multiple),

    41              "Filter claims to contain 'multiple' when it should not");

    43   MOZ_RELEASE_ASSERT(filter->mightContain(&many),

    44              "Filter should contain 'many' (false positive)");

    46   filter->add(&two);

    47   MOZ_RELEASE_ASSERT(filter->mightContain(&multiple),

    48              "Filter should contain 'multiple' (false positive)");

    50   // Test basic removals

    51   filter->remove(&two);

    52   MOZ_RELEASE_ASSERT(!filter->mightContain(&multiple),

    53              "Filter claims to contain 'multiple' when it should not after two "

    54              "was removed");

    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);

    61   MOZ_RELEASE_ASSERT(filter->mightContain(&multiple),

    62              "Filter should contain 'multiple' after 'two' added lots of times "

    63              "(false positive)");

    65   for (size_t i = 0; i < FILTER_SIZE - 1; ++i)

    66     filter->remove(&two);

    68   MOZ_RELEASE_ASSERT(!filter->mightContain(&multiple),

    69              "Filter claims to contain 'multiple' when it should not after two "

    70              "was removed lots of times");

    72   // Test overflowing the filter buckets

    73   for (size_t i = 0; i < FILTER_SIZE + 1; ++i)

    74     filter->add(&two);

    76   MOZ_RELEASE_ASSERT(filter->mightContain(&multiple),

    77              "Filter should contain 'multiple' after 'two' added lots more "

    78              "times (false positive)");

    80   for (size_t i = 0; i < FILTER_SIZE + 1; ++i)

    81     filter->remove(&two);

    83   MOZ_RELEASE_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_RELEASE_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)");

    90   filter->remove(&one);

    92   MOZ_RELEASE_ASSERT(!filter->mightContain(&one),

    93              "Filter should not contain 'one', because we didn't overflow its "

    94              "bucket");

    96   filter->clear();

    98   MOZ_RELEASE_ASSERT(!filter->mightContain(&multiple),

    99              "clear() failed to work");

   101   return 0;

   102 }

The Tor Browser / file revision