[Boost-commit] svn:boost r73483 - in sandbox/bloom_filter/trunk/boost/bloom_filter: . detail

Subject: [Boost-commit] svn:boost r73483 - in sandbox/bloom_filter/trunk/boost/bloom_filter: . detail
From: cpp.cabrera_at_[hidden]
Date: 2011-08-02 05:32:38

Author: alejandro
Date: 2011-08-02 05:32:36 EDT (Tue, 02 Aug 2011)
New Revision: 73483
URL: http://svn.boost.org/trac/boost/changeset/73483

Log:
Added commentary to counting_bloom. Tinkering with counting_apply_hash.
Text files modified: 
   sandbox/bloom_filter/trunk/boost/bloom_filter/counting_bloom_filter.hpp      |     4 +                                       
   sandbox/bloom_filter/trunk/boost/bloom_filter/detail/counting_apply_hash.hpp |   106 +++++++++++++-------------------------- 
   2 files changed, 38 insertions(+), 72 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-02 05:32:36 EDT (Tue, 02 Aug 2011)
@@ -59,7 +59,9 @@
       // can have internal fragmentation if the calculation for 
       // bins_per_slot has a remainder. The severity of the  internal
       // fragmentation is equal to the remainder * the number of slots.
-      // This check prevents internal fragmentation
+      // This check prevents internal fragmentation.
+      // This also necessarily limits to bin sizes to one of:
+      // [1,2,4,8,16,32,64] bits
       BOOST_STATIC_ASSERT( ((sizeof(Block) * 8) % BitsPerBin) == 0);
 
       // a slot is one element position in the array

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-02 05:32:36 EDT (Tue, 02 Aug 2011)
@@ -24,9 +24,23 @@
   namespace bloom_filters {
     namespace detail {
 
-      /*************************************************************************
-       *                          static bloom filter
-       ************************************************************************/
+      template <typename T, 
+		typename Hash, 
+		typename Bitset,
+		size_t NumBins, size_t BinsPerSlot, 
+		size_t BitsPerBin, size_t Mask>
+      static size_t 
+      get_bits(const T& t, const Bitset slots)
+      {
+	static Hash hasher;
+
+	const size_t hash_val = hasher(t) % NumBins;
+	const size_t pos = hash_val / BinsPerSlot;
+	const size_t offset_bits = (hash_val % BinsPerSlot) * BitsPerBin;
+	
+	return ((slots[pos] >> offset_bits) & Mask);
+      }
+
       template <size_t N,
                 typename T,
                 size_t NumBins,
@@ -45,13 +59,13 @@
           typedef typename boost::mpl::at_c<HashFunctions, N>::type Hash;
           static Hash hasher;
           
-	  const size_t hash_val = Hash(t) % NumBins;
+	  const size_t hash_val = hasher(t) % NumBins;
           const size_t pos = hash_val / BinsPerSlot;
           const size_t offset_bits = (hash_val % BinsPerSlot) * BitsPerBin;
           size_t target_bits = (_slots[pos] >> offset_bits) & MASK;
           ++target_bits;
 
-	  if (target_bits == 0) 
+	  if (target_bits == (1 << BitsPerBin))
             throw bin_overflow_exception();
           
           _slots[pos] |= (target_bits << offset_bits);
@@ -71,10 +85,10 @@
           const size_t offset_bits = (hash_val % BinsPerSlot) * BitsPerBin;
           size_t target_bits = (_slots[pos] >> offset_bits) & MASK;
 
-	  if (target_bits == 0) 
+	  if (target_bits == 0)
             throw bin_underflow_exception();
           
-	  --target_bits;	  
+	  --target_bits;
 
           _slots[pos] |= (target_bits << offset_bits);
 
@@ -93,7 +107,7 @@
           const size_t offset_bits = (hash_val % BinsPerSlot) * BitsPerBin;
           const size_t target_bits = (_slots[pos] >> offset_bits) & MASK;
 
-	  return ((target_bits > 0) && 
+	  return ((target_bits != 0) && 
                   counting_apply_hash<N-1, T, NumBins, 
                                       BitsPerBin, HashFunctions,
                                       Block, ArraySize, BinsPerSlot>::contains(t, _slots));
@@ -113,106 +127,56 @@
         static const size_t MASK = 
           static_cast<Block>(0 - 1) >> (sizeof(Block) * 8 - BitsPerBin);
 
-        static void insert(const T& t, boost::array<Block, ArraySize>& _slots) 
+        static void insert(const T& t, 
+			   boost::array<Block, ArraySize>& _slots) 
         {
           typedef typename boost::mpl::at_c<HashFunctions, 0>::type Hash;
           static Hash hasher;
 
-	  /*
-	  std::cout << "(meta) NumBins: " << NumBins
-		    << " BitsPerBin: " << BitsPerBin 
-		    << " ArraySize: " << ArraySize 
-		    << " BinsPerSlot: " << BinsPerSlot
-		    << " incoming value: " << t << "\n";
-	  */
-
           const size_t hash_val = hasher(t) % NumBins;
           const size_t pos = hash_val / BinsPerSlot;
           const size_t offset_bits = (hash_val % BinsPerSlot) * BitsPerBin;
           size_t target_bits = (_slots[pos] >> offset_bits) & MASK;
 
-	  ++target_bits;	  
+	  ++target_bits;
 
-	  if (target_bits == 0) 
+	  if (target_bits == (1 << BitsPerBin)) 
             throw bin_overflow_exception();
           
           _slots[pos] &= ~(MASK << offset_bits);
           _slots[pos] |= (target_bits << offset_bits);
-
-	  /*
-	  std::cout << "(insert) updated bits at pos " << pos 
-		    << " at bit offset " << offset_bits
-		    << " using mask " << MASK
-		    << " hashed as " << hash_val
-		    << " from " << target_bits - 1 
-		    << " to " << target_bits << "\n";
-	  */
         }
 
-        static void remove(const T& t, boost::array<Block, ArraySize>& _slots) 
+        static void remove(const T& t, 
+			   boost::array<Block, ArraySize>& _slots) 
         {
           typedef typename boost::mpl::at_c<HashFunctions, 0>::type Hash;
           static Hash hasher;
 
-	  /*
-	  std::cout << "(meta) NumBins: " << NumBins
-		    << " BitsPerBin: " << BitsPerBin 
-		    << " ArraySize: " << ArraySize 
-		    << " BinsPerSlot: " << BinsPerSlot
-		    << " incoming value: " << t << "\n";
-	  */
-	  
           const size_t hash_val = hasher(t) % NumBins;
           const size_t pos = hash_val / BinsPerSlot;
           const size_t offset_bits = (hash_val % BinsPerSlot) * BitsPerBin;
           size_t target_bits = (_slots[pos] >> offset_bits) & MASK;
 
-
-	  if (target_bits == 0) 
+	  if (target_bits == 0)
             throw bin_underflow_exception();
 
           --target_bits;
 
           _slots[pos] &= ~(MASK << offset_bits);
           _slots[pos] |= (target_bits << offset_bits);
-
-	  /*
-	  std::cout << "(remove) updated bits at pos " << pos 
-		    << " at bit offset " << offset_bits
-		    << " using mask " << MASK
-		    << " hashed as " << hash_val
-		    << " from " << target_bits + 1 
-		    << " to " << target_bits << "\n";
-	  */
         }
 
-        static bool contains(const T& t, const boost::array<Block, ArraySize>& _slots) 
+        static bool contains(const T& t, 
+			     const boost::array<Block, ArraySize>& _slots) 
         {
           typedef typename boost::mpl::at_c<HashFunctions, 0>::type Hash;
-	  static Hash hasher;
-	  
-	  /*
-	  std::cout << "(meta) NumBins: " << NumBins
-		    << " BitsPerBin: " << BitsPerBin 
-		    << " ArraySize: " << ArraySize 
-		    << " BinsPerSlot: " << BinsPerSlot 
-		    << " incoming value: " << t << "\n";
-	  */
-	  
-	  const size_t hash_val = hasher(t) % NumBins;
-	  const size_t pos = hash_val / BinsPerSlot;
-	  const size_t offset_bits = (hash_val % BinsPerSlot) * BitsPerBin;
-	  const size_t target_bits = (_slots[pos] >> offset_bits) & MASK;
 
-	  /*
-	  std::cout << "(contains) checked bits at pos " << pos 
-		    << " at bit offset " << offset_bits
-		    << " using mask " << MASK
-		    << " hashed as " << hash_val
-		    << " as " << target_bits << "\n";
-	  */
+	  size_t target_bits = 
+	    get_bits<T, Hash, boost::array<Block, ArraySize>,
+		     NumBins, BinsPerSlot, BitsPerBin, MASK>(t, _slots);
 
-	  return (target_bits > 0);
+	  return (target_bits != 0);
         }
       };
     } // namespace detail