fc::bloom_filter Class Reference

#include <bloom_filter.hpp>

Collaboration diagram for fc::bloom_filter:

Public Member Functions
	bloom_filter ()
	bloom_filter (const bloom_parameters &p)
	bloom_filter (const bloom_filter &filter)
bool	operator== (const bloom_filter &f) const
bool	operator!= (const bloom_filter &f) const
bloom_filter &	operator= (const bloom_filter &f)
virtual	~bloom_filter ()
bool	operator! () const
void	clear ()
void	insert (const unsigned char *key_begin, const std::size_t &length)
template<typename T >
void	insert (const T &t)
void	insert (const std::string &key)
void	insert (const char *data, const std::size_t &length)
template<typename InputIterator >
void	insert (const InputIterator begin, const InputIterator end)
virtual bool	contains (const unsigned char *key_begin, const std::size_t length) const
template<typename T >
bool	contains (const T &t) const
bool	contains (const std::string &key) const
bool	contains (const char *data, const std::size_t &length) const
template<typename InputIterator >
InputIterator	contains_all (const InputIterator begin, const InputIterator end) const
template<typename InputIterator >
InputIterator	contains_none (const InputIterator begin, const InputIterator end) const
virtual unsigned long long int	size () const
std::size_t	element_count () const
double	effective_fpp () const
bloom_filter &	operator&= (const bloom_filter &f)
bloom_filter &	operator|= (const bloom_filter &f)
bloom_filter &	operator^= (const bloom_filter &f)
const cell_type *	table () const
std::size_t	hash_count ()

Public Attributes
std::vector< bloom_type >	salt_
std::vector< unsigned char >	bit_table_
unsigned int	salt_count_
unsigned long long int	table_size_
unsigned long long int	raw_table_size_
unsigned long long int	projected_element_count_
unsigned int	inserted_element_count_
unsigned long long int	random_seed_
double	desired_false_positive_probability_

Protected Types
typedef unsigned int	bloom_type
typedef unsigned char	cell_type

Protected Member Functions
virtual void	compute_indices (const bloom_type &hash, std::size_t &bit_index, std::size_t &bit) const
void	generate_unique_salt ()
bloom_type	hash_ap (const unsigned char *begin, std::size_t remaining_length, bloom_type hash) const

Detailed Description

Definition at line 161 of file bloom_filter.hpp.

Member Typedef Documentation

bloom_type

unsigned int fc::bloom_filter::bloom_type

protected

Definition at line 165 of file bloom_filter.hpp.

cell_type

unsigned char fc::bloom_filter::cell_type

protected

Definition at line 166 of file bloom_filter.hpp.

Constructor & Destructor Documentation

bloom_filter() [1/3]

fc::bloom_filter::bloom_filter ( )

inline

Definition at line 170 of file bloom_filter.hpp.

   : salt_count_(0),
     table_size_(0),
     raw_table_size_(0),
     projected_element_count_(0),
     inserted_element_count_(0),
     random_seed_(0),
     desired_false_positive_probability_(0.0)
   {}

bloom_filter() [2/3]

fc::bloom_filter::bloom_filter ( const bloom_parameters & p )

inline

Definition at line 180 of file bloom_filter.hpp.

   : projected_element_count_(p.projected_element_count),
     inserted_element_count_(0),
     random_seed_((p.random_seed * 0xA5A5A5A5) + 1),
     desired_false_positive_probability_(p.false_positive_probability)
   {
      salt_count_ = p.optimal_parameters.number_of_hashes;
      table_size_ = p.optimal_parameters.table_size;
      generate_unique_salt();
      raw_table_size_ = table_size_ / bits_per_char;
 
      bit_table_.resize( static_cast<std::size_t>(raw_table_size_) );
      //bit_table_ = new cell_type[static_cast<std::size_t>(raw_table_size_)];
      std::fill_n(bit_table_.data(),raw_table_size_,0x00);
   }

Here is the call graph for this function:

bloom_filter() [3/3]

fc::bloom_filter::bloom_filter ( const bloom_filter & filter )

inline

Definition at line 196 of file bloom_filter.hpp.

   {
      this->operator=(filter);
   }

Here is the call graph for this function:

~bloom_filter()

virtual fc::bloom_filter::~bloom_filter ( )

inlinevirtual

Definition at line 243 of file bloom_filter.hpp.

   {
   }

Member Function Documentation

clear()

void fc::bloom_filter::clear ( )

inline

Definition at line 252 of file bloom_filter.hpp.

   {
      std::fill_n(bit_table_.data(),raw_table_size_,0x00);
      inserted_element_count_ = 0;
   }

compute_indices()

virtual void fc::bloom_filter::compute_indices ( const bloom_type & hash, std::size_t & bit_index, std::size_t & bit ) const

inlineprotectedvirtual

Definition at line 443 of file bloom_filter.hpp.

   {
      bit_index = hash % table_size_;
      bit = bit_index % bits_per_char;
   }

Here is the caller graph for this function:

contains() [1/4]

bool fc::bloom_filter::contains ( const char * data, const std::size_t & length ) const

inline

Definition at line 323 of file bloom_filter.hpp.

   {
      return contains(reinterpret_cast<const unsigned char*>(data),length);
   }

Here is the call graph for this function:

contains() [2/4]

bool fc::bloom_filter::contains ( const std::string & key ) const

inline

Definition at line 318 of file bloom_filter.hpp.

   {
      return contains(reinterpret_cast<const unsigned char*>(key.c_str()),key.size());
   }

Here is the call graph for this function:

contains() [3/4]

template<typename T >

bool fc::bloom_filter::contains ( const T & t ) const

inline

Definition at line 313 of file bloom_filter.hpp.

   {
      return contains(reinterpret_cast<const unsigned char*>(&t),static_cast<std::size_t>(sizeof(T)));
   }

Here is the call graph for this function:

contains() [4/4]

virtual bool fc::bloom_filter::contains ( const unsigned char * key_begin, const std::size_t length ) const

inlinevirtual

Definition at line 297 of file bloom_filter.hpp.

   {
      std::size_t bit_index = 0;
      std::size_t bit = 0;
      for (std::size_t i = 0; i < salt_.size(); ++i)
      {
         compute_indices(hash_ap(key_begin,length,salt_[i]),bit_index,bit);
         if ((bit_table_[bit_index / bits_per_char] & bit_mask[bit]) != bit_mask[bit])
         {
            return false;
         }
      }
      return true;
   }

Here is the call graph for this function:

Here is the caller graph for this function:

contains_all()

template<typename InputIterator >

InputIterator fc::bloom_filter::contains_all ( const InputIterator begin, const InputIterator end ) const

inline

Definition at line 329 of file bloom_filter.hpp.

   {
      InputIterator itr = begin;
      while (end != itr)
      {
         if (!contains(*itr))
         {
            return itr;
         }
         ++itr;
      }
      return end;
   }

Here is the call graph for this function:

contains_none()

template<typename InputIterator >

InputIterator fc::bloom_filter::contains_none ( const InputIterator begin, const InputIterator end ) const

inline

Definition at line 344 of file bloom_filter.hpp.

   {
      InputIterator itr = begin;
      while (end != itr)
      {
         if (contains(*itr))
         {
            return itr;
         }
         ++itr;
      }
      return end;
   }

Here is the call graph for this function:

effective_fpp()

double fc::bloom_filter::effective_fpp ( ) const

inline

Definition at line 368 of file bloom_filter.hpp.

   {
      /*
        Note:
        The effective false positive probability is calculated using the
        designated table size and hash function count in conjunction with
        the current number of inserted elements - not the user defined
        predicated/expected number of inserted elements.
      */
      return std::pow(1.0 - std::exp(-1.0 * salt_.size() * inserted_element_count_ / size()), 1.0 * salt_.size());
   }

Here is the call graph for this function:

element_count()

std::size_t fc::bloom_filter::element_count ( ) const

inline

Definition at line 363 of file bloom_filter.hpp.

   {
      return inserted_element_count_;
   }

generate_unique_salt()

void fc::bloom_filter::generate_unique_salt ( )

inlineprotected

Definition at line 449 of file bloom_filter.hpp.

   {
      /*
        Note:
        A distinct hash function need not be implementation-wise
        distinct. In the current implementation "seeding" a common
        hash function with different values seems to be adequate.
      */
      const unsigned int predef_salt_count = 128;
      static const bloom_type predef_salt[predef_salt_count] =
                                 {
                                    0xAAAAAAAA, 0x55555555, 0x33333333, 0xCCCCCCCC,
                                    0x66666666, 0x99999999, 0xB5B5B5B5, 0x4B4B4B4B,
                                    0xAA55AA55, 0x55335533, 0x33CC33CC, 0xCC66CC66,
                                    0x66996699, 0x99B599B5, 0xB54BB54B, 0x4BAA4BAA,
                                    0xAA33AA33, 0x55CC55CC, 0x33663366, 0xCC99CC99,
                                    0x66B566B5, 0x994B994B, 0xB5AAB5AA, 0xAAAAAA33,
                                    0x555555CC, 0x33333366, 0xCCCCCC99, 0x666666B5,
                                    0x9999994B, 0xB5B5B5AA, 0xFFFFFFFF, 0xFFFF0000,
                                    0xB823D5EB, 0xC1191CDF, 0xF623AEB3, 0xDB58499F,
                                    0xC8D42E70, 0xB173F616, 0xA91A5967, 0xDA427D63,
                                    0xB1E8A2EA, 0xF6C0D155, 0x4909FEA3, 0xA68CC6A7,
                                    0xC395E782, 0xA26057EB, 0x0CD5DA28, 0x467C5492,
                                    0xF15E6982, 0x61C6FAD3, 0x9615E352, 0x6E9E355A,
                                    0x689B563E, 0x0C9831A8, 0x6753C18B, 0xA622689B,
                                    0x8CA63C47, 0x42CC2884, 0x8E89919B, 0x6EDBD7D3,
                                    0x15B6796C, 0x1D6FDFE4, 0x63FF9092, 0xE7401432,
                                    0xEFFE9412, 0xAEAEDF79, 0x9F245A31, 0x83C136FC,
                                    0xC3DA4A8C, 0xA5112C8C, 0x5271F491, 0x9A948DAB,
                                    0xCEE59A8D, 0xB5F525AB, 0x59D13217, 0x24E7C331,
                                    0x697C2103, 0x84B0A460, 0x86156DA9, 0xAEF2AC68,
                                    0x23243DA5, 0x3F649643, 0x5FA495A8, 0x67710DF8,
                                    0x9A6C499E, 0xDCFB0227, 0x46A43433, 0x1832B07A,
                                    0xC46AFF3C, 0xB9C8FFF0, 0xC9500467, 0x34431BDF,
                                    0xB652432B, 0xE367F12B, 0x427F4C1B, 0x224C006E,
                                    0x2E7E5A89, 0x96F99AA5, 0x0BEB452A, 0x2FD87C39,
                                    0x74B2E1FB, 0x222EFD24, 0xF357F60C, 0x440FCB1E,
                                    0x8BBE030F, 0x6704DC29, 0x1144D12F, 0x948B1355,
                                    0x6D8FD7E9, 0x1C11A014, 0xADD1592F, 0xFB3C712E,
                                    0xFC77642F, 0xF9C4CE8C, 0x31312FB9, 0x08B0DD79,
                                    0x318FA6E7, 0xC040D23D, 0xC0589AA7, 0x0CA5C075,
                                    0xF874B172, 0x0CF914D5, 0x784D3280, 0x4E8CFEBC,
                                    0xC569F575, 0xCDB2A091, 0x2CC016B4, 0x5C5F4421
                                 };
 
      if (salt_count_ <= predef_salt_count)
      {
         std::copy(predef_salt,
                   predef_salt + salt_count_,
                   std::back_inserter(salt_));
          for (unsigned int i = 0; i < salt_.size(); ++i)
          {
            /*
              Note:
              This is done to integrate the user defined random seed,
              so as to allow for the generation of unique bloom filter
              instances.
            */
            salt_[i] = salt_[i] * salt_[(i + 3) % salt_.size()] + static_cast<bloom_type>(random_seed_);
          }
      }
      else
      {
         std::copy(predef_salt,predef_salt + predef_salt_count,std::back_inserter(salt_));
         srand(static_cast<unsigned int>(random_seed_));
         while (salt_.size() < salt_count_)
         {
            bloom_type current_salt = static_cast<bloom_type>(rand()) * static_cast<bloom_type>(rand());
            if (0 == current_salt) continue;
            if (salt_.end() == std::find(salt_.begin(), salt_.end(), current_salt))
            {
               salt_.push_back(current_salt);
            }
         }
      }
   }

Here is the caller graph for this function:

hash_ap()

bloom_type fc::bloom_filter::hash_ap ( const unsigned char * begin, std::size_t remaining_length, bloom_type hash ) const

inlineprotected

Definition at line 526 of file bloom_filter.hpp.

   {
      const unsigned char* itr = begin;
      unsigned int loop = 0;
      while (remaining_length >= 8)
      {
         const unsigned int& i1 = *(reinterpret_cast<const unsigned int*>(itr)); itr += sizeof(unsigned int);
         const unsigned int& i2 = *(reinterpret_cast<const unsigned int*>(itr)); itr += sizeof(unsigned int);
         hash ^= (hash <<  7) ^  i1 * (hash >> 3) ^
              (~((hash << 11) + (i2 ^ (hash >> 5))));
         remaining_length -= 8;
      }
      if (remaining_length)
      {
         if (remaining_length >= 4)
         {
            const unsigned int& i = *(reinterpret_cast<const unsigned int*>(itr));
            if (loop & 0x01)
               hash ^=    (hash <<  7) ^  i * (hash >> 3);
            else
               hash ^= (~((hash << 11) + (i ^ (hash >> 5))));
            ++loop;
            remaining_length -= 4;
            itr += sizeof(unsigned int);
         }
         if (remaining_length >= 2)
         {
            const unsigned short& i = *(reinterpret_cast<const unsigned short*>(itr));
            if (loop & 0x01)
               hash ^=    (hash <<  7) ^  i * (hash >> 3);
            else
               hash ^= (~((hash << 11) + (i ^ (hash >> 5))));
            ++loop;
            remaining_length -= 2;
            itr += sizeof(unsigned short);
         }
         if (remaining_length)
         {
            hash += ((*itr) ^ (hash * 0xA5A5A5A5)) + loop;
         }
      }
      return hash;
   }

Here is the caller graph for this function:

hash_count()

std::size_t fc::bloom_filter::hash_count ( )

inline

Definition at line 436 of file bloom_filter.hpp.

   {
      return salt_.size();
   }

insert() [1/5]

void fc::bloom_filter::insert ( const char * data, const std::size_t & length )

inline

Definition at line 282 of file bloom_filter.hpp.

   {
      insert(reinterpret_cast<const unsigned char*>(data),length);
   }

Here is the call graph for this function:

insert() [2/5]

template<typename InputIterator >

void fc::bloom_filter::insert ( const InputIterator begin, const InputIterator end )

inline

Definition at line 288 of file bloom_filter.hpp.

   {
      InputIterator itr = begin;
      while (end != itr)
      {
         insert(*(itr++));
      }
   }

Here is the call graph for this function:

insert() [3/5]

void fc::bloom_filter::insert ( const std::string & key )

inline

Definition at line 277 of file bloom_filter.hpp.

   {
      insert(reinterpret_cast<const unsigned char*>(key.c_str()),key.size());
   }

Here is the call graph for this function:

insert() [4/5]

template<typename T >

void fc::bloom_filter::insert ( const T & t )

inline

Definition at line 271 of file bloom_filter.hpp.

   {
      // Note: T must be a C++ POD type.
      insert(reinterpret_cast<const unsigned char*>(&t),sizeof(T));
   }

Here is the call graph for this function:

insert() [5/5]

void fc::bloom_filter::insert ( const unsigned char * key_begin, const std::size_t & length )

inline

Definition at line 258 of file bloom_filter.hpp.

   {
      std::size_t bit_index = 0;
      std::size_t bit = 0;
      for (std::size_t i = 0; i < salt_.size(); ++i)
      {
         compute_indices(hash_ap(key_begin,length,salt_[i]),bit_index,bit);
         bit_table_[bit_index / bits_per_char] |= bit_mask[bit];
      }
      ++inserted_element_count_;
   }

Here is the call graph for this function:

Here is the caller graph for this function:

operator!()

bool fc::bloom_filter::operator! ( ) const

inline

Definition at line 247 of file bloom_filter.hpp.

   {
      return (0 == table_size_);
   }

operator!=()

bool fc::bloom_filter::operator!= ( const bloom_filter & f ) const

inline

Definition at line 220 of file bloom_filter.hpp.

   {
      return !operator==(f);
   }

Here is the call graph for this function:

operator&=()

bloom_filter & fc::bloom_filter::operator&= ( const bloom_filter & f )

inline

Definition at line 380 of file bloom_filter.hpp.

   {
      /* intersection */
      if (
          (salt_count_  == f.salt_count_) &&
          (table_size_  == f.table_size_) &&
          (random_seed_ == f.random_seed_)
         )
      {
         for (std::size_t i = 0; i < raw_table_size_; ++i)
         {
            bit_table_[i] &= f.bit_table_[i];
         }
      }
      return *this;
   }

operator=()

bloom_filter & fc::bloom_filter::operator= ( const bloom_filter & f )

inline

Definition at line 225 of file bloom_filter.hpp.

   {
      if (this != &f)
      {
         salt_count_ = f.salt_count_;
         table_size_ = f.table_size_;
         raw_table_size_ = f.raw_table_size_;
         projected_element_count_ = f.projected_element_count_;
         inserted_element_count_ = f.inserted_element_count_;
         random_seed_ = f.random_seed_;
         desired_false_positive_probability_ = f.desired_false_positive_probability_;
         bit_table_.resize( raw_table_size_ );
         std::copy(f.bit_table_.data(),f.bit_table_.data() + raw_table_size_,bit_table_.data());
         salt_ = f.salt_;
      }
      return *this;
   }

Here is the caller graph for this function:

operator==()

bool fc::bloom_filter::operator== ( const bloom_filter & f ) const

inline

Definition at line 201 of file bloom_filter.hpp.

   {
      if (this != &f)
      {
         return
            (salt_count_                         == f.salt_count_)                         &&
            (table_size_                         == f.table_size_)                         &&
            (raw_table_size_                     == f.raw_table_size_)                     &&
            (projected_element_count_            == f.projected_element_count_)            &&
            (inserted_element_count_             == f.inserted_element_count_)             &&
            (random_seed_                        == f.random_seed_)                        &&
            (desired_false_positive_probability_ == f.desired_false_positive_probability_) &&
            (salt_                               == f.salt_)                               &&
            std::equal(f.bit_table_.data(),f.bit_table_.data() + raw_table_size_,bit_table_.data());
      }
      else
         return true;
   }

Here is the caller graph for this function:

operator^=()

bloom_filter & fc::bloom_filter::operator^= ( const bloom_filter & f )

inline

Definition at line 414 of file bloom_filter.hpp.

   {
      /* difference */
      if (
          (salt_count_  == f.salt_count_) &&
          (table_size_  == f.table_size_) &&
          (random_seed_ == f.random_seed_)
         )
      {
         for (std::size_t i = 0; i < raw_table_size_; ++i)
         {
            bit_table_[i] ^= f.bit_table_[i];
         }
      }
      return *this;
   }

operator|=()

bloom_filter & fc::bloom_filter::operator|= ( const bloom_filter & f )

inline

Definition at line 397 of file bloom_filter.hpp.

   {
      /* union */
      if (
          (salt_count_  == f.salt_count_) &&
          (table_size_  == f.table_size_) &&
          (random_seed_ == f.random_seed_)
         )
      {
         for (std::size_t i = 0; i < raw_table_size_; ++i)
         {
            bit_table_[i] |= f.bit_table_[i];
         }
      }
      return *this;
   }

size()

virtual unsigned long long int fc::bloom_filter::size ( ) const

inlinevirtual

Definition at line 358 of file bloom_filter.hpp.

   {
      return table_size_;
   }

Here is the caller graph for this function:

table()

const cell_type * fc::bloom_filter::table ( ) const

inline

Definition at line 431 of file bloom_filter.hpp.

   {
      return bit_table_.data();
   }

Member Data Documentation

bit_table_

std::vector<unsigned char> fc::bloom_filter::bit_table_

Definition at line 572 of file bloom_filter.hpp.

desired_false_positive_probability_

double fc::bloom_filter::desired_false_positive_probability_

Definition at line 579 of file bloom_filter.hpp.

inserted_element_count_

unsigned int fc::bloom_filter::inserted_element_count_

Definition at line 577 of file bloom_filter.hpp.

projected_element_count_

unsigned long long int fc::bloom_filter::projected_element_count_

Definition at line 576 of file bloom_filter.hpp.

random_seed_

unsigned long long int fc::bloom_filter::random_seed_

Definition at line 578 of file bloom_filter.hpp.

raw_table_size_

unsigned long long int fc::bloom_filter::raw_table_size_

Definition at line 575 of file bloom_filter.hpp.

salt_

std::vector<bloom_type> fc::bloom_filter::salt_

Definition at line 571 of file bloom_filter.hpp.

salt_count_

unsigned int fc::bloom_filter::salt_count_

Definition at line 573 of file bloom_filter.hpp.

table_size_

unsigned long long int fc::bloom_filter::table_size_

Definition at line 574 of file bloom_filter.hpp.

---

The documentation for this class was generated from the following file:

• libraries/fc/include/fc/bloom_filter.hpp