Boost logo

Boost-Commit :

Subject: [Boost-commit] svn:boost r73562 - in sandbox/bloom_filter/trunk/boost/bloom_filter: . detail
From: cpp.cabrera_at_[hidden]
Date: 2011-08-05 23:07:21


Author: alejandro
Date: 2011-08-05 23:07:20 EDT (Fri, 05 Aug 2011)
New Revision: 73562
URL: http://svn.boost.org/trac/boost/changeset/73562

Log:
New data structure:

   - Implemented dynamic_counting_bloom_filter from
     counting_bloom_filter sources.
   - Modified counting_apply_hash to handle num_bins parameter
     for dynamic variant.
Text files modified:
   sandbox/bloom_filter/trunk/boost/bloom_filter/counting_bloom_filter.hpp | 14 ++++++--
   sandbox/bloom_filter/trunk/boost/bloom_filter/detail/counting_apply_hash.hpp | 47 ++++++++++++++++++-------------
   sandbox/bloom_filter/trunk/boost/bloom_filter/dynamic_counting_bloom_filter.hpp | 60 +++++++++++++++++++++++----------------
   3 files changed, 72 insertions(+), 49 deletions(-)

Modified: sandbox/bloom_filter/trunk/boost/bloom_filter/counting_bloom_filter.hpp
==============================================================================
--- sandbox/bloom_filter/trunk/boost/bloom_filter/counting_bloom_filter.hpp (original)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/counting_bloom_filter.hpp 2011-08-05 23:07:20 EDT (Fri, 05 Aug 2011)
@@ -181,7 +181,9 @@
       void insert(const T& t)
       {
         static const unsigned N = boost::mpl::size<hash_function_type>::value - 1;
- detail::counting_apply_hash<N, this_type>::insert(t, this->bits);
+ detail::counting_apply_hash<N, this_type>::insert(t,
+ this->bits,
+ this->num_bins());
       }
 
       template <typename InputIterator>
@@ -195,7 +197,9 @@
       void remove(const T& t)
       {
         static const unsigned N = boost::mpl::size<hash_function_type>::value - 1;
- detail::counting_apply_hash<N, this_type>::remove(t, this->bits);
+ detail::counting_apply_hash<N, this_type>::remove(t,
+ this->bits,
+ this->num_bins());
       }
 
       template <typename InputIterator>
@@ -209,8 +213,10 @@
       bool probably_contains(const T& t) const
       {
         static const unsigned N = mpl::size<HashFunctions>::value - 1;
- return detail::counting_apply_hash<N, this_type>::contains(t,
- this->bits);
+ return detail::counting_apply_hash<N,
+ this_type>::contains(t,
+ this->bits,
+ this->num_bins());
       }
 
       //! auxiliary ops

Modified: sandbox/bloom_filter/trunk/boost/bloom_filter/detail/counting_apply_hash.hpp
==============================================================================
--- sandbox/bloom_filter/trunk/boost/bloom_filter/detail/counting_apply_hash.hpp (original)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/detail/counting_apply_hash.hpp 2011-08-05 23:07:20 EDT (Fri, 05 Aug 2011)
@@ -44,17 +44,18 @@
         typedef typename boost::mpl::at_c<typename CBF::hash_function_type,
                                           N>::type Hash;
 
+ public:
         BloomOp(const typename CBF::value_type& t,
- const typename CBF::bucket_type& slots)
+ const typename CBF::bucket_type& slots,
+ const size_t num_bins)
           :
- hash_val(hasher(t) % CBF::num_bins()),
+ hash_val(hasher(t) % num_bins),
           pos(hash_val / CBF::bins_per_slot()),
           offset_bits((hash_val % CBF::bins_per_slot()) * CBF::bits_per_bin()),
           target_bits((slots[pos] >> offset_bits) & CBF::mask())
         {}
 
- void update(const typename CBF::value_type& t,
- typename CBF::bucket_type& slots,
+ void update(typename CBF::bucket_type& slots,
                     const size_t limit) const {
           static Op op;
 
@@ -80,27 +81,30 @@
       struct counting_apply_hash
       {
         static void insert(const typename CBF::value_type& t,
- typename CBF::bucket_type& slots)
+ typename CBF::bucket_type& slots,
+ const size_t num_bins)
         {
- BloomOp<N, CBF, increment> inserter(t, slots);
- inserter.update(t, slots, (1ull << CBF::bits_per_bin()) - 1ull);
+ BloomOp<N, CBF, increment> inserter(t, slots, num_bins);
+ inserter.update(slots, (1ull << CBF::bits_per_bin()) - 1ull);
 
           counting_apply_hash<N-1, CBF>::insert(t, slots);
         }
 
         static void remove(const typename CBF::value_type& t,
- typename CBF::bucket_type& slots)
+ typename CBF::bucket_type& slots,
+ const size_t num_bins)
         {
- BloomOp<N, CBF, decrement> remover(t, slots);
- remover.update(t, slots, 0);
+ BloomOp<N, CBF, decrement> remover(t, slots, num_bins);
+ remover.update(slots, 0);
 
           counting_apply_hash<N-1, CBF>::remove(t, slots);
         }
 
         static bool contains(const typename CBF::value_type& t,
- const typename CBF::bucket_type& slots)
+ const typename CBF::bucket_type& slots,
+ const size_t num_bins)
         {
- BloomOp<N, CBF> checker(t, slots);
+ BloomOp<N, CBF> checker(t, slots, num_bins);
           return (checker.check() &&
                   counting_apply_hash<N-1, CBF>::contains(t, slots));
         }
@@ -110,23 +114,26 @@
       struct counting_apply_hash<0, CBF>
       {
         static void insert(const typename CBF::value_type& t,
- typename CBF::bucket_type& slots)
+ typename CBF::bucket_type& slots,
+ const size_t num_bins)
         {
- BloomOp<0, CBF, increment> inserter(t, slots);
- inserter.update(t, slots, (1ull << CBF::bits_per_bin()) - 1ull);
+ BloomOp<0, CBF, increment> inserter(t, slots, num_bins);
+ inserter.update(slots, (1ull << CBF::bits_per_bin()) - 1ull);
         }
 
         static void remove(const typename CBF::value_type& t,
- typename CBF::bucket_type& slots)
+ typename CBF::bucket_type& slots,
+ const size_t num_bins)
         {
- BloomOp<0, CBF, decrement> remover(t, slots);
- remover.update(t, slots, 0);
+ BloomOp<0, CBF, decrement> remover(t, slots, num_bins);
+ remover.update(slots, 0);
         }
 
         static bool contains(const typename CBF::value_type& t,
- const typename CBF::bucket_type& slots)
+ const typename CBF::bucket_type& slots,
+ const size_t num_bins)
         {
- BloomOp<0, CBF> checker(t, slots);
+ BloomOp<0, CBF> checker(t, slots, num_bins);
           return (checker.check());
         }
       };

Modified: sandbox/bloom_filter/trunk/boost/bloom_filter/dynamic_counting_bloom_filter.hpp
==============================================================================
--- sandbox/bloom_filter/trunk/boost/bloom_filter/dynamic_counting_bloom_filter.hpp (original)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/dynamic_counting_bloom_filter.hpp 2011-08-05 23:07:20 EDT (Fri, 05 Aug 2011)
@@ -74,36 +74,35 @@
       typedef typename bucket_type::iterator bucket_iterator;
       typedef typename bucket_type::const_iterator bucket_const_iterator;
 
- static const slot_bits = sizeof(block_type) * 8;
- static const size_t default_num_bins = 10000;
+ static const size_t slot_bits = sizeof(block_type) * 8;
+ static const size_t default_num_bins = 32;
 
     private:
- size_t bucket_size(const size_t num_bins) const {
- const size_t bin_bits = num_bins * this->bits_per_bin();
+ size_t bucket_size(const size_t requested_bins) const {
+ const size_t bin_bits = requested_bins * BitsPerBin;
         return bin_bits / slot_bits + 1;
       }
 
     public:
       //! constructors
       dynamic_counting_bloom_filter()
- : bits(bucket_size(default_num_bins))
+ : bits(bucket_size(default_num_bins)),
+ _num_bins(default_num_bins)
       {
- this->clear();
       }
 
- explicit dynamic_counting_bloom_filter(const size_t num_bins)
- : bits(bucket_size(num_bins))
+ explicit dynamic_counting_bloom_filter(const size_t requested_bins)
+ : bits(bucket_size(requested_bins)),
+ _num_bins(requested_bins)
       {
- this->clear();
       }
 
       template <typename InputIterator>
       dynamic_counting_bloom_filter(const InputIterator start,
                                     const InputIterator end)
- : bits(bucket_size(std::distance(start, end) * 4))
+ : bits(bucket_size(std::distance(start, end) * 4)),
+ _num_bins(std::distance(start, end) * 4)
       {
- this->clear();
-
         for (InputIterator i = start; i != end; ++i)
           this->insert(*i);
       }
@@ -111,7 +110,7 @@
       //! meta functions
       size_t num_bins() const
       {
- return NumBins;
+ return this->_num_bins;
       }
 
       static BOOST_CONSTEXPR size_t bits_per_bin()
@@ -143,7 +142,7 @@
       {
         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>(NumBins);
+ static const double m = static_cast<double>(this->num_bins());
         static const double e =
           2.718281828459045235360287471352662497757247093699959574966;
         return std::pow(1 - std::pow(e, -k * n / m), k);
@@ -178,7 +177,10 @@
       void insert(const T& t)
       {
         static const unsigned N = boost::mpl::size<hash_function_type>::value - 1;
- detail::counting_apply_hash<N, this_type>::insert(t, this->bits);
+ detail::counting_apply_hash<N,
+ this_type>::insert(t,
+ this->bits,
+ this->num_bins());
       }
 
       template <typename InputIterator>
@@ -192,7 +194,10 @@
       void remove(const T& t)
       {
         static const unsigned N = boost::mpl::size<hash_function_type>::value - 1;
- detail::counting_apply_hash<N, this_type>::remove(t, this->bits);
+ detail::counting_apply_hash<N,
+ this_type>::remove(t,
+ this->bits,
+ this->num_bins());
       }
 
       template <typename InputIterator>
@@ -206,26 +211,30 @@
       bool probably_contains(const T& t) const
       {
         static const unsigned N = mpl::size<HashFunctions>::value - 1;
- return detail::counting_apply_hash<N, this_type>::contains(t,
- this->bits);
+ return detail::counting_apply_hash<N,
+ this_type>::contains(t,
+ this->bits,
+ this->num_bins());
       }
 
       //! auxiliary ops
       void clear()
       {
- this->bits.clear();
+ for (bucket_iterator i = bits.begin(), end = bits.end();
+ i != end; ++i)
+ *i = 0;
       }
 
- void swap(counting_bloom_filter& other)
+ void swap(dynamic_counting_bloom_filter& other)
       {
- counting_bloom_filter tmp = other;
+ dynamic_counting_bloom_filter tmp = other;
         other = *this;
         *this = tmp;
       }
 
       //! pairwise ops
- counting_bloom_filter&
- experimental_union_assign(const counting_bloom_filter& rhs)
+ dynamic_counting_bloom_filter&
+ experimental_union_assign(const dynamic_counting_bloom_filter& rhs)
       {
         if (this->bit_capacity() != rhs.bit_capacity())
           throw detail::incompatible_size_exception();
@@ -241,8 +250,8 @@
         return *this;
       }
 
- counting_bloom_filter&
- experimental_intersect_assign(const counting_bloom_filter& rhs)
+ dynamic_counting_bloom_filter&
+ experimental_intersect_assign(const dynamic_counting_bloom_filter& rhs)
       {
         if (this->bit_capacity() != rhs.bit_capacity())
           throw detail::incompatible_size_exception();
@@ -282,6 +291,7 @@
 
     private:
       bucket_type bits;
+ size_t _num_bins;
     };
 
     // union


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk