Subject: [Boost-commit] svn:boost r73709 - in sandbox/bloom_filter/trunk/boost/bloom_filter: . hash
From: cpp.cabrera_at_[hidden]
Date: 2011-08-13 01:10:26
Author: alejandro
Date: 2011-08-13 01:10:24 EDT (Sat, 13 Aug 2011)
New Revision: 73709
URL: http://svn.boost.org/trac/boost/changeset/73709
Log:
New data structure:
- twohash_dynamic_counting_bloom_filter
Updates:
- Removed requirement that Seed parameter be
specified for boost_hash. Updated several
files to reflect this change.
- Added expectedInsertionCount function to 2H_CBF.
Refactoring:
- Added private typedef apply_hash_type for:
* basic_bloom_filter
* dynamic_bloom_filter
* counting_bloom_filter
* dynamic_counting_bloom_filter
Added:
sandbox/bloom_filter/trunk/boost/bloom_filter/twohash_dynamic_counting_bloom_filter.hpp
- copied, changed from r73662, /sandbox/bloom_filter/trunk/boost/bloom_filter/dynamic_counting_bloom_filter.hpp
Text files modified:
sandbox/bloom_filter/trunk/boost/bloom_filter/basic_bloom_filter.hpp | 15 -
sandbox/bloom_filter/trunk/boost/bloom_filter/counting_bloom_filter.hpp | 97 ++----------
sandbox/bloom_filter/trunk/boost/bloom_filter/dynamic_bloom_filter.hpp | 23 +-
sandbox/bloom_filter/trunk/boost/bloom_filter/dynamic_counting_bloom_filter.hpp | 116 ++-------------
sandbox/bloom_filter/trunk/boost/bloom_filter/hash/default.hpp | 2
sandbox/bloom_filter/trunk/boost/bloom_filter/twohash_basic_bloom_filter.hpp | 2
sandbox/bloom_filter/trunk/boost/bloom_filter/twohash_counting_bloom_filter.hpp | 7
sandbox/bloom_filter/trunk/boost/bloom_filter/twohash_dynamic_basic_bloom_filter.hpp | 2
sandbox/bloom_filter/trunk/boost/bloom_filter/twohash_dynamic_counting_bloom_filter.hpp | 299 +++++++++++++++++++--------------------
9 files changed, 210 insertions(+), 353 deletions(-)
Modified: sandbox/bloom_filter/trunk/boost/bloom_filter/basic_bloom_filter.hpp
==============================================================================
--- sandbox/bloom_filter/trunk/boost/bloom_filter/basic_bloom_filter.hpp (original)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/basic_bloom_filter.hpp 2011-08-13 01:10:24 EDT (Sat, 13 Aug 2011)
@@ -31,7 +31,7 @@
namespace bloom_filters {
template <typename T,
size_t Size,
- class HashFunctions = mpl::vector<boost_hash<T, 3> > >
+ class HashFunctions = mpl::vector<boost_hash<T> > >
class basic_bloom_filter {
public:
typedef T value_type;
@@ -41,6 +41,10 @@
typedef basic_bloom_filter<T, Size,
HashFunctions> this_type;
+ private:
+ typedef detail::apply_hash<mpl::size<HashFunctions>::value - 1,
+ this_type> apply_hash_type;
+
public:
basic_bloom_filter() {}
@@ -91,9 +95,7 @@
}
void insert(const T& t) {
- static const unsigned N = mpl::size<HashFunctions>::value - 1;
- detail::apply_hash<N,
- this_type>::insert(t, bits);
+ apply_hash_type::insert(t, bits);
}
template <typename InputIterator>
@@ -104,10 +106,7 @@
}
bool probably_contains(const T& t) const {
- static const unsigned N = mpl::size<HashFunctions>::value - 1;
- return detail::
- apply_hash<N,
- this_type>::contains(t, bits);
+ return apply_hash_type::contains(t, bits);
}
void clear() {
Modified: sandbox/bloom_filter/trunk/boost/bloom_filter/counting_bloom_filter.hpp
==============================================================================
--- sandbox/bloom_filter/trunk/boost/bloom_filter/counting_bloom_filter.hpp (original)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/counting_bloom_filter.hpp 2011-08-13 01:10:24 EDT (Sat, 13 Aug 2011)
@@ -37,7 +37,7 @@
template <typename T,
size_t NumBins,
size_t BitsPerBin = 4,
- class HashFunctions = mpl::vector<boost_hash<T, 0> >,
+ class HashFunctions = mpl::vector<boost_hash<T> >,
typename Block = size_t>
class counting_bloom_filter {
@@ -82,8 +82,12 @@
typedef typename bucket_type::iterator bucket_iterator;
typedef typename bucket_type::const_iterator bucket_const_iterator;
+ private:
+ typedef detail::counting_apply_hash<mpl::size<HashFunctions>::value - 1,
+ this_type> apply_hash_type;
+
public:
- //! constructors
+ //* constructors
counting_bloom_filter()
{
this->clear();
@@ -111,7 +115,7 @@
}
#endif
- //! meta functions
+ //* meta functions
static BOOST_CONSTEXPR size_t num_bins()
{
return NumBins;
@@ -183,13 +187,12 @@
return this->bits;
}
- //! core ops
+ //* core ops
void insert(const T& t)
{
- static const unsigned N = boost::mpl::size<hash_function_type>::value - 1;
- detail::counting_apply_hash<N, this_type>::insert(t,
- this->bits,
- this->num_bins());
+ apply_hash_type::insert(t,
+ this->bits,
+ this->num_bins());
}
template <typename InputIterator>
@@ -202,10 +205,9 @@
void remove(const T& t)
{
- static const unsigned N = boost::mpl::size<hash_function_type>::value - 1;
- detail::counting_apply_hash<N, this_type>::remove(t,
- this->bits,
- this->num_bins());
+ apply_hash_type::remove(t,
+ this->bits,
+ this->num_bins());
}
template <typename InputIterator>
@@ -218,14 +220,12 @@
bool probably_contains(const T& t) const
{
- static const unsigned N = mpl::size<HashFunctions>::value - 1;
- return detail::counting_apply_hash<N,
- this_type>::contains(t,
- this->bits,
- this->num_bins());
+ return apply_hash_type::contains(t,
+ this->bits,
+ this->num_bins());
}
- //! auxiliary ops
+ //* auxiliary ops
void clear()
{
for (bucket_iterator i = bits.begin(), end = bits.end();
@@ -241,36 +241,7 @@
*this = tmp;
}
- //! pairwise ops
- counting_bloom_filter&
- experimental_union_assign(const counting_bloom_filter& rhs)
- {
- bucket_iterator this_end = this->bits.end();
- bucket_iterator this_start = this->bits.begin();
- bucket_const_iterator rhs_start = rhs.bits.begin();
-
- for (; this_start != this_end; ++this_start, ++rhs_start) {
- *this_start |= *rhs_start;
- }
-
- return *this;
- }
-
- counting_bloom_filter&
- experimental_intersect_assign(const counting_bloom_filter& rhs)
- {
- bucket_iterator this_end = this->bits.end();
- bucket_iterator this_start = this->bits.begin();
- bucket_const_iterator rhs_start = rhs.bits.begin();
-
- for (; this_start != this_end; ++this_start, ++rhs_start) {
- *this_start &= *rhs_start;
- }
-
- return *this;
- }
-
- // equality comparison operators
+ //* equality comparison operators
template <typename _T, size_t _Bins, size_t _BitsPerBin,
typename _HashFns, typename _Block>
friend bool
@@ -292,36 +263,6 @@
bucket_type bits;
};
- // union
- template<class T, size_t NumBins, size_t BitsPerBin, class HashFunctions,
- typename Block>
- counting_bloom_filter<T, NumBins, BitsPerBin, HashFunctions, Block>
- experimental_union(const counting_bloom_filter<T, NumBins, BitsPerBin,
- HashFunctions, Block>& lhs,
- const counting_bloom_filter<T, NumBins, BitsPerBin,
- HashFunctions, Block>& rhs)
- {
- counting_bloom_filter<T, NumBins, BitsPerBin,
- HashFunctions, Block> ret(lhs);
- ret.experimental_union_assign(rhs);
- return ret;
- }
-
- // intersection
- template<class T, size_t NumBins, size_t BitsPerBin, class HashFunctions,
- typename Block>
- counting_bloom_filter<T, NumBins, BitsPerBin, HashFunctions, Block>
- experimental_intersect(const counting_bloom_filter<T, NumBins, BitsPerBin,
- HashFunctions, Block>& lhs,
- const counting_bloom_filter<T, NumBins, BitsPerBin,
- HashFunctions, Block>& rhs)
- {
- counting_bloom_filter<T, NumBins, BitsPerBin,
- HashFunctions, Block> ret(lhs);
- ret.experimental_intersect_assign(rhs);
- return ret;
- }
-
template<class T, size_t NumBins, size_t BitsPerBin, class HashFunctions,
typename Block>
void
Modified: sandbox/bloom_filter/trunk/boost/bloom_filter/dynamic_bloom_filter.hpp
==============================================================================
--- sandbox/bloom_filter/trunk/boost/bloom_filter/dynamic_bloom_filter.hpp (original)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/dynamic_bloom_filter.hpp 2011-08-13 01:10:24 EDT (Sat, 13 Aug 2011)
@@ -27,7 +27,7 @@
namespace boost {
namespace bloom_filters {
template <typename T,
- class HashFunctions = mpl::vector<boost_hash<T, 3> >,
+ class HashFunctions = mpl::vector<boost_hash<T> >,
class Block = size_t,
class Allocator = std::allocator<Block> >
class dynamic_bloom_filter {
@@ -41,9 +41,13 @@
typedef dynamic_bloom_filter<T, HashFunctions,
Block, Allocator> this_type;
+ private:
+ typedef detail::apply_hash<mpl::size<HashFunctions>::value - 1,
+ this_type> apply_hash_type;
+
public:
- // constructors
+ //* constructors
dynamic_bloom_filter() {}
explicit dynamic_bloom_filter(const size_t bit_capacity) :
@@ -58,7 +62,7 @@
this->insert(*i);
}
- // query functions
+ //* query functions
static BOOST_CONSTEXPR size_t num_hash_functions() {
return mpl::size<HashFunctions>::value;
}
@@ -90,11 +94,9 @@
return this->bits;
}
- // core operations
+ //* core operations
void insert(const T& t) {
- static const unsigned N = mpl::size<HashFunctions>::value - 1;
- detail::apply_hash<N, this_type>::
- insert(t, bits);
+ apply_hash_type::insert(t, bits);
}
template <typename InputIterator>
@@ -105,13 +107,10 @@
}
bool probably_contains(const T& t) const {
- static const unsigned N = mpl::size<HashFunctions>::value - 1;
- return detail::
- apply_hash<N, this_type>::
- contains(t, bits);
+ return apply_hash_type::contains(t, bits);
}
- // auxilliary operations
+ //* auxilliary operations
void clear() {
this->bits.reset();
}
Modified: sandbox/bloom_filter/trunk/boost/bloom_filter/dynamic_counting_bloom_filter.hpp
==============================================================================
--- sandbox/bloom_filter/trunk/boost/bloom_filter/dynamic_counting_bloom_filter.hpp (original)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/dynamic_counting_bloom_filter.hpp 2011-08-13 01:10:24 EDT (Sat, 13 Aug 2011)
@@ -32,7 +32,7 @@
namespace bloom_filters {
template <typename T,
size_t BitsPerBin = 4,
- class HashFunctions = mpl::vector<boost_hash<T, 0> >,
+ class HashFunctions = mpl::vector<boost_hash<T> >,
typename Block = size_t,
typename Allocator = std::allocator<Block> >
class dynamic_counting_bloom_filter {
@@ -83,8 +83,11 @@
return bin_bits / slot_bits + 1;
}
+ typedef detail::counting_apply_hash<mpl::size<HashFunctions>::value - 1,
+ this_type> apply_hash_type;
+
public:
- //! constructors
+ //* constructors
dynamic_counting_bloom_filter()
: bits(bucket_size(default_num_bins)),
_num_bins(default_num_bins)
@@ -107,7 +110,7 @@
this->insert(*i);
}
- //! meta functions
+ //* meta functions
size_t num_bins() const
{
return this->_num_bins;
@@ -179,14 +182,12 @@
return this->bits;
}
- //! core ops
+ //* core ops
void insert(const T& t)
{
- static const unsigned N = boost::mpl::size<hash_function_type>::value - 1;
- detail::counting_apply_hash<N,
- this_type>::insert(t,
- this->bits,
- this->num_bins());
+ apply_hash_type::insert(t,
+ this->bits,
+ this->num_bins());
}
template <typename InputIterator>
@@ -199,11 +200,9 @@
void remove(const T& t)
{
- static const unsigned N = boost::mpl::size<hash_function_type>::value - 1;
- detail::counting_apply_hash<N,
- this_type>::remove(t,
- this->bits,
- this->num_bins());
+ apply_hash_type::remove(t,
+ this->bits,
+ this->num_bins());
}
template <typename InputIterator>
@@ -216,14 +215,12 @@
bool probably_contains(const T& t) const
{
- static const unsigned N = mpl::size<HashFunctions>::value - 1;
- return detail::counting_apply_hash<N,
- this_type>::contains(t,
- this->bits,
- this->num_bins());
+ return apply_hash_type::contains(t,
+ this->bits,
+ this->num_bins());
}
- //! auxiliary ops
+ //* auxiliary ops
void clear()
{
for (bucket_iterator i = bits.begin(), end = bits.end();
@@ -238,42 +235,7 @@
*this = tmp;
}
- //! pairwise ops
- dynamic_counting_bloom_filter&
- experimental_union_assign(const dynamic_counting_bloom_filter& rhs)
- {
- if (this->bit_capacity() != rhs.bit_capacity())
- throw detail::incompatible_size_exception();
-
- bucket_iterator this_end = this->bits.end();
- bucket_iterator this_start = this->bits.begin();
- bucket_const_iterator rhs_start = rhs.bits.begin();
-
- for (; this_start != this_end; ++this_start, ++rhs_start) {
- *this_start |= *rhs_start;
- }
-
- return *this;
- }
-
- dynamic_counting_bloom_filter&
- experimental_intersect_assign(const dynamic_counting_bloom_filter& rhs)
- {
- if (this->bit_capacity() != rhs.bit_capacity())
- throw detail::incompatible_size_exception();
-
- bucket_iterator this_end = this->bits.end();
- bucket_iterator this_start = this->bits.begin();
- bucket_const_iterator rhs_start = rhs.bits.begin();
-
- for (; this_start != this_end; ++this_start, ++rhs_start) {
- *this_start &= *rhs_start;
- }
-
- return *this;
- }
-
- // equality comparison operators
+ //* equality comparison operators
template <typename _T, size_t _BitsPerBin,
typename _HashFns, typename _Block, typename _Allocator>
friend bool
@@ -300,48 +262,6 @@
size_t _num_bins;
};
- // union
- template<class T, size_t BitsPerBin, class HashFunctions,
- typename Block, typename Allocator>
- dynamic_counting_bloom_filter<T, BitsPerBin,
- HashFunctions, Block, Allocator>
- experimental_union(const dynamic_counting_bloom_filter<T, BitsPerBin,
- HashFunctions,
- Block,
- Allocator>& lhs,
- const dynamic_counting_bloom_filter<T, BitsPerBin,
- HashFunctions,
- Block,
- Allocator>& rhs)
- {
- dynamic_counting_bloom_filter<T, BitsPerBin,
- HashFunctions, Block,
- Allocator> ret(lhs);
- ret.experimental_union_assign(rhs);
- return ret;
- }
-
- // intersection
- template<class T, size_t BitsPerBin, class HashFunctions,
- typename Block, typename Allocator>
- dynamic_counting_bloom_filter<T, BitsPerBin, HashFunctions,
- Block, Allocator>
- experimental_intersect(const dynamic_counting_bloom_filter<T, BitsPerBin,
- HashFunctions,
- Block,
- Allocator>& lhs,
- const dynamic_counting_bloom_filter<T, BitsPerBin,
- HashFunctions,
- Block,
- Allocator>& rhs)
- {
- dynamic_counting_bloom_filter<T, BitsPerBin,
- HashFunctions, Block,
- Allocator> ret(lhs);
- ret.experimental_intersect_assign(rhs);
- return ret;
- }
-
template<class T, size_t BitsPerBin, class HashFunctions,
typename Block, typename Allocator>
void
Modified: sandbox/bloom_filter/trunk/boost/bloom_filter/hash/default.hpp
==============================================================================
--- sandbox/bloom_filter/trunk/boost/bloom_filter/hash/default.hpp (original)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/hash/default.hpp 2011-08-13 01:10:24 EDT (Sat, 13 Aug 2011)
@@ -20,7 +20,7 @@
namespace boost {
namespace bloom_filters {
- template <typename T, size_t Seed>
+ template <typename T, size_t Seed = 0>
struct boost_hash {
size_t operator()(const T& t) {
return boost::hash_value(t) + Seed;
Modified: sandbox/bloom_filter/trunk/boost/bloom_filter/twohash_basic_bloom_filter.hpp
==============================================================================
--- sandbox/bloom_filter/trunk/boost/bloom_filter/twohash_basic_bloom_filter.hpp (original)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/twohash_basic_bloom_filter.hpp 2011-08-13 01:10:24 EDT (Sat, 13 Aug 2011)
@@ -33,7 +33,7 @@
size_t Size,
size_t HashValues = 2,
size_t ExpectedInsertionCount = 0,
- class HashFunction1 = boost_hash<T, 0>,
+ class HashFunction1 = boost_hash<T>,
class HashFunction2 = murmurhash3<T>,
typename ExtensionFunction = detail::square>// = ???
class twohash_basic_bloom_filter {
Modified: sandbox/bloom_filter/trunk/boost/bloom_filter/twohash_counting_bloom_filter.hpp
==============================================================================
--- sandbox/bloom_filter/trunk/boost/bloom_filter/twohash_counting_bloom_filter.hpp (original)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/twohash_counting_bloom_filter.hpp 2011-08-13 01:10:24 EDT (Sat, 13 Aug 2011)
@@ -38,7 +38,7 @@
size_t BitsPerBin = 4,
size_t HashValues = 2,
size_t ExpectedInsertionCount = 0,
- class HashFunction1 = boost_hash<T, 0>,
+ class HashFunction1 = boost_hash<T>,
class HashFunction2 = murmurhash3<T>,
class ExtensionFunction = detail::square,
typename Block = size_t>
@@ -134,6 +134,11 @@
return BitsPerBin;
}
+ static BOOST_CONSTEXPR size_t expected_insertion_count()
+ {
+ return ExpectedInsertionCount;
+ }
+
static BOOST_CONSTEXPR size_t bins_per_slot()
{
return sizeof(block_type) * 8 / BitsPerBin;
Modified: sandbox/bloom_filter/trunk/boost/bloom_filter/twohash_dynamic_basic_bloom_filter.hpp
==============================================================================
--- sandbox/bloom_filter/trunk/boost/bloom_filter/twohash_dynamic_basic_bloom_filter.hpp (original)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/twohash_dynamic_basic_bloom_filter.hpp 2011-08-13 01:10:24 EDT (Sat, 13 Aug 2011)
@@ -29,7 +29,7 @@
template <typename T,
size_t HashValues = 2,
size_t ExpectedInsertionCount = 0,
- class HashFunction1 = boost_hash<T, 0>,
+ class HashFunction1 = boost_hash<T>,
class HashFunction2 = murmurhash3<T>,
typename ExtensionFunction = detail::square,
typename Block = size_t,
Copied: sandbox/bloom_filter/trunk/boost/bloom_filter/twohash_dynamic_counting_bloom_filter.hpp (from r73662, /sandbox/bloom_filter/trunk/boost/bloom_filter/dynamic_counting_bloom_filter.hpp)
==============================================================================
--- /sandbox/bloom_filter/trunk/boost/bloom_filter/dynamic_counting_bloom_filter.hpp (original)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/twohash_dynamic_counting_bloom_filter.hpp 2011-08-13 01:10:24 EDT (Sat, 13 Aug 2011)
@@ -18,24 +18,27 @@
#include <boost/config.hpp>
-#include <boost/mpl/vector.hpp>
-#include <boost/mpl/size.hpp>
-
#include <boost/static_assert.hpp>
#include <boost/type_traits/is_integral.hpp>
#include <boost/type_traits/is_unsigned.hpp>
-#include <boost/bloom_filter/detail/counting_apply_hash.hpp>
+#include <boost/bloom_filter/detail/twohash_counting_apply_hash.hpp>
+#include <boost/bloom_filter/detail/extenders.hpp>
#include <boost/bloom_filter/hash/default.hpp>
+#include <boost/bloom_filter/hash/murmurhash3.hpp>
namespace boost {
namespace bloom_filters {
template <typename T,
size_t BitsPerBin = 4,
- class HashFunctions = mpl::vector<boost_hash<T, 0> >,
+ size_t HashValues = 2,
+ size_t ExpectedInsertionCount = 0,
+ class HashFunction1 = boost_hash<T>,
+ class HashFunction2 = murmurhash3<T>,
+ class ExtensionFunction = detail::square,
typename Block = size_t,
typename Allocator = std::allocator<Block> >
- class dynamic_counting_bloom_filter {
+ class twohash_dynamic_counting_bloom_filter {
// Block needs to be an integral type
BOOST_STATIC_ASSERT( boost::is_integral<Block>::value == true);
@@ -63,43 +66,53 @@
public:
typedef T value_type;
typedef T key_type;
- typedef HashFunctions hash_function_type;
+ typedef HashFunction1 hash_function1_type;
+ typedef HashFunction2 hash_function2_type;
+ typedef ExtensionFunction extension_function_type;
typedef Block block_type;
typedef Allocator allocator_type;
- typedef dynamic_counting_bloom_filter<T, BitsPerBin,
- HashFunctions,
- Block, Allocator> this_type;
+ typedef twohash_dynamic_counting_bloom_filter<T, BitsPerBin,
+ HashValues,
+ ExpectedInsertionCount,
+ HashFunction1,
+ HashFunction2,
+ ExtensionFunction,
+ Block, Allocator> this_type;
typedef std::vector<Block, Allocator> bucket_type;
typedef typename bucket_type::iterator bucket_iterator;
typedef typename bucket_type::const_iterator bucket_const_iterator;
- static const size_t slot_bits = sizeof(block_type) * 8;
static const size_t default_num_bins = 32;
private:
+ static const size_t slot_bits = sizeof(block_type) * 8;
+
size_t bucket_size(const size_t requested_bins) const {
const size_t bin_bits = requested_bins * BitsPerBin;
return bin_bits / slot_bits + 1;
}
+ typedef detail::twohash_counting_apply_hash<HashValues,
+ this_type> apply_hash_type;
+
public:
//! constructors
- dynamic_counting_bloom_filter()
+ twohash_dynamic_counting_bloom_filter()
: bits(bucket_size(default_num_bins)),
_num_bins(default_num_bins)
{
}
- explicit dynamic_counting_bloom_filter(const size_t requested_bins)
+ explicit twohash_dynamic_counting_bloom_filter(const size_t requested_bins)
: bits(bucket_size(requested_bins)),
_num_bins(requested_bins)
{
}
template <typename InputIterator>
- dynamic_counting_bloom_filter(const InputIterator start,
- const InputIterator end)
+ twohash_dynamic_counting_bloom_filter(const InputIterator start,
+ const InputIterator end)
: bits(bucket_size(std::distance(start, end) * 4)),
_num_bins(std::distance(start, end) * 4)
{
@@ -113,6 +126,11 @@
return this->_num_bins;
}
+ static BOOST_CONSTEXPR size_t expected_insertion_count()
+ {
+ return ExpectedInsertionCount;
+ }
+
static BOOST_CONSTEXPR size_t bits_per_bin()
{
return BitsPerBin;
@@ -135,7 +153,7 @@
static BOOST_CONSTEXPR size_t num_hash_functions()
{
- return mpl::size<HashFunctions>::value;
+ return HashValues;
}
double false_positive_rate() const
@@ -182,11 +200,9 @@
//! core ops
void insert(const T& t)
{
- static const unsigned N = boost::mpl::size<hash_function_type>::value - 1;
- detail::counting_apply_hash<N,
- this_type>::insert(t,
- this->bits,
- this->num_bins());
+ apply_hash_type::insert(t,
+ this->bits,
+ this->num_bins());
}
template <typename InputIterator>
@@ -199,11 +215,9 @@
void remove(const T& t)
{
- static const unsigned N = boost::mpl::size<hash_function_type>::value - 1;
- detail::counting_apply_hash<N,
- this_type>::remove(t,
- this->bits,
- this->num_bins());
+ apply_hash_type::remove(t,
+ this->bits,
+ this->num_bins());
}
template <typename InputIterator>
@@ -216,11 +230,9 @@
bool probably_contains(const T& t) const
{
- static const unsigned N = mpl::size<HashFunctions>::value - 1;
- return detail::counting_apply_hash<N,
- this_type>::contains(t,
- this->bits,
- this->num_bins());
+ return apply_hash_type::contains(t,
+ this->bits,
+ this->num_bins());
}
//! auxiliary ops
@@ -231,142 +243,112 @@
*i = 0;
}
- void swap(dynamic_counting_bloom_filter& other)
+ void swap(twohash_dynamic_counting_bloom_filter& other)
{
- dynamic_counting_bloom_filter tmp = other;
+ twohash_dynamic_counting_bloom_filter tmp = other;
other = *this;
*this = tmp;
}
- //! pairwise ops
- dynamic_counting_bloom_filter&
- experimental_union_assign(const dynamic_counting_bloom_filter& rhs)
- {
- if (this->bit_capacity() != rhs.bit_capacity())
- throw detail::incompatible_size_exception();
-
- bucket_iterator this_end = this->bits.end();
- bucket_iterator this_start = this->bits.begin();
- bucket_const_iterator rhs_start = rhs.bits.begin();
-
- for (; this_start != this_end; ++this_start, ++rhs_start) {
- *this_start |= *rhs_start;
- }
-
- return *this;
- }
-
- dynamic_counting_bloom_filter&
- experimental_intersect_assign(const dynamic_counting_bloom_filter& rhs)
- {
- if (this->bit_capacity() != rhs.bit_capacity())
- throw detail::incompatible_size_exception();
-
- bucket_iterator this_end = this->bits.end();
- bucket_iterator this_start = this->bits.begin();
- bucket_const_iterator rhs_start = rhs.bits.begin();
-
- for (; this_start != this_end; ++this_start, ++rhs_start) {
- *this_start &= *rhs_start;
- }
-
- return *this;
- }
-
// equality comparison operators
template <typename _T, size_t _BitsPerBin,
- typename _HashFns, typename _Block, typename _Allocator>
+ size_t _HashValues, size_t _ExpectedInsertionCount,
+ class _HashFn1, class _HashFn2, class _Extender,
+ typename _Block, class _Allocator>
friend bool
- operator==(const dynamic_counting_bloom_filter<_T, _BitsPerBin,
- _HashFns, _Block,
- _Allocator>& lhs,
- const dynamic_counting_bloom_filter<_T, _BitsPerBin,
- _HashFns, _Block,
- _Allocator>& rhs);
+ operator==(const twohash_dynamic_counting_bloom_filter<_T, _BitsPerBin,
+ _HashValues,
+ _ExpectedInsertionCount,
+ _HashFn1,
+ _HashFn2,
+ _Extender,
+ _Block,
+ _Allocator>& lhs,
+ const twohash_dynamic_counting_bloom_filter<_T, _BitsPerBin,
+ _HashValues,
+ _ExpectedInsertionCount,
+ _HashFn1,
+ _HashFn2,
+ _Extender,
+ _Block,
+ _Allocator>& rhs);
template <typename _T, size_t _BitsPerBin,
- typename _HashFns, typename _Block, typename _Allocator>
+ size_t _HashValues, size_t _ExpectedInsertionCount,
+ class _HashFn1, class _HashFn2, class _Extender,
+ typename _Block, class _Allocator>
friend bool
- operator!=(const dynamic_counting_bloom_filter<_T, _BitsPerBin,
- _HashFns, _Block,
- _Allocator>& lhs,
- const dynamic_counting_bloom_filter<_T, _BitsPerBin,
- _HashFns, _Block,
- _Allocator>& rhs);
-
+ operator!=(const twohash_dynamic_counting_bloom_filter<_T, _BitsPerBin,
+ _HashValues,
+ _ExpectedInsertionCount,
+ _HashFn1,
+ _HashFn2,
+ _Extender,
+ _Block,
+ _Allocator>& lhs,
+ const twohash_dynamic_counting_bloom_filter<_T, _BitsPerBin,
+ _HashValues,
+ _ExpectedInsertionCount,
+ _HashFn1,
+ _HashFn2,
+ _Extender,
+ _Block,
+ _Allocator>& rhs);
private:
bucket_type bits;
size_t _num_bins;
};
- // union
- template<class T, size_t BitsPerBin, class HashFunctions,
- typename Block, typename Allocator>
- dynamic_counting_bloom_filter<T, BitsPerBin,
- HashFunctions, Block, Allocator>
- experimental_union(const dynamic_counting_bloom_filter<T, BitsPerBin,
- HashFunctions,
- Block,
- Allocator>& lhs,
- const dynamic_counting_bloom_filter<T, BitsPerBin,
- HashFunctions,
- Block,
- Allocator>& rhs)
- {
- dynamic_counting_bloom_filter<T, BitsPerBin,
- HashFunctions, Block,
- Allocator> ret(lhs);
- ret.experimental_union_assign(rhs);
- return ret;
- }
-
- // intersection
- template<class T, size_t BitsPerBin, class HashFunctions,
- typename Block, typename Allocator>
- dynamic_counting_bloom_filter<T, BitsPerBin, HashFunctions,
- Block, Allocator>
- experimental_intersect(const dynamic_counting_bloom_filter<T, BitsPerBin,
- HashFunctions,
- Block,
- Allocator>& lhs,
- const dynamic_counting_bloom_filter<T, BitsPerBin,
- HashFunctions,
- Block,
- Allocator>& rhs)
- {
- dynamic_counting_bloom_filter<T, BitsPerBin,
- HashFunctions, Block,
- Allocator> ret(lhs);
- ret.experimental_intersect_assign(rhs);
- return ret;
- }
-
- template<class T, size_t BitsPerBin, class HashFunctions,
- typename Block, typename Allocator>
+ template<class T, size_t BitsPerBin, size_t HashValues,
+ size_t ExpectedInsertionCount,
+ class HashFunction1, class HashFunction2,
+ class ExtensionFunction, typename Block,
+ class Allocator>
void
- swap(dynamic_counting_bloom_filter<T, BitsPerBin,
- HashFunctions, Block,
- Allocator>& lhs,
- dynamic_counting_bloom_filter<T, BitsPerBin,
- HashFunctions, Block,
- Allocator>& rhs)
+ swap(twohash_dynamic_counting_bloom_filter<T, BitsPerBin,
+ HashValues,
+ ExpectedInsertionCount,
+ HashFunction1,
+ HashFunction2,
+ ExtensionFunction,
+ Block,
+ Allocator>& lhs,
+ twohash_dynamic_counting_bloom_filter<T, BitsPerBin,
+ HashValues,
+ ExpectedInsertionCount,
+ HashFunction1,
+ HashFunction2,
+ ExtensionFunction,
+ Block,
+ Allocator>& rhs)
{
lhs.swap(rhs);
}
- template<class T, size_t BitsPerBin, class HashFunctions,
- typename Block, typename Allocator>
+ template<class T, size_t BitsPerBin, size_t HashValues,
+ size_t ExpectedInsertionCount,
+ class HashFunction1, class HashFunction2,
+ class ExtensionFunction, typename Block,
+ class Allocator>
bool
- operator==(const dynamic_counting_bloom_filter<T, BitsPerBin,
- HashFunctions,
- Block,
- Allocator>& lhs,
- const dynamic_counting_bloom_filter<T, BitsPerBin,
- HashFunctions,
- Block,
- Allocator>& rhs)
+ operator==(const twohash_dynamic_counting_bloom_filter<T, BitsPerBin,
+ HashValues,
+ ExpectedInsertionCount,
+ HashFunction1,
+ HashFunction2,
+ ExtensionFunction,
+ Block,
+ Allocator>& lhs,
+ const twohash_dynamic_counting_bloom_filter<T, BitsPerBin,
+ HashValues,
+ ExpectedInsertionCount,
+ HashFunction1,
+ HashFunction2,
+ ExtensionFunction,
+ Block,
+ Allocator>& rhs)
{
if (lhs.bit_capacity() != rhs.bit_capacity())
throw detail::incompatible_size_exception();
@@ -374,17 +356,28 @@
return (lhs.bits == rhs.bits);
}
- template<class T, size_t BitsPerBin, class HashFunctions,
- typename Block, typename Allocator>
+ template<class T, size_t BitsPerBin, size_t HashValues,
+ size_t ExpectedInsertionCount,
+ class HashFunction1, class HashFunction2,
+ class ExtensionFunction, typename Block,
+ class Allocator>
bool
- operator!=(const dynamic_counting_bloom_filter<T, BitsPerBin,
- HashFunctions,
- Block,
- Allocator>& lhs,
- const dynamic_counting_bloom_filter<T, BitsPerBin,
- HashFunctions,
- Block,
- Allocator>& rhs)
+ operator!=(const twohash_dynamic_counting_bloom_filter<T, BitsPerBin,
+ HashValues,
+ ExpectedInsertionCount,
+ HashFunction1,
+ HashFunction2,
+ ExtensionFunction,
+ Block,
+ Allocator>& lhs,
+ const twohash_dynamic_counting_bloom_filter<T, BitsPerBin,
+ HashValues,
+ ExpectedInsertionCount,
+ HashFunction1,
+ HashFunction2,
+ ExtensionFunction,
+ Block,
+ Allocator>& rhs)
{
if (lhs.bit_capacity() != rhs.bit_capacity())
throw detail::incompatible_size_exception();