bloom.c

/*This is a slightly modified code snippet from http://en.literateprograms.org/Bloom_filter_%28C%29.
*/
#include<limits.h>
#include<stdarg.h>

#include"bloom.h"

#define SETBIT(a, n) (a[n/CHAR_BIT] |= (1<<(n%CHAR_BIT)))
#define GETBIT(a, n) (a[n/CHAR_BIT] & (1<<(n%CHAR_BIT)))

unsigned int sax_hash(const char *key)
{
  unsigned int h=0;

  while(*key) h^=(h<<5)+(h>>2)+(unsigned char)*key++;

  return h;
}

unsigned int sdbm_hash(const char *key)
{
  unsigned int h=0;
  while(*key) h=(unsigned char)*key++ + (h<<6) + (h<<16) - h;
  return h;
}

BLOOM *bloom_create(size_t size) {
 return bloom_create_hash(size,2, sax_hash, sdbm_hash); 
}

BLOOM *bloom_create_hash(size_t size, size_t nfuncs, ...)
{
  BLOOM *bloom;
  va_list l;
  int n;
  //reserve memory for bloom array (in case of honeydv6 40,000,000
  if(!(bloom=malloc(sizeof(BLOOM)))) return NULL;
  if(!(bloom->a=calloc((size+CHAR_BIT-1)/CHAR_BIT, sizeof(char)))) {
    free(bloom);
    return NULL;
  }
  //reserve some memory for hash functions
  if(!(bloom->funcs=(hashfunc_t*)malloc(nfuncs*sizeof(hashfunc_t)))) {
    free(bloom->a);
    free(bloom);
    return NULL;
  }

  //assign hash functions
  va_start(l, nfuncs);
  for(n=0; n<nfuncs; ++n) {
    bloom->funcs[n]=va_arg(l, hashfunc_t);
  }
  va_end(l);

  bloom->nfuncs=nfuncs;
  bloom->asize=size;

  return bloom;
}

int bloom_destroy(BLOOM *bloom)
{
  free(bloom->a);
  free(bloom->funcs);
  free(bloom);

  return 0;
}

int bloom_add(BLOOM *bloom, const char *s)
{
  size_t n;

  //set 
  for(n=0; n<bloom->nfuncs; ++n) {
    SETBIT(bloom->a, bloom->funcs[n](s)%bloom->asize);
  }

  return 0;
}

int bloom_check(BLOOM *bloom, const char *s)
{
  size_t n;

  for(n=0; n<bloom->nfuncs; ++n) {
    if(!(GETBIT(bloom->a, bloom->funcs[n](s)%bloom->asize))) return 0;
  }

  return 1;
}