Repository navigation
Expand file tree
/
Copy pathbloom.c
More file actions
331 lines (258 loc) · 7.39 KB
/
Copy pathbloom.c
File metadata and controls
331 lines (258 loc) · 7.39 KB
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
/*
* Copyright (c) 2012-2022, Jyri J. Virkki
* All rights reserved.
*
* This file is under BSD license. See LICENSE file.
*/
/*
* Refer to bloom.h for documentation on the public interfaces.
*/
#include <assert.h>
#include <fcntl.h>
#include <math.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <unistd.h>
#include "bloom.h"
#include "murmurhash2.h"
#define MAKESTRING(n) STRING(n)
#define STRING(n) #n
#define BLOOM_MAGIC "libbloom2"
inline static int test_bit_set_bit(unsigned char * buf,
unsigned long int bit, int set_bit)
{
unsigned long int byte = bit >> 3;
unsigned char c = buf[byte]; // expensive memory access
unsigned char mask = 1 << (bit % 8ul);
if (c & mask) {
return 1;
} else {
if (set_bit) {
buf[byte] = c | mask;
}
return 0;
}
}
static int bloom_check_add(struct bloom * bloom,
const void * buffer, int len, int add)
{
if (bloom->ready == 0) {
printf("bloom at %p not initialized!\n", (void *)bloom);
return -1;
}
unsigned char hits = 0;
unsigned int a = murmurhash2(buffer, len, 0x9747b28c);
unsigned int b = murmurhash2(buffer, len, a);
unsigned long int x;
unsigned long int i;
for (i = 0; i < bloom->hashes; i++) {
x = (a + b*i) % bloom->bits;
if (test_bit_set_bit(bloom->bf, x, add)) {
hits++;
} else if (!add) {
// Don't care about the presence of all the bits. Just our own.
return 0;
}
}
if (hits == bloom->hashes) {
return 1; // 1 == element already in (or collision)
}
return 0;
}
// DEPRECATED - Please migrate to bloom_init2.
int bloom_init(struct bloom * bloom, int entries, double error)
{
return bloom_init2(bloom, (unsigned int)entries, error);
}
int bloom_init2(struct bloom * bloom, unsigned int entries, double error)
{
if (sizeof(unsigned long int) < 8) {
printf("error: libbloom will not function correctly because\n");
printf("sizeof(unsigned long int) == %ld\n", sizeof(unsigned long int));
exit(1);
}
memset(bloom, 0, sizeof(struct bloom));
if (entries < 1000 || error <= 0 || error >= 1) {
return 1;
}
bloom->entries = entries;
bloom->error = error;
double num = -log(bloom->error);
double denom = 0.480453013918201; // ln(2)^2
bloom->bpe = (num / denom);
long double dentries = (long double)entries;
long double allbits = dentries * bloom->bpe;
bloom->bits = (unsigned long int)allbits;
if (bloom->bits % 8) {
bloom->bytes = (bloom->bits / 8) + 1;
} else {
bloom->bytes = bloom->bits / 8;
}
bloom->hashes = (unsigned char)ceil(0.693147180559945 * bloom->bpe); // ln(2)
bloom->bf = (unsigned char *)calloc(bloom->bytes, sizeof(unsigned char));
if (bloom->bf == NULL) { // LCOV_EXCL_START
return 1;
} // LCOV_EXCL_STOP
bloom->ready = 1;
bloom->major = BLOOM_VERSION_MAJOR;
bloom->minor = BLOOM_VERSION_MINOR;
return 0;
}
int bloom_check(struct bloom * bloom, const void * buffer, int len)
{
return bloom_check_add(bloom, buffer, len, 0);
}
int bloom_add(struct bloom * bloom, const void * buffer, int len)
{
return bloom_check_add(bloom, buffer, len, 1);
}
void bloom_print(struct bloom * bloom)
{
printf("bloom at %p\n", (void *)bloom);
if (!bloom->ready) { printf(" *** NOT READY ***\n"); }
printf(" ->version = %d.%d\n", bloom->major, bloom->minor);
printf(" ->entries = %u\n", bloom->entries);
printf(" ->error = %f\n", bloom->error);
printf(" ->bits = %lu\n", bloom->bits);
printf(" ->bits per elem = %f\n", bloom->bpe);
printf(" ->bytes = %lu", bloom->bytes);
unsigned int KB = bloom->bytes / 1024;
unsigned int MB = KB / 1024;
printf(" (%u KB, %u MB)\n", KB, MB);
printf(" ->hash functions = %d\n", bloom->hashes);
}
void bloom_free(struct bloom * bloom)
{
if (bloom->ready) {
free(bloom->bf);
}
bloom->ready = 0;
}
int bloom_reset(struct bloom * bloom)
{
if (!bloom->ready) return 1;
memset(bloom->bf, 0, bloom->bytes);
return 0;
}
int bloom_save(struct bloom * bloom, char * filename)
{
if (filename == NULL || filename[0] == 0) {
return 1;
}
int fd = open(filename, O_WRONLY | O_CREAT, 0644);
if (fd < 0) {
return 1;
}
ssize_t out = write(fd, BLOOM_MAGIC, strlen(BLOOM_MAGIC));
if (out != strlen(BLOOM_MAGIC)) { goto save_error; } // LCOV_EXCL_LINE
uint16_t size = sizeof(struct bloom);
out = write(fd, &size, sizeof(uint16_t));
if (out != sizeof(uint16_t)) { goto save_error; } // LCOV_EXCL_LINE
out = write(fd, bloom, sizeof(struct bloom));
if (out != sizeof(struct bloom)) { goto save_error; } // LCOV_EXCL_LINE
out = write(fd, bloom->bf, bloom->bytes);
if (out != bloom->bytes) { goto save_error; } // LCOV_EXCL_LINE
close(fd);
return 0;
// LCOV_EXCL_START
save_error:
close(fd);
return 1;
// LCOV_EXCL_STOP
}
int bloom_load(struct bloom * bloom, char * filename)
{
int rv = 0;
if (filename == NULL || filename[0] == 0) { return 1; }
if (bloom == NULL) { return 2; }
memset(bloom, 0, sizeof(struct bloom));
int fd = open(filename, O_RDONLY);
if (fd < 0) { return 3; }
char line[30];
memset(line, 0, 30);
ssize_t in = read(fd, line, strlen(BLOOM_MAGIC));
if (in != strlen(BLOOM_MAGIC)) {
rv = 4;
goto load_error;
}
if (strncmp(line, BLOOM_MAGIC, strlen(BLOOM_MAGIC))) {
rv = 5;
goto load_error;
}
uint16_t size;
in = read(fd, &size, sizeof(uint16_t));
if (in != sizeof(uint16_t)) {
rv = 6;
goto load_error;
}
if (size != sizeof(struct bloom)) {
rv = 7;
goto load_error;
}
in = read(fd, bloom, sizeof(struct bloom));
if (in != sizeof(struct bloom)) {
rv = 8;
goto load_error;
}
bloom->bf = NULL;
if (bloom->major != BLOOM_VERSION_MAJOR) {
rv = 9;
goto load_error;
}
bloom->bf = (unsigned char *)malloc(bloom->bytes);
if (bloom->bf == NULL) { rv = 10; goto load_error; } // LCOV_EXCL_LINE
in = read(fd, bloom->bf, bloom->bytes);
if (in != bloom->bytes) {
rv = 11;
free(bloom->bf);
bloom->bf = NULL;
goto load_error;
}
close(fd);
return rv;
load_error:
close(fd);
bloom->ready = 0;
return rv;
}
int bloom_merge(struct bloom * bloom_dest, struct bloom * bloom_src)
{
if (bloom_dest->ready == 0) {
printf("bloom at %p not initialized!\n", (void *)bloom_dest);
return -1;
}
if (bloom_src->ready == 0) {
printf("bloom at %p not initialized!\n", (void *)bloom_src);
return -1;
}
if (bloom_dest->entries != bloom_src->entries) {
return 1;
}
if (bloom_dest->error != bloom_src->error) {
return 1;
}
if (bloom_dest->major != bloom_src->major) {
return 1;
}
if (bloom_dest->minor != bloom_src->minor) {
return 1;
}
// Not really possible if properly used but check anyway to avoid the
// possibility of buffer overruns.
if (bloom_dest->bytes != bloom_src->bytes) {
return 1; // LCOV_EXCL_LINE
}
unsigned long int p;
for (p = 0; p < bloom_dest->bytes; p++) {
bloom_dest->bf[p] |= bloom_src->bf[p];
}
return 0;
}
const char * bloom_version()
{
return MAKESTRING(BLOOM_VERSION);
}