bloom.c

int test_bit(char * buf, int pos){
    return buf[pos/8] & (1<<(pos%8));
}
void set_bit(char * buf, int pos){
    buf[pos/8] |= 1<<(pos%8);
}
int bloom_check(struct bloom * bloom, const void * buffer, int len) {
  int hits = 0;
  unsigned int a = murmurhash2(buffer, len, 0x9747b28c);
  unsigned int b = murmurhash2(buffer, len, a);
  for (int i = 0; i < bloom->hashes; i++)
    if(test_bit(bloom->bf, (a + i*b) % bloom->bits)) hits++;
  return hits == bloom->hashes;
}
int bloom_add(struct bloom * bloom, const void * buffer, int len) {
  unsigned int a = murmurhash2(buffer, len, 0x9747b28c);
  unsigned int b = murmurhash2(buffer, len, a);
  for (int i = 0; i < bloom->hashes; i++)
    set_bit(bloom->bf, (a + i*b) % bloom->bits);
}
int bloom_init(struct bloom * bloom, int entries, double error) {
  if (entries < 1000 || error == 0)
    return 1;
  double bpe = -(log(error) / 0.480453013918201);
  bloom->bits = (int)(entries * bpe);
  if (bloom->bits % 8)
      bloom->bf = (unsigned char *)calloc(bloom->bits/8+1, sizeof(unsigned char));
  else
      bloom->bf = (unsigned char *)calloc(bloom->bits/8, sizeof(unsigned char));
  if (bloom->bf == NULL)
    return 1;
  bloom->hashes = (int)ceil(0.693147180559945 * bpe);  // ln(2)
  return 0;
}
void bloom_free(struct bloom * bloom) {
  free(bloom->bf);
}