aboutsummaryrefslogtreecommitdiff
path: root/src/util/container_bloomfilter.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/util/container_bloomfilter.c')
-rw-r--r--src/util/container_bloomfilter.c816
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
57struct 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
86size_t
87GNUNET_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
96size_t
97GNUNET_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
106struct GNUNET_CONTAINER_BloomFilter *
107GNUNET_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 */
123static void
124setBit (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 */
143static void
144clearBit (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 */
162static bool
163testBit (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 */
186static void
187incrementBit (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 */
237static void
238decrementBit (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 */
303static enum GNUNET_GenericReturnValue
304make_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 */
348typedef 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 */
363static void
364iterateBits (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 */
408static enum GNUNET_GenericReturnValue
409incrementBitCallback (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 */
430static enum GNUNET_GenericReturnValue
431decrementBitCallback (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 */
452static enum GNUNET_GenericReturnValue
453testBitCallback (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 */
481struct GNUNET_CONTAINER_BloomFilter *
482GNUNET_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
622struct GNUNET_CONTAINER_BloomFilter *
623GNUNET_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
648enum GNUNET_GenericReturnValue
649GNUNET_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
663void
664GNUNET_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
676void
677GNUNET_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
688bool
689GNUNET_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
706void
707GNUNET_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
719enum GNUNET_GenericReturnValue
720GNUNET_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
745enum GNUNET_GenericReturnValue
746GNUNET_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
776void
777GNUNET_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
791void
792GNUNET_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 */
generated by cgit v1.2.3 (git 2.39.1) at 2024-04-18 06:17:18 +0000