diff options
Diffstat (limited to 'src/util/container_bloomfilter.c')
-rw-r--r-- | src/util/container_bloomfilter.c | 235 |
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 | */ |
85 | size_t | 85 | size_t |
86 | GNUNET_CONTAINER_bloomfilter_get_size (const struct GNUNET_CONTAINER_BloomFilter | 86 | GNUNET_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 | */ |
101 | struct GNUNET_CONTAINER_BloomFilter * | 101 | struct GNUNET_CONTAINER_BloomFilter * |
102 | GNUNET_CONTAINER_bloomfilter_copy (const struct GNUNET_CONTAINER_BloomFilter *bf) | 102 | GNUNET_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 | */ |
321 | typedef void (*BitIterator) (void *cls, | 322 | typedef 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 | */ |
334 | static void | 335 | static void |
335 | iterateBits (const struct GNUNET_CONTAINER_BloomFilter *bf, | 336 | iterateBits (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, | |||
408 | static void | 411 | static void |
409 | testBitCallback (void *cls, | 412 | testBitCallback (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 | */ |
565 | int | 569 | int |
566 | GNUNET_CONTAINER_bloomfilter_get_raw_data (const struct GNUNET_CONTAINER_BloomFilter | 570 | GNUNET_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 | */ |
620 | int | 625 | int |
621 | GNUNET_CONTAINER_bloomfilter_test (const struct GNUNET_CONTAINER_BloomFilter *bf, | 626 | GNUNET_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 | */ |
694 | int | 699 | int |
695 | GNUNET_CONTAINER_bloomfilter_or2 (struct GNUNET_CONTAINER_BloomFilter *bf, | 700 | GNUNET_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 | } |