bloom.h
#ifndef __BLOOM_H__ #define __BLOOM_H__ #include <stdlib.h> typedef unsigned int (*hashfunc_t)(const char *); typedef struct { size_t asize; unsigned char *a; size_t nfuncs; hashfunc_t *funcs; } BLOOM; BLOOM *bloom_create(size_t size, size_t nfuncs, ...); int bloom_destroy(BLOOM *bloom); int bloom_add(BLOOM *bloom, const char *s); int bloom_check(BLOOM *bloom, const char *s); #endif
bloom.c
#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))) BLOOM *bloom_create(size_t size, size_t nfuncs, ...) { BLOOM *bloom; va_list l; int n; if(!(bloom=malloc(sizeof(BLOOM)))) return NULL; if(!(bloom->a=calloc((size+CHAR_BIT-1)/CHAR_BIT, sizeof(char)))) { free(bloom); return NULL; } if(!(bloom->funcs=(hashfunc_t*)malloc(nfuncs*sizeof(hashfunc_t)))) { free(bloom->a); free(bloom); return NULL; } 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; 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; }
测试程序mybloom.c
编译指令 gcc mybloom.c bloom.c -o mybloom
功能：查询整个linux文件系统中是否有从用户端输入的文件
#include<stdio.h> #include<string.h> #include <dirent.h> #include <time.h> #include "bloom.h" long n=0; 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; } // JS Hash unsigned int JS_hash(char *str) { unsigned int hash = 1315423911; while (*str) { hash ^= ((hash << 5) + (*str++) + (hash >> 2)); } return (hash & 0x7FFFFFFF); } int traverse(char *s,BLOOM *bloom1) { DIR *directory_pointer; char current_path[10000]; char filepath[10000]; char now[10000]; struct dirent *entry; strcpy(current_path,s); if ((directory_pointer=opendir(s))==NULL) printf("Error opening!/n"); else { while ((entry=readdir(directory_pointer))!=NULL) { if(strcmp(entry->d_name,".")!=0&&strcmp(entry->d_name,"..")!=0) { if(entry->d_type==4) { strcpy(filepath,current_path); strcat(filepath,"/"); strcat(filepath,entry->d_name); traverse(filepath,bloom1); } else if(entry->d_type==8) { strcpy(now,current_path); strcat(now,"/"); strcat(now,entry->d_name); n++; printf("%ld/n",n); bloom_add(bloom1,now); } } } closedir(directory_pointer); } } void bloom_set(BLOOM *bloom1) { DIR *directory_pointer; char temp[100]=""; struct dirent *entry; if ((directory_pointer=opendir("/"))==NULL) printf("Error opening!/n"); else { while ((entry=readdir(directory_pointer))!=NULL) { if(strcmp(entry->d_name,".")!=0&&strcmp(entry->d_name,"..")!=0) { if(entry->d_type==4) { strcpy(temp,"/"); strcat(temp,entry->d_name); traverse(temp,bloom1); } else { strcpy(temp,"/"); strcat(temp,entry->d_name); bloom_add(bloom1,temp); n++; printf("%ld/n",n); } } } closedir(directory_pointer); } } int main() { BLOOM *bloom; char s[200]; int result; if(!(bloom=bloom_create(250000, 3, sax_hash, sdbm_hash,JS_hash))) { fprintf(stderr, "ERROR: Could not create bloom filter/n"); return EXIT_FAILURE; } bloom_set(bloom); printf("bloom set successfully!/ninput the file u want to search:/n"); while(1) { scanf("%s",s); if(strcmp(s,"quit")==0)break; result=bloom_check(bloom,s); if(result==1)printf("file found!/n"); else printf("no such file!/n"); } }
