IDFilter/BloomFilter.h at master · BlockLiu/IDFilter · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#ifndef BLOOMFILTER_H
#define BLOOMFILTER_H

#include <stdlib.h>
#include <string.h>

class BloomFilter{
	unsigned char *ary;
	int size;
public:
	BloomFilter(){}
	BloomFilter(int s);
	~BloomFilter();
	void create_ary(int s);
	void set_0(int pos);
	void set_1(int pos);
	void set(int pos, int length, unsigned char* val);
	int query(int pos);
	unsigned char* query(int pos, int length);
};

BloomFilter::BloomFilter(int s){
	create_ary(s);
}
void BloomFilter::create_ary(int s){
	size = s;
	ary = (unsigned char*)malloc((s - 1) / 8 + 1);
	memset(ary, 0, (s - 1) / 8 + 1);
}
BloomFilter::~BloomFilter(){
	free(ary);
}
void BloomFilter::set_0(int pos){
	pos = pos % size;
	ary[pos/8] &= ~((unsigned char)1 << (7 - (pos % 8)));
}
void BloomFilter::set_1(int pos){
	pos = pos % size;
	ary[pos/8] |= (unsigned char)1 << (7 - (pos % 8));
}
void BloomFilter::set(int pos, int length, unsigned char* val){
	for(int i = 0; i < length; ++i){
		int bit = (int)((val[i/8] & ((unsigned char)1 << (7 - (i %8)))) != 0);
		if(bit == 1)
			set_1(pos + i);
		else
			set_0(pos + i);
	}
}
int BloomFilter::query(int pos){
	pos = pos % size;
	return (int)((ary[pos/8] & ((unsigned char)1 << (7 - (pos % 8)))) != 0);
}
// remember to free str
unsigned char* BloomFilter::query(int pos, int length){
	unsigned char *str = (unsigned char*)malloc((length - 1) / 8 + 1);
	memset(str, 0, (length - 1) / 8 + 1);
	for(int i = 0; i < length; ++i){
		int offset = (pos + i) % size;
		int bit = (int)((ary[offset/8] & ((unsigned char)1 << (7 - (offset % 8)))) != 0);
		if(bit == 1)
			str[i / 8] |= (unsigned char)1 << (7 - (i % 8));
	}
	return str;
}


#endif