bloom.cpp File Reference

Definitions of the binary tree functions you'll be writing for this lab. More...

Functions
float	measureFPR (std::vector< int > inList, uint64_t size, std::vector< hashFunction > hashList, unsigned max)
	Measures the false positive rate for a bloom filter The insert should use every hash function in hashList The calculation should query every value between 0 and max-1 (So not including max) HINT: The FPR is calculated using the counts of True Negatives (TN) and False Positives (FP). More...
bool	getBitFromArray (std::vector< char > bv, int index)
	A logic-based function to find the correct byte register given an integer index in bits You should assume that the starting character in our vector are the bits 0-7 In other words, our bit vector is indexed from left to right. More...
bool	getBitFromByte (char in, int index)
	A bitmask-based function to get a boolean value from a character To be clear, the character itself isnt relevant – its an encoding of 8 bits! You should assume the left-most bit is 0-indexed. More...

Detailed Description

Definitions of the binary tree functions you'll be writing for this lab.

You'll need to modify this file.

Function Documentation

getBitFromArray()

bool getBitFromArray	(	std::vector< char >	bv,
		int	index
	)

A logic-based function to find the correct byte register given an integer index in bits You should assume that the starting character in our vector are the bits 0-7 In other words, our bit vector is indexed from left to right.

NOTE: That is not a guarantee using some other forms of bit encoding! The use of vectors here is to make our approach system agnostic.

HINT: You will have to use one or more bit operations (and, or, xor) to do this.

Parameters

bv	A vector storing a bit vector as a collection of characters (8 bits each)
index	The register whose value we want to get in the vector ofbytes

Returns

The boolean value of the indexed bit

getBitFromByte()

bool getBitFromByte	(	char	in,
		int	index
	)

A bitmask-based function to get a boolean value from a character To be clear, the character itself isnt relevant – its an encoding of 8 bits! You should assume the left-most bit is 0-indexed.

In other words: Bit Index: 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |

HINT: You will have to use one or more bit operations (and, or, xor) to do this.

Parameters

in	A character representing an eight-bit (one byte) register in the bloom filter
index	The register whose value we want to get in the byte

Returns

The boolean value of the indexed bit

measureFPR()

float measureFPR	(	std::vector< int >	inList,
		uint64_t	size,
		std::vector< hashFunction >	hashList,
		unsigned	max
	)

Measures the false positive rate for a bloom filter The insert should use every hash function in hashList The calculation should query every value between 0 and max-1 (So not including max) HINT: The FPR is calculated using the counts of True Negatives (TN) and False Positives (FP).

Parameters

inList	A vector of integers to be inserted into the bloom filter
size	The size (in bits) of the bloom filter to create
hashList	A vector containing a list of hash functions to use in the BF
max	The size of the range of numbers being tested (our universe)

Returns

A value between 0 and 1 (inclusive) estimating the FPR for the BF under these conditions