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