#include <bloom_filter.hpp>

Inheritance diagram for 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

unsigned long long int	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 ()

Protected Types
typedef unsigned int	bloom_type

typedef unsigned char	cell_type

typedef std::vector< unsigned char >	table_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

Protected 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	projected_element_count_

unsigned long long int	inserted_element_count_

unsigned long long int	random_seed_

double	desired_false_positive_probability_

Detailed Description

Definition at line 164 of file bloom_filter.hpp.

Member Typedef Documentation

◆ bloom_type

typedef unsigned int bloom_filter::bloom_type

protected

Definition at line 168 of file bloom_filter.hpp.

◆ cell_type

typedef unsigned char bloom_filter::cell_type

protected

Definition at line 169 of file bloom_filter.hpp.

◆ table_type

typedef std::vector<unsigned char> bloom_filter::table_type

protected

Definition at line 170 of file bloom_filter.hpp.

Constructor & Destructor Documentation

◆ bloom_filter() [1/3]

bloom_filter::bloom_filter ( )

inline

Definition at line 174 of file bloom_filter.hpp.

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

◆ bloom_filter() [2/3]

bloom_filter::bloom_filter ( const bloom_parameters & p )

inline

Definition at line 183 of file bloom_filter.hpp.

References bits_per_char, bloom_parameters::optimal_parameters_t::number_of_hashes, bloom_parameters::optimal_parameters, and bloom_parameters::optimal_parameters_t::table_size.

    : 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();
 
       bit_table_.resize(table_size_ / bits_per_char, static_cast<unsigned char>(0x00));
    }

◆ bloom_filter() [3/3]

bloom_filter::bloom_filter ( const bloom_filter & filter )

inline

Definition at line 197 of file bloom_filter.hpp.

    {
       this->operator=(filter);
    }

◆ ~bloom_filter()

virtual bloom_filter::~bloom_filter ( )

inlinevirtual

Definition at line 246 of file bloom_filter.hpp.

247 {}

Member Function Documentation

◆ clear()

void bloom_filter::clear ( )

inline

Definition at line 254 of file bloom_filter.hpp.

    {
       std::fill(bit_table_.begin(), bit_table_.end(), static_cast<unsigned char>(0x00));
       inserted_element_count_ = 0;
    }

◆ compute_indices()

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

inlineprotectedvirtual

Definition at line 461 of file bloom_filter.hpp.

References bits_per_char.

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

◆ contains() [1/4]

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

inlinevirtual

Definition at line 303 of file bloom_filter.hpp.

References bit_mask, and bits_per_char.

Referenced by main().

    {
       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 caller graph for this function:

◆ contains() [2/4]

template<typename T >

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

inline

Definition at line 322 of file bloom_filter.hpp.

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

◆ contains() [3/4]

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

inline

Definition at line 327 of file bloom_filter.hpp.

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

◆ contains() [4/4]

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

inline

Definition at line 332 of file bloom_filter.hpp.

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

◆ contains_all()

template<typename InputIterator >

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

inline

Definition at line 338 of file bloom_filter.hpp.

Referenced by main().

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

Here is the caller graph for this function:

◆ contains_none()

template<typename InputIterator >

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

inline

Definition at line 356 of file bloom_filter.hpp.

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

◆ effective_fpp()

double bloom_filter::effective_fpp ( ) const

inline

Definition at line 383 of file bloom_filter.hpp.

Referenced by main().

    {
       /*
         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 caller graph for this function:

◆ element_count()

unsigned long long int bloom_filter::element_count ( ) const

inline

Definition at line 378 of file bloom_filter.hpp.

    {
       return inserted_element_count_;
    }

◆ generate_unique_salt()

void bloom_filter::generate_unique_salt ( )

inlineprotected

Definition at line 467 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 (std::size_t 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);
             }
          }
       }
    }

◆ hash_ap()

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

inlineprotected

Definition at line 551 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;
    }

◆ hash_count()

std::size_t bloom_filter::hash_count ( )

inline

Definition at line 454 of file bloom_filter.hpp.

    {
       return salt_.size();
    }

◆ insert() [1/5]

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

inline

Definition at line 260 of file bloom_filter.hpp.

References bit_mask, and bits_per_char.

Referenced by main().

    {
       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 caller graph for this function:

◆ insert() [2/5]

template<typename T >

void bloom_filter::insert ( const T & t )

inline

Definition at line 276 of file bloom_filter.hpp.

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

◆ insert() [3/5]

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

inline

Definition at line 282 of file bloom_filter.hpp.

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

◆ insert() [4/5]

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

inline

Definition at line 287 of file bloom_filter.hpp.

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

◆ insert() [5/5]

template<typename InputIterator >

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

inline

Definition at line 293 of file bloom_filter.hpp.

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

◆ operator!()

bool bloom_filter::operator! ( ) const

inline

Definition at line 249 of file bloom_filter.hpp.

    {
       return (0 == table_size_);
    }

◆ operator!=()

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

inline

Definition at line 221 of file bloom_filter.hpp.

    {
       return !operator==(f);
    }

◆ operator&=()

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

inline

Definition at line 395 of file bloom_filter.hpp.

References bit_table_, random_seed_, salt_count_, and table_size_.

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

◆ operator=()

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

inline

Definition at line 226 of file bloom_filter.hpp.

References bit_table_, desired_false_positive_probability_, inserted_element_count_, projected_element_count_, random_seed_, salt_, salt_count_, and table_size_.

    {
       if (this != &f)
       {
          salt_count_ = f.salt_count_;
          table_size_ = f.table_size_;
          bit_table_  = f.bit_table_;
          salt_       = f.salt_;
 
          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_;
       }
 
       return *this;
    }

◆ operator==()

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

inline

Definition at line 202 of file bloom_filter.hpp.

References bit_table_, desired_false_positive_probability_, inserted_element_count_, projected_element_count_, random_seed_, salt_, salt_count_, and table_size_.

    {
       if (this != &f)
       {
          return
             (salt_count_                         == f.salt_count_                        ) &&
             (table_size_                         == f.table_size_                        ) &&
             (bit_table_.size()                   == f.bit_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_                              ) &&
             (bit_table_                          == f.bit_table_                         ) ;
       }
       else
          return true;
    }

◆ operator^=()

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

inline

Definition at line 431 of file bloom_filter.hpp.

References bit_table_, random_seed_, salt_count_, and table_size_.

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

◆ operator|=()

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

inline

Definition at line 413 of file bloom_filter.hpp.

References bit_table_, random_seed_, salt_count_, and table_size_.

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

◆ size()

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

inlinevirtual

Reimplemented in compressible_bloom_filter.

Definition at line 373 of file bloom_filter.hpp.

Referenced by main().

    {
       return table_size_;
    }

Here is the caller graph for this function:

◆ table()

const cell_type* bloom_filter::table ( ) const

inline

Definition at line 449 of file bloom_filter.hpp.

    {
       return bit_table_.data();
    }

Member Data Documentation

◆ bit_table_

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

protected

Definition at line 611 of file bloom_filter.hpp.

Referenced by operator&=(), operator=(), operator==(), operator^=(), and operator|=().

◆ desired_false_positive_probability_

double bloom_filter::desired_false_positive_probability_

protected

Definition at line 617 of file bloom_filter.hpp.

Referenced by operator=(), and operator==().

◆ inserted_element_count_

unsigned long long int bloom_filter::inserted_element_count_

protected

Definition at line 615 of file bloom_filter.hpp.

Referenced by operator=(), and operator==().

◆ projected_element_count_

unsigned long long int bloom_filter::projected_element_count_

protected

Definition at line 614 of file bloom_filter.hpp.

Referenced by operator=(), and operator==().

◆ random_seed_

unsigned long long int bloom_filter::random_seed_

protected

Definition at line 616 of file bloom_filter.hpp.

Referenced by operator&=(), operator=(), operator==(), operator^=(), and operator|=().

◆ salt_

std::vector<bloom_type> bloom_filter::salt_

protected

Definition at line 610 of file bloom_filter.hpp.

Referenced by operator=(), and operator==().

◆ salt_count_

unsigned int bloom_filter::salt_count_

protected

Definition at line 612 of file bloom_filter.hpp.

Referenced by operator&=(), operator=(), operator==(), operator^=(), and operator|=().

◆ table_size_

unsigned long long int bloom_filter::table_size_

protected

Definition at line 613 of file bloom_filter.hpp.

Referenced by operator&=(), operator=(), operator==(), operator^=(), and operator|=().

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

bloom/bloom_filter.hpp

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ bloom_type

◆ cell_type

◆ table_type

Constructor & Destructor Documentation

◆ bloom_filter() [1/3]

◆ bloom_filter() [2/3]

◆ bloom_filter() [3/3]

◆ ~bloom_filter()

Member Function Documentation

◆ clear()

◆ compute_indices()

◆ contains() [1/4]

◆ contains() [2/4]

◆ contains() [3/4]

◆ contains() [4/4]

◆ contains_all()

◆ contains_none()

◆ effective_fpp()

◆ element_count()

◆ generate_unique_salt()

◆ hash_ap()

◆ hash_count()

◆ insert() [1/5]

◆ insert() [2/5]

◆ insert() [3/5]

◆ insert() [4/5]

◆ insert() [5/5]

◆ operator!()

◆ operator!=()

◆ operator&=()

◆ operator=()

◆ operator==()

◆ operator^=()

◆ operator|=()

◆ size()

◆ table()

Member Data Documentation

◆ bit_table_

◆ desired_false_positive_probability_

◆ inserted_element_count_

◆ projected_element_count_

◆ random_seed_

◆ salt_

◆ salt_count_

◆ table_size_