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.c235
1 files changed, 120 insertions, 115 deletions
diff --git a/src/util/container_bloomfilter.c b/src/util/container_bloomfilter.c
index b4c3ad08d..a0749a18a 100644
--- a/src/util/container_bloomfilter.c
+++ b/src/util/container_bloomfilter.c
@@ -82,9 +82,9 @@ struct GNUNET_CONTAINER_BloomFilter
82 * @param bf the filter 82 * @param bf the filter
83 * @return number of bytes used for the data of the bloom filter 83 * @return number of bytes used for the data of the bloom filter
84 */ 84 */
85size_t 85size_t
86GNUNET_CONTAINER_bloomfilter_get_size (const struct GNUNET_CONTAINER_BloomFilter 86GNUNET_CONTAINER_bloomfilter_get_size (const struct GNUNET_CONTAINER_BloomFilter
87 *bf) 87 *bf)
88{ 88{
89 if (bf == NULL) 89 if (bf == NULL)
90 return 0; 90 return 0;
@@ -99,11 +99,12 @@ GNUNET_CONTAINER_bloomfilter_get_size (const struct GNUNET_CONTAINER_BloomFilter
99 * @return copy of the bf 99 * @return copy of the bf
100 */ 100 */
101struct GNUNET_CONTAINER_BloomFilter * 101struct GNUNET_CONTAINER_BloomFilter *
102GNUNET_CONTAINER_bloomfilter_copy (const struct GNUNET_CONTAINER_BloomFilter *bf) 102GNUNET_CONTAINER_bloomfilter_copy (const struct GNUNET_CONTAINER_BloomFilter
103 *bf)
103{ 104{
104 return GNUNET_CONTAINER_bloomfilter_init (bf->bitArray, 105 return GNUNET_CONTAINER_bloomfilter_init (bf->bitArray,
105 bf->bitArraySize, 106 bf->bitArraySize,
106 bf->addressesPerElement); 107 bf->addressesPerElement);
107} 108}
108 109
109 110
@@ -198,15 +199,15 @@ incrementBit (char *bitArray, unsigned int bitIdx,
198 high = (value & (~0xF)) >> 4; 199 high = (value & (~0xF)) >> 4;
199 200
200 if (targetLoc == 0) 201 if (targetLoc == 0)
201 { 202 {
202 if (low < 0xF) 203 if (low < 0xF)
203 low++; 204 low++;
204 } 205 }
205 else 206 else
206 { 207 {
207 if (high < 0xF) 208 if (high < 0xF)
208 high++; 209 high++;
209 } 210 }
210 value = ((high << 4) | low); 211 value = ((high << 4) | low);
211 GNUNET_assert (fileSlot == GNUNET_DISK_file_seek (fh, 212 GNUNET_assert (fileSlot == GNUNET_DISK_file_seek (fh,
212 fileSlot, 213 fileSlot,
@@ -245,23 +246,23 @@ decrementBit (char *bitArray, unsigned int bitIdx,
245 246
246 /* decrement, but once we have reached the max, never go back! */ 247 /* decrement, but once we have reached the max, never go back! */
247 if (targetLoc == 0) 248 if (targetLoc == 0)
249 {
250 if ((low > 0) && (low < 0xF))
251 low--;
252 if (low == 0)
248 { 253 {
249 if ((low > 0) && (low < 0xF)) 254 clearBit (bitArray, bitIdx);
250 low--;
251 if (low == 0)
252 {
253 clearBit (bitArray, bitIdx);
254 }
255 } 255 }
256 }
256 else 257 else
258 {
259 if ((high > 0) && (high < 0xF))
260 high--;
261 if (high == 0)
257 { 262 {
258 if ((high > 0) && (high < 0xF)) 263 clearBit (bitArray, bitIdx);
259 high--;
260 if (high == 0)
261 {
262 clearBit (bitArray, bitIdx);
263 }
264 } 264 }
265 }
265 value = ((high << 4) | low); 266 value = ((high << 4) | low);
266 GNUNET_DISK_file_seek (fh, fileSlot, GNUNET_DISK_SEEK_SET); 267 GNUNET_DISK_file_seek (fh, fileSlot, GNUNET_DISK_SEEK_SET);
267 GNUNET_assert (1 == GNUNET_DISK_file_write (fh, &value, 1)); 268 GNUNET_assert (1 == GNUNET_DISK_file_write (fh, &value, 1));
@@ -290,19 +291,19 @@ makeEmptyFile (const struct GNUNET_DISK_FileHandle *fh, size_t size)
290 GNUNET_DISK_file_seek (fh, 0, GNUNET_DISK_SEEK_SET); 291 GNUNET_DISK_file_seek (fh, 0, GNUNET_DISK_SEEK_SET);
291 292
292 while (bytesleft > 0) 293 while (bytesleft > 0)
294 {
295 if (bytesleft > BUFFSIZE)
293 { 296 {
294 if (bytesleft > BUFFSIZE) 297 res = GNUNET_DISK_file_write (fh, buffer, BUFFSIZE);
295 { 298 bytesleft -= BUFFSIZE;
296 res = GNUNET_DISK_file_write (fh, buffer, BUFFSIZE);
297 bytesleft -= BUFFSIZE;
298 }
299 else
300 {
301 res = GNUNET_DISK_file_write (fh, buffer, bytesleft);
302 bytesleft = 0;
303 }
304 GNUNET_assert (res != GNUNET_SYSERR);
305 } 299 }
300 else
301 {
302 res = GNUNET_DISK_file_write (fh, buffer, bytesleft);
303 bytesleft = 0;
304 }
305 GNUNET_assert (res != GNUNET_SYSERR);
306 }
306 GNUNET_free (buffer); 307 GNUNET_free (buffer);
307 return GNUNET_OK; 308 return GNUNET_OK;
308} 309}
@@ -319,7 +320,7 @@ makeEmptyFile (const struct GNUNET_DISK_FileHandle *fh, size_t size)
319 * @param bit the current bit 320 * @param bit the current bit
320 */ 321 */
321typedef void (*BitIterator) (void *cls, 322typedef void (*BitIterator) (void *cls,
322 const struct GNUNET_CONTAINER_BloomFilter *bf, 323 const struct GNUNET_CONTAINER_BloomFilter * bf,
323 unsigned int bit); 324 unsigned int bit);
324 325
325/** 326/**
@@ -333,7 +334,7 @@ typedef void (*BitIterator) (void *cls,
333 */ 334 */
334static void 335static void
335iterateBits (const struct GNUNET_CONTAINER_BloomFilter *bf, 336iterateBits (const struct GNUNET_CONTAINER_BloomFilter *bf,
336 BitIterator callback, void *arg, const GNUNET_HashCode *key) 337 BitIterator callback, void *arg, const GNUNET_HashCode * key)
337{ 338{
338 GNUNET_HashCode tmp[2]; 339 GNUNET_HashCode tmp[2];
339 int bitCount; 340 int bitCount;
@@ -344,26 +345,26 @@ iterateBits (const struct GNUNET_CONTAINER_BloomFilter *bf,
344 memcpy (&tmp[0], key, sizeof (GNUNET_HashCode)); 345 memcpy (&tmp[0], key, sizeof (GNUNET_HashCode));
345 round = 0; 346 round = 0;
346 while (bitCount > 0) 347 while (bitCount > 0)
348 {
349 while (slot < (sizeof (GNUNET_HashCode) / sizeof (uint32_t)))
347 { 350 {
348 while (slot < (sizeof (GNUNET_HashCode) / sizeof (uint32_t))) 351 callback (arg,
349 { 352 bf,
350 callback (arg, 353 (((uint32_t *) & tmp[round & 1])[slot]) &
351 bf, 354 ((bf->bitArraySize * 8) - 1));
352 (((uint32_t *) &tmp[round & 1])[slot]) & 355 slot++;
353 ((bf->bitArraySize * 8) - 1)); 356 bitCount--;
354 slot++; 357 if (bitCount == 0)
355 bitCount--; 358 break;
356 if (bitCount == 0)
357 break;
358 }
359 if (bitCount > 0)
360 {
361 GNUNET_CRYPTO_hash (&tmp[round & 1], sizeof (GNUNET_HashCode),
362 &tmp[(round + 1) & 1]);
363 round++;
364 slot = 0;
365 }
366 } 359 }
360 if (bitCount > 0)
361 {
362 GNUNET_CRYPTO_hash (&tmp[round & 1], sizeof (GNUNET_HashCode),
363 &tmp[(round + 1) & 1]);
364 round++;
365 slot = 0;
366 }
367 }
367} 368}
368 369
369/** 370/**
@@ -379,6 +380,7 @@ incrementBitCallback (void *cls,
379 unsigned int bit) 380 unsigned int bit)
380{ 381{
381 struct GNUNET_CONTAINER_BloomFilter *b = cls; 382 struct GNUNET_CONTAINER_BloomFilter *b = cls;
383
382 incrementBit (b->bitArray, bit, bf->fh); 384 incrementBit (b->bitArray, bit, bf->fh);
383} 385}
384 386
@@ -395,6 +397,7 @@ decrementBitCallback (void *cls,
395 unsigned int bit) 397 unsigned int bit)
396{ 398{
397 struct GNUNET_CONTAINER_BloomFilter *b = cls; 399 struct GNUNET_CONTAINER_BloomFilter *b = cls;
400
398 decrementBit (b->bitArray, bit, bf->fh); 401 decrementBit (b->bitArray, bit, bf->fh);
399} 402}
400 403
@@ -408,9 +411,10 @@ decrementBitCallback (void *cls,
408static void 411static void
409testBitCallback (void *cls, 412testBitCallback (void *cls,
410 const struct GNUNET_CONTAINER_BloomFilter *bf, 413 const struct GNUNET_CONTAINER_BloomFilter *bf,
411 unsigned int bit) 414 unsigned int bit)
412{ 415{
413 int *arg = cls; 416 int *arg = cls;
417
414 if (GNUNET_NO == testBit (bf->bitArray, bit)) 418 if (GNUNET_NO == testBit (bf->bitArray, bit))
415 *arg = GNUNET_NO; 419 *arg = GNUNET_NO;
416} 420}
@@ -450,25 +454,25 @@ GNUNET_CONTAINER_bloomfilter_load (const char *filename,
450 bf = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_BloomFilter)); 454 bf = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_BloomFilter));
451 /* Try to open a bloomfilter file */ 455 /* Try to open a bloomfilter file */
452 bf->fh = GNUNET_DISK_file_open (filename, GNUNET_DISK_OPEN_READWRITE 456 bf->fh = GNUNET_DISK_file_open (filename, GNUNET_DISK_OPEN_READWRITE
453 | GNUNET_DISK_OPEN_CREATE, 457 | GNUNET_DISK_OPEN_CREATE,
454 GNUNET_DISK_PERM_USER_READ | 458 GNUNET_DISK_PERM_USER_READ |
455 GNUNET_DISK_PERM_USER_WRITE); 459 GNUNET_DISK_PERM_USER_WRITE);
456 if (NULL == bf->fh) 460 if (NULL == bf->fh)
457 { 461 {
458 GNUNET_free (bf); 462 GNUNET_free (bf);
459 return NULL; 463 return NULL;
460 } 464 }
461 bf->filename = GNUNET_strdup (filename); 465 bf->filename = GNUNET_strdup (filename);
462 /* Alloc block */ 466 /* Alloc block */
463 bf->bitArray = GNUNET_malloc_large (size); 467 bf->bitArray = GNUNET_malloc_large (size);
464 if (bf->bitArray == NULL) 468 if (bf->bitArray == NULL)
465 { 469 {
466 if (bf->fh != NULL) 470 if (bf->fh != NULL)
467 GNUNET_DISK_file_close (bf->fh); 471 GNUNET_DISK_file_close (bf->fh);
468 GNUNET_free (bf->filename); 472 GNUNET_free (bf->filename);
469 GNUNET_free (bf); 473 GNUNET_free (bf);
470 return NULL; 474 return NULL;
471 } 475 }
472 bf->bitArraySize = size; 476 bf->bitArraySize = size;
473 bf->addressesPerElement = k; 477 bf->addressesPerElement = k;
474 memset (bf->bitArray, 0, bf->bitArraySize); 478 memset (bf->bitArray, 0, bf->bitArraySize);
@@ -477,28 +481,28 @@ GNUNET_CONTAINER_bloomfilter_load (const char *filename,
477 rbuff = GNUNET_malloc (BUFFSIZE); 481 rbuff = GNUNET_malloc (BUFFSIZE);
478 pos = 0; 482 pos = 0;
479 while (pos < size * 8) 483 while (pos < size * 8)
484 {
485 int res;
486
487 res = GNUNET_DISK_file_read (bf->fh, rbuff, BUFFSIZE);
488 if (res == -1)
489 {
490 GNUNET_log_strerror_file (GNUNET_ERROR_TYPE_WARNING,
491 "read", bf->filename);
492 }
493 if (res == 0)
494 break; /* is ok! we just did not use that many bits yet */
495 for (i = 0; i < res; i++)
480 { 496 {
481 int res; 497 if ((rbuff[i] & 0x0F) != 0)
482 498 setBit (bf->bitArray, pos + i * 2);
483 res = GNUNET_DISK_file_read (bf->fh, rbuff, BUFFSIZE); 499 if ((rbuff[i] & 0xF0) != 0)
484 if (res == -1) 500 setBit (bf->bitArray, pos + i * 2 + 1);
485 {
486 GNUNET_log_strerror_file (GNUNET_ERROR_TYPE_WARNING,
487 "read", bf->filename);
488 }
489 if (res == 0)
490 break; /* is ok! we just did not use that many bits yet */
491 for (i = 0; i < res; i++)
492 {
493 if ((rbuff[i] & 0x0F) != 0)
494 setBit (bf->bitArray, pos + i * 2);
495 if ((rbuff[i] & 0xF0) != 0)
496 setBit (bf->bitArray, pos + i * 2 + 1);
497 }
498 if (res < BUFFSIZE)
499 break;
500 pos += BUFFSIZE * 2; /* 2 bits per byte in the buffer */
501 } 501 }
502 if (res < BUFFSIZE)
503 break;
504 pos += BUFFSIZE * 2; /* 2 bits per byte in the buffer */
505 }
502 GNUNET_free (rbuff); 506 GNUNET_free (rbuff);
503 return bf; 507 return bf;
504} 508}
@@ -530,19 +534,19 @@ GNUNET_CONTAINER_bloomfilter_init (const char *data,
530 while (ui < size) 534 while (ui < size)
531 ui *= 2; 535 ui *= 2;
532 if (size != ui) 536 if (size != ui)
533 { 537 {
534 GNUNET_break (0); 538 GNUNET_break (0);
535 return NULL; 539 return NULL;
536 } 540 }
537 bf = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_BloomFilter)); 541 bf = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_BloomFilter));
538 bf->filename = NULL; 542 bf->filename = NULL;
539 bf->fh = NULL; 543 bf->fh = NULL;
540 bf->bitArray = GNUNET_malloc_large (size); 544 bf->bitArray = GNUNET_malloc_large (size);
541 if (bf->bitArray == NULL) 545 if (bf->bitArray == NULL)
542 { 546 {
543 GNUNET_free (bf); 547 GNUNET_free (bf);
544 return NULL; 548 return NULL;
545 } 549 }
546 bf->bitArraySize = size; 550 bf->bitArraySize = size;
547 bf->addressesPerElement = k; 551 bf->addressesPerElement = k;
548 if (data != NULL) 552 if (data != NULL)
@@ -563,8 +567,9 @@ GNUNET_CONTAINER_bloomfilter_init (const char *data,
563 * @return GNUNET_SYSERR if the data array is not big enough 567 * @return GNUNET_SYSERR if the data array is not big enough
564 */ 568 */
565int 569int
566GNUNET_CONTAINER_bloomfilter_get_raw_data (const struct GNUNET_CONTAINER_BloomFilter 570GNUNET_CONTAINER_bloomfilter_get_raw_data (const struct
567 *bf, char *data, size_t size) 571 GNUNET_CONTAINER_BloomFilter *bf,
572 char *data, size_t size)
568{ 573{
569 if (NULL == bf) 574 if (NULL == bf)
570 return GNUNET_SYSERR; 575 return GNUNET_SYSERR;
@@ -618,8 +623,8 @@ GNUNET_CONTAINER_bloomfilter_clear (struct GNUNET_CONTAINER_BloomFilter *bf)
618 * @return GNUNET_YES if the element is in the filter, GNUNET_NO if not 623 * @return GNUNET_YES if the element is in the filter, GNUNET_NO if not
619 */ 624 */
620int 625int
621GNUNET_CONTAINER_bloomfilter_test (const struct GNUNET_CONTAINER_BloomFilter *bf, 626GNUNET_CONTAINER_bloomfilter_test (const struct GNUNET_CONTAINER_BloomFilter
622 const GNUNET_HashCode * e) 627 *bf, const GNUNET_HashCode * e)
623{ 628{
624 int res; 629 int res;
625 630
@@ -663,20 +668,20 @@ GNUNET_CONTAINER_bloomfilter_or (struct GNUNET_CONTAINER_BloomFilter *bf,
663{ 668{
664 unsigned int i; 669 unsigned int i;
665 unsigned int n; 670 unsigned int n;
666 unsigned long long* fc; 671 unsigned long long *fc;
667 const unsigned long long* dc; 672 const unsigned long long *dc;
668 673
669 if (NULL == bf) 674 if (NULL == bf)
670 return GNUNET_YES; 675 return GNUNET_YES;
671 if (bf->bitArraySize != size) 676 if (bf->bitArraySize != size)
672 return GNUNET_SYSERR; 677 return GNUNET_SYSERR;
673 fc = (unsigned long long*) bf->bitArray; 678 fc = (unsigned long long *) bf->bitArray;
674 dc = (const unsigned long long*) data; 679 dc = (const unsigned long long *) data;
675 n = size / sizeof (unsigned long long); 680 n = size / sizeof (unsigned long long);
676 681
677 for (i = 0; i < n; i++) 682 for (i = 0; i < n; i++)
678 fc[i] |= dc[i]; 683 fc[i] |= dc[i];
679 for (i = n * sizeof(unsigned long long); i < size; i++) 684 for (i = n * sizeof (unsigned long long); i < size; i++)
680 bf->bitArray[i] |= data[i]; 685 bf->bitArray[i] |= data[i];
681 return GNUNET_OK; 686 return GNUNET_OK;
682} 687}
@@ -693,25 +698,25 @@ GNUNET_CONTAINER_bloomfilter_or (struct GNUNET_CONTAINER_BloomFilter *bf,
693 */ 698 */
694int 699int
695GNUNET_CONTAINER_bloomfilter_or2 (struct GNUNET_CONTAINER_BloomFilter *bf, 700GNUNET_CONTAINER_bloomfilter_or2 (struct GNUNET_CONTAINER_BloomFilter *bf,
696 const struct GNUNET_CONTAINER_BloomFilter *to_or, 701 const struct GNUNET_CONTAINER_BloomFilter
697 size_t size) 702 *to_or, size_t size)
698{ 703{
699 unsigned int i; 704 unsigned int i;
700 unsigned int n; 705 unsigned int n;
701 unsigned long long* fc; 706 unsigned long long *fc;
702 const unsigned long long* dc; 707 const unsigned long long *dc;
703 708
704 if (NULL == bf) 709 if (NULL == bf)
705 return GNUNET_YES; 710 return GNUNET_YES;
706 if (bf->bitArraySize != size) 711 if (bf->bitArraySize != size)
707 return GNUNET_SYSERR; 712 return GNUNET_SYSERR;
708 fc = (unsigned long long*) bf->bitArray; 713 fc = (unsigned long long *) bf->bitArray;
709 dc = (const unsigned long long*) to_or->bitArray; 714 dc = (const unsigned long long *) to_or->bitArray;
710 n = size / sizeof (unsigned long long); 715 n = size / sizeof (unsigned long long);
711 716
712 for (i = 0; i < n; i++) 717 for (i = 0; i < n; i++)
713 fc[i] |= dc[i]; 718 fc[i] |= dc[i];
714 for (i = n * sizeof(unsigned long long); i < size; i++) 719 for (i = n * sizeof (unsigned long long); i < size; i++)
715 bf->bitArray[i] |= to_or->bitArray[i]; 720 bf->bitArray[i] |= to_or->bitArray[i];
716 return GNUNET_OK; 721 return GNUNET_OK;
717} 722}