Subject: [Boost-commit] svn:boost r72829 - in sandbox/bloom_filter/trunk/boost/bloom_filter: . detail
From: cpp.cabrera_at_[hidden]
Date: 2011-06-30 20:36:15
Author: alejandro
Date: 2011-06-30 20:36:14 EDT (Thu, 30 Jun 2011)
New Revision: 72829
URL: http://svn.boost.org/trac/boost/changeset/72829
Log:
Preliminary CBF committed - may not compile. Added dynamic_apply_hash for dynamic Bloom filter. Solidified interface for dynamic Bloom filter a bit more. Needs a test suite and documentation.
Added:
sandbox/bloom_filter/trunk/boost/bloom_filter/counting_bloom.hpp
- copied, changed from r72740, /sandbox/bloom_filter/trunk/boost/bloom_filter/dynamic_bloom.hpp
Text files modified:
sandbox/bloom_filter/trunk/boost/bloom_filter/counting_bloom.hpp | 120 ++++++++++++++++++----------------------
sandbox/bloom_filter/trunk/boost/bloom_filter/detail/apply_hash.hpp | 60 ++++++++++++++++++++
sandbox/bloom_filter/trunk/boost/bloom_filter/dynamic_bloom.hpp | 47 +++++++++++++--
3 files changed, 155 insertions(+), 72 deletions(-)
Copied: sandbox/bloom_filter/trunk/boost/bloom_filter/counting_bloom.hpp (from r72740, /sandbox/bloom_filter/trunk/boost/bloom_filter/dynamic_bloom.hpp)
==============================================================================
--- /sandbox/bloom_filter/trunk/boost/bloom_filter/dynamic_bloom.hpp (original)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/counting_bloom.hpp 2011-06-30 20:36:14 EDT (Thu, 30 Jun 2011)
@@ -10,19 +10,19 @@
//
//////////////////////////////////////////////////////////////////////////////
-#ifndef BOOST_BLOOM_FILTER_DYNAMIC_BLOOM_HPP
-#define BOOST_BLOOM_FILTER_DYNAMIC_BLOOM_HPP 1
+#ifndef BOOST_BLOOM_FILTER_COUNTING_BLOOM_HPP
+#define BOOST_BLOOM_FILTER_COUNTING_BLOOM_HPP 1
/**
* \author Alejandro Cabrera
- * \brief A generic Bloom filter providing compile-time unrolling
- * of hash function application.
+ * \brief A generic counting Bloom filter providing compile-time unrolling
+ * of hash function application.
*/
#include <cmath>
+#include <boost/array.hpp>
#include <boost/config.hpp>
#include <boost/mpl/vector.hpp>
#include <boost/mpl/size.hpp>
-#include <boost/dynamic_bitset.hpp>
#include <boost/bloom_filter/detail/apply_hash.hpp>
#include <boost/bloom_filter/hash/default.hpp>
@@ -34,33 +34,28 @@
namespace boost {
namespace bloom_filter {
template <typename T,
+ size_t NumBins,
class HashFunctions = mpl::vector<boost_hash<T, 3> >,
- class Block = size_t,
- class Allocator = std::allocator<Block> >
- class dynamic_bloom_filter {
+ typename Block,
+ typename BitsPerBin>
+ class counting_bloom_filter {
+ typedef boost::array<NumBlocks, Block> bucket_type;
+
public:
typedef T value_type;
typedef T key_type;
- typedef HashFunctions hash_function_type;
- typedef Block block_type;
- typedef Allocator allocator_type;
public:
-
- // constructors
- dynamic_bloom_filter() {}
-
- explicit dynamic_bloom_filter(const size_t bit_capacity);
+ counting_bloom_filter() {}
template <typename InputIterator>
- dynamic_bloom_filter(const InputIterator start,
- const InputIterator end) {
+ counting_bloom_filter(const InputIterator start, const InputIterator end) {
for (InputIterator i = start; i != end; ++i)
this->insert(*i);
}
#ifndef BOOST_NO_0X_HDR_INITIALIZER_LIST
- dynamic_bloom_filter(const std::initializer_list<T>& ilist) {
+ counting_bloom_filter(const std::initializer_list<T>& ilist) {
typedef typename std::initializer_list<T>::const_iterator citer;
for (citer i = ilist.begin(), end = ilist.end(); i != end; ++i) {
this->insert(*i);
@@ -68,13 +63,20 @@
}
#endif
- // query functions
+ static BOOST_CONSTEXPR size_t num_blocks() {
+ return NumBlocks;
+ }
+
+ static BOOST_CONSTEXPR size_t bit_capacity() {
+ return NumBlocks * sizeof(Block);
+ }
+
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());
+ 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>(Size);
static const double e =
@@ -83,17 +85,16 @@
};
size_t count() const {
- return this->bits.count();
+ return std::accumulate(this->blocks.begin(), this->blocks.end(), 0);
};
bool empty() const {
return this->count() == 0;
}
- // core operations
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::counting_apply_hash<N, T, Size, HashFunctions>::insert(t, bits);
}
template <typename InputIterator>
@@ -103,78 +104,65 @@
}
}
+ void remove(const T& t);
+
+ template <typename InputIterator>
+ void insert(const InputIterator start, const InputIterator end) {
+ for (InputIterator i = start; i != end; ++i) {
+ this->remove(*i);
+ }
+ }
+
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 false;
}
- // auxilliary operations
void clear() {
- this->bits.reset();
+ for (bucket_type::const_iterator i = blocks.begin(), end = blocks.end();
+ i != end; ++i) {
+ *i = 0;
+ }
}
- void swap(bloom_filter& other) {
- bloom_filter tmp = other;
+ void swap(counting_bloom_filter& other) {
+ counting_bloom_filter tmp = other;
other = *this;
*this = tmp;
}
- void resize(const size_t bit_capacity);
-
- bloom_filter& operator|=(const bloom_filter& rhs) {
- this->bits |= rhs.bits;
- return *this;
- }
-
- bloom_filter& operator&=(const bloom_filter& rhs) {
- this->bits &= rhs.bits;
- return *this;
- }
+ counting_bloom_filter& operator|=(const counting_bloom_filter& rhs);
+ counting_bloom_filter& operator&=(const bloom_filter& rhs);
private:
- dynamic_bitset<block_type, allocator_type> bits;
+ bucket_type blocks;
};
- template<class T, class HashFunctions,
- class Block, class Allocator>
- dynamic_bloom_filter<T, HashFunctions, Block, Allocator>
- operator|(const dynamic_bloom_filter<T,
- HashFunctions,
- Block, Allocator>& lhs,
- const dynamic_bloom_filter<T,
- HashFunctions,
- Block, Allocator>& rhs)
+ template<class _T, size_t _Size, class _HashFunctions>
+ bloom_filter<_T, _Size, _HashFunctions>
+ operator|(const bloom_filter<_T, _Size, _HashFunctions>& lhs,
+ const bloom_filter<_T, _Size, _HashFunctions>& rhs)
{
bloom_filter<_T, _Size, _HashFunctions> ret(lhs);
ret |= rhs;
return ret;
}
- template<class T, class HashFunctions,
- class Block, class Allocator>
- dynamic_bloom_filter<T, HashFunctions, Block, Allocator>
- operator&(const dynamic_bloom_filter<T,
- HashFunctions,
- Block, Allocator>& lhs,
- const dynamic_bloom_filter<T,
- HashFunctions,
- Block, Allocator>& rhs)
+ template<class _T, size_t _Size, class _HashFunctions>
+ bloom_filter<_T, _Size, _HashFunctions>
+ operator&(const bloom_filter<_T, _Size, _HashFunctions>& lhs,
+ const bloom_filter<_T, _Size, _HashFunctions>& rhs)
{
bloom_filter<_T, _Size, _HashFunctions> ret(lhs);
ret &= rhs;
return ret;
}
- template<class T, class HashFunctions,
- class Block, class Allocator>
+ template<class _T, size_t _Size, class _HashFunctions>
void
- swap(dynamic_bloom_filter<T,
- HashFunctions,
- Block, Allocator>& lhs,
- dynamic_bloom_filter<T,
- HashFunctions,
- Block, Allocator>& rhs)
+ swap(bloom_filter<_T, _Size, _HashFunctions>& lhs,
+ bloom_filter<_T, _Size, _HashFunctions>& rhs)
{
lhs.swap(rhs);
}
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-06-30 20:36:14 EDT (Thu, 30 Jun 2011)
@@ -13,11 +13,14 @@
#ifndef BOOST_BLOOM_FILTER_APPLY_HASH_HPP
#define BOOST_BLOOM_FILTER_APPLY_HASH_HPP
+#include <boost/dynamic_bitset.hpp>
#include <boost/mpl/at.hpp>
namespace boost {
namespace bloom_filter {
namespace detail {
+
+ // static bloom filter
template <size_t N,
typename T,
size_t Size,
@@ -56,6 +59,63 @@
return (_bits[hasher(t) % Size]);
}
};
+
+ // dynamic bloom filter
+ template <size_t N,
+ typename T,
+ class HashFunctions,
+ typename Block,
+ class Allocator>
+ struct dynamic_apply_hash
+ {
+ 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;
+ 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 Hash hasher;
+ _bits[hasher(t) % 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 Hash hasher;
+ return (_bits[hasher(t) % size]);
+ }
+ };
} // namespace detail
} // namespace bloom_filter
} // namespace boost
Modified: sandbox/bloom_filter/trunk/boost/bloom_filter/dynamic_bloom.hpp
==============================================================================
--- sandbox/bloom_filter/trunk/boost/bloom_filter/dynamic_bloom.hpp (original)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/dynamic_bloom.hpp 2011-06-30 20:36:14 EDT (Thu, 30 Jun 2011)
@@ -50,8 +50,8 @@
// constructors
dynamic_bloom_filter() {}
- explicit dynamic_bloom_filter(const size_t bit_capacity);
-
+ explicit dynamic_bloom_filter(const size_t bit_capacity) : bits(bit_capacity) {}
+
template <typename InputIterator>
dynamic_bloom_filter(const InputIterator start,
const InputIterator end) {
@@ -93,7 +93,8 @@
// core operations
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::dynamic_apply_hash<N, T, HashFunctions, Block, Allocator>::
+ insert(t, bits, bits.size());
}
template <typename InputIterator>
@@ -105,8 +106,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 false;
+ return detail::
+ dynamic_apply_hash<N, T, HashFunctions, Block, Allocator>::
+ contains(t, bits, bits.size());
}
// auxilliary operations
@@ -120,7 +122,13 @@
*this = tmp;
}
- void resize(const size_t bit_capacity);
+ void resize(const size_t bit_capacity) {
+ bits.clear();
+ bits.resize(bit_capacity);
+ }
+
+ friend bool operator==(const bloom_filter&, const bloom_filter&);
+ friend bool operator!=(const bloom_filter&, const bloom_filter&);
bloom_filter& operator|=(const bloom_filter& rhs) {
this->bits |= rhs.bits;
@@ -166,6 +174,33 @@
return ret;
}
+
+ template<class T, class HashFunctions,
+ class Block, class Allocator>
+ bool
+ operator==(const dynamic_bloom_filter<T,
+ HashFunctions,
+ Block, Allocator>& lhs,
+ const dynamic_bloom_filter<T,
+ HashFunctions,
+ Block, Allocator>& rhs)
+ {
+ return lhs.bits == rhs.bits;
+ }
+
+ template<class T, class HashFunctions,
+ class Block, class Allocator>
+ bool
+ operator!=(const dynamic_bloom_filter<T,
+ HashFunctions,
+ Block, Allocator>& lhs,
+ const dynamic_bloom_filter<T,
+ HashFunctions,
+ Block, Allocator>& rhs)
+ {
+ return !(lhs == rhs);
+ }
+
template<class T, class HashFunctions,
class Block, class Allocator>
void