First implement the Bloom filter functions by implementing the bloom_init, bloom_query, and bloom_add in the source file bloom.c.

To help you implement bloom_add and bloom_query, we provide you with a particular hash function implementation for Bloom filter, int hash_i(int i, long long x). This function will hash a given Rabin-Karp hash value x into an int value according to the i-th hash function. The number of hash functions that you should use is given by BLOOM_HASH_NUM, a global constant defined in file bloom.c.

Given Code:

 /*********************************************************** File Name: bloom.c Description: implementation of bloom filter goes here **********************************************************/ #include  #include  #include  #include  #include "bloom.h" /* Constants for bloom filter implementation */ const int H1PRIME = 4189793; const int H2PRIME = 3296731; const int BLOOM_HASH_NUM = 10; /* The hash function used by the bloom filter */ int hash_i(int i, /* which of the BLOOM_HASH_NUM hashes to use */ long long x /* the element (a RK value) to be hashed */) { return ((x % H1PRIME) + i*(x % H2PRIME) + 1 + i*i); } /* Initialize a bloom filter by allocating a character array that can pack bsz bits. Furthermore, clear all bits for the allocated character array. Each char should contain 8 bits of the array. Hint: use the malloc and memset library function Return value is the allocated character array.*/ bloom_filter bloom_init(int bsz /* size of bitmap to allocate in bits*/ ) { bloom_filter f; assert((bsz % 8) == 0); f.bsz = bsz; /* your code here*/ return f; } /* Add elm into the given bloom filter * We use a specific bit-ordering convention for the bloom filter implemention. Specifically, you are expected to use the character array in big-endian format. As an example, To set the 9-th bit of the bitmap to be "1", you should set the left-most bit of the second character in the character array to be "1". */ void bloom_add(bloom_filter f, long long elm /* the element to be added (a RK hash value) */) { /* Your code here */ } /* Query if elm is a probably in the given bloom filter */ int bloom_query(bloom_filter f, long long elm /* the query element (a RK hash value) */ ) { /* Your code here */ return 0; } void bloom_free(bloom_filter *f) { free(f->buf); f->buf = (char *)0; f->bsz = 0; } /* print out the first count bits in the bloom filter, * where count is the given function argument */ void bloom_print(bloom_filter f, int count /* number of bits to display*/ ) { assert(count % 8 == 0); for(int i=0; i< (f.bsz>>3) && i < (count>>3); i++) { printf("%02x ", (unsigned char)(f.buf[i])); } printf(" "); return; } 

bloom.h:

#ifndef __BLOOM_H_ #define __BLOOM_H_ /*********************************************************** File Name: bloom.h Description: definition of Bloom filter functions **********************************************************/ typedef struct { char *buf; /* the bitmap representing the bloom filter*/ int bsz; /* size of bitmap in bits*/ } bloom_filter; bloom_filter bloom_init(int bsz); void bloom_free(bloom_filter *f); void bloom_add(bloom_filter f, long long elm); int bloom_query(bloom_filter f, long long elm); void bloom_print(bloom_filter f, int count); #endif