부룬 필터 구현
#pragma once
#include
#include
typedef struct BitMap
{
uint64_t* data;
size_t capacity; // max bit
} BitMap;
void BitMapInit(BitMap* bm, size_t capacity);
// index 1
void BitMapSet(BitMap* bm, size_t index);
// index 0
void BitMapUnset(BitMap* bm, size_t index);
// index 1 , 0. 1, 1. 0.
int BitMapTest(BitMap* bm, size_t index);
// 1.
void BitMapFill(BitMap* bm);
// 0.
void BitMapClear(BitMap* bm);
void BitMapDestroy(BitMap* bm);
void ShowSturct(BitMap* bm);
void ShowBit(BitMap* bm);
bitmap.c
#include
#include
#include"bitmap.h"
#define TEST_HEADER printf("
=================%s===============
", __FUNCTION__)
void BitMapInit(BitMap* bm, size_t capacity)
{
if(bm==NULL)
{
return;
}
size_t tmp = capacity % 64;
if(tmp==0)
{
bm->data=(uint64_t*)malloc( sizeof(uint64_t) * (capacity / 64) );
bm->capacity =capacity ;
}
else
{
bm->data=(uint64_t*)malloc( sizeof(uint64_t) * ( 1 + (capacity / 64) ) );
bm->capacity = (1 + (capacity / 64))*64 ;
}
}
// index 1
void BitMapSet(BitMap* bm, size_t index)
{
if(bm==NULL)
{
return;
}
if(bm->capacity<= index)
{
return;
}
size_t subscript= index / 64;
size_t offset = index % 64;
// 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001
bm->data[subscript] |= (uint64_t) 1 << offset;
}
// [00000000]64 [000000000]64
// index 0
void BitMapUnset(BitMap* bm, size_t index)
{
if(bm==NULL)
{
return;
}
if(bm->capacity <= index)
{
return;
}
uint64_t tmp=0xffffffffffffffff;
size_t subscript = index/64;
size_t offset = index % 64;
tmp ^= (uint64_t)1<data[subscript] &= tmp;
}
// index 1 , 0. 1, 1. 0.
int BitMapTest(BitMap* bm, size_t index)
{
if(bm==NULL)
{
return -1;
}
if(bm->capacity<= index)
{
return -2;
}
size_t subscript= index/64;
size_t offset = index % 64;
return ( 1 & (bm->data[subscript] >>offset));
}
// 1.
void BitMapFill(BitMap* bm)
{
if(bm==NULL)
{
return;
}
size_t i;
size_t max= bm->capacity/64;
for(i=0;idata[i]=0xffffffffffffffff;
}
}
// 0.
void BitMapClear(BitMap* bm)
{
if(bm==NULL)
{
return;
}
size_t i;
size_t max= bm->capacity/64;
for(i=0;idata[i]=0;
}
}
void BitMapDestroy(BitMap* bm)
{
if(bm==NULL)
{
return;
}
free(bm->data);
bm->data=NULL;
bm->capacity=0;
}
void ShowSturct(BitMap* bm)
{
printf(" Bit Map Sturct
");
printf("data : %10p
",bm->data);
printf("capacity : %10lu
",bm->capacity);
}
void ShowBit(BitMap * bm)
{
if(bm==NULL)
{
return;
}
printf("==================================================================================
");
size_t i;
for(i=0;i< (bm->capacity/64);i++)
{
uint64_t tmp= bm->data[i];
size_t t;
for(t=0;t<64;t++)
{
if( tmp & (uint64_t)1<
Bloon_fliter.h
#pragma once
#include
#include"bitmap.h"
#define HashFuncMaxSize 2
#define BitMapCapcity 1024
typedef size_t (*HashFunc)(const char*);
typedef struct BloomFilter
{
BitMap bitmap;
HashFunc hash_func[HashFuncMaxSize];
}BloomFilter;
void BloomFilterInit(BloomFilter* bf);
void BloomFilterInsert(BloomFilter* bf, const char* str);
int BloomFilterIsExist(BloomFilter* bf, const char* str);
void BloomFilterDestroy(BloomFilter* bf);
// , .
Bloon_fliter.c
#include
#include "Bloon_filter.h"
#define TESH_HEADER printf("
=================%s================
",__FUNCTION__)
size_t SDBMHash(const char *str)
{
size_t hash = 0;
while (*str)
{
hash = hash + (*str++);
}
return hash ;
}
// RS Hash Function
size_t RSHash(const char *str)
{
size_t b = 3;
size_t a = 6;
size_t hash = 0;
while (*str)
{
hash = hash +a + (*str++);
a += b;
}
return hash;
}
void BloomFilterInit(BloomFilter* bf)
{
if(bf==NULL)
{
return;
}
BitMapInit(&bf->bitmap, BitMapCapcity);
bf-> hash_func[0]=SDBMHash;
bf-> hash_func[1]=RSHash;
}
void BloomFilterInsert(BloomFilter* bf, const char* str)
{
if(bf==NULL)
{
return;
}
size_t i;
for(i=0;ihash_func[i](str);
printf("ret =%lu
",ret);
BitMapSet(&bf->bitmap,ret);
}
}
int BloomFilterIsExist(BloomFilter* bf, const char* str)
{
if(bf==NULL)
{
return -1;
}
size_t i;
for(i=0;ihash_func[i](str);
printf("ret:%lu
", ret);
int result=BitMapTest(&bf->bitmap,ret);
if(result!=1)
{
return 0;
}
}
return 1;
}
void BloomFilterDestroy(BloomFilter* bf)
{
if(bf==NULL)
{
return;
}
BitMapDestroy(&bf->bitmap);
size_t i;
for(i=0;ihash_func[i]=NULL;
}
return;
}
// , .
void ShowBloon(BloomFilter* bf)
{
size_t i;
for(i=0;ihash_func[i]);
}
ShowSturct(&bf->bitmap);
ShowBit(&bf->bitmap);
}
void TestAll()
{
TESH_HEADER;
BloomFilter bf;
BloomFilterInit(&bf);
BloomFilterInsert(&bf,"a");
BloomFilterInsert(&bf,"TingHua");
BloomFilterInsert(&bf, "Paking");
int ret= BloomFilterIsExist(&bf, "TingHua");
printf("The result is %d
", ret);
ret=BloomFilterIsExist(&bf,"wo shi lianjie");
printf("The result is %d
", ret);
ret=BloomFilterIsExist(&bf,"Tinghua");
printf("The result is %d
", ret);
ShowBloon(&bf);
BloomFilterDestroy(&bf);
ShowBloon(&bf);
}
int main()
{
TestAll();
return 0;
}
Makefile
bloon_filter:bitmap.c Bloon_filter.c
gcc -o $@ $^
.PHONY:clean
clean:
rm bloon_filter
Test result
[abc123@localhost bloon_filter]$ ./bloon_filter
=================TestAll================
ret =97
ret =103
ret =688
ret =793
ret =602
ret =683
ret:688
ret:793
The result is 1
ret:1350
The result is 0
ret:720
The result is 0
Filterfunc[0]: 0x400a50
Filterfunc[1]: 0x400a8a
Bit Map Sturct
data : 0x75e010
capacity : 1024
==================================================================================
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
===========================================================================
Filterfunc[0]: (nil)
Filterfunc[1]: (nil)
Bit Map Sturct
data : (nil)
capacity : 0
==================================================================================
===========================================================================
[abc123@localhost bloon_filter]$ ./bloon_filter
=================TestAll================
ret =97
ret =103
ret =688
ret =793
ret =602
ret =683
ret:688
ret:793
The result is 1
ret:1350
The result is 0
ret:720
The result is 0
Filterfunc[0]: 0x400a50
Filterfunc[1]: 0x400a8a
Bit Map Sturct
data : 0x10f0010
capacity : 1024
==================================================================================
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
===========================================================================
Filterfunc[0]: (nil)
Filterfunc[1]: (nil)
Bit Map Sturct
data : (nil)
capacity : 0
==================================================================================
===========================================================================
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
ES6 Javascript의 루프키를 기반으로 어레이 그룹화 심판 -...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
