diff options
Diffstat (limited to 'src/lib/util/container_bloomfilter.c')
-rw-r--r-- | src/lib/util/container_bloomfilter.c | 806 |
1 files changed, 806 insertions, 0 deletions
diff --git a/src/lib/util/container_bloomfilter.c b/src/lib/util/container_bloomfilter.c new file mode 100644 index 000000000..7e4faaf3f --- /dev/null +++ b/src/lib/util/container_bloomfilter.c | |||
@@ -0,0 +1,806 @@ | |||
1 | /* | ||
2 | This file is part of GNUnet. | ||
3 | Copyright (C) 2001, 2002, 2003, 2004, 2006, 2008, 2011, 2012, 2018 GNUnet e.V. | ||
4 | |||
5 | GNUnet is free software: you can redistribute it and/or modify it | ||
6 | under the terms of the GNU Affero General Public License as published | ||
7 | by the Free Software Foundation, either version 3 of the License, | ||
8 | or (at your option) any later version. | ||
9 | |||
10 | GNUnet is distributed in the hope that it will be useful, but | ||
11 | WITHOUT ANY WARRANTY; without even the implied warranty of | ||
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | ||
13 | Affero General Public License for more details. | ||
14 | |||
15 | You should have received a copy of the GNU Affero General Public License | ||
16 | along with this program. If not, see <http://www.gnu.org/licenses/>. | ||
17 | |||
18 | SPDX-License-Identifier: AGPL3.0-or-later | ||
19 | */ | ||
20 | /** | ||
21 | * @file util/container_bloomfilter.c | ||
22 | * @brief data structure used to reduce disk accesses. | ||
23 | * | ||
24 | * The idea basically: Create a signature for each element in the | ||
25 | * database. Add those signatures to a bit array. When doing a lookup, | ||
26 | * check if the bit array matches the signature of the requested | ||
27 | * element. If yes, address the disk, otherwise return 'not found'. | ||
28 | * | ||
29 | * A property of the bloom filter is that sometimes we will have | ||
30 | * a match even if the element is not on the disk (then we do | ||
31 | * an unnecessary disk access), but what's most important is that | ||
32 | * we never get a single "false negative". | ||
33 | * | ||
34 | * To be able to delete entries from the bloom filter, we maintain | ||
35 | * a 4 bit counter in the file on the drive (we still use only one | ||
36 | * bit in memory). | ||
37 | * | ||
38 | * @author Igor Wronsky | ||
39 | * @author Christian Grothoff | ||
40 | */ | ||
41 | |||
42 | |||
43 | #include "platform.h" | ||
44 | #include "gnunet_util_lib.h" | ||
45 | |||
46 | #define LOG(kind, ...) \ | ||
47 | GNUNET_log_from (kind, "util-container-bloomfilter", __VA_ARGS__) | ||
48 | |||
49 | #define LOG_STRERROR(kind, syscall) \ | ||
50 | GNUNET_log_from_strerror (kind, "util-container-bloomfilter", syscall) | ||
51 | |||
52 | #define LOG_STRERROR_FILE(kind, syscall, filename) \ | ||
53 | GNUNET_log_from_strerror_file (kind, \ | ||
54 | "util-container-bloomfilter", \ | ||
55 | syscall, \ | ||
56 | filename) | ||
57 | |||
58 | struct GNUNET_CONTAINER_BloomFilter | ||
59 | { | ||
60 | /** | ||
61 | * The actual bloomfilter bit array | ||
62 | */ | ||
63 | char *bitArray; | ||
64 | |||
65 | /** | ||
66 | * Filename of the filter | ||
67 | */ | ||
68 | char *filename; | ||
69 | |||
70 | /** | ||
71 | * The bit counter file on disk | ||
72 | */ | ||
73 | struct GNUNET_DISK_FileHandle *fh; | ||
74 | |||
75 | /** | ||
76 | * How many bits we set for each stored element | ||
77 | */ | ||
78 | unsigned int addressesPerElement; | ||
79 | |||
80 | /** | ||
81 | * Size of bitArray in bytes | ||
82 | */ | ||
83 | size_t bitArraySize; | ||
84 | }; | ||
85 | |||
86 | |||
87 | size_t | ||
88 | GNUNET_CONTAINER_bloomfilter_get_element_addresses ( | ||
89 | const struct GNUNET_CONTAINER_BloomFilter *bf) | ||
90 | { | ||
91 | if (bf == NULL) | ||
92 | return 0; | ||
93 | return bf->addressesPerElement; | ||
94 | } | ||
95 | |||
96 | |||
97 | size_t | ||
98 | GNUNET_CONTAINER_bloomfilter_get_size ( | ||
99 | const struct GNUNET_CONTAINER_BloomFilter *bf) | ||
100 | { | ||
101 | if (bf == NULL) | ||
102 | return 0; | ||
103 | return bf->bitArraySize; | ||
104 | } | ||
105 | |||
106 | |||
107 | struct GNUNET_CONTAINER_BloomFilter * | ||
108 | GNUNET_CONTAINER_bloomfilter_copy ( | ||
109 | const struct GNUNET_CONTAINER_BloomFilter *bf) | ||
110 | { | ||
111 | return GNUNET_CONTAINER_bloomfilter_init (bf->bitArray, | ||
112 | bf->bitArraySize, | ||
113 | bf->addressesPerElement); | ||
114 | } | ||
115 | |||
116 | |||
117 | /** | ||
118 | * Sets a bit active in the bitArray. Increment bit-specific | ||
119 | * usage counter on disk only if below 4bit max (==15). | ||
120 | * | ||
121 | * @param bitArray memory area to set the bit in | ||
122 | * @param bitIdx which bit to set | ||
123 | */ | ||
124 | static void | ||
125 | setBit (char *bitArray, | ||
126 | unsigned int bitIdx) | ||
127 | { | ||
128 | size_t arraySlot; | ||
129 | unsigned int targetBit; | ||
130 | |||
131 | arraySlot = bitIdx / 8; | ||
132 | targetBit = (1L << (bitIdx % 8)); | ||
133 | bitArray[arraySlot] |= targetBit; | ||
134 | } | ||
135 | |||
136 | |||
137 | /** | ||
138 | * Clears a bit from bitArray. Bit is cleared from the array | ||
139 | * only if the respective usage counter on the disk hits/is zero. | ||
140 | * | ||
141 | * @param bitArray memory area to set the bit in | ||
142 | * @param bitIdx which bit to unset | ||
143 | */ | ||
144 | static void | ||
145 | clearBit (char *bitArray, unsigned int bitIdx) | ||
146 | { | ||
147 | size_t slot; | ||
148 | unsigned int targetBit; | ||
149 | |||
150 | slot = bitIdx / 8; | ||
151 | targetBit = (1L << (bitIdx % 8)); | ||
152 | bitArray[slot] = bitArray[slot] & (~targetBit); | ||
153 | } | ||
154 | |||
155 | |||
156 | /** | ||
157 | * Checks if a bit is active in the bitArray | ||
158 | * | ||
159 | * @param bitArray memory area to set the bit in | ||
160 | * @param bitIdx which bit to test | ||
161 | * @return true if the bit is set, false if not. | ||
162 | */ | ||
163 | static bool | ||
164 | testBit (char *bitArray, | ||
165 | unsigned int bitIdx) | ||
166 | { | ||
167 | size_t slot; | ||
168 | unsigned int targetBit; | ||
169 | |||
170 | slot = bitIdx / 8; | ||
171 | targetBit = (1L << (bitIdx % 8)); | ||
172 | if (bitArray[slot] & targetBit) | ||
173 | return true; | ||
174 | return false; | ||
175 | } | ||
176 | |||
177 | |||
178 | /** | ||
179 | * Sets a bit active in the bitArray and increments | ||
180 | * bit-specific usage counter on disk (but only if | ||
181 | * the counter was below 4 bit max (==15)). | ||
182 | * | ||
183 | * @param bitArray memory area to set the bit in | ||
184 | * @param bitIdx which bit to test | ||
185 | * @param fh A file to keep the 4 bit address usage counters in | ||
186 | */ | ||
187 | static void | ||
188 | incrementBit (char *bitArray, | ||
189 | unsigned int bitIdx, | ||
190 | const struct GNUNET_DISK_FileHandle *fh) | ||
191 | { | ||
192 | off_t fileSlot; | ||
193 | unsigned char value; | ||
194 | unsigned int high; | ||
195 | unsigned int low; | ||
196 | unsigned int targetLoc; | ||
197 | |||
198 | setBit (bitArray, | ||
199 | bitIdx); | ||
200 | if (GNUNET_DISK_handle_invalid (fh)) | ||
201 | return; | ||
202 | /* Update the counter file on disk */ | ||
203 | fileSlot = bitIdx / 2; | ||
204 | targetLoc = bitIdx % 2; | ||
205 | |||
206 | GNUNET_assert (fileSlot == | ||
207 | GNUNET_DISK_file_seek (fh, fileSlot, GNUNET_DISK_SEEK_SET)); | ||
208 | if (1 != GNUNET_DISK_file_read (fh, &value, 1)) | ||
209 | value = 0; | ||
210 | low = value & 0xF; | ||
211 | high = (value & (~0xF)) >> 4; | ||
212 | |||
213 | if (targetLoc == 0) | ||
214 | { | ||
215 | if (low < 0xF) | ||
216 | low++; | ||
217 | } | ||
218 | else | ||
219 | { | ||
220 | if (high < 0xF) | ||
221 | high++; | ||
222 | } | ||
223 | value = ((high << 4) | low); | ||
224 | GNUNET_assert (fileSlot == | ||
225 | GNUNET_DISK_file_seek (fh, fileSlot, GNUNET_DISK_SEEK_SET)); | ||
226 | GNUNET_assert (1 == GNUNET_DISK_file_write (fh, &value, 1)); | ||
227 | } | ||
228 | |||
229 | |||
230 | /** | ||
231 | * Clears a bit from bitArray if the respective usage | ||
232 | * counter on the disk hits/is zero. | ||
233 | * | ||
234 | * @param bitArray memory area to set the bit in | ||
235 | * @param bitIdx which bit to test | ||
236 | * @param fh A file to keep the 4bit address usage counters in | ||
237 | */ | ||
238 | static void | ||
239 | decrementBit (char *bitArray, | ||
240 | unsigned int bitIdx, | ||
241 | const struct GNUNET_DISK_FileHandle *fh) | ||
242 | { | ||
243 | off_t fileslot; | ||
244 | unsigned char value; | ||
245 | unsigned int high; | ||
246 | unsigned int low; | ||
247 | unsigned int targetLoc; | ||
248 | |||
249 | if (GNUNET_DISK_handle_invalid (fh)) | ||
250 | return; /* cannot decrement! */ | ||
251 | /* Each char slot in the counter file holds two 4 bit counters */ | ||
252 | fileslot = bitIdx / 2; | ||
253 | targetLoc = bitIdx % 2; | ||
254 | if (GNUNET_SYSERR == | ||
255 | GNUNET_DISK_file_seek (fh, fileslot, GNUNET_DISK_SEEK_SET)) | ||
256 | { | ||
257 | GNUNET_log_strerror (GNUNET_ERROR_TYPE_ERROR, "seek"); | ||
258 | return; | ||
259 | } | ||
260 | if (1 != GNUNET_DISK_file_read (fh, &value, 1)) | ||
261 | value = 0; | ||
262 | low = value & 0xF; | ||
263 | high = (value & 0xF0) >> 4; | ||
264 | |||
265 | /* decrement, but once we have reached the max, never go back! */ | ||
266 | if (targetLoc == 0) | ||
267 | { | ||
268 | if ((low > 0) && (low < 0xF)) | ||
269 | low--; | ||
270 | if (low == 0) | ||
271 | { | ||
272 | clearBit (bitArray, bitIdx); | ||
273 | } | ||
274 | } | ||
275 | else | ||
276 | { | ||
277 | if ((high > 0) && (high < 0xF)) | ||
278 | high--; | ||
279 | if (high == 0) | ||
280 | { | ||
281 | clearBit (bitArray, bitIdx); | ||
282 | } | ||
283 | } | ||
284 | value = ((high << 4) | low); | ||
285 | if (GNUNET_SYSERR == | ||
286 | GNUNET_DISK_file_seek (fh, fileslot, GNUNET_DISK_SEEK_SET)) | ||
287 | { | ||
288 | GNUNET_log_strerror (GNUNET_ERROR_TYPE_ERROR, "seek"); | ||
289 | return; | ||
290 | } | ||
291 | GNUNET_assert (1 == GNUNET_DISK_file_write (fh, &value, 1)); | ||
292 | } | ||
293 | |||
294 | |||
295 | #define BUFFSIZE 65536 | ||
296 | |||
297 | /** | ||
298 | * Creates a file filled with zeroes | ||
299 | * | ||
300 | * @param fh the file handle | ||
301 | * @param size the size of the file | ||
302 | * @return #GNUNET_OK if created ok, #GNUNET_SYSERR otherwise | ||
303 | */ | ||
304 | static enum GNUNET_GenericReturnValue | ||
305 | make_empty_file (const struct GNUNET_DISK_FileHandle *fh, | ||
306 | size_t size) | ||
307 | { | ||
308 | char buffer[BUFFSIZE]; | ||
309 | size_t bytesleft = size; | ||
310 | int res = 0; | ||
311 | |||
312 | if (GNUNET_DISK_handle_invalid (fh)) | ||
313 | return GNUNET_SYSERR; | ||
314 | memset (buffer, 0, sizeof(buffer)); | ||
315 | GNUNET_DISK_file_seek (fh, 0, GNUNET_DISK_SEEK_SET); | ||
316 | while (bytesleft > 0) | ||
317 | { | ||
318 | if (bytesleft > sizeof(buffer)) | ||
319 | { | ||
320 | res = GNUNET_DISK_file_write (fh, buffer, sizeof(buffer)); | ||
321 | if (res >= 0) | ||
322 | bytesleft -= res; | ||
323 | } | ||
324 | else | ||
325 | { | ||
326 | res = GNUNET_DISK_file_write (fh, buffer, bytesleft); | ||
327 | if (res >= 0) | ||
328 | bytesleft -= res; | ||
329 | } | ||
330 | if (GNUNET_SYSERR == res) | ||
331 | return GNUNET_SYSERR; | ||
332 | } | ||
333 | return GNUNET_OK; | ||
334 | } | ||
335 | |||
336 | |||
337 | /* ************** GNUNET_CONTAINER_BloomFilter iterator ********* */ | ||
338 | |||
339 | /** | ||
340 | * Iterator (callback) method to be called by the | ||
341 | * bloomfilter iterator on each bit that is to be | ||
342 | * set or tested for the key. | ||
343 | * | ||
344 | * @param cls closure | ||
345 | * @param bf the filter to manipulate | ||
346 | * @param bit the current bit | ||
347 | * @return #GNUNET_YES to continue, #GNUNET_NO to stop early | ||
348 | */ | ||
349 | typedef enum GNUNET_GenericReturnValue | ||
350 | (*BitIterator)(void *cls, | ||
351 | const struct GNUNET_CONTAINER_BloomFilter *bf, | ||
352 | unsigned int bit); | ||
353 | |||
354 | |||
355 | /** | ||
356 | * Call an iterator for each bit that the bloomfilter | ||
357 | * must test or set for this element. | ||
358 | * | ||
359 | * @param bf the filter | ||
360 | * @param callback the method to call | ||
361 | * @param arg extra argument to callback | ||
362 | * @param key the key for which we iterate over the BF bits | ||
363 | */ | ||
364 | static void | ||
365 | iterateBits (const struct GNUNET_CONTAINER_BloomFilter *bf, | ||
366 | BitIterator callback, | ||
367 | void *arg, | ||
368 | const struct GNUNET_HashCode *key) | ||
369 | { | ||
370 | struct GNUNET_HashCode tmp = *key; | ||
371 | int bitCount; | ||
372 | unsigned int slot = 0; | ||
373 | |||
374 | bitCount = bf->addressesPerElement; | ||
375 | GNUNET_assert (bf->bitArraySize > 0); | ||
376 | GNUNET_assert (bf->bitArraySize * 8LL > bf->bitArraySize); | ||
377 | while (bitCount > 0) | ||
378 | { | ||
379 | while ( (0 != bitCount) && | ||
380 | (slot < (sizeof(struct GNUNET_HashCode) / sizeof(uint32_t))) ) | ||
381 | { | ||
382 | if (GNUNET_YES != | ||
383 | callback (arg, | ||
384 | bf, | ||
385 | ntohl ((((uint32_t *) &tmp)[slot])) | ||
386 | % ((bf->bitArraySize * 8LL)))) | ||
387 | return; | ||
388 | slot++; | ||
389 | bitCount--; | ||
390 | } | ||
391 | if (0 == bitCount) | ||
392 | break; | ||
393 | GNUNET_CRYPTO_hash (&tmp, | ||
394 | sizeof(tmp), | ||
395 | &tmp); | ||
396 | slot = 0; | ||
397 | } | ||
398 | } | ||
399 | |||
400 | |||
401 | /** | ||
402 | * Callback: increment bit | ||
403 | * | ||
404 | * @param cls pointer to writeable form of bf | ||
405 | * @param bf the filter to manipulate | ||
406 | * @param bit the bit to increment | ||
407 | * @return #GNUNET_YES | ||
408 | */ | ||
409 | static enum GNUNET_GenericReturnValue | ||
410 | incrementBitCallback (void *cls, | ||
411 | const struct GNUNET_CONTAINER_BloomFilter *bf, | ||
412 | unsigned int bit) | ||
413 | { | ||
414 | struct GNUNET_CONTAINER_BloomFilter *b = cls; | ||
415 | |||
416 | incrementBit (b->bitArray, | ||
417 | bit, | ||
418 | bf->fh); | ||
419 | return GNUNET_YES; | ||
420 | } | ||
421 | |||
422 | |||
423 | /** | ||
424 | * Callback: decrement bit | ||
425 | * | ||
426 | * @param cls pointer to writeable form of bf | ||
427 | * @param bf the filter to manipulate | ||
428 | * @param bit the bit to decrement | ||
429 | * @return #GNUNET_YES | ||
430 | */ | ||
431 | static enum GNUNET_GenericReturnValue | ||
432 | decrementBitCallback (void *cls, | ||
433 | const struct GNUNET_CONTAINER_BloomFilter *bf, | ||
434 | unsigned int bit) | ||
435 | { | ||
436 | struct GNUNET_CONTAINER_BloomFilter *b = cls; | ||
437 | |||
438 | decrementBit (b->bitArray, | ||
439 | bit, | ||
440 | bf->fh); | ||
441 | return GNUNET_YES; | ||
442 | } | ||
443 | |||
444 | |||
445 | /** | ||
446 | * Callback: test if all bits are set | ||
447 | * | ||
448 | * @param cls pointer set to false if bit is not set | ||
449 | * @param bf the filter | ||
450 | * @param bit the bit to test | ||
451 | * @return #GNUNET_YES if the bit is set, #GNUNET_NO if not | ||
452 | */ | ||
453 | static enum GNUNET_GenericReturnValue | ||
454 | testBitCallback (void *cls, | ||
455 | const struct GNUNET_CONTAINER_BloomFilter *bf, | ||
456 | unsigned int bit) | ||
457 | { | ||
458 | bool *arg = cls; | ||
459 | |||
460 | if (! testBit (bf->bitArray, bit)) | ||
461 | { | ||
462 | *arg = false; | ||
463 | return GNUNET_NO; | ||
464 | } | ||
465 | return GNUNET_YES; | ||
466 | } | ||
467 | |||
468 | |||
469 | /* *********************** INTERFACE **************** */ | ||
470 | |||
471 | struct GNUNET_CONTAINER_BloomFilter * | ||
472 | GNUNET_CONTAINER_bloomfilter_load (const char *filename, | ||
473 | size_t size, | ||
474 | unsigned int k) | ||
475 | { | ||
476 | struct GNUNET_CONTAINER_BloomFilter *bf; | ||
477 | char *rbuff; | ||
478 | off_t pos; | ||
479 | int i; | ||
480 | size_t ui; | ||
481 | off_t fsize; | ||
482 | int must_read; | ||
483 | |||
484 | GNUNET_assert (NULL != filename); | ||
485 | if ((k == 0) || (size == 0)) | ||
486 | return NULL; | ||
487 | if (size < BUFFSIZE) | ||
488 | size = BUFFSIZE; | ||
489 | ui = 1; | ||
490 | while ((ui < size) && (ui * 2 > ui)) | ||
491 | ui *= 2; | ||
492 | size = ui; /* make sure it's a power of 2 */ | ||
493 | |||
494 | bf = GNUNET_new (struct GNUNET_CONTAINER_BloomFilter); | ||
495 | /* Try to open a bloomfilter file */ | ||
496 | if (GNUNET_YES == GNUNET_DISK_file_test (filename)) | ||
497 | bf->fh = GNUNET_DISK_file_open (filename, | ||
498 | GNUNET_DISK_OPEN_READWRITE, | ||
499 | GNUNET_DISK_PERM_USER_READ | ||
500 | | GNUNET_DISK_PERM_USER_WRITE); | ||
501 | if (NULL != bf->fh) | ||
502 | { | ||
503 | /* file existed, try to read it! */ | ||
504 | must_read = GNUNET_YES; | ||
505 | if (GNUNET_OK != | ||
506 | GNUNET_DISK_file_handle_size (bf->fh, | ||
507 | &fsize)) | ||
508 | { | ||
509 | GNUNET_DISK_file_close (bf->fh); | ||
510 | GNUNET_free (bf); | ||
511 | return NULL; | ||
512 | } | ||
513 | if (0 == fsize) | ||
514 | { | ||
515 | /* found existing empty file, just overwrite */ | ||
516 | if (GNUNET_OK != | ||
517 | make_empty_file (bf->fh, | ||
518 | size * 4LL)) | ||
519 | { | ||
520 | GNUNET_log_strerror (GNUNET_ERROR_TYPE_WARNING, | ||
521 | "write"); | ||
522 | GNUNET_DISK_file_close (bf->fh); | ||
523 | GNUNET_free (bf); | ||
524 | return NULL; | ||
525 | } | ||
526 | } | ||
527 | else if (fsize != ((off_t) size) * 4LL) | ||
528 | { | ||
529 | GNUNET_log ( | ||
530 | GNUNET_ERROR_TYPE_ERROR, | ||
531 | _ ( | ||
532 | "Size of file on disk is incorrect for this Bloom filter (want %llu, have %llu)\n"), | ||
533 | (unsigned long long) (size * 4LL), | ||
534 | (unsigned long long) fsize); | ||
535 | GNUNET_DISK_file_close (bf->fh); | ||
536 | GNUNET_free (bf); | ||
537 | return NULL; | ||
538 | } | ||
539 | } | ||
540 | else | ||
541 | { | ||
542 | /* file did not exist, don't read, just create */ | ||
543 | must_read = GNUNET_NO; | ||
544 | bf->fh = GNUNET_DISK_file_open (filename, | ||
545 | GNUNET_DISK_OPEN_CREATE | ||
546 | | GNUNET_DISK_OPEN_READWRITE, | ||
547 | GNUNET_DISK_PERM_USER_READ | ||
548 | | GNUNET_DISK_PERM_USER_WRITE); | ||
549 | if (NULL == bf->fh) | ||
550 | { | ||
551 | GNUNET_free (bf); | ||
552 | return NULL; | ||
553 | } | ||
554 | if (GNUNET_OK != make_empty_file (bf->fh, size * 4LL)) | ||
555 | { | ||
556 | GNUNET_log_strerror (GNUNET_ERROR_TYPE_WARNING, "write"); | ||
557 | GNUNET_DISK_file_close (bf->fh); | ||
558 | GNUNET_free (bf); | ||
559 | return NULL; | ||
560 | } | ||
561 | } | ||
562 | bf->filename = GNUNET_strdup (filename); | ||
563 | /* Alloc block */ | ||
564 | bf->bitArray = GNUNET_malloc_large (size); | ||
565 | if (NULL == bf->bitArray) | ||
566 | { | ||
567 | if (NULL != bf->fh) | ||
568 | GNUNET_DISK_file_close (bf->fh); | ||
569 | GNUNET_free (bf->filename); | ||
570 | GNUNET_free (bf); | ||
571 | return NULL; | ||
572 | } | ||
573 | bf->bitArraySize = size; | ||
574 | bf->addressesPerElement = k; | ||
575 | if (GNUNET_YES != must_read) | ||
576 | return bf; /* already done! */ | ||
577 | /* Read from the file what bits we can */ | ||
578 | rbuff = GNUNET_malloc (BUFFSIZE); | ||
579 | pos = 0; | ||
580 | while (pos < ((off_t) size) * 8LL) | ||
581 | { | ||
582 | int res; | ||
583 | |||
584 | res = GNUNET_DISK_file_read (bf->fh, rbuff, BUFFSIZE); | ||
585 | if (res == -1) | ||
586 | { | ||
587 | LOG_STRERROR_FILE (GNUNET_ERROR_TYPE_WARNING, "read", bf->filename); | ||
588 | GNUNET_free (rbuff); | ||
589 | GNUNET_free (bf->filename); | ||
590 | GNUNET_DISK_file_close (bf->fh); | ||
591 | GNUNET_free (bf); | ||
592 | return NULL; | ||
593 | } | ||
594 | if (res == 0) | ||
595 | break; /* is ok! we just did not use that many bits yet */ | ||
596 | for (i = 0; i < res; i++) | ||
597 | { | ||
598 | if ((rbuff[i] & 0x0F) != 0) | ||
599 | setBit (bf->bitArray, pos + i * 2); | ||
600 | if ((rbuff[i] & 0xF0) != 0) | ||
601 | setBit (bf->bitArray, pos + i * 2 + 1); | ||
602 | } | ||
603 | if (res < BUFFSIZE) | ||
604 | break; | ||
605 | pos += BUFFSIZE * 2; /* 2 bits per byte in the buffer */ | ||
606 | } | ||
607 | GNUNET_free (rbuff); | ||
608 | return bf; | ||
609 | } | ||
610 | |||
611 | |||
612 | struct GNUNET_CONTAINER_BloomFilter * | ||
613 | GNUNET_CONTAINER_bloomfilter_init (const char *data, | ||
614 | size_t size, | ||
615 | unsigned int k) | ||
616 | { | ||
617 | struct GNUNET_CONTAINER_BloomFilter *bf; | ||
618 | |||
619 | if ((0 == k) || (0 == size)) | ||
620 | return NULL; | ||
621 | bf = GNUNET_new (struct GNUNET_CONTAINER_BloomFilter); | ||
622 | bf->filename = NULL; | ||
623 | bf->fh = NULL; | ||
624 | bf->bitArray = GNUNET_malloc_large (size); | ||
625 | if (NULL == bf->bitArray) | ||
626 | { | ||
627 | GNUNET_free (bf); | ||
628 | return NULL; | ||
629 | } | ||
630 | bf->bitArraySize = size; | ||
631 | bf->addressesPerElement = k; | ||
632 | if (NULL != data) | ||
633 | GNUNET_memcpy (bf->bitArray, data, size); | ||
634 | return bf; | ||
635 | } | ||
636 | |||
637 | |||
638 | enum GNUNET_GenericReturnValue | ||
639 | GNUNET_CONTAINER_bloomfilter_get_raw_data ( | ||
640 | const struct GNUNET_CONTAINER_BloomFilter *bf, | ||
641 | char *data, | ||
642 | size_t size) | ||
643 | { | ||
644 | if (NULL == bf) | ||
645 | return GNUNET_SYSERR; | ||
646 | if (bf->bitArraySize != size) | ||
647 | return GNUNET_SYSERR; | ||
648 | GNUNET_memcpy (data, bf->bitArray, size); | ||
649 | return GNUNET_OK; | ||
650 | } | ||
651 | |||
652 | |||
653 | void | ||
654 | GNUNET_CONTAINER_bloomfilter_free (struct GNUNET_CONTAINER_BloomFilter *bf) | ||
655 | { | ||
656 | if (NULL == bf) | ||
657 | return; | ||
658 | if (bf->fh != NULL) | ||
659 | GNUNET_DISK_file_close (bf->fh); | ||
660 | GNUNET_free (bf->filename); | ||
661 | GNUNET_free (bf->bitArray); | ||
662 | GNUNET_free (bf); | ||
663 | } | ||
664 | |||
665 | |||
666 | void | ||
667 | GNUNET_CONTAINER_bloomfilter_clear (struct GNUNET_CONTAINER_BloomFilter *bf) | ||
668 | { | ||
669 | if (NULL == bf) | ||
670 | return; | ||
671 | |||
672 | memset (bf->bitArray, 0, bf->bitArraySize); | ||
673 | if (bf->filename != NULL) | ||
674 | make_empty_file (bf->fh, bf->bitArraySize * 4LL); | ||
675 | } | ||
676 | |||
677 | |||
678 | bool | ||
679 | GNUNET_CONTAINER_bloomfilter_test ( | ||
680 | const struct GNUNET_CONTAINER_BloomFilter *bf, | ||
681 | const struct GNUNET_HashCode *e) | ||
682 | { | ||
683 | bool res; | ||
684 | |||
685 | if (NULL == bf) | ||
686 | return true; | ||
687 | res = true; | ||
688 | iterateBits (bf, | ||
689 | &testBitCallback, | ||
690 | &res, | ||
691 | e); | ||
692 | return res; | ||
693 | } | ||
694 | |||
695 | |||
696 | void | ||
697 | GNUNET_CONTAINER_bloomfilter_add (struct GNUNET_CONTAINER_BloomFilter *bf, | ||
698 | const struct GNUNET_HashCode *e) | ||
699 | { | ||
700 | if (NULL == bf) | ||
701 | return; | ||
702 | iterateBits (bf, | ||
703 | &incrementBitCallback, | ||
704 | bf, | ||
705 | e); | ||
706 | } | ||
707 | |||
708 | |||
709 | enum GNUNET_GenericReturnValue | ||
710 | GNUNET_CONTAINER_bloomfilter_or (struct GNUNET_CONTAINER_BloomFilter *bf, | ||
711 | const char *data, | ||
712 | size_t size) | ||
713 | { | ||
714 | unsigned int i; | ||
715 | unsigned int n; | ||
716 | unsigned long long *fc; | ||
717 | const unsigned long long *dc; | ||
718 | |||
719 | if (NULL == bf) | ||
720 | return GNUNET_YES; | ||
721 | if (bf->bitArraySize != size) | ||
722 | return GNUNET_SYSERR; | ||
723 | fc = (unsigned long long *) bf->bitArray; | ||
724 | dc = (const unsigned long long *) data; | ||
725 | n = size / sizeof(unsigned long long); | ||
726 | |||
727 | for (i = 0; i < n; i++) | ||
728 | fc[i] |= dc[i]; | ||
729 | for (i = n * sizeof(unsigned long long); i < size; i++) | ||
730 | bf->bitArray[i] |= data[i]; | ||
731 | return GNUNET_OK; | ||
732 | } | ||
733 | |||
734 | |||
735 | enum GNUNET_GenericReturnValue | ||
736 | GNUNET_CONTAINER_bloomfilter_or2 ( | ||
737 | struct GNUNET_CONTAINER_BloomFilter *bf, | ||
738 | const struct GNUNET_CONTAINER_BloomFilter *to_or) | ||
739 | { | ||
740 | unsigned int i; | ||
741 | unsigned int n; | ||
742 | unsigned long long *fc; | ||
743 | const unsigned long long *dc; | ||
744 | size_t size; | ||
745 | |||
746 | if (NULL == bf) | ||
747 | return GNUNET_OK; | ||
748 | if (bf->bitArraySize != to_or->bitArraySize) | ||
749 | { | ||
750 | GNUNET_break (0); | ||
751 | return GNUNET_SYSERR; | ||
752 | } | ||
753 | size = bf->bitArraySize; | ||
754 | fc = (unsigned long long *) bf->bitArray; | ||
755 | dc = (const unsigned long long *) to_or->bitArray; | ||
756 | n = size / sizeof(unsigned long long); | ||
757 | |||
758 | for (i = 0; i < n; i++) | ||
759 | fc[i] |= dc[i]; | ||
760 | for (i = n * sizeof(unsigned long long); i < size; i++) | ||
761 | bf->bitArray[i] |= to_or->bitArray[i]; | ||
762 | return GNUNET_OK; | ||
763 | } | ||
764 | |||
765 | |||
766 | void | ||
767 | GNUNET_CONTAINER_bloomfilter_remove (struct GNUNET_CONTAINER_BloomFilter *bf, | ||
768 | const struct GNUNET_HashCode *e) | ||
769 | { | ||
770 | if (NULL == bf) | ||
771 | return; | ||
772 | if (NULL == bf->filename) | ||
773 | return; | ||
774 | iterateBits (bf, | ||
775 | &decrementBitCallback, | ||
776 | bf, | ||
777 | e); | ||
778 | } | ||
779 | |||
780 | |||
781 | void | ||
782 | GNUNET_CONTAINER_bloomfilter_resize (struct GNUNET_CONTAINER_BloomFilter *bf, | ||
783 | GNUNET_CONTAINER_HashCodeIterator iterator, | ||
784 | void *iterator_cls, | ||
785 | size_t size, | ||
786 | unsigned int k) | ||
787 | { | ||
788 | struct GNUNET_HashCode hc; | ||
789 | unsigned int i; | ||
790 | |||
791 | GNUNET_free (bf->bitArray); | ||
792 | i = 1; | ||
793 | while (i < size) | ||
794 | i *= 2; | ||
795 | size = i; /* make sure it's a power of 2 */ | ||
796 | bf->addressesPerElement = k; | ||
797 | bf->bitArraySize = size; | ||
798 | bf->bitArray = GNUNET_malloc (size); | ||
799 | if (NULL != bf->filename) | ||
800 | make_empty_file (bf->fh, bf->bitArraySize * 4LL); | ||
801 | while (GNUNET_YES == iterator (iterator_cls, &hc)) | ||
802 | GNUNET_CONTAINER_bloomfilter_add (bf, &hc); | ||
803 | } | ||
804 | |||
805 | |||
806 | /* end of container_bloomfilter.c */ | ||