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