bloom: allow to pass in whether to set bits for strings
[fio.git] / lib / bloom.c
CommitLineData
652ae149
JA
1#include <stdlib.h>
2#include <inttypes.h>
3
4#include "bloom.h"
5#include "../hash.h"
265c0032 6#include "../minmax.h"
899834b5 7#include "../crc/xxhash.h"
f83ffd02 8#include "../crc/murmur3.h"
78583f91
JA
9#include "../crc/crc32c.h"
10#include "../crc/fnv.h"
652ae149
JA
11
12struct bloom {
13 uint64_t nentries;
14
15 uint32_t *map;
16};
17
18#define BITS_PER_INDEX (sizeof(uint32_t) * 8)
19#define BITS_INDEX_MASK (BITS_PER_INDEX - 1)
20
899834b5
JA
21struct bloom_hash {
22 unsigned int seed;
23 uint32_t (*fn)(const void *, uint32_t, uint32_t);
24};
25
78583f91
JA
26static uint32_t bloom_crc32c(const void *buf, uint32_t len, uint32_t seed)
27{
28 return fio_crc32c(buf, len);
29}
30
31static uint32_t bloom_fnv(const void *buf, uint32_t len, uint32_t seed)
32{
33 return fnv(buf, len, seed);
34}
35
36#define BLOOM_SEED 0x8989
37
a89ba4b1 38static struct bloom_hash hashes[] = {
899834b5 39 {
78583f91 40 .seed = BLOOM_SEED,
899834b5
JA
41 .fn = jhash,
42 },
43 {
78583f91 44 .seed = BLOOM_SEED,
899834b5
JA
45 .fn = XXH32,
46 },
47 {
78583f91 48 .seed = BLOOM_SEED,
9f0e365d 49 .fn = murmurhash3,
899834b5 50 },
78583f91
JA
51 {
52 .seed = BLOOM_SEED,
53 .fn = bloom_crc32c,
54 },
55 {
56 .seed = BLOOM_SEED,
57 .fn = bloom_fnv,
58 },
899834b5
JA
59};
60
78583f91 61#define N_HASHES 5
652ae149 62
265c0032
JA
63#define MIN_ENTRIES 1073741824UL
64
652ae149
JA
65struct bloom *bloom_new(uint64_t entries)
66{
67 struct bloom *b;
68 size_t no_uints;
69
78583f91
JA
70 crc32c_intel_probe();
71
652ae149
JA
72 b = malloc(sizeof(*b));
73 b->nentries = entries;
74 no_uints = (entries + BITS_PER_INDEX - 1) / BITS_PER_INDEX;
265c0032 75 no_uints = max((unsigned long) no_uints, MIN_ENTRIES);
652ae149
JA
76 b->map = calloc(no_uints, sizeof(uint32_t));
77 if (!b->map) {
78 free(b);
79 return NULL;
80 }
81
82 return b;
83}
84
85void bloom_free(struct bloom *b)
86{
87 free(b->map);
88 free(b);
89}
90
0a301e93 91static bool __bloom_check(struct bloom *b, const void *data, unsigned int len,
c0d75983 92 bool set)
652ae149 93{
899834b5 94 uint32_t hash[N_HASHES];
652ae149
JA
95 int i, was_set;
96
899834b5 97 for (i = 0; i < N_HASHES; i++) {
7790f697 98 hash[i] = hashes[i].fn(data, len, hashes[i].seed);
899834b5
JA
99 hash[i] = hash[i] % b->nentries;
100 }
652ae149
JA
101
102 was_set = 0;
103 for (i = 0; i < N_HASHES; i++) {
899834b5
JA
104 const unsigned int index = hash[i] / BITS_PER_INDEX;
105 const unsigned int bit = hash[i] & BITS_INDEX_MASK;
652ae149
JA
106
107 if (b->map[index] & (1U << bit))
108 was_set++;
109 if (set)
110 b->map[index] |= 1U << bit;
111 }
112
113 return was_set == N_HASHES;
114}
115
c0d75983 116bool bloom_set(struct bloom *b, uint32_t *data, unsigned int nwords)
652ae149 117{
7790f697 118 return __bloom_check(b, data, nwords * sizeof(uint32_t), true);
652ae149 119}
0a301e93 120
eb50727a
JA
121bool bloom_string(struct bloom *b, const char *data, unsigned int len,
122 bool set)
0a301e93 123{
eb50727a 124 return __bloom_check(b, data, len, set);
0a301e93 125}