[Boost-commit] svn:boost r53782 - in sandbox/bloom_filter/trunk: boost boost/bloom_filter libs/bloom_filter/test

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;
+}
+