Subject: [Boost-commit] svn:boost r53769 - in sandbox/bloom_filter/trunk: boost/bloom_filter boost/bloom_filter/detail libs/bloom_filter/test
From: mikhailberis_at_[hidden]
Date: 2009-06-09 03:33:24
Author: mikhailberis
Date: 2009-06-09 03:33:22 EDT (Tue, 09 Jun 2009)
New Revision: 53769
URL: http://svn.boost.org/trac/boost/changeset/53769
Log:
Changes:
* Adding default constructed filter test.
* Adding default hash function implementation.
* Adding bloom_filter convenience include header.
* Simplifying test for bloom filter implementation.
Added:
sandbox/bloom_filter/trunk/boost/bloom_filter/detail/
sandbox/bloom_filter/trunk/boost/bloom_filter/detail/default_hash.hpp (contents, props changed)
sandbox/bloom_filter/trunk/libs/bloom_filter/test/default_constructed_filter_test.cpp (contents, props changed)
Text files modified:
sandbox/bloom_filter/trunk/boost/bloom_filter/bloom_filter.hpp | 9 ++++++++-
sandbox/bloom_filter/trunk/libs/bloom_filter/test/Jamfile.v2 | 4 +++-
sandbox/bloom_filter/trunk/libs/bloom_filter/test/bloom_filter_test.cpp | 5 -----
3 files changed, 11 insertions(+), 7 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-09 03:33:22 EDT (Tue, 09 Jun 2009)
@@ -12,6 +12,7 @@
#include <boost/type_traits/add_const.hpp>
#include <boost/type_traits/add_reference.hpp>
+#include <boost/bloom_filter/detail/default_hash.hpp>
namespace boost {
@@ -21,18 +22,24 @@
std::bitset<M> bit_set;
array<function<size_t(Input)>, K> hash_array;
- typedef typename add_const<typename add_reference<Input>::type>::type const_ref;
+ typedef typename add_reference<typename add_const<Input>::type>::type const_ref;
public:
typedef std::bitset<M> bitset_type;
static size_t const size = M;
static size_t const functions = K;
+ typedef Input element_type;
explicit bloom_filter(
array<function<size_t(Input)>, K> const & hash_functions
) :
hash_array(hash_functions) {}
+ bloom_filter() {
+ for(size_t k = 0; k < K; ++k)
+ hash_array[k] = detail::default_hash<Input,M>(k);
+ }
+
bloom_filter(bloom_filter const & other) :
bit_set(other.bit_set), hash_array(other.hash_array) {}
Added: sandbox/bloom_filter/trunk/boost/bloom_filter/detail/default_hash.hpp
==============================================================================
--- (empty file)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/detail/default_hash.hpp 2009-06-09 03:33:22 EDT (Tue, 09 Jun 2009)
@@ -0,0 +1,39 @@
+#ifndef BOOST_BLOOM_FILTER_DETAIL_DEFAULT_HASH_20090609_0
+#define BOOST_BLOOM_FILTER_DETAIL_DEFAULT_HASH_20090609_0
+
+#include <string>
+#include <boost/crc.hpp>
+#include <boost/type_traits/add_const.hpp>
+#include <boost/type_traits/add_reference.hpp>
+
+namespace boost {
+
+ namespace detail {
+
+ template <class Input, size_t M>
+ struct default_hash {
+ typedef typename add_reference<typename add_const<Input>::type>::type const_ref;
+
+ size_t offset_;
+ explicit default_hash(size_t offset)
+ : offset_(offset) {}
+
+ size_t operator()(std::string const & input) const {
+ crc_32_type crc32_computer;
+ crc32_computer.process_bytes(input.c_str(), input.size());
+ return (crc32_computer.checksum() + offset_) % M;
+ }
+
+ size_t operator()(const_ref input) const {
+ crc_32_type crc32_computer;
+ crc32_computer.process_bytes(&input, sizeof(input));
+ return (crc32_computer.checksum() + offset_) % M;
+ }
+ };
+
+ } // namespace detail
+
+} // namespace boost
+
+#endif
+
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-09 03:33:22 EDT (Tue, 09 Jun 2009)
@@ -3,7 +3,9 @@
{
test-suite "bloom_filter"
- : [ run bloom_filter_test.cpp ]
+ :
+ [ run bloom_filter_test.cpp ]
+ [ run default_constructed_filter_test.cpp ]
;
}
Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/test/bloom_filter_test.cpp
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/test/bloom_filter_test.cpp (original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/test/bloom_filter_test.cpp 2009-06-09 03:33:22 EDT (Tue, 09 Jun 2009)
@@ -3,9 +3,6 @@
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-#include <bitset>
-#include <cassert>
-#include <iostream>
#include <boost/bloom_filter.hpp>
#include <boost/detail/lightweight_test.hpp>
@@ -41,8 +38,6 @@
for(uint32_t i = 0; i < 10; ++i) filter.insert(i);
for(uint32_t i = 0; i < 10; ++i) assert(filter.contains(i));
filter_type::bitset_type bit_set = filter.state();
- for(uint32_t i = 0; i < filter_type::size ; ++i)
- cout << (bit_set[i] ? '1' : '0');
cout << endl;
// assignment test
filter_copy = filter;
Added: sandbox/bloom_filter/trunk/libs/bloom_filter/test/default_constructed_filter_test.cpp
==============================================================================
--- (empty file)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/test/default_constructed_filter_test.cpp 2009-06-09 03:33:22 EDT (Tue, 09 Jun 2009)
@@ -0,0 +1,20 @@
+// 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/bloom_filter.hpp>
+#include <boost/detail/lightweight_test.hpp>
+
+#define FILTER_SIZE 256
+
+using boost::bloom_filter;
+
+int main(int argc, char * argv[]) {
+ typedef bloom_filter<uint32_t, FILTER_SIZE, 3> filter_type;
+ filter_type filter; // default constructed
+ filter.insert(1u);
+ assert(filter.contains(1u));
+ return EXIT_SUCCESS;
+}
+