The Tor Browser / file comparison
comparison: mfbt/tests/TestBloomFilter.cpp
mfbt/tests/TestBloomFilter.cpp
- changeset 2
- 7e26c7da4463
equal
deleted
inserted
replaced
| -1:000000000000 | 0:29ce6580c1f2 |
|---|---|
| 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_RELEASE_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_RELEASE_ASSERT(filter->mightContain(&one), | |
| 38 "Filter should contain 'one'"); | |
| 39 | |
| 40 MOZ_RELEASE_ASSERT(!filter->mightContain(&multiple), | |
| 41 "Filter claims to contain 'multiple' when it should not"); | |
| 42 | |
| 43 MOZ_RELEASE_ASSERT(filter->mightContain(&many), | |
| 44 "Filter should contain 'many' (false positive)"); | |
| 45 | |
| 46 filter->add(&two); | |
| 47 MOZ_RELEASE_ASSERT(filter->mightContain(&multiple), | |
| 48 "Filter should contain 'multiple' (false positive)"); | |
| 49 | |
| 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"); | |
| 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_RELEASE_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_RELEASE_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_RELEASE_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_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)"); | |
| 89 | |
| 90 filter->remove(&one); | |
| 91 | |
| 92 MOZ_RELEASE_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_RELEASE_ASSERT(!filter->mightContain(&multiple), | |
| 99 "clear() failed to work"); | |
| 100 | |
| 101 return 0; | |
| 102 } |
