Subject: [Boost-commit] svn:boost r53782 - in sandbox/bloom_filter/trunk: boost boost/bloom_filter libs/bloom_filter/test
From: mikhailberis_at_[hidden]
Date: 2009-06-10 02:14:32
Author: mikhailberis
Date: 2009-06-10 02:14:31 EDT (Wed, 10 Jun 2009)
New Revision: 53782
URL: http://svn.boost.org/trac/boost/changeset/53782
Log:
Adding initial implementation of a runtime-sized bloom filter.
Added:
sandbox/bloom_filter/trunk/boost/bloom_filter/bloom_filter.hpp (contents, props changed)
sandbox/bloom_filter/trunk/libs/bloom_filter/test/bloom_filter_construct_runtime_size_test.cpp (contents, props changed)
Text files modified:
sandbox/bloom_filter/trunk/boost/bloom_filter.hpp | 1 +
sandbox/bloom_filter/trunk/boost/bloom_filter/static_bloom_filter.hpp | 4 ++--
sandbox/bloom_filter/trunk/libs/bloom_filter/test/Jamfile.v2 | 1 +
3 files changed, 4 insertions(+), 2 deletions(-)
Modified: sandbox/bloom_filter/trunk/boost/bloom_filter.hpp
==============================================================================
--- sandbox/bloom_filter/trunk/boost/bloom_filter.hpp (original)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter.hpp 2009-06-10 02:14:31 EDT (Wed, 10 Jun 2009)
@@ -7,6 +7,7 @@
// http://www.boost.org/LICENSE_1_0.txt)
#include <boost/bloom_filter/static_bloom_filter.hpp>
+#include <boost/bloom_filter/bloom_filter.hpp>
#endif
Added: sandbox/bloom_filter/trunk/boost/bloom_filter/bloom_filter.hpp
==============================================================================
--- (empty file)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/bloom_filter.hpp 2009-06-10 02:14:31 EDT (Wed, 10 Jun 2009)
@@ -0,0 +1,81 @@
+#ifndef BLOOM_FILTER_20090610_0
+#define BLOOM_FILTER_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)
+
+#include <boost/dynamic_bitset.hpp>
+#include <boost/type_traits/add_reference.hpp>
+#include <boost/type_traits/add_const.hpp>
+
+#include <boost/fusion/algorithm/iteration/for_each.hpp>
+#include <boost/fusion/include/for_each.hpp>
+
+namespace boost {
+
+ template <class Input, class Sequence, class Block = unsigned char, class Allocator = std::allocator<unsigned char> >
+ struct bloom_filter {
+ public:
+ typedef dynamic_bitset<Block, Allocator> bitset_type;
+
+ private:
+ bitset_type bit_set;
+ 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()];
+ }
+ };
+
+ public:
+ bloom_filter(
+ size_t size,
+ Sequence const & functions = Sequence())
+ : bit_set(size, 0), hash_functions(functions)
+ { }
+
+ void insert(const_ref input) {
+ using fusion::for_each;
+ for_each(
+ hash_functions,
+ insert_impl(bit_set, input));
+ }
+
+ bool contains(const_ref input) const {
+ using fusion::for_each;
+ bool found = true;
+ for_each(
+ hash_functions,
+ contains_impl(bit_set, input, found));
+ return found;
+ }
+ };
+
+} // 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 02:14:31 EDT (Wed, 10 Jun 2009)
@@ -1,5 +1,5 @@
-#ifndef BLOOM_FILTER_20090608_0
-#define BLOOM_FILTER_20090608_0
+#ifndef STATIC_BLOOM_FILTER_20090608_0
+#define STATIC_BLOOM_FILTER_20090608_0
// Copyright 2009 (c) Dean Michael Berris <mikhailberis_at_[hidden]>
// Distributed under the Boost Software License, Version 1.0.
Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/test/Jamfile.v2
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/test/Jamfile.v2 (original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/test/Jamfile.v2 2009-06-10 02:14:31 EDT (Wed, 10 Jun 2009)
@@ -9,6 +9,7 @@
[ run static_bloom_filter_swap_adl_test.cpp ]
[ run static_bloom_filter_equality_test.cpp ]
[ run static_bloom_filter_construct_from_bitset_test.cpp ]
+ [ run bloom_filter_construct_runtime_size_test.cpp ]
;
}
Added: sandbox/bloom_filter/trunk/libs/bloom_filter/test/bloom_filter_construct_runtime_size_test.cpp
==============================================================================
--- (empty file)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/test/bloom_filter_construct_runtime_size_test.cpp 2009-06-10 02:14:31 EDT (Wed, 10 Jun 2009)
@@ -0,0 +1,31 @@
+// 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)
+
+#include <boost/bloom_filter.hpp>
+#include <boost/detail/lightweight_test.hpp>
+#include <boost/fusion/tuple.hpp>
+#include <boost/functional/hash.hpp>
+
+using boost::bloom_filter;
+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);
+ bf.insert(1);
+ assert(bf.contains(1));
+ return EXIT_SUCCESS;
+}
+