tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

TestBloomFilter.cpp (4303B)

      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 auto filter = mozilla::MakeUnique<BitBloomFilter<12, FilterChecker>>();
     29  MOZ_RELEASE_ASSERT(filter);
     30 
     31  FilterChecker one(1);
     32  FilterChecker two(0x20000);
     33 
     34  filter->add(&one);
     35  MOZ_RELEASE_ASSERT(filter->mightContain(&one), "Filter should contain 'one'");
     36 
     37  MOZ_RELEASE_ASSERT(!filter->mightContain(&two),
     38                     "Filter claims to contain 'two' when it should not");
     39 
     40  // Test multiple addition
     41  filter->add(&two);
     42  MOZ_RELEASE_ASSERT(filter->mightContain(&two),
     43                     "Filter should contain 'two' after 'two' is added");
     44  filter->add(&two);
     45  MOZ_RELEASE_ASSERT(filter->mightContain(&two),
     46                     "Filter should contain 'two' after 'two' is added again");
     47 
     48  filter->clear();
     49 
     50  MOZ_RELEASE_ASSERT(!filter->mightContain(&one), "clear() failed to work");
     51  MOZ_RELEASE_ASSERT(!filter->mightContain(&two), "clear() failed to work");
     52 }
     53 
     54 void testCountingBloomFilter() {
     55  const auto filter =
     56      mozilla::MakeUnique<CountingBloomFilter<12, FilterChecker>>();
     57  MOZ_RELEASE_ASSERT(filter);
     58 
     59  FilterChecker one(1);
     60  FilterChecker two(0x20000);
     61  FilterChecker many(0x10000);
     62  FilterChecker multiple(0x20001);
     63 
     64  filter->add(&one);
     65  MOZ_RELEASE_ASSERT(filter->mightContain(&one), "Filter should contain 'one'");
     66 
     67  MOZ_RELEASE_ASSERT(!filter->mightContain(&multiple),
     68                     "Filter claims to contain 'multiple' when it should not");
     69 
     70  MOZ_RELEASE_ASSERT(filter->mightContain(&many),
     71                     "Filter should contain 'many' (false positive)");
     72 
     73  filter->add(&two);
     74  MOZ_RELEASE_ASSERT(filter->mightContain(&multiple),
     75                     "Filter should contain 'multiple' (false positive)");
     76 
     77  // Test basic removals
     78  filter->remove(&two);
     79  MOZ_RELEASE_ASSERT(
     80      !filter->mightContain(&multiple),
     81      "Filter claims to contain 'multiple' when it should not after two "
     82      "was removed");
     83 
     84  // Test multiple addition/removal
     85  const size_t FILTER_SIZE = 255;
     86  for (size_t i = 0; i < FILTER_SIZE - 1; ++i) {
     87    filter->add(&two);
     88  }
     89  MOZ_RELEASE_ASSERT(
     90      filter->mightContain(&multiple),
     91      "Filter should contain 'multiple' after 'two' added lots of times "
     92      "(false positive)");
     93 
     94  for (size_t i = 0; i < FILTER_SIZE - 1; ++i) {
     95    filter->remove(&two);
     96  }
     97  MOZ_RELEASE_ASSERT(
     98      !filter->mightContain(&multiple),
     99      "Filter claims to contain 'multiple' when it should not after two "
    100      "was removed lots of times");
    101 
    102  // Test overflowing the filter buckets
    103  for (size_t i = 0; i < FILTER_SIZE + 1; ++i) {
    104    filter->add(&two);
    105  }
    106  MOZ_RELEASE_ASSERT(
    107      filter->mightContain(&multiple),
    108      "Filter should contain 'multiple' after 'two' added lots more "
    109      "times (false positive)");
    110 
    111  for (size_t i = 0; i < FILTER_SIZE + 1; ++i) {
    112    filter->remove(&two);
    113  }
    114  MOZ_RELEASE_ASSERT(
    115      filter->mightContain(&multiple),
    116      "Filter claims to not contain 'multiple' even though we should "
    117      "have run out of space in the buckets (false positive)");
    118  MOZ_RELEASE_ASSERT(
    119      filter->mightContain(&two),
    120      "Filter claims to not contain 'two' even though we should have "
    121      "run out of space in the buckets (false positive)");
    122 
    123  filter->remove(&one);
    124 
    125  MOZ_RELEASE_ASSERT(
    126      !filter->mightContain(&one),
    127      "Filter should not contain 'one', because we didn't overflow its "
    128      "bucket");
    129 
    130  filter->clear();
    131 
    132  MOZ_RELEASE_ASSERT(!filter->mightContain(&multiple),
    133                     "clear() failed to work");
    134 }
    135 
    136 int main() {
    137  testBitBloomFilter();
    138  testCountingBloomFilter();
    139 
    140  return 0;
    141 }