# 一个简单的布隆过滤器 原

a
alex_wei

——摘自维基百科

simple_bf.h:

``````#ifndef _SIMPLE_BF_H_
#define _SIMPLE_BF_H_

#include <stdint.h>
#include <stdbool.h>

#define VEC_LEN (1024 * 1024 * 64 + 1)

#ifdef __cplusplus
extern "C" {
#endif

typedef struct _bf_vec {
uint64_t part[VEC_LEN];
} bf_vec_t;

extern bool bf_add(bf_vec_t *vec, const char *str);

extern bool bf_is_contains(bf_vec_t *vec, const char *str);

#ifndef likely
#define likely(x) __builtin_expect((x),1)
#endif

#ifndef unlikely
#define unlikely(x) __builtin_expect((x),0)
#endif

#ifdef __cplusplus
}
#endif

#endif``````
simple_bf.c:
``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "simple_bf.h"

/* return false means the arg bit is over the bit length of the arg vec,
* otherwise return true means successfully set the right bit.
* for simple, only consider about these two conditions */
static inline __attribute__((always_inline)) bool bf_set_bit(bf_vec_t *vec, uint64_t bit)
{
uint64_t part_cnt = bit / 64;
if (unlikely(part_cnt > VEC_LEN))
return false;
uint8_t mod = bit % 64;
vec->part[part_cnt] |= (1ULL << mod);
return true;
}

static inline __attribute__((always_inline)) bool bf_test_bit(bf_vec_t *vec, uint64_t bit)
{
uint64_t part_cnt = bit / 64;
if (unlikely(part_cnt > VEC_LEN))
return false;
uint8_t mod = bit % 64;
return ((vec->part[part_cnt] & (1ULL << mod)) != 0);
}

/* the seed vector and the BKDR hash function */
static uint32_t seeds[8] = {31, 131, 1313, 13131, 131313, 1313131, 13131313, 131313131};
static uint32_t bkdr_hash_modified(const char *str, uint32_t seed)
{
register uint32_t hash = 0;
uint32_t ch;
while ((ch = (uint32_t)*str++)) {
hash = hash * seed + ch;
}
return hash;
}

bool bf_add(bf_vec_t *vec, const char *str)
{
int i;
for (i = 0; i < 8; ++i) {
uint32_t val = bkdr_hash_modified(str, seeds[i]);
if (!bf_set_bit(vec, val))
return false;
}
return true;
}

bool bf_is_contains(bf_vec_t *vec, const char *str)
{
int i;
for (i = 0; i < 8; ++i) {
uint32_t val = bkdr_hash_modified(str, seeds[i]);
if (!bf_test_bit(vec, val))
return false;
}
return true;
}

#ifndef NDEBUG
int main1(int argc, char *argv[])
{
if (argc < 3) {
fprintf(stderr, "usage: bf as0 [as1 as2 ...] ts\n"
"as means string to add to the bloom filter\n"
"ts means the string to test if it is in the filter vector\n"
);
return 1;
}

bf_vec_t *vec = calloc(1, sizeof(bf_vec_t));
if (vec == NULL)
return 1;

int i;
for (i = 1; i < argc - 1; ++i) {
printf("add to bloom filter successed, string %s\n", argv[i]);
else
printf("add to bloom filter FAILED, string %s\n", argv[i]);
}
printf("------------------------------------------------------------------\n");
if (bf_is_contains(vec, argv[argc - 1]))
printf("test string %s is in bloom filter\n", argv[argc - 1]);
else
printf("test string %s is NOT in bloom filter\n", argv[argc - 1]);

free(vec);
return 0;
}

int main2(int argc, char *argv[])
{
if (argc != 3) {
fprintf(stderr, "usage: bf filename ts\n"
"file of filename contains the strings to be added\n"
"ts means the string to test if it is in the filter vector\n"
);
return 1;
}

bf_vec_t *vec = calloc(1, sizeof(bf_vec_t));
if (vec == NULL)
return 1;

char buf[128] = {0};
FILE *fp = fopen(argv[1], "rt");
if (fp == NULL) {
free(vec);
return 1;
}
while (fgets(buf, sizeof(buf), fp) != NULL) {
buf[strlen(buf) - 1] = '\0';
printf("add to bloom filter successed, string %s\n", buf);
else
printf("add to bloom filter FAILED, string %s\n", buf);
}

printf("------------------------------------------------------------------\n");
if (bf_is_contains(vec, argv[2]))
printf("test string %s is in bloom filter\n", argv[2]);
else
printf("test string %s is NOT in bloom filter\n", argv[2]);

free(vec);
return 0;
}

int main(int argc, char *argv[])
{
return main2(argc, argv);
}
#endif``````

``````typedef int (*bf_contains_cb)(void *data);
int bf_oper_if_contains(bf_vec_t *vec, const char *str, bf_contains_cb callback, void *data);``````

a

### alex_wei

2014/04/12
0
0

2013/01/25
6.1K
1

YoungChen__
08/30
0
0

1、什么情况下需要布隆过滤器？ 先来看几个比较常见的例子 字处理软件中，需要检查一个英语单词是否拼写正确 在 FBI，一个嫌疑人的名字是否已经在嫌疑名单上 在网络爬虫里，一个网址是否被访...

2017/06/18
0
0

2015/11/12
0
0

《阿里铁军》的读书笔记和读后感范文2600字

《阿里铁军》的读书笔记和读后感范文2600字： 在中国互联网，有一个流传很广的说法是，百度强在技术，腾讯强在产品，阿里强在运营。虽然发展到今天，已经不能再用这样简单的视角来看待这三个...

10分钟前
1
0

1 模式概要 1.1 简介 责任链模式为请求创建一个接收者对象链，每个接收者都包含对另一个接收者的引用，如果一个对象不能处理该请求，那么它会把请求传给下一个接收者，依此类推 责任链模式避...

25分钟前
1
0
【宇润日常疯测-004】JS 遍历数组如何快！快！快！

29分钟前
10
1
Linux系统如何定制History输出格式

Linux系统使用History命令来查看系统的运行记录，从而找出一些问题。但是History输出的数据中常常没有时间等信息。本文就来教大家Linux系统如何定制History输出格式。 　　具体方法如下 以r...

linuxprobe16
31分钟前
1
0
(一) pyhon 基础语法(数值 字符串 元组 列表 字典)

1、python的数据类型： 数值 字符串 列表 元组 字典； 数值类型包括； 整型(int) 长整型(long) 浮点型(float) 复数型 字符串； 可以通过type() 来查看是什么类型的； 注释：len()只支持 字符...

32分钟前
2
0