Subject: [Boost-commit] svn:boost r53784 - in sandbox/bloom_filter/trunk: boost/bloom_filter boost/bloom_filter/detail libs/bloom_filter/test
From: mikhailberis_at_[hidden]
Date: 2009-06-10 04:03:41
Author: mikhailberis
Date: 2009-06-10 04:03:38 EDT (Wed, 10 Jun 2009)
New Revision: 53784
URL: http://svn.boost.org/trac/boost/changeset/53784
Log:
Changes:
* Making the collection of hash function types a template parameter instead of a number; The requirement on the collection is that it should be a valid Fusion sequence.
* Changing the signature and tests to support the changes to the static_bloom_filter and bloom_filter interfaces.
* Refactoring the insert and contains implementation to a common internals base.
* All static_bloom_filters are now fully equally comparable since the types will contain the hash functions in the signature too.
* The default hash implementation has been changed to use Boost.Hash internally.
Added:
sandbox/bloom_filter/trunk/boost/bloom_filter/detail/internals.hpp (contents, props changed)
Text files modified:
sandbox/bloom_filter/trunk/boost/bloom_filter/bloom_filter.hpp | 50 ++++++++++---------------
sandbox/bloom_filter/trunk/boost/bloom_filter/detail/default_hash.hpp | 12 ++----
sandbox/bloom_filter/trunk/boost/bloom_filter/static_bloom_filter.hpp | 77 +++++++++++++++++++++++++--------------
sandbox/bloom_filter/trunk/libs/bloom_filter/test/bloom_filter_construct_runtime_size_test.cpp | 13 +-----
sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_construct_from_bitset_test.cpp | 4 +-
sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_default_construct_test.cpp | 4 -
sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_equality_test.cpp | 2
sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_swap_adl_test.cpp | 2
sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_test.cpp | 40 +++++++++++---------
9 files changed, 104 insertions(+), 100 deletions(-)
Modified: sandbox/bloom_filter/trunk/boost/bloom_filter/bloom_filter.hpp
==============================================================================
--- sandbox/bloom_filter/trunk/boost/bloom_filter/bloom_filter.hpp (original)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/bloom_filter.hpp 2009-06-10 04:03:38 EDT (Wed, 10 Jun 2009)
@@ -12,11 +12,23 @@
#include <boost/fusion/algorithm/iteration/for_each.hpp>
#include <boost/fusion/include/for_each.hpp>
+#include <boost/fusion/container/vector.hpp>
+#include <boost/fusion/include/vector.hpp>
+#include <boost/bloom_filter/detail/internals.hpp>
namespace boost {
- template <class Input, class Sequence, class Block = unsigned char, class Allocator = std::allocator<unsigned char> >
- struct bloom_filter {
+ template <
+ class Input,
+ class Sequence = fusion::vector<
+ detail::default_hash<0>,
+ detail::default_hash<1>,
+ detail::default_hash<2>
+ >,
+ class Block = unsigned char,
+ class Allocator = std::allocator<unsigned char>
+ >
+ struct bloom_filter : protected detail::bloom_filter_internals<Input, dynamic_bitset<Block,Allocator> > {
public:
typedef dynamic_bitset<Block, Allocator> bitset_type;
@@ -25,31 +37,7 @@
Sequence hash_functions;
typedef typename add_reference<typename add_const<Input>::type>::type const_ref;
-
- struct insert_impl {
- bitset_type & bit_set_;
- const_ref input_;
- insert_impl(bitset_type & bit_set, const_ref input)
- : bit_set_(bit_set), input_(input)
- {}
- template <class F>
- void operator()(F const & f) const {
- bit_set_[f(input_) % bit_set_.size()] = true;
- }
- };
-
- struct contains_impl {
- bitset_type const & bit_set_;
- const_ref input_;
- bool & result_;
- contains_impl(bitset_type const & bit_set, const_ref input, bool & result)
- : bit_set_(bit_set), input_(input), result_(result)
- {}
- template <class F>
- void operator()(F const & f) const {
- result_ = result_ && bit_set_[f(input_) % bit_set_.size()];
- }
- };
+ typedef detail::bloom_filter_internals<Input, dynamic_bitset<Block,Allocator> > base;
public:
bloom_filter(
@@ -60,17 +48,21 @@
void insert(const_ref input) {
using fusion::for_each;
+ typedef typename base::insert_impl inserter;
for_each(
hash_functions,
- insert_impl(bit_set, input));
+ inserter(bit_set, input)
+ );
}
bool contains(const_ref input) const {
using fusion::for_each;
+ typedef typename base::contains_impl contains_checker;
bool found = true;
for_each(
hash_functions,
- contains_impl(bit_set, input, found));
+ contains_checker(bit_set, input, found)
+ );
return found;
}
};
Modified: sandbox/bloom_filter/trunk/boost/bloom_filter/detail/default_hash.hpp
==============================================================================
--- sandbox/bloom_filter/trunk/boost/bloom_filter/detail/default_hash.hpp (original)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/detail/default_hash.hpp 2009-06-10 04:03:38 EDT (Wed, 10 Jun 2009)
@@ -10,15 +10,11 @@
namespace detail {
- template <class Input>
+ template <size_t Seed = 0>
struct default_hash {
- typedef typename add_reference<typename add_const<Input>::type>::type const_ref;
- size_t seed_;
- default_hash(size_t seed)
- : seed_(seed) {}
-
- size_t operator()(const_ref input) const {
- size_t seed = seed_;
+ template <class T>
+ size_t operator() (T const & input) const {
+ size_t seed = Seed;
hash_combine(seed, input);
return seed;
}
Added: sandbox/bloom_filter/trunk/boost/bloom_filter/detail/internals.hpp
==============================================================================
--- (empty file)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/detail/internals.hpp 2009-06-10 04:03:38 EDT (Wed, 10 Jun 2009)
@@ -0,0 +1,50 @@
+#ifndef BLOOM_FILTER_INTERNALS_20090610_0
+#define BLOOM_FILTER_INTERNALS_20090610_0
+
+// Copyright 2009 (c) Dean Michael Berris <mikhailberis_at_[hidden]>
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+namespace boost {
+
+ namespace detail {
+
+ template <class Input, class BitSet>
+ class bloom_filter_internals {
+ protected:
+ typedef BitSet bitset_type;
+ typedef typename add_reference<typename add_const<Input>::type>::type const_ref;
+
+ struct insert_impl {
+ bitset_type & bit_set_;
+ const_ref input_;
+ insert_impl(bitset_type & bit_set, const_ref input)
+ : bit_set_(bit_set), input_(input)
+ {}
+ template <class F>
+ void operator()(F const & f) const {
+ bit_set_[f(input_) % bit_set_.size()] = true;
+ }
+ };
+
+ struct contains_impl {
+ bitset_type const & bit_set_;
+ const_ref input_;
+ bool & result_;
+ contains_impl(bitset_type const & bit_set, const_ref input, bool & result)
+ : bit_set_(bit_set), input_(input), result_(result)
+ {}
+ template <class F>
+ void operator()(F const & f) const {
+ result_ = result_ && bit_set_[f(input_) % bit_set_.size()];
+ }
+ };
+
+ };
+
+ } // namespace detail
+
+} // namespace boost
+
+#endif
Modified: sandbox/bloom_filter/trunk/boost/bloom_filter/static_bloom_filter.hpp
==============================================================================
--- sandbox/bloom_filter/trunk/boost/bloom_filter/static_bloom_filter.hpp (original)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/static_bloom_filter.hpp 2009-06-10 04:03:38 EDT (Wed, 10 Jun 2009)
@@ -12,40 +12,57 @@
#include <boost/type_traits/add_const.hpp>
#include <boost/type_traits/add_reference.hpp>
+#include <boost/fusion/container/vector.hpp>
+#include <boost/fusion/include/vector.hpp>
+#include <boost/fusion/algorithm/iteration/for_each.hpp>
+#include <boost/fusion/include/for_each.hpp>
#include <boost/bloom_filter/detail/default_hash.hpp>
+#include <boost/bloom_filter/detail/internals.hpp>
namespace boost {
- template <class Input, size_t M, size_t K>
- struct static_bloom_filter {
+ template <
+ class Input,
+ size_t M,
+ class Sequence = fusion::vector<
+ detail::default_hash<0>,
+ detail::default_hash<1>,
+ detail::default_hash<2>
+ >
+ >
+ struct static_bloom_filter : protected detail::bloom_filter_internals<Input, std::bitset<M> > {
public:
typedef std::bitset<M> bitset_type;
private:
bitset_type bit_set;
- array<function<size_t(Input)>, K> hash_array;
+ Sequence hash_functions;
typedef typename add_reference<typename add_const<Input>::type>::type const_ref;
+ typedef detail::bloom_filter_internals<Input, std::bitset<M> > base;
+
+ struct insert_impl {
+ bitset_type & bit_set_;
+ };
public:
static size_t const size = M;
- static size_t const functions = K;
typedef Input element_type;
+ static_bloom_filter(
+ bitset_type const & initial_state = bitset_type(),
+ Sequence const & hash_functions = Sequence())
+ : bit_set(initial_state), hash_functions(hash_functions)
+ {}
+
explicit static_bloom_filter(
- array<function<size_t(Input)>, K> const & hash_functions
- ) :
- hash_array(hash_functions) {}
-
- static_bloom_filter(bitset_type const & initial_state = bitset_type())
- : bit_set(initial_state)
- {
- for(size_t k = 0; k < K; ++k)
- hash_array[k] = detail::default_hash<Input>(k);
- }
+ Sequence const & hash_functions
+ )
+ : bit_set(), hash_functions(hash_functions)
+ {}
static_bloom_filter(static_bloom_filter const & other) :
- bit_set(other.bit_set), hash_array(other.hash_array) {}
+ bit_set(other.bit_set), hash_functions(other.hash_functions) {}
static_bloom_filter & operator=(static_bloom_filter rhs) {
rhs.swap(*this);
@@ -55,20 +72,28 @@
static_bloom_filter & swap(static_bloom_filter & other) {
using std::swap;
swap(bit_set, other.bit_set);
- swap(hash_array, other.hash_array);
+ swap(hash_functions, other.hash_functions);
return *this;
}
void insert(const_ref input) {
- for(size_t k = 0; k < K; ++k)
- bit_set[hash_array[k](input) % M] = 1;
+ using fusion::for_each;
+ typedef typename base::insert_impl inserter;
+ for_each(
+ hash_functions,
+ inserter(bit_set, input)
+ );
}
bool contains(const_ref input) const {
- bool result = true;
- for(size_t k = 0; k < K && result; ++k)
- result = result && bit_set[hash_array[k](input) % M];
- return result;
+ using fusion::for_each;
+ typedef typename base::contains_impl contains_checker;
+ bool found = true;
+ for_each(
+ hash_functions,
+ contains_checker(bit_set, input, found)
+ );
+ return found;
}
bool operator[](const_ref input) const {
@@ -85,8 +110,6 @@
}
bool operator== (static_bloom_filter const & other) const {
- // FIXME For some reason, we cannot compare boost::function instances...
- // return (hash_array == other.hash_array) && (bit_set == other.bit_set);
return bit_set == other.bit_set;
}
@@ -95,10 +118,10 @@
}
};
- template <class Input, size_t M, size_t K>
+ template <class Input, size_t M, class Sequence>
inline void swap(
- static_bloom_filter<Input, M, K> & left,
- static_bloom_filter<Input, M, K> & right) {
+ static_bloom_filter<Input, M, Sequence> & left,
+ static_bloom_filter<Input, M, Sequence> & right) {
left.swap(right);
}
}
Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/test/bloom_filter_construct_runtime_size_test.cpp
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/test/bloom_filter_construct_runtime_size_test.cpp (original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/test/bloom_filter_construct_runtime_size_test.cpp 2009-06-10 04:03:38 EDT (Wed, 10 Jun 2009)
@@ -12,20 +12,11 @@
using boost::fusion::tuple;
using boost::hash_combine;
-template <size_t Offset>
-struct hash {
- template <class T>
- size_t operator() (T const & element) const {
- size_t seed = Offset;
- hash_combine(seed, element);
- return seed;
- }
-};
-
int main(int argc, char * argv[]) {
- bloom_filter<int, tuple<hash<1>, hash<2>, hash<3> > > bf(2048);
+ bloom_filter<int> bf(2048);
bf.insert(1);
assert(bf.contains(1));
+ assert(!bf.contains(2));
return EXIT_SUCCESS;
}
Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_construct_from_bitset_test.cpp
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_construct_from_bitset_test.cpp (original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_construct_from_bitset_test.cpp 2009-06-10 04:03:38 EDT (Wed, 10 Jun 2009)
@@ -9,9 +9,9 @@
using boost::static_bloom_filter;
int main(int argc, char * argv[]) {
- static_bloom_filter<int, 32, 3> filter1;
+ static_bloom_filter<int, 32> filter1;
filter1.insert(1);
- static_bloom_filter<int, 32, 3> filter2(filter1.state()); // construct from bitset
+ static_bloom_filter<int, 32> filter2(filter1.state()); // construct from bitset
assert(filter2.contains(1));
return EXIT_SUCCESS;
}
Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_default_construct_test.cpp
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_default_construct_test.cpp (original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_default_construct_test.cpp 2009-06-10 04:03:38 EDT (Wed, 10 Jun 2009)
@@ -6,12 +6,10 @@
#include <boost/bloom_filter/static_bloom_filter.hpp>
#include <boost/detail/lightweight_test.hpp>
-#define FILTER_SIZE 256
-
using boost::static_bloom_filter;
int main(int argc, char * argv[]) {
- typedef static_bloom_filter<uint32_t, FILTER_SIZE, 3> filter_type;
+ typedef static_bloom_filter<uint32_t, 256> filter_type;
filter_type filter; // default constructed
filter.insert(1u);
assert(filter.contains(1u));
Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_equality_test.cpp
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_equality_test.cpp (original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_equality_test.cpp 2009-06-10 04:03:38 EDT (Wed, 10 Jun 2009)
@@ -9,7 +9,7 @@
using boost::static_bloom_filter;
int main(int argc, char * arg[]) {
- static_bloom_filter<int, 32, 3> filter1, filter2;
+ static_bloom_filter<int, 32> filter1, filter2;
assert(filter1 == filter2);
filter1.insert(1);
assert(filter1 != filter2);
Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_swap_adl_test.cpp
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_swap_adl_test.cpp (original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_swap_adl_test.cpp 2009-06-10 04:03:38 EDT (Wed, 10 Jun 2009)
@@ -9,7 +9,7 @@
using boost::static_bloom_filter;
int main(int argc, char * argv[]) {
- typedef static_bloom_filter<uint32_t, 32, 3> filter_type;
+ typedef static_bloom_filter<uint32_t, 32> filter_type;
filter_type filter1, filter2;
filter1.insert(1u);
filter2.insert(2u);
Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_test.cpp
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_test.cpp (original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/test/static_bloom_filter_test.cpp 2009-06-10 04:03:38 EDT (Wed, 10 Jun 2009)
@@ -5,35 +5,39 @@
#include <boost/bloom_filter.hpp>
#include <boost/detail/lightweight_test.hpp>
+#include <boost/fusion/tuple.hpp>
#define FILTER_SIZE 256
-size_t hash1(uint32_t id) {
- return ((id << 4) | (id >> 4)) % FILTER_SIZE;
-}
-
-size_t hash2(uint32_t id) {
- return (id * id) % FILTER_SIZE;
-}
-
-size_t hash3(uint32_t id) {
- return (id * 97) % FILTER_SIZE;
-}
+struct hash1 {
+ size_t operator()(uint32_t id) const {
+ return ((id << 4) | (id >> 4)) % FILTER_SIZE;
+ }
+};
+
+struct hash2 {
+ size_t operator()(uint32_t id) const {
+ return (id * id) % FILTER_SIZE;
+ }
+};
+
+struct hash3 {
+ size_t operator()(uint32_t id) const {
+ return (id * 97) % FILTER_SIZE;
+ }
+};
using std::bitset;
using std::cout;
using std::endl;
-using boost::array;
using boost::function;
using boost::static_bloom_filter;
+using boost::fusion::tuple;
+using boost::fusion::make_tuple;
int main(int argc, char * argv[]) {
- array<function<size_t(uint32_t)>, 3> functions;
- functions[0] = hash1;
- functions[1] = hash2;
- functions[2] = hash3;
- typedef static_bloom_filter<uint32_t, FILTER_SIZE, 3> filter_type;
- filter_type filter(functions);
+ typedef static_bloom_filter<uint32_t, FILTER_SIZE, tuple<hash1, hash2, hash3> > filter_type;
+ filter_type filter(make_tuple(hash1(), hash2(), hash3()));
filter_type filter_copy = filter;
for(uint32_t i = 0; i < 10; ++i) filter.insert(i);
for(uint32_t i = 0; i < 10; ++i) assert(filter.contains(i));