Subject: [Boost-commit] svn:boost r73562 - in sandbox/bloom_filter/trunk/boost/bloom_filter: . detail
From: cpp.cabrera_at_[hidden]
Date: 2011-08-05 23:07:21
Author: alejandro
Date: 2011-08-05 23:07:20 EDT (Fri, 05 Aug 2011)
New Revision: 73562
URL: http://svn.boost.org/trac/boost/changeset/73562
Log:
New data structure:
- Implemented dynamic_counting_bloom_filter from
counting_bloom_filter sources.
- Modified counting_apply_hash to handle num_bins parameter
for dynamic variant.
Text files modified:
sandbox/bloom_filter/trunk/boost/bloom_filter/counting_bloom_filter.hpp | 14 ++++++--
sandbox/bloom_filter/trunk/boost/bloom_filter/detail/counting_apply_hash.hpp | 47 ++++++++++++++++++-------------
sandbox/bloom_filter/trunk/boost/bloom_filter/dynamic_counting_bloom_filter.hpp | 60 +++++++++++++++++++++++----------------
3 files changed, 72 insertions(+), 49 deletions(-)
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-05 23:07:20 EDT (Fri, 05 Aug 2011)
@@ -181,7 +181,9 @@
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);
+ detail::counting_apply_hash<N, this_type>::insert(t,
+ this->bits,
+ this->num_bins());
}
template <typename InputIterator>
@@ -195,7 +197,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);
+ detail::counting_apply_hash<N, this_type>::remove(t,
+ this->bits,
+ this->num_bins());
}
template <typename InputIterator>
@@ -209,8 +213,10 @@
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);
+ return detail::counting_apply_hash<N,
+ this_type>::contains(t,
+ this->bits,
+ this->num_bins());
}
//! auxiliary ops
Modified: sandbox/bloom_filter/trunk/boost/bloom_filter/detail/counting_apply_hash.hpp
==============================================================================
--- sandbox/bloom_filter/trunk/boost/bloom_filter/detail/counting_apply_hash.hpp (original)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/detail/counting_apply_hash.hpp 2011-08-05 23:07:20 EDT (Fri, 05 Aug 2011)
@@ -44,17 +44,18 @@
typedef typename boost::mpl::at_c<typename CBF::hash_function_type,
N>::type Hash;
+ public:
BloomOp(const typename CBF::value_type& t,
- const typename CBF::bucket_type& slots)
+ const typename CBF::bucket_type& slots,
+ const size_t num_bins)
:
- hash_val(hasher(t) % CBF::num_bins()),
+ hash_val(hasher(t) % num_bins),
pos(hash_val / CBF::bins_per_slot()),
offset_bits((hash_val % CBF::bins_per_slot()) * CBF::bits_per_bin()),
target_bits((slots[pos] >> offset_bits) & CBF::mask())
{}
- void update(const typename CBF::value_type& t,
- typename CBF::bucket_type& slots,
+ void update(typename CBF::bucket_type& slots,
const size_t limit) const {
static Op op;
@@ -80,27 +81,30 @@
struct counting_apply_hash
{
static void insert(const typename CBF::value_type& t,
- typename CBF::bucket_type& slots)
+ typename CBF::bucket_type& slots,
+ const size_t num_bins)
{
- BloomOp<N, CBF, increment> inserter(t, slots);
- inserter.update(t, slots, (1ull << CBF::bits_per_bin()) - 1ull);
+ BloomOp<N, CBF, increment> inserter(t, slots, num_bins);
+ inserter.update(slots, (1ull << CBF::bits_per_bin()) - 1ull);
counting_apply_hash<N-1, CBF>::insert(t, slots);
}
static void remove(const typename CBF::value_type& t,
- typename CBF::bucket_type& slots)
+ typename CBF::bucket_type& slots,
+ const size_t num_bins)
{
- BloomOp<N, CBF, decrement> remover(t, slots);
- remover.update(t, slots, 0);
+ BloomOp<N, CBF, decrement> remover(t, slots, num_bins);
+ remover.update(slots, 0);
counting_apply_hash<N-1, CBF>::remove(t, slots);
}
static bool contains(const typename CBF::value_type& t,
- const typename CBF::bucket_type& slots)
+ const typename CBF::bucket_type& slots,
+ const size_t num_bins)
{
- BloomOp<N, CBF> checker(t, slots);
+ BloomOp<N, CBF> checker(t, slots, num_bins);
return (checker.check() &&
counting_apply_hash<N-1, CBF>::contains(t, slots));
}
@@ -110,23 +114,26 @@
struct counting_apply_hash<0, CBF>
{
static void insert(const typename CBF::value_type& t,
- typename CBF::bucket_type& slots)
+ typename CBF::bucket_type& slots,
+ const size_t num_bins)
{
- BloomOp<0, CBF, increment> inserter(t, slots);
- inserter.update(t, slots, (1ull << CBF::bits_per_bin()) - 1ull);
+ BloomOp<0, CBF, increment> inserter(t, slots, num_bins);
+ inserter.update(slots, (1ull << CBF::bits_per_bin()) - 1ull);
}
static void remove(const typename CBF::value_type& t,
- typename CBF::bucket_type& slots)
+ typename CBF::bucket_type& slots,
+ const size_t num_bins)
{
- BloomOp<0, CBF, decrement> remover(t, slots);
- remover.update(t, slots, 0);
+ BloomOp<0, CBF, decrement> remover(t, slots, num_bins);
+ remover.update(slots, 0);
}
static bool contains(const typename CBF::value_type& t,
- const typename CBF::bucket_type& slots)
+ const typename CBF::bucket_type& slots,
+ const size_t num_bins)
{
- BloomOp<0, CBF> checker(t, slots);
+ BloomOp<0, CBF> checker(t, slots, num_bins);
return (checker.check());
}
};
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-05 23:07:20 EDT (Fri, 05 Aug 2011)
@@ -74,36 +74,35 @@
typedef typename bucket_type::iterator bucket_iterator;
typedef typename bucket_type::const_iterator bucket_const_iterator;
- static const slot_bits = sizeof(block_type) * 8;
- static const size_t default_num_bins = 10000;
+ static const size_t slot_bits = sizeof(block_type) * 8;
+ static const size_t default_num_bins = 32;
private:
- size_t bucket_size(const size_t num_bins) const {
- const size_t bin_bits = num_bins * this->bits_per_bin();
+ size_t bucket_size(const size_t requested_bins) const {
+ const size_t bin_bits = requested_bins * BitsPerBin;
return bin_bits / slot_bits + 1;
}
public:
//! constructors
dynamic_counting_bloom_filter()
- : bits(bucket_size(default_num_bins))
+ : bits(bucket_size(default_num_bins)),
+ _num_bins(default_num_bins)
{
- this->clear();
}
- explicit dynamic_counting_bloom_filter(const size_t num_bins)
- : bits(bucket_size(num_bins))
+ explicit dynamic_counting_bloom_filter(const size_t requested_bins)
+ : bits(bucket_size(requested_bins)),
+ _num_bins(requested_bins)
{
- this->clear();
}
template <typename InputIterator>
dynamic_counting_bloom_filter(const InputIterator start,
const InputIterator end)
- : bits(bucket_size(std::distance(start, end) * 4))
+ : bits(bucket_size(std::distance(start, end) * 4)),
+ _num_bins(std::distance(start, end) * 4)
{
- this->clear();
-
for (InputIterator i = start; i != end; ++i)
this->insert(*i);
}
@@ -111,7 +110,7 @@
//! meta functions
size_t num_bins() const
{
- return NumBins;
+ return this->_num_bins;
}
static BOOST_CONSTEXPR size_t bits_per_bin()
@@ -143,7 +142,7 @@
{
const double n = static_cast<double>(this->count());
static const double k = static_cast<double>(num_hash_functions());
- static const double m = static_cast<double>(NumBins);
+ static const double m = static_cast<double>(this->num_bins());
static const double e =
2.718281828459045235360287471352662497757247093699959574966;
return std::pow(1 - std::pow(e, -k * n / m), k);
@@ -178,7 +177,10 @@
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);
+ detail::counting_apply_hash<N,
+ this_type>::insert(t,
+ this->bits,
+ this->num_bins());
}
template <typename InputIterator>
@@ -192,7 +194,10 @@
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);
+ detail::counting_apply_hash<N,
+ this_type>::remove(t,
+ this->bits,
+ this->num_bins());
}
template <typename InputIterator>
@@ -206,26 +211,30 @@
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);
+ return detail::counting_apply_hash<N,
+ this_type>::contains(t,
+ this->bits,
+ this->num_bins());
}
//! auxiliary ops
void clear()
{
- this->bits.clear();
+ for (bucket_iterator i = bits.begin(), end = bits.end();
+ i != end; ++i)
+ *i = 0;
}
- void swap(counting_bloom_filter& other)
+ void swap(dynamic_counting_bloom_filter& other)
{
- counting_bloom_filter tmp = other;
+ dynamic_counting_bloom_filter tmp = other;
other = *this;
*this = tmp;
}
//! pairwise ops
- counting_bloom_filter&
- experimental_union_assign(const counting_bloom_filter& rhs)
+ 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();
@@ -241,8 +250,8 @@
return *this;
}
- counting_bloom_filter&
- experimental_intersect_assign(const counting_bloom_filter& rhs)
+ 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();
@@ -282,6 +291,7 @@
private:
bucket_type bits;
+ size_t _num_bins;
};
// union