Subject: [Boost-commit] svn:boost r73393 - in sandbox/bloom_filter/trunk/boost/bloom_filter: . detail
From: cpp.cabrera_at_[hidden]
Date: 2011-07-26 17:23:54
Author: alejandro
Date: 2011-07-26 17:23:52 EDT (Tue, 26 Jul 2011)
New Revision: 73393
URL: http://svn.boost.org/trac/boost/changeset/73393
Log:
Major refactoring on apply_hash:
- combined dynamic_apply_hash and apply_hash into a single meta-function.
Updated basic_bloom_filter and dynamic_bloom_filter:
- both use new version of apply_hash.
- added incompatible_size_exception for pairwise operations
Working on refactoring counting_apply_hash.
Bug:
- counting_bloom_filter: bin_exceptions do not trigger.
Text files modified:
sandbox/bloom_filter/trunk/boost/bloom_filter/basic_bloom_filter.hpp | 18 +++--
sandbox/bloom_filter/trunk/boost/bloom_filter/counting_bloom_filter.hpp | 42 +++++++-------
sandbox/bloom_filter/trunk/boost/bloom_filter/detail/apply_hash.hpp | 119 ++++++++++-----------------------------
sandbox/bloom_filter/trunk/boost/bloom_filter/detail/counting_apply_hash.hpp | 64 ++++++++++++++-------
sandbox/bloom_filter/trunk/boost/bloom_filter/detail/exceptions.hpp | 15 +++-
sandbox/bloom_filter/trunk/boost/bloom_filter/dynamic_bloom_filter.hpp | 65 +++++++++++++--------
6 files changed, 158 insertions(+), 165 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-07-26 17:23:52 EDT (Tue, 26 Jul 2011)
@@ -12,11 +12,7 @@
#ifndef BOOST_BLOOM_FILTER_BLOOM_FILTER_HPP
#define BOOST_BLOOM_FILTER_BLOOM_FILTER_HPP 1
-/**
- * \author Alejandro Cabrera
- * \brief A generic Bloom filter providing compile-time unrolling
- * of hash function application.
- */
+
#include <cmath>
#include <bitset>
@@ -40,7 +36,10 @@
public:
typedef T value_type;
typedef T key_type;
+ typedef std::bitset<Size> bitset_type;
typedef HashFunctions hash_function_type;
+ typedef basic_bloom_filter<T, Size,
+ HashFunctions> this_type;
public:
basic_bloom_filter() {}
@@ -87,7 +86,8 @@
void insert(const T& t) {
static const unsigned N = mpl::size<HashFunctions>::value - 1;
- detail::apply_hash<N, T, Size, HashFunctions>::insert(t, bits);
+ detail::apply_hash<N,
+ this_type>::insert(t, bits);
}
template <typename InputIterator>
@@ -99,7 +99,9 @@
bool probably_contains(const T& t) const {
static const unsigned N = mpl::size<HashFunctions>::value - 1;
- return detail::apply_hash<N, T, Size, HashFunctions>::contains(t, bits);
+ return detail::
+ apply_hash<N,
+ this_type>::contains(t, bits);
}
void clear() {
@@ -133,7 +135,7 @@
const basic_bloom_filter<_T, _Size, _HashFunctions>&);
private:
- std::bitset<Size> bits;
+ bitset_type bits;
};
template<class _T, size_t _Size, class _HashFunctions>
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-07-26 17:23:52 EDT (Tue, 26 Jul 2011)
@@ -59,7 +59,7 @@
// can have internal fragmentation if the calculation for
// bins_per_slot has a remainder. The severity of the internal
// fragmentation is equal to the remainder * the number of slots.
- // this check prevents internal fragmentation
+ // This check prevents internal fragmentation
BOOST_STATIC_ASSERT( ((sizeof(Block) * 8) % BitsPerBin) == 0);
// a slot is one element position in the array
@@ -72,17 +72,16 @@
static const size_t mask =
static_cast<Block>(0 - 1) >> (slot_bits - BitsPerBin);
- private:
- typedef boost::array<Block, array_size> bucket_type;
- typedef typename bucket_type::iterator bucket_iterator;
- typedef typename bucket_type::const_iterator bucket_const_iterator;
-
public:
typedef T value_type;
typedef T key_type;
typedef HashFunctions hash_function_type;
typedef Block block_type;
+ typedef boost::array<Block, array_size> bucket_type;
+ typedef typename bucket_type::iterator bucket_iterator;
+ typedef typename bucket_type::const_iterator bucket_const_iterator;
+
public:
counting_bloom_filter()
{
@@ -130,13 +129,6 @@
size_t count() const {
size_t ret = 0;
- /*
- std::cout << "Num Bins: " << NumBins << "\n"
- << "Bins Per Slot: " << bins_per_slot << "\n"
- << "Bits Per Bin: " << BitsPerBin << "\n"
- << "Array Size: " << array_size << "\n";
- */
-
for (bucket_const_iterator i = this->bits.begin(),
end = this->bits.end();
i != end; ++i) {
@@ -144,14 +136,6 @@
size_t offset_bits = bin * BitsPerBin;
size_t target_bits = (*i >> offset_bits) & mask;
- /*
- std::cout << "(count) targeting pos: " << std::distance(i, end) - 1
- << " with offset: " << offset_bits
- << " and bin: " << bin
- << " with slot value: " << *i
- << " and bin value: " << target_bits << "\n";
- */
-
if (target_bits > 0)
++ret;
}
@@ -217,11 +201,27 @@
counting_bloom_filter& operator|=(const counting_bloom_filter& rhs)
{
+ const bucket_iterator this_end = this->bits.end();
+ bucket_iterator this_start = this->bits.begin();
+ bucket_iterator rhs_start = rhs.bits.begin();
+
+ for (; this_start != this_end; ++this_start, ++rhs_start) {
+ *this_start |= *rhs_start;
+ }
+
return *this;
}
counting_bloom_filter& operator&=(const counting_bloom_filter& rhs)
{
+ const bucket_iterator this_end = this->bits.end();
+ bucket_iterator this_start = this->bits.begin();
+ bucket_iterator rhs_start = rhs.bits.begin();
+
+ for (; this_start != this_end; ++this_start, ++rhs_start) {
+ *this_start &= *rhs_start;
+ }
+
return *this;
}
Modified: sandbox/bloom_filter/trunk/boost/bloom_filter/detail/apply_hash.hpp
==============================================================================
--- sandbox/bloom_filter/trunk/boost/bloom_filter/detail/apply_hash.hpp (original)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/detail/apply_hash.hpp 2011-07-26 17:23:52 EDT (Tue, 26 Jul 2011)
@@ -13,122 +13,67 @@
#ifndef BOOST_BLOOM_FILTER_APPLY_HASH_HPP
#define BOOST_BLOOM_FILTER_APPLY_HASH_HPP
-#include <bitset>
-#include <boost/dynamic_bitset.hpp>
#include <boost/mpl/at.hpp>
namespace boost {
namespace bloom_filters {
namespace detail {
- /*************************************************************************
- * static bloom filter
- ************************************************************************/
template <size_t N,
- typename T,
- size_t Size,
- class HashFunctions>
+ typename Container>
struct apply_hash
{
- static void insert(const T& t, std::bitset<Size>& _bits) {
- typedef typename boost::mpl::at_c<HashFunctions, N>::type Hash;
- static Hash hasher;
-
- _bits[hasher(t) % Size] = true;
- apply_hash<N-1, T, Size, HashFunctions>::insert(t, _bits);
- }
-
- static bool contains(const T& t, const std::bitset<Size>& _bits) {
- typedef typename boost::mpl::at_c<HashFunctions, N>::type Hash;
- static Hash hasher;
+ typedef typename Container::value_type value_type;
+ typedef typename Container::bitset_type bitset_type;
+ typedef typename Container::hash_function_type hash_function_type;
- return (_bits[hasher(t) % Size] &&
- apply_hash<N-1, T, Size, HashFunctions>::contains(t, _bits));
- }
- };
-
- template <typename T,
- size_t Size,
- class HashFunctions>
- struct apply_hash<0, T, Size, HashFunctions>
- {
- static void insert(const T& t, std::bitset<Size>& _bits) {
- typedef typename boost::mpl::at_c<HashFunctions, 0>::type Hash;
+ static void insert(const value_type& t,
+ bitset_type& _bits)
+ {
+ typedef typename boost::mpl::at_c<hash_function_type, N>::type Hash;
static Hash hasher;
- _bits[hasher(t) % Size] = true;
+ _bits[hasher(t) % _bits.size()] = true;
+ apply_hash<N-1, Container>::insert(t, _bits);
}
- static bool contains(const T& t, const std::bitset<Size>& _bits) {
- typedef typename boost::mpl::at_c<HashFunctions, 0>::type Hash;
+ static bool contains(const value_type& t,
+ const bitset_type& _bits)
+ {
+ typedef typename boost::mpl::at_c<hash_function_type, N>::type Hash;
static Hash hasher;
- return (_bits[hasher(t) % Size]);
+ return (_bits[hasher(t) % _bits.size()] &&
+ apply_hash<N-1, Container>::contains(t, _bits));
}
};
- /*************************************************************************
- * dynamic bloom filter
- ************************************************************************/
- template <size_t N,
- typename T,
- class HashFunctions,
- typename Block,
- class Allocator>
- struct dynamic_apply_hash
+ template <typename Container>
+ struct apply_hash<0, Container>
{
- static void insert(const T& t, boost::dynamic_bitset<Block, Allocator>& _bits,
- const size_t size) {
- typedef typename boost::mpl::at_c<HashFunctions, N>::type Hash;
- static Hash hasher;
-
- _bits[hasher(t) % size] = true;
- dynamic_apply_hash<N-1,
- T,
- HashFunctions,
- Block,
- Allocator>::insert(t, _bits, size);
- }
-
- static bool contains(const T& t,
- const boost::dynamic_bitset<Block, Allocator>& _bits,
- const size_t size) {
- typedef typename boost::mpl::at_c<HashFunctions, N>::type Hash;
- static Hash hasher;
+ typedef typename Container::value_type value_type;
+ typedef typename Container::bitset_type bitset_type;
+ typedef typename Container::hash_function_type hash_function_type;
- return (_bits[hasher(t) % size] &&
- dynamic_apply_hash<N-1,
- T,
- HashFunctions,
- Block,
- Allocator>::contains(t, _bits, size));
- }
- };
-
- template <typename T,
- class HashFunctions,
- typename Block,
- class Allocator>
- struct dynamic_apply_hash<0, T, HashFunctions, Block, Allocator>
- {
- static void insert(const T& t,
- boost::dynamic_bitset<Block, Allocator>& _bits,
- const size_t size) {
- typedef typename boost::mpl::at_c<HashFunctions, 0>::type Hash;
+ static void insert(const value_type& t,
+ bitset_type& _bits)
+ {
+ typedef typename boost::mpl::at_c<hash_function_type, 0>::type Hash;
static Hash hasher;
- _bits[hasher(t) % size] = true;
+ _bits[hasher(t) % _bits.size()] = true;
}
- static bool contains(const T& t,
- const boost::dynamic_bitset<Block, Allocator>& _bits,
- const size_t size) {
- typedef typename boost::mpl::at_c<HashFunctions, 0>::type Hash;
+ static bool contains(const value_type& t,
+ const bitset_type& _bits)
+ {
+ typedef typename boost::mpl::at_c<hash_function_type, 0>::type Hash;
static Hash hasher;
- return (_bits[hasher(t) % size]);
+ return (_bits[hasher(t) % _bits.size()]);
}
};
+
} // namespace detail
} // namespace bloom_filter
} // namespace boost
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-07-26 17:23:52 EDT (Tue, 26 Jul 2011)
@@ -18,6 +18,8 @@
#include <boost/array.hpp>
#include <boost/mpl/at.hpp>
+#include <boost/bloom_filter/detail/exceptions.hpp>
+
namespace boost {
namespace bloom_filters {
namespace detail {
@@ -43,11 +45,15 @@
typedef typename boost::mpl::at_c<HashFunctions, N>::type Hash;
static Hash hasher;
- size_t hash_val = Hash(t) % NumBins;
- size_t pos = hash_val / BinsPerSlot;
- size_t offset_bits = (hash_val % BinsPerSlot) * BitsPerBin;
+ const size_t hash_val = Hash(t) % NumBins;
+ const size_t pos = hash_val / BinsPerSlot;
+ const size_t offset_bits = (hash_val % BinsPerSlot) * BitsPerBin;
size_t target_bits = (_slots[pos] >> offset_bits) & MASK;
- ++target_bits;
+ ++target_bits;
+
+ if (target_bits == 0)
+ throw bin_overflow_exception();
+
_slots[pos] |= (target_bits << offset_bits);
counting_apply_hash<N-1, T, NumBins,
@@ -60,11 +66,16 @@
typedef typename boost::mpl::at_c<HashFunctions, N>::type Hash;
static Hash hasher;
- size_t hash_val = hasher(t) % NumBins;
- size_t pos = hash_val / BinsPerSlot;
- size_t offset_bits = (hash_val % BinsPerSlot) * BitsPerBin;
+ const size_t hash_val = hasher(t) % NumBins;
+ const size_t pos = hash_val / BinsPerSlot;
+ const size_t offset_bits = (hash_val % BinsPerSlot) * BitsPerBin;
size_t target_bits = (_slots[pos] >> offset_bits) & MASK;
+
+ if (target_bits == 0)
+ throw bin_underflow_exception();
+
--target_bits;
+
_slots[pos] |= (target_bits << offset_bits);
counting_apply_hash<N-1, T, NumBins,
@@ -77,10 +88,10 @@
typedef typename boost::mpl::at_c<HashFunctions, N>::type Hash;
static Hash hasher;
- size_t hash_val = hasher(t) % NumBins;
- size_t pos = hash_val / BinsPerSlot;
- size_t offset_bits = (hash_val % BinsPerSlot) * BitsPerBin;
- size_t target_bits = (_slots[pos] >> offset_bits) & MASK;
+ const size_t hash_val = hasher(t) % NumBins;
+ const size_t pos = hash_val / BinsPerSlot;
+ const size_t offset_bits = (hash_val % BinsPerSlot) * BitsPerBin;
+ const size_t target_bits = (_slots[pos] >> offset_bits) & MASK;
return ((target_bits > 0) &&
counting_apply_hash<N-1, T, NumBins,
@@ -115,11 +126,16 @@
<< " incoming value: " << t << "\n";
*/
- size_t hash_val = hasher(t) % NumBins;
- size_t pos = hash_val / BinsPerSlot;
- size_t offset_bits = (hash_val % BinsPerSlot) * BitsPerBin;
+ const size_t hash_val = hasher(t) % NumBins;
+ const size_t pos = hash_val / BinsPerSlot;
+ const size_t offset_bits = (hash_val % BinsPerSlot) * BitsPerBin;
size_t target_bits = (_slots[pos] >> offset_bits) & MASK;
+
++target_bits;
+
+ if (target_bits == 0)
+ throw bin_overflow_exception();
+
_slots[pos] &= ~(MASK << offset_bits);
_slots[pos] |= (target_bits << offset_bits);
@@ -146,11 +162,17 @@
<< " incoming value: " << t << "\n";
*/
- size_t hash_val = hasher(t) % NumBins;
- size_t pos = hash_val / BinsPerSlot;
- size_t offset_bits = (hash_val % BinsPerSlot) * BitsPerBin;
+ const size_t hash_val = hasher(t) % NumBins;
+ const size_t pos = hash_val / BinsPerSlot;
+ const size_t offset_bits = (hash_val % BinsPerSlot) * BitsPerBin;
size_t target_bits = (_slots[pos] >> offset_bits) & MASK;
+
+
+ if (target_bits == 0)
+ throw bin_underflow_exception();
+
--target_bits;
+
_slots[pos] &= ~(MASK << offset_bits);
_slots[pos] |= (target_bits << offset_bits);
@@ -177,10 +199,10 @@
<< " incoming value: " << t << "\n";
*/
- size_t hash_val = hasher(t) % NumBins;
- size_t pos = hash_val / BinsPerSlot;
- size_t offset_bits = (hash_val % BinsPerSlot) * BitsPerBin;
- size_t target_bits = (_slots[pos] >> offset_bits) & MASK;
+ const size_t hash_val = hasher(t) % NumBins;
+ const size_t pos = hash_val / BinsPerSlot;
+ const size_t offset_bits = (hash_val % BinsPerSlot) * BitsPerBin;
+ const size_t target_bits = (_slots[pos] >> offset_bits) & MASK;
/*
std::cout << "(contains) checked bits at pos " << pos
Modified: sandbox/bloom_filter/trunk/boost/bloom_filter/detail/exceptions.hpp
==============================================================================
--- sandbox/bloom_filter/trunk/boost/bloom_filter/detail/exceptions.hpp (original)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/detail/exceptions.hpp 2011-07-26 17:23:52 EDT (Tue, 26 Jul 2011)
@@ -19,20 +19,27 @@
namespace bloom_filters {
namespace detail {
- class underflow : public std::exception {
+ class bin_underflow_exception : public std::exception {
virtual const char *
what() const throw() {
- return "boost::bloom_filters::detail::underflow";
+ return "boost::bloom_filters::detail::bin_underflow_exception";
}
};
- class overrflow : public std::exception {
+ class bin_overflow_exception : public std::exception {
virtual const char *
what() const throw() {
- return "boost::bloom_filters::detail::overflow";
+ return "boost::bloom_filters::detail::bin_overflow_exception";
}
};
+ class incompatible_size_exception : public std::exception {
+ virtual const char *
+ what() const throw() {
+ return "boost::bloom_filters::detail::incompatible_size_exception";
+ }
+ };
+
} // namespace detail
} // namespace bloom_filter
} // namespace boost
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-07-26 17:23:52 EDT (Tue, 26 Jul 2011)
@@ -12,13 +12,8 @@
#ifndef BOOST_BLOOM_FILTER_DYNAMIC_BLOOM_FILTER_HPP
#define BOOST_BLOOM_FILTER_DYNAMIC_BLOOM_FILTER_HPP 1
-/**
- * \author Alejandro Cabrera
- * \brief A generic Bloom filter providing compile-time unrolling
- * of hash function application.
- */
+
#include <cmath>
-#include <cassert>
#include <boost/config.hpp>
#include <boost/mpl/vector.hpp>
@@ -26,6 +21,7 @@
#include <boost/dynamic_bitset.hpp>
#include <boost/bloom_filter/detail/apply_hash.hpp>
+#include <boost/bloom_filter/detail/exceptions.hpp>
#include <boost/bloom_filter/hash/default.hpp>
namespace boost {
@@ -41,19 +37,22 @@
typedef HashFunctions hash_function_type;
typedef Block block_type;
typedef Allocator allocator_type;
+ typedef dynamic_bitset<block_type, allocator_type> bitset_type;
+ typedef dynamic_bloom_filter<T, HashFunctions,
+ Block, Allocator> this_type;
public:
// constructors
dynamic_bloom_filter() {}
- explicit dynamic_bloom_filter(const size_t bit_capacity) : bits(bit_capacity) {}
+ explicit dynamic_bloom_filter(const size_t bit_capacity) :
+ bits(bit_capacity) {}
template <typename InputIterator>
- dynamic_bloom_filter(const size_t bit_capacity,
- const InputIterator start,
+ dynamic_bloom_filter(const InputIterator start,
const InputIterator end)
- : bits(bit_capacity)
+ : bits(std::distance(start, end) * 4)
{
for (InputIterator i = start; i != end; ++i)
this->insert(*i);
@@ -62,7 +61,7 @@
// query functions
static BOOST_CONSTEXPR size_t num_hash_functions() {
return mpl::size<HashFunctions>::value;
- };
+ }
double false_positive_rate() const {
const double n = static_cast<double>(this->bits.count());
@@ -71,11 +70,11 @@
static const double e =
2.718281828459045235360287471352662497757247093699959574966;
return std::pow(1 - std::pow(e, -k * n / m), k);
- };
+ }
size_t count() const {
return this->bits.count();
- };
+ }
size_t bit_capacity() const {
return this->bits.size();
@@ -88,8 +87,8 @@
// core operations
void insert(const T& t) {
static const unsigned N = mpl::size<HashFunctions>::value - 1;
- detail::dynamic_apply_hash<N, T, HashFunctions, Block, Allocator>::
- insert(t, bits, bits.size());
+ detail::apply_hash<N, this_type>::
+ insert(t, bits);
}
template <typename InputIterator>
@@ -102,8 +101,8 @@
bool probably_contains(const T& t) const {
static const unsigned N = mpl::size<HashFunctions>::value - 1;
return detail::
- dynamic_apply_hash<N, T, HashFunctions, Block, Allocator>::
- contains(t, bits, bits.size());
+ apply_hash<N, this_type>::
+ contains(t, bits);
}
// auxilliary operations
@@ -124,8 +123,10 @@
template <typename _T, typename _HashFunctions,
typename _Block, typename _Allocator>
- friend bool operator==(const dynamic_bloom_filter<_T, _HashFunctions, _Block, _Allocator>&,
- const dynamic_bloom_filter<_T, _HashFunctions, _Block, _Allocator>&);
+ friend bool operator==(const dynamic_bloom_filter<_T, _HashFunctions,
+ _Block, _Allocator>&,
+ const dynamic_bloom_filter<_T, _HashFunctions,
+ _Block, _Allocator>&);
template <typename _T, typename _HashFunctions,
typename _Block, typename _Allocator>
@@ -139,19 +140,25 @@
_Allocator>&);
dynamic_bloom_filter& operator|=(const dynamic_bloom_filter& rhs) {
- assert(this->bit_capacity() == rhs.bit_capacity());
+ if(this->bit_capacity() != rhs.bit_capacity()) {
+ throw detail::incompatible_size_exception();
+ }
+
this->bits |= rhs.bits;
return *this;
}
dynamic_bloom_filter& operator&=(const dynamic_bloom_filter& rhs) {
- assert(this->bit_capacity() == rhs.bit_capacity());
+ if(this->bit_capacity() != rhs.bit_capacity()) {
+ throw detail::incompatible_size_exception();
+ }
+
this->bits &= rhs.bits;
return *this;
}
private:
- dynamic_bitset<block_type, allocator_type> bits;
+ bitset_type bits;
};
template<class T, class HashFunctions,
@@ -164,7 +171,10 @@
HashFunctions,
Block, Allocator>& rhs)
{
- assert(lhs.bit_capacity() == rhs.bit_capacity());
+ if(lhs.bit_capacity() != rhs.bit_capacity()) {
+ throw detail::incompatible_size_exception();
+ }
+
dynamic_bloom_filter<T, HashFunctions, Block, Allocator> ret(lhs);
ret |= rhs;
return ret;
@@ -180,7 +190,10 @@
HashFunctions,
Block, Allocator>& rhs)
{
- assert(lhs.bit_capacity() == rhs.bit_capacity());
+ if(lhs.bit_capacity() != rhs.bit_capacity()) {
+ throw detail::incompatible_size_exception();
+ }
+
dynamic_bloom_filter<T, HashFunctions, Block, Allocator> ret(lhs);
ret &= rhs;
return ret;
@@ -197,6 +210,10 @@
HashFunctions,
Block, Allocator>& rhs)
{
+ if(lhs.bit_capacity() != rhs.bit_capacity()) {
+ throw detail::incompatible_size_exception();
+ }
+
return lhs.bits == rhs.bits;
}