|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r72853 - in sandbox/bloom_filter/trunk/boost/bloom_filter: . detail
From: cpp.cabrera_at_[hidden]
Date: 2011-07-02 10:43:00
Author: alejandro
Date: 2011-07-02 10:42:59 EDT (Sat, 02 Jul 2011)
New Revision: 72853
URL: http://svn.boost.org/trac/boost/changeset/72853
Log:
counting_bloom_filter nows compiles!
Major changes:
- dummy implementation for:
count()
intersection
union
- complete implementations for:
insert()
remove()
probably_contains()
- added counting_apply_hash metafunctions
- regression suite mostly fails. Count needs an implementation.
- regression suite needs more test cases with strange bits_per_bin
values.
Added:
sandbox/bloom_filter/trunk/boost/bloom_filter/detail/counting_apply_hash.hpp (contents, props changed)
Text files modified:
sandbox/bloom_filter/trunk/boost/bloom_filter/counting_bloom.hpp | 64 ++++++++++++++++++++++++++++-----------
sandbox/bloom_filter/trunk/boost/bloom_filter/detail/apply_hash.hpp | 8 +++++
2 files changed, 53 insertions(+), 19 deletions(-)
Modified: sandbox/bloom_filter/trunk/boost/bloom_filter/counting_bloom.hpp
==============================================================================
--- sandbox/bloom_filter/trunk/boost/bloom_filter/counting_bloom.hpp (original)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/counting_bloom.hpp 2011-07-02 10:42:59 EDT (Sat, 02 Jul 2011)
@@ -25,7 +25,7 @@
#include <boost/mpl/size.hpp>
#include <boost/static_assert.hpp>
-#include <boost/bloom_filter/detail/apply_hash.hpp>
+#include <boost/bloom_filter/detail/counting_apply_hash.hpp>
#include <boost/bloom_filter/hash/default.hpp>
#ifndef BOOST_NO_0X_HDR_INITIALIZER_LIST
@@ -49,8 +49,8 @@
// a slot is one element position in the array
// a bin is a segment of a slot
static const size_t slot_bits = sizeof(Block) * 4;
- static const size_t elements_per_slot = slot_bits / BitsPerBin;
- static const size_t array_size = elements_per_slot * NumBins + 1;
+ static const size_t bins_per_slot = slot_bits / BitsPerBin;
+ static const size_t array_size = bins_per_slot * NumBins + 1;
private:
typedef boost::array<Block, array_size> bucket_type;
@@ -100,16 +100,20 @@
};
size_t count() const {
- return error;
+ return 0;
};
bool empty() const {
- return error;
+ return this->count() == 0;
}
- void insert(const T& t);
- //static const unsigned N = mpl::size<HashFunctions>::value - 1;
- //detail::counting_apply_hash<N, T, Size, HashFunctions>::insert(t, bits);
+ void insert(const T& t) {
+ static const unsigned N = mpl::size<HashFunctions>::value - 1;
+ detail::counting_apply_hash<N, T, NumBins,
+ BitsPerBin, HashFunctions,
+ Block, array_size,
+ bins_per_slot>::insert(t, this->bits);
+ }
template <typename InputIterator>
void insert(const InputIterator start, const InputIterator end) {
@@ -118,7 +122,13 @@
}
}
- void remove(const T& t);
+ void remove(const T& t) {
+ static const unsigned N = mpl::size<HashFunctions>::value - 1;
+ detail::counting_apply_hash<N, T, NumBins,
+ BitsPerBin, HashFunctions,
+ Block, array_size,
+ bins_per_slot>::remove(t, this->bits);
+ }
template <typename InputIterator>
void remove(const InputIterator start, const InputIterator end) {
@@ -127,13 +137,16 @@
}
}
- bool probably_contains(const T& t) const;
- //static const unsigned N = mpl::size<HashFunctions>::value - 1;
- //return detail::apply_hash<N, T, Size, HashFunctions>::contains(t, bits);
- //return false;
+ bool probably_contains(const T& t) const {
+ static const unsigned N = mpl::size<HashFunctions>::value - 1;
+ return detail::counting_apply_hash<N, T, NumBins,
+ BitsPerBin, HashFunctions,
+ Block, array_size,
+ bins_per_slot>::contains(t, this->bits);
+ }
void clear() {
- for (bucket_iterator i = blocks.begin(), end = blocks.end();
+ for (bucket_iterator i = bits.begin(), end = bits.end();
i != end; ++i) {
*i = 0;
}
@@ -145,8 +158,15 @@
*this = tmp;
}
- counting_bloom_filter& operator|=(const counting_bloom_filter& rhs);
- counting_bloom_filter& operator&=(const counting_bloom_filter& rhs);
+ counting_bloom_filter& operator|=(const counting_bloom_filter& rhs)
+ {
+ return *this;
+ }
+
+ counting_bloom_filter& operator&=(const counting_bloom_filter& rhs)
+ {
+ return *this;
+ }
// equality comparison operators
template <typename _T, size_t _Bins, size_t _BitsPerBin,
@@ -167,7 +187,7 @@
private:
- bucket_type blocks;
+ bucket_type bits;
};
// union
@@ -218,7 +238,10 @@
operator==(const counting_bloom_filter<T, NumBins, BitsPerBin,
HashFunctions, Block>& lhs,
const counting_bloom_filter<T, NumBins, BitsPerBin,
- HashFunctions, Block>& rhs);
+ HashFunctions, Block>& rhs)
+ {
+ return (lhs.bits == rhs.bits);
+ }
template<class T, size_t NumBins, size_t BitsPerBin, class HashFunctions,
typename Block>
@@ -226,7 +249,10 @@
operator!=(const counting_bloom_filter<T, NumBins, BitsPerBin,
HashFunctions, Block>& lhs,
const counting_bloom_filter<T, NumBins, BitsPerBin,
- HashFunctions, Block>& rhs);
+ HashFunctions, Block>& rhs)
+ {
+ return !(lhs == rhs);
+ }
} // namespace bloom_filter
} // namespace boost
Modified: sandbox/bloom_filter/trunk/boost/bloom_filter/detail/apply_hash.hpp
==============================================================================
--- sandbox/bloom_filter/trunk/boost/bloom_filter/detail/apply_hash.hpp (original)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/detail/apply_hash.hpp 2011-07-02 10:42:59 EDT (Sat, 02 Jul 2011)
@@ -33,6 +33,7 @@
static void insert(const T& t, std::bitset<Size>& _bits) {
typedef typename boost::mpl::at_c<HashFunctions, N>::type Hash;
static Hash hasher;
+
_bits[hasher(t) % Size] = true;
apply_hash<N-1, T, Size, HashFunctions>::insert(t, _bits);
}
@@ -40,6 +41,7 @@
static bool contains(const T& t, const std::bitset<Size>& _bits) {
typedef typename boost::mpl::at_c<HashFunctions, N>::type Hash;
static Hash hasher;
+
return (_bits[hasher(t) % Size] &&
apply_hash<N-1, T, Size, HashFunctions>::contains(t, _bits));
}
@@ -53,12 +55,14 @@
static void insert(const T& t, std::bitset<Size>& _bits) {
typedef typename boost::mpl::at_c<HashFunctions, 0>::type Hash;
static Hash hasher;
+
_bits[hasher(t) % Size] = true;
}
static bool contains(const T& t, const std::bitset<Size>& _bits) {
typedef typename boost::mpl::at_c<HashFunctions, 0>::type Hash;
static Hash hasher;
+
return (_bits[hasher(t) % Size]);
}
};
@@ -77,6 +81,7 @@
const size_t size) {
typedef typename boost::mpl::at_c<HashFunctions, N>::type Hash;
static Hash hasher;
+
_bits[hasher(t) % size] = true;
dynamic_apply_hash<N-1,
T,
@@ -90,6 +95,7 @@
const size_t size) {
typedef typename boost::mpl::at_c<HashFunctions, N>::type Hash;
static Hash hasher;
+
return (_bits[hasher(t) % size] &&
dynamic_apply_hash<N-1,
T,
@@ -110,6 +116,7 @@
const size_t size) {
typedef typename boost::mpl::at_c<HashFunctions, 0>::type Hash;
static Hash hasher;
+
_bits[hasher(t) % size] = true;
}
@@ -118,6 +125,7 @@
const size_t size) {
typedef typename boost::mpl::at_c<HashFunctions, 0>::type Hash;
static Hash hasher;
+
return (_bits[hasher(t) % size]);
}
};
Added: sandbox/bloom_filter/trunk/boost/bloom_filter/detail/counting_apply_hash.hpp
==============================================================================
--- (empty file)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/detail/counting_apply_hash.hpp 2011-07-02 10:42:59 EDT (Sat, 02 Jul 2011)
@@ -0,0 +1,140 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Alejandro Cabrera 2011.
+// 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)
+//
+// See http://www.boost.org/libs/bloom_filter for documentation.
+//
+//////////////////////////////////////////////////////////////////////////////
+
+#ifndef BOOST_BLOOM_FILTER_COUNTING_APPLY_HASH_HPP
+#define BOOST_BLOOM_FILTER_COUNTING_APPLY_HASH_HPP
+
+#include <boost/array.hpp>
+#include <boost/mpl/at.hpp>
+
+#include <limits>
+
+namespace boost {
+ namespace bloom_filter {
+ namespace detail {
+
+ /*************************************************************************
+ * static bloom filter
+ ************************************************************************/
+ template <size_t N,
+ typename T,
+ size_t NumBins,
+ size_t BitsPerBin,
+ class HashFunctions,
+ typename Block,
+ size_t ArraySize,
+ size_t BinsPerSlot>
+ struct counting_apply_hash
+ {
+ static const size_t MASK =
+ std::numeric_limits<Block>::max() >> (sizeof(Block) * 8 - BitsPerBin);
+
+ static void insert(const T& t, boost::array<Block, ArraySize>& _slots) {
+ typedef typename boost::mpl::at_c<HashFunctions, N>::type Hash;
+ static Hash hasher;
+
+ size_t hash_val = Hash(t) % NumBins;
+ size_t pos = hash_val / BinsPerSlot;
+ size_t offset_bits = (hash_val % BinsPerSlot) * BitsPerBin;
+ size_t target_bits = (_slots[pos] >> offset_bits) & MASK;
+ ++target_bits;
+ _slots[pos] |= (target_bits << offset_bits);
+
+ counting_apply_hash<N-1, T, NumBins,
+ BitsPerBin, HashFunctions,
+ Block, ArraySize, BinsPerSlot>::insert(t, _slots);
+ }
+
+ static void remove(const T& t, boost::array<Block, ArraySize>& _slots) {
+ typedef typename boost::mpl::at_c<HashFunctions, N>::type Hash;
+ static Hash hasher;
+
+ size_t hash_val = hasher(t) % NumBins;
+ size_t pos = hash_val / BinsPerSlot;
+ size_t offset_bits = (hash_val % BinsPerSlot) * BitsPerBin;
+ size_t target_bits = (_slots[pos] >> offset_bits) & MASK;
+ --target_bits;
+ _slots[pos] |= (target_bits << offset_bits);
+
+ counting_apply_hash<N-1, T, NumBins,
+ BitsPerBin, HashFunctions,
+ Block, ArraySize, BinsPerSlot>::remove(t, _slots);
+ }
+
+ static bool contains(const T& t, const boost::array<Block, ArraySize>& _slots) {
+ typedef typename boost::mpl::at_c<HashFunctions, N>::type Hash;
+ static Hash hasher;
+
+ size_t hash_val = hasher(t) % NumBins;
+ size_t pos = hash_val / BinsPerSlot;
+ size_t offset_bits = (hash_val % BinsPerSlot) * BitsPerBin;
+ size_t target_bits = (_slots[pos] >> offset_bits) & MASK;
+ return ((target_bits > 0) &&
+ counting_apply_hash<N-1, T, NumBins,
+ BitsPerBin, HashFunctions,
+ Block, ArraySize, BinsPerSlot>::contains(t, _slots));
+ }
+ };
+
+ template <typename T,
+ size_t NumBins,
+ size_t BitsPerBin,
+ class HashFunctions,
+ typename Block,
+ size_t ArraySize,
+ size_t BinsPerSlot>
+ struct counting_apply_hash<0, T, NumBins, BitsPerBin, HashFunctions,
+ Block, ArraySize, BinsPerSlot>
+ {
+ static const size_t MASK =
+ std::numeric_limits<Block>::max() >> (sizeof(Block) * 8 - BitsPerBin);
+
+ static void insert(const T& t, boost::array<Block, ArraySize>& _slots) {
+ typedef typename boost::mpl::at_c<HashFunctions, 0>::type Hash;
+ static Hash hasher;
+
+ size_t hash_val = hasher(t) % NumBins;
+ size_t pos = hash_val / BinsPerSlot;
+ size_t offset_bits = (hash_val % BinsPerSlot) * BitsPerBin;
+ size_t target_bits = (_slots[pos] >> offset_bits) & MASK;
+ ++target_bits;
+ _slots[pos] |= (target_bits << offset_bits);
+ }
+
+ static void remove(const T& t, boost::array<Block, ArraySize>& _slots) {
+ typedef typename boost::mpl::at_c<HashFunctions, 0>::type Hash;
+ static Hash hasher;
+
+ size_t hash_val = hasher(t) % NumBins;
+ size_t pos = hash_val / BinsPerSlot;
+ size_t offset_bits = (hash_val % BinsPerSlot) * BitsPerBin;
+ size_t target_bits = (_slots[pos] >> offset_bits) & MASK;
+ --target_bits;
+ _slots[pos] |= (target_bits << offset_bits);
+ }
+
+ 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;
+
+ size_t hash_val = hasher(t) % NumBins;
+ size_t pos = hash_val / BinsPerSlot;
+ size_t offset_bits = (hash_val % BinsPerSlot) * BitsPerBin;
+ size_t target_bits = (_slots[pos] >> offset_bits) & MASK;
+
+ return (target_bits > 0);
+ }
+ };
+ } // namespace detail
+ } // namespace bloom_filter
+} // namespace boost
+#endif
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