#include <stdio.h>
#include <stdlib.h>
void set_bitmap(char* b, unsigned int i) {
b[i / 8] |= 1 << (i & 7);
}
void unset_bitmap(char* b, unsigned int i) {
b[i / 8] &= ~(1 << (i & 7));
}
char get_bitmap(char* b, unsigned int i) {
return b[i / 8] & (1 << (i & 7)) ? 1 : 0;
}
char* create_bitmap(unsigned int n) {
return malloc((n + 7) / 8);
}
unsigned int sdbm(char* str) {
unsigned int hash = 0;
while(*str != 0) {
hash = ((hash << 6) + (hash << 16) - hash) + *str++;
}
return hash;
}
char* bloomFilter; int size;
void createBloomFilter(unsigned int n) {
bloomFilter = create_bitmap(n);
size = n;
}
void addElement(char* str) {
set_bitmap(bloomFilter, sdbm(str) % size);
}
char checkElement(char* str) {
return get_bitmap(bloomFilter, sdbm(str) % size);
}
int main() {
createBloomFilter(1024);
addElement("hello");
addElement("world");
addElement("please");
printf("%d", checkElement("please"));
printf("%d", checkElement("world"));
printf("%d\n", checkElement("checkout"));
return 0;
}
bloom filter